{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:32:42Z","timestamp":1740123162541,"version":"3.37.3"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2021,1,19]],"date-time":"2021-01-19T00:00:00Z","timestamp":1611014400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,1,19]],"date-time":"2021-01-19T00:00:00Z","timestamp":1611014400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Ann Oper Res"],"published-print":{"date-parts":[[2022,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Extending the results of Kruk (Queueing theory and network applications. QTNA 2019. Lecture notes in computer science, vol 11688. Springer, Cham, pp 263\u2013275, 2019), we derive heavy traffic limit theorems for a single server, single customer class queue in which the server uses the Shortest Remaining Processing Time (SRPT) policy from heavy traffic limits for the corresponding Earliest Deadline First queueing systems. Our analysis allows for correlated customer inter-arrival and service times and heavy-tailed inter-arrival and service time distributions, as long as the corresponding stochastic primitive processes converge weakly to continuous limits under heavy traffic scaling. Our approach yields simple, concise justifications and new insights for SRPT heavy traffic limit theorems of Gromoll et al. (Stoch Syst 1(1):1\u201316, 2011). Corresponding results for the longest remaining processing time policy are also provided.<\/jats:p>","DOI":"10.1007\/s10479-021-03929-0","type":"journal-article","created":{"date-parts":[[2021,1,19]],"date-time":"2021-01-19T15:03:10Z","timestamp":1611068590000},"page":"411-429","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Heavy traffic analysis for single-server SRPT and LRPT queues via EDF diffusion limits"],"prefix":"10.1007","volume":"310","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3073-959X","authenticated-orcid":false,"given":"\u0141ukasz","family":"Kruk","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,1,19]]},"reference":[{"key":"3929_CR1","unstructured":"Banerjee, S., Budhiraja, A., & Puha, A. L. (2020). Heavy traffic scaling limits for shortest remaining processing time queues with heavy tailed processing time distributions. arXiv: 2003.03655v1."},{"key":"3929_CR2","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1145\/384268.378792","volume":"29","author":"N Bansal","year":"2001","unstructured":"Bansal, N., & Harchol-Balter, M. (2001). Analysis of SRPT scheduling: Investigating unfairness. ACM Sigmetrics Performance Evaluation Review, 29, 279\u2013290.","journal-title":"ACM Sigmetrics Performance Evaluation Review"},{"key":"3929_CR3","unstructured":"Bender, M., Chakrabarti, S., & Muthukrishnan, S. (1998). Flow and stretch metrics for scheduling continuous job streams. In proceedings of the 9th annual ACM-SIAM symposium on discrete algorithms."},{"key":"3929_CR4","doi-asserted-by":"publisher","DOI":"10.1002\/9780470316962","volume-title":"Convergence of probability measures","author":"P Billingsley","year":"1999","unstructured":"Billingsley, P. (1999). Convergence of probability measures (2nd ed.). New York: Wiley.","edition":"2"},{"key":"3929_CR5","volume-title":"Probability and measure","author":"P Billingsley","year":"1986","unstructured":"Billingsley, P. (1986). Probability and measure (2nd ed.). New York: Wiley.","edition":"2"},{"key":"3929_CR6","doi-asserted-by":"publisher","first-page":"880","DOI":"10.1287\/moor.1090.0409","volume":"34","author":"DG Down","year":"2009","unstructured":"Down, D. G., Gromoll, H. C., & Puha, A. L. (2009). Fluid limits for shortest remaining processing time queues. Mathematics of Operations Research, 34, 880\u2013911.","journal-title":"Mathematics of Operations Research"},{"key":"3929_CR7","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/s11134-006-7419-9","volume":"53","author":"DG Down","year":"2006","unstructured":"Down, D. G., & Wu, R. (2006). Multi-layered round robin routing for parallel servers. Queueing Systems, 53, 177\u2013188.","journal-title":"Queueing Systems"},{"key":"3929_CR8","doi-asserted-by":"publisher","first-page":"332","DOI":"10.1214\/aoap\/1015345295","volume":"11","author":"B Doytchinov","year":"2001","unstructured":"Doytchinov, B., Lehoczky, J. P., & Shreve, S. E. (2001). Real-time queues in heavy traffic with earliest-deadline-first queue discipline. Annals of Applied Probability, 11, 332\u2013378.","journal-title":"Annals of Applied Probability"},{"key":"3929_CR9","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/s11134-011-9267-5","volume":"70","author":"HC Gromoll","year":"2012","unstructured":"Gromoll, H. C., & Keutel, M. (2012). Invariance of fluid limits for the shortest remaining processing time and shortest job first policies. Queueing Systems, 70, 145\u2013164.","journal-title":"Queueing Systems"},{"issue":"1","key":"3929_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1287\/10-SSY016","volume":"1","author":"HC Gromoll","year":"2011","unstructured":"Gromoll, H. C., Kruk, \u0141., & Puha, A. L. (2011). Diffusion limits for shortest remaining processing time queues. Stochastic Systems, 1(1), 1\u201316.","journal-title":"Stochastic Systems"},{"key":"3929_CR11","volume-title":"Markov processes: Characterization and convergence","author":"SN Ethier","year":"1985","unstructured":"Ethier, S. N., & Kurtz, T. G. (1985). Markov processes: Characterization and convergence. New York: Wiley."},{"key":"3929_CR12","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1287\/mnsc.1040.0301","volume":"51","author":"T Kittsteiner","year":"2005","unstructured":"Kittsteiner, T., & Moldovanu, B. (2005). Priority auctions and queue disciplines that depend on processing time. Management Science, 51, 236\u2013248.","journal-title":"Management Science"},{"key":"3929_CR13","first-page":"51","volume":"61","author":"\u0141 Kruk","year":"2007","unstructured":"Kruk, \u0141. (2007). Diffusion approximation for a G\/G\/1 EDF queue with unbounded lead times. Annales UMCS Mathematica A, 61, 51\u201390.","journal-title":"Annales UMCS Mathematica A"},{"key":"3929_CR14","doi-asserted-by":"crossref","unstructured":"Kruk, \u0141. (2019). Diffusion limits for SRPT and LRPT queues via EDF approximations. In T. Phung-Duc, S. Kasahara, S. Wittevrongel (Eds.), Queueing theory and network applications. QTNA 2019. Lecture notes in computer science (Vol. 11688, pp. 263\u2013275). Cham: Springer.","DOI":"10.1007\/978-3-030-27181-7_16"},{"issue":"3","key":"3929_CR15","doi-asserted-by":"publisher","first-page":"1055","DOI":"10.1287\/moor.2015.0768","volume":"41","author":"\u0141 Kruk","year":"2016","unstructured":"Kruk, \u0141., & Soko\u0142owska, E. (2016). Fluid limits for multiple-input shortest remaining processing time queues. Mathematics of Operations Research, 41(3), 1055\u20131092.","journal-title":"Mathematics of Operations Research"},{"key":"3929_CR16","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1023\/A:1020905810996","volume":"113","author":"R N\u00fa\u00f1ez-Queija","year":"2002","unstructured":"N\u00fa\u00f1ez-Queija, R. (2002). Queues with equally heavy sojourn time and service requirement distributions. Annals of Operations Research, 113, 101\u2013117.","journal-title":"Annals of Operations Research"},{"key":"3929_CR17","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/s11134-006-8767-1","volume":"54","author":"M Nuyens","year":"2006","unstructured":"Nuyens, M., & Zwart, B. (2006). A large deviations analysis of the GI\/GI\/1 SRPT queue. Queueing Systems, 54, 85\u201397.","journal-title":"Queueing Systems"},{"key":"3929_CR18","unstructured":"Pavlov, A. V. (1983). A system with Schrage servicing discipline in the case of a high load. Engineering Cybernetics 21, 114\u2013121 (1984). translated from Izv. Akad. Nauk SSSR Tekhn. Kibernet. 6, 59\u201366 (Russian)."},{"key":"3929_CR19","unstructured":"Pechinkin, A. V. (1986). Heavy traffic in a system with a discipline of priority servicing for the job with the shortest remaining length with interruption (Russian). Math. Issled. No. 89, Veroyatn. Anal. 97, 85\u201393."},{"key":"3929_CR20","first-page":"110","volume":"47","author":"R Perera","year":"1993","unstructured":"Perera, R. (1993). The variance of delay time in queueing system M\/G\/1 with optimal strategy SRPT. Archiv f\u00fcr Elektronik und \u00dcbertragungstechnik, 47, 110\u2013114.","journal-title":"Archiv f\u00fcr Elektronik und \u00dcbertragungstechnik"},{"key":"3929_CR21","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1137\/1101016","volume":"1","author":"Yu Prokhorov","year":"1956","unstructured":"Prokhorov, Yu. (1956). Convergence of random processes and limit theorems in probability. Theory of Probability and Applications, 1, 157\u2013214.","journal-title":"Theory of Probability and Applications"},{"issue":"6","key":"3929_CR22","doi-asserted-by":"publisher","first-page":"3301","DOI":"10.1214\/14-AAP1076","volume":"25","author":"AL Puha","year":"2015","unstructured":"Puha, A. L. (2015). Diffusion limits for shortest remaining processing time queues under nonstandard spatial scaling. Annals of Applied Probability, 25(6), 3301\u20133404.","journal-title":"Annals of Applied Probability"},{"key":"3929_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1214\/aoap\/998926986","volume":"11","author":"K Ramanan","year":"2001","unstructured":"Ramanan, K., & Stolyar, A. (2001). Largest weighted delay first scheduling: large deviations and optimality. Annals of Applied Probability, 11, 1\u201348.","journal-title":"Annals of Applied Probability"},{"key":"3929_CR24","doi-asserted-by":"publisher","first-page":"456","DOI":"10.2307\/1427545","volume":"22","author":"R Schassberger","year":"1990","unstructured":"Schassberger, R. (1990). The steady-state appearance of the M\/G\/1 queue under the discipline of shortest remaining processing time. Advances in Applied Probability, 22, 456\u2013479.","journal-title":"Advances in Applied Probability"},{"key":"3929_CR25","doi-asserted-by":"publisher","first-page":"687","DOI":"10.1287\/opre.16.3.687","volume":"16","author":"LE Schrage","year":"1968","unstructured":"Schrage, L. E. (1968). A proof of the optimality of the shortest remaining processing time discipline. Operations Research, 16, 687\u2013690.","journal-title":"Operations Research"},{"key":"3929_CR26","doi-asserted-by":"publisher","first-page":"670","DOI":"10.1287\/opre.14.4.670","volume":"14","author":"LE Schrage","year":"1966","unstructured":"Schrage, L. E., & Miller, L. W. (1966). The queue M\/G\/1 with the shortest remaining processing time discipline. Operations Research, 14, 670\u2013684.","journal-title":"Operations Research"},{"key":"3929_CR27","doi-asserted-by":"publisher","DOI":"10.1007\/b97479","volume-title":"Stochastic-process limits","author":"W Whitt","year":"2002","unstructured":"Whitt, W. (2002). Stochastic-process limits. New York: Springer."},{"key":"3929_CR28","doi-asserted-by":"crossref","unstructured":"Wierman, A., & Harchol-Balter, M. (2003). Classifying scheduling policies with respect to unfairness in an M\/G\/1. In Proceedings of the 2003 ACM SIGMETRICS international conference on measurement and modeling of computer systems (pp. 238\u2013249).","DOI":"10.1145\/885651.781057"}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-021-03929-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10479-021-03929-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-021-03929-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,2,28]],"date-time":"2022-02-28T10:20:27Z","timestamp":1646043627000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10479-021-03929-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,19]]},"references-count":28,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,3]]}},"alternative-id":["3929"],"URL":"https:\/\/doi.org\/10.1007\/s10479-021-03929-0","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"type":"print","value":"0254-5330"},{"type":"electronic","value":"1572-9338"}],"subject":[],"published":{"date-parts":[[2021,1,19]]},"assertion":[{"value":"5 January 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 January 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}