×

Diffusion limits for shortest remaining processing time queues under nonstandard spatial scaling. (English) Zbl 1328.60205

Summary: We develop a heavy traffic diffusion limit theorem under nonstandard spatial scaling for the queue length process in a single server queue employing shortest remaining processing time (SRPT). For processing time distributions with unbounded support, it has been shown that standard diffusion scaling yields an identically zero limit. We specify an alternative spatial scaling that produces a nonzero limit. Our model allows for renewal arrivals and i.i.d. processing times satisfying a rapid variation condition. We add a corrective spatial scale factor to standard diffusion scaling, and specify conditions under which the sequence of unconventionally scaled queue length processes converges in distribution to the same nonzero reflected Brownian motion to which the sequence of conventionally scaled workload processes converges. Consequently, this corrective spatial scale factor characterizes the order of magnitude difference between the queue length and workload processes of SRPT queues in heavy traffic. It is determined by the processing time distribution such that the rate at which it tends to infinity depends on the rate at which the tail of the processing time distribution tends to zero. For Weibull processing time distributions, we restate this result in a manner that makes the resulting state space collapse more apparent.

MSC:

60K25 Queueing theory (aspects of probability theory)
60F17 Functional limit theorems; invariance principles
60J60 Diffusion processes
60G57 Random measures
90B22 Queues and service in operations research
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems

References:

[1] Bansal, N. and Harchol-Balter, M. (2001). Analysis of SRPT scheduling: Investigating unfairness. ACM SIGMETRICS Performance Evaluation Review 29 279-290.
[2] Billingsley, P. (1968). Convergence of Probability Measures . Wiley, New York. · Zbl 0172.21201
[3] Bingham, N. H., Goldie, C. M. and Teugels, J. L. (1987). Regular Variation. Encyclopedia of Mathematics and Its Applications 27 . Cambridge Univ. Press, Cambridge. · Zbl 0617.26001
[4] Bojanić, R. and Seneta, E. (1971). Slowly varying functions and asymptotic relations. J. Math. Anal. Appl. 34 302-315. · Zbl 0222.26003 · doi:10.1016/0022-247X(71)90114-4
[5] Down, D. G., Gromoll, H. C. and Puha, A. L. (2009). State-dependent response times via fluid limits for shortest remaining processing time queues. ACM SIGMETRICS Performance Evaluation Review 37 75-76. · Zbl 1213.60145 · doi:10.1287/moor.1090.0409
[6] Down, D. G., Gromoll, H. C. and Puha, A. L. (2009). Fluid limits for shortest remaining processing time queues. Math. Oper. Res. 34 880-911. · Zbl 1213.60145 · doi:10.1287/moor.1090.0409
[7] Ethier, S. N. and Kurtz, T. G. (1986). Markov Processes : Characterization and Convergence . Wiley, New York. · Zbl 0592.60049
[8] Gromoll, H. C. (2004). Diffusion approximation for a processor sharing queue in heavy traffic. Ann. Appl. Probab. 14 555-611. · Zbl 1050.60085 · doi:10.1214/105051604000000035
[9] Gromoll, H. C., Kruk, Ł. and Puha, A. L. (2011). Diffusion limits for shortest remaining processing time queues. Stoch. Syst. 1 1-16. · Zbl 1291.60187 · doi:10.1214/10-SSY016
[10] Harrison, J. M. and Williams, R. J. (1996). A multiclass closed queueing network with unconventional heavy traffic behavior. Ann. Appl. Probab. 6 1-47. · Zbl 0865.60078 · doi:10.1214/aoap/1034968064
[11] Iglehart, D. L. and Whitt, W. (1970). Multiple channel queues in heavy traffic. I. Adv. in Appl. Probab. 2 150-177. · Zbl 0218.60098 · doi:10.2307/3518347
[12] Limic, V. (2001). A LIFO queue in heavy traffic. Ann. Appl. Probab. 11 301-331. · Zbl 1015.60079
[13] Lin, M., Wierman, A. and Zwart, B. (2011). The heavy-traffic analysis of mean response time under shortest remaining processing time. Performance Evaluation 68 955-966.
[14] Núñez-Queija, R. (2002). Queues with equally heavy sojourn time and service requirement distributions. Ann. Oper. Res. 113 101-117. · Zbl 1013.90036 · doi:10.1023/A:1020905810996
[15] Nuyens, M. and Zwart, B. (2006). A large-deviations analysis of the \(GI/GI/1\) SRPT queue. Queueing Syst. 54 85-97. · Zbl 1107.60061 · doi:10.1007/s11134-006-8767-1
[16] Pavlov, A. V. (1984). A system with Schrage servicing discipline in the case of a high load. Engrg. Cybernetics 21 114-121; translated from Izv. Akad. Nauk SSSR Tekhn. Kibernet. 6 (1983) 59-66 (Russian). · Zbl 0576.90034
[17] Pechinkin, A. V. (1986). Heavy traffic in a system with a discipline of priority servicing for the job of shortest remaining length with interruption. Mat. Issled. 89 85-93. · Zbl 0591.90031
[18] Perera, R. (1993). The variance of delay time in queueing system \(M/G/1\) with optimal strategy SRPT. Archiv für Elektronik und Uebertragungstechnik 47 110-114.
[19] Prohorov, Yu. V. (1956). Convergence of random processes and limit theorems in probability theory. Theory Probab. Appl. 1 157-214.
[20] Schassberger, R. (1990). The steady-state appearance of the \(M/G/1\) queue under the discipline of shortest remaining processing time. Adv. in Appl. Probab. 22 456-479. · Zbl 0707.60085 · doi:10.2307/1427545
[21] Schrage, L. E. (1968). A proof of the optimality of the shortest remaining processing time discipline. Oper. Res. 16 687-690. · Zbl 0237.60039 · doi:10.1287/opre.16.3.687
[22] Schrage, L. E. and Miller, L. W. (1966). The queue \(M/G/1\) with the shortest remaining processing time discipline. Oper. Res. 14 670-684. · Zbl 0147.16702 · doi:10.1287/opre.14.4.670
[23] Schreiber, F. (1993). Properties and applications of the optimal queueing strategy SRPT: A survey. Archiv für Elektronik und Übertragungstechnik 47 372-378.
[24] Smith, D. R. (1978). A new proof of the optimality of the shortest remaining processing time discipline. Oper. Res. 26 197-199. · Zbl 0373.60124 · doi:10.1287/opre.26.1.197
[25] Whitt, W. (1971). Weak convergence theorems for priority queues: Preemptive-resume discipline. J. Appl. Probab. 8 74-94. · Zbl 0215.53801 · doi:10.2307/3211839
[26] Wierman, A. and Harchol-Balter, M. (2003). Classifying scheduling policies with respect to unfairness in an M/GI/1. In Proceedings of the 2003 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems 238-249. ACM, New York.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.