Diffusion Limits for Shortest Remaining Processing Time Queues with Multiple Customer Types

• Autorzy: Gieroba Robert , Kruk Łukasz

Identyfikatory

DOI

10.15439/2023F4407

• Języki publikacji: EN

Abstrakty

EN

We consider a single-server queueing system with multiple customer types in which users are scheduled according to the Shortest Remaining Processing Time (SRPT) discipline, with First In First Out (FIFO) as the tie-breaker. We use probabilistic methods to find, under typical heavy traffic assumptions, a suitable approximation of the workload and queue length processes after a long time has passed and show that these processes are divided among the customer classes according to specific proportions, depending on their arrival rates and distributions of initial service times. Our results are confirmed by simulations.

Słowa kluczowe

EN

queueing systems; shortest remaining processing time; heavy traffic; diffusion approximation; multiple customer classes

PL

systemy kolejkowe; duży ruch; przybliżenie dyfuzji; grupy klientów

• Wydawca: Polskie Towarzystwo Informatyczne
• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2023
• Tom: Vol. 35
• Strony: 119--130
• Opis fizyczny: Bibliogr. 27 poz., wz., wykr.

Twórcy

autor

Gieroba Robert

• Maria Curie-Skłodowska University in Lublin Pl. Marii Curie-Skłodowskiej 1, 20-031 Lublin, Poland

• https://orcid.org/0000-0001-6419-3209

autor

Kruk Łukasz

• Maria Curie-Skłodowska University in Lublin Pl. Marii Curie-Skłodowskiej 1, 20-031 Lublin, Poland

• https://orcid.org/0000-0002-3073-959X

Bibliografia

• 1. M. Agrawal, N. Barsal, M. Harchol-Balter, B. Schroeder, Implementation of SRPT scheduling in Web servers (2001). https://www.cs.cmu.edu/~harchol/Papers/srpt.impl.tech.rept.pdf
• 2. M. Agrawal, N. Barsal, M. Harchol-Balter, B. Schroeder, Size-based scheduling to improve Web performance. ACM Transactions on Computer Systems. 21. (2002), https://doi.org/10.1145/762483.762486
• 3. R. Atar, A. Biswas, H. Kaspi, K. Ramanan, A Skorokhod map on measure-valued paths with applications to priority queues. Annals of Applied Probability 28:418-481 (2018), https://doi.org/10.1214/17-AAP1309
• 4. S. Banerjee, A, Budhiraja, A. L. Puha , Heavy traffic scaling limits for shortest remaining processing time queues with heavy tailed processing time distributions, Annals of Applied Probability 32(4), 2587-2651 (2022), https://dx.doi.org/10.1214/21-AAP1741
• 5. P. Billingsley, Convergence of Probability Measures (2nd Edition), John Wiley and Sons, Inc., New York, 1999.
• 6. S. Cheng, Y. Cheng, Y. Fu, L. Liu, H. Wang, SFS: Smart OS scheduling for serverless functions, SC ’22: Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis, pp. 1-16 (2022), https://10.1109/SC41404.2022.00047
• 7. T. Chojecki, Ł. Kruk, Instability of SRPT, SERPT and SJF queueing networks. Queueing Systems: Theory and Applications 101:57-92 (2022), https://doi.org/10.1007/s11134-021-09733-8
• 8. J. Dong, R. Ibrahim, On the SRPT scheduling discipline in many-server queues with impatient customers. Management Science 67(12):7708-7718 (2021), https://doi.org/10.1287/mnsc.2021.4110
• 9. S. N. Ethier, T. G. Kurtz. Markov Processes: Characterization and Convergence. John Wiley and Sons, Inc., New York, 1986.
• 10. R. Gieroba, Ł. Kruk, Minimality of SRPT networks with resource sharing. WSEAS Transactions on Mathematics 20:74-83 (2021), https://doi.org/10.37394/23206.2021.20.8
• 11. R. Gieroba, Ł. Kruk, Local edge minimality of SRPT networks with shared resources, Mathematical Methods of Operations Research, 96:459-492 (2022), https://doi.org/10.1007/s00186-022-00801-0
• 12. H. C. Gromoll, Ł. Kruk, A. L. Puha, Diffusion limits for shortest remaining processing time queues, Stochastic Systems 1, 1-16, 2011, https://doi.org/10.1214/10-SSY016.
• 13. I. Grosof, Z. Scully, M. Harchol-Balter, SRPT for multiserver systems. Performance Evaluation 127-128:154-175 (2018), https://doi.org/10.1145/3308897.3308902
• 14. M. Harchol-Balter, B. Schroeder, Web servers under overload: How scheduling can help. ACM Transactions on Internet Technology 6 (2003), https://doi.org/10.1145/1125274.1125276
• 15. D.L. Iglehart, W. Whitt, Multiple channel queues in heavy traffic I, Advances in Applied Probability 2, 150-177, https://doi.org/10.2307/3518347.
• 16. Ł. Kruk, Diffusion Limits for SRPT and LRPT Queues via EDF Approximations, QTNA 2019, Lecture Notes in Computer Science, vol. 11688, pp. 263-275. Springer, Cham 2019, https://doi.org/10.1007/978-3-030-27181-7_16
• 17. Ł. Kruk, E. Sokołowska, Fluid limits for multiple-input shortest remaining processing time queues, Mathematics of Operation Research 41, 1055-1092, 2016, https://doi.org/10.1287/moor.2015.0768.
• 18. L. W. Miller, L. E. Schrage, The queue M/G/1 with the shortest remaining processing time discipline, Operations Research 14, 670-684 (1966), https://doi.org/10.1287/opre.14.4.670
• 19. R. Núñez-Queija: Queues with equally heavy sojourn time and service requirement distributions, Annals of Operations Research 113, 101-117 (2002), https://doi.org/10.1023/A:1020905810996
• 20. M. Nuyens, B. Zwart: A large deviations analysis of the GI/GI/1 SRPT queue, Queueing Systems 54, 85-97 (2006), https://doi.org/10.1007/s11134-006-8767-1
• 21. W. P. Peterson, A heavy traffic limit theorem for networks of Queues with multiple customer types, Mathematics of Operations Research 16, 90-118, 1991, https://doi.org/10.1287/moor.16.1.90
• 22. Yu. V. Prohorov, Convergence of random processes and limit theorems in probability theory, Theory of Probability and its Applications 1, 157-214, 1956, https://doi.org/10.1137/1101016.
• 23. A. L. Puha, Diffusion limits for shortest remaining processing time queues under nonstandard spatial scaling, Annals of Applied Probability 25(6), 3381–3404 (2015), https://dx.doi.org/10.1214/14-AAP1076
• 24. L. E. Schrage, A proof of the optimality of the shortest remaining processing time discipline, Operations Research 16, 687-690 (1968), https://doi.org/10.1287/opre.26.1.197
• 25. F. Schreiber, Properties and applications of the optimal queueing strategy SRPT: a survey, Archiv für Elektronik und Übertragungstechnik, 47:372-378, 1993,
• 26. W. Whitt, Stochastic-Process Limits: An Introduction to Stochastic-Process Limits and Their Application to Queues, Springer-Verlag, New York, 2002.
• 27. A. Wierman and M. Harchol-Balter. Classifying scheduling policies with respect to unfairness in an M/G/1, Proceedings of the 2003 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, 238-249, 2003, https://doi.org/10.1145/885651.781057

Uwagi

1. Main Track Regular Papers

2. Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2024).