{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,6]],"date-time":"2026-10-06T07:52:57Z","timestamp":1791273177322,"version":"4.1.0"},"reference-count":24,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2005,1]]},"abstract":"<jats:p>We consider the classical problem of online job scheduling on uniprocessor and multiprocessor machines. For a given job, we measure the quality of service provided by an algorithm by the stretch of the job, which is defined as the ratio of the amount of time that the job spends in the system to the processing time of the job. For a given sequence of jobs, we measure the performance of an algorithm by the average stretch achieved by the algorithm over all the jobs in the sequence. The average stretch metric has been used to evaluate the performance of scheduling algorithms in many applications arising in databases, networks, and systems.<\/jats:p>\n                  <jats:p>The main contribution of this paper is to show that the shortest remaining processing time (SRPT) algorithm is O(1)-competitive with respect to average stretch for both uniprocessors and multiprocessors. For uniprocessors, we prove that SRPT is 2-competitive; we also establish an essentially matching lower bound on the competitive ratio of SRPT. For multiprocessors, we show that the competitive ratio of SRPT is at most $9 + 2\\sqrt{6} \\le 14$. Furthermore, we establish constant-factor lower bounds on the competitive ratio of any online algorithm for both uniprocessors and multiprocessors.<\/jats:p>","DOI":"10.1137\/s0097539701387544","type":"journal-article","created":{"date-parts":[[2005,3,2]],"date-time":"2005-03-02T21:00:22Z","timestamp":1109797222000},"page":"433-452","source":"Crossref","is-referenced-by-count":23,"title":["Online Scheduling to Minimize Average Stretch"],"prefix":"10.1137","volume":"34","author":[{"given":"S.","family":"Muthukrishnan","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rajmohan","family":"Rajaraman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Anthony","family":"Shaheen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Johannes E.","family":"Gehrke","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,27]]},"reference":[{"key":"R1","unstructured":"Foto Afrati, Evripidis Bampis, Chandra Chekuri, David Karger, Claire Kenyon, Sanjeev Khanna, Ioannis Milis, Maurice Queyranne, Martin Skutella, Cliff Stein, Maxim Sviridenko, Approximation schemes for minimizing average weighted completion time with release dates, IEEE Computer Soc., Los Alamitos, CA, 1999, 32\u2013431916182"},{"key":"R2","unstructured":"Baruch Awerbuch, Yossi Azar, Stefano Leonardi, Oded Regev, Minimizing the flow time without migration, ACM, New York, 1999, 198\u20132051798038"},{"key":"R3","unstructured":"K. R. Baker,\n                      Introduction to Sequencing and Scheduling\n                      , Wiley, New York, 1974."},{"key":"R4","unstructured":"N. Bansal and M. Harchol\u2010Balter,\n                      Analysis of SRPT scheduling: Investigating unfairness\n                      , in Proceedings of ACM SIGMETRICS 2001\/Performance 2001:"},{"key":"R4","unstructured":"Joint International Conference on Measurement & Modeling of Computer Systems, Cambridge, MA, 2001, pp. 279\u2013290."},{"key":"R5","unstructured":"Luca Becchetti, Stefano Leonardi, S. Muthukrishnan, Scheduling to minimize average stretch without migration, ACM, New York, 2000, 548\u20135571755514"},{"key":"R6","unstructured":"Michael Bender, Soumen Chakrabarti, S. Muthukrishnan, Flow and stretch metrics for scheduling continuous job streams, ACM, New York, 1998, 270\u20132791642937"},{"key":"R7","unstructured":"M. A. Bender, S. Muthukrishnan, and R. Rajaraman,\n                      Improved algorithms for stretch scheduling\n                      , in Proceedings of the 13th Annual ACM\u2010SIAM Symposium on Discrete Algorithms, San Francisco, 2002, SIAM, Philadelphia, pp. 762\u2013771."},{"key":"R8","unstructured":"C. Chekuri and S. Khanna,\n                      Approximation schemes for preemptive weighted flow time\n                      , in Proceedings of the 34th Annual ACM Symposium on Theory of Computing, Montreal, 2002, ACM, New York, pp. 297\u2013305."},{"key":"R9","unstructured":"C. Chekuri, S. Khanna, and A. Zhu,\n                      Algorithms for minimizing weighted flow time\n                      , In Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, Heraklion, Crete, 2001, ACM, New York, pp. 84\u201393."},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(90)90100-V"},{"key":"R11","unstructured":"Ashish Goel, Monika Henzinger, Serge Plotkin, Eva Tardos, Scheduling data transfers in a network and the set scheduling problem, ACM, New York, 1999, 189\u20131971798037"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1287\/moor.22.3.513"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1999.1577"},{"key":"R14","unstructured":"M. Harchol\u2010Balter, M. Crovella, and S. Park,\n                      The Case for SRPT Scheduling in Web Servers\n                      , Technical Report MIT\u2013LCS\u2013TR\u2013767, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, 1998."},{"key":"R15","unstructured":"R. Jain,\n                      The Art of Computer Systems Performance Analysis\n                      , John Wiley, New York, 1991."},{"key":"R16","unstructured":"David Karger, Cliff Stein, Joel Wein, Scheduling algorithms, CRC, Boca Raton, FL, 1999, 0\u20130, 35\u20101\u201335\u2010331797202"},{"key":"R17","unstructured":"E. Lawler, J. Lenstra, A. Rinnooy Kan, and D. Shmoys,\n                      Sequencing and scheduling: Algorithms and complexity\n                      , in Handbooks in Operations Research and Management Science, Vol. 4: Logistics of Production and Inventory, S. Graves, A. Rinnooy Kan, and P. Zipkin, eds., North\u2013Holland, Amsterdam, 1993, pp. 445\u2013522."},{"key":"R18","unstructured":"Stefano Leonardi, Danny Raz, Approximating total flow time on parallel machines, ACM, New York, 1999, 110\u20131191715629"},{"key":"R19","unstructured":"M. Mehta and D. J. DeWitt,\n                      Dynamic memory allocation for multiple\u2010query workloads\n                      , in Proceedings of the 19th International Conference on Very Large Data Bases, Dublin, Ireland, 1993, pp. 354\u2013367."},{"key":"R20","unstructured":"Andreas Schulz, Martin Skutella, Scheduling\u2010LPs bear probabilities: randomized approximations for min\u2010sum criteria, Lecture Notes in Comput. Sci., Vol. 1284, Springer, Berlin, 1997, 416\u20134291640433"},{"key":"R21","unstructured":"Ji\u0159\u00edSgall, On\u2010line scheduling, Lecture Notes in Comput. Sci., Vol. 1442, Springer, Berlin, 1998, 196\u20132311676828"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1145\/2786.2793"},{"key":"R23","unstructured":"H. Zhu, B. Smith, and T. Yang,\n                      A scheduling framework for Web server clusters with intensive dynamic content processing\n                      , Technical Report TRCS98\u201029, Department of Computer Science, University of California, Santa Barbara, CA, 1998."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539701387544","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:18:22Z","timestamp":1787336302000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539701387544"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,1]]},"references-count":24,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2005,1]]}},"alternative-id":["10.1137\/S0097539701387544"],"URL":"https:\/\/doi.org\/10.1137\/s0097539701387544","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,1]]}}}