{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:28:15Z","timestamp":1750307295944,"version":"3.41.0"},"reference-count":21,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2010,10,15]],"date-time":"2010-10-15T00:00:00Z","timestamp":1287100800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGMETRICS Perform. Eval. Rev."],"published-print":{"date-parts":[[2010,10,15]]},"abstract":"<jats:p>Shortest Remaining Processing Time first (SRPT) has long been known to optimize the queue length distribution and the mean response time (a.k.a. flow time, sojourn time). As such, it has been the focus of a wide body of analysis. However, results about the heavy-traffic behavior of SRPT have only recently started to emerge. In this work, we characterize the growth rate of the mean response time under SRPT in the M\/GI\/1 system under general job size distributions. Our results illustrate the relationship between the job size tail and the heavy traffic growth rate of mean response time. Further, we show that the heavy traffic growth rate can be used to provide an accurate approximation for mean response time outside of heavy traffic.<\/jats:p>","DOI":"10.1145\/1870178.1870183","type":"journal-article","created":{"date-parts":[[2010,10,26]],"date-time":"2010-10-26T12:36:02Z","timestamp":1288096562000},"page":"12-14","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["The average response time in a heavy-traffic srpt queue"],"prefix":"10.1145","volume":"38","author":[{"given":"Minghong","family":"Lin","sequence":"first","affiliation":[{"name":"CMS, California Institute of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Adam","family":"Wierman","sequence":"additional","affiliation":[{"name":"CMS, California Institute of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bert","family":"Zwart","sequence":"additional","affiliation":[{"name":"CWI Amsterdam, VU University Amsterdam, Eurandom &amp; Georgia Tech."}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2010,10,15]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1811039.1811044"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2004.04.006"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11134-006-8218-z"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1243401.1243406"},{"volume-title":"On the impact of heterogeneity and back-end scheduling in load balancing designs","year":"2009","author":"Chen H.-L.","key":"e_1_2_1_5_1"},{"key":"e_1_2_1_6_1","unstructured":"D. Down H. C. Gromoll and A. L. Puha. The fluid limit of an SRPT queue. Under submission.  D. Down H. C. Gromoll and A. L. Puha. The fluid limit of an SRPT queue. Under submission."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCOM.1986.1096548"},{"volume-title":"Heavy traffic approximations for busy period in an M\/G\/\u221e queue. Stochastic Processes and their Applications, 19(2):259--269","year":"1985","author":"Hall P.","key":"e_1_2_1_8_1"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/762483.762486"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.2307\/3212781"},{"volume-title":"Globecom","year":"2003","author":"Hu M.","key":"e_1_2_1_11_1"},{"volume-title":"Queueing Systems","year":"1975","author":"Kleinrock L.","key":"e_1_2_1_12_1"},{"key":"e_1_2_1_13_1","unstructured":"M. Lin A. Wierman and B. Zwart. Heavy-traffic analysis of mean response time under shortest remaining processing time. Under submission.  M. Lin A. Wierman and B. Zwart. Heavy-traffic analysis of mean response time under shortest remaining processing time. Under submission."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511721434"},{"volume-title":"Veroyatn. Anal.):85--93, 97","year":"1986","author":"Pechinkin A. V.","key":"e_1_2_1_15_1"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0040585X97978498"},{"volume-title":"Proc. of ACM Sigmetrics-Performance","year":"2004","author":"Rai I. A.","key":"e_1_2_1_17_1"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.16.3.687"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.14.4.670"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.1040.0279"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1243401.1243405"}],"container-title":["ACM SIGMETRICS Performance Evaluation Review"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1870178.1870183","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1870178.1870183","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T10:59:47Z","timestamp":1750244387000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1870178.1870183"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,10,15]]},"references-count":21,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2010,10,15]]}},"alternative-id":["10.1145\/1870178.1870183"],"URL":"https:\/\/doi.org\/10.1145\/1870178.1870183","relation":{},"ISSN":["0163-5999"],"issn-type":[{"type":"print","value":"0163-5999"}],"subject":[],"published":{"date-parts":[[2010,10,15]]},"assertion":[{"value":"2010-10-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}