Heavy traffic scaling limits for shortest remaining processing time queues with light tailed processing time distributions

被引:0
作者
Ji, Chunxu [1 ]
Puha, Amber L. [1 ]
机构
[1] Calif State Univ San Marcos, Dept Math, 333 S Twin Oaks Valley Rd, San Marcos, CA 92096 USA
关键词
Shortest remaining processing time queue; Rapidly varying tails; Diffusion approximation; Nonstandard scaling; Measure valued state process; Secondary; OPTIMALITY; PROOF; SRPT;
D O I
10.1007/s11134-024-09929-8
中图分类号
TP39 [计算机的应用];
学科分类号
081203 ; 0835 ;
摘要
We prove a heavy traffic scaling limit for a shortest remaining processing time queue. We are interested in the case where the processing time distribution has a tail that decays rapidly, i.e., has light tails. In particular, we revisit the work in Puha (2015), which shows that the diffusion scaled queue length process multiplied by a processing time distribution dependent factor that tends to infinity converges to a nontrivial reflecting Brownian motion, under the condition that this distribution dependent factor is slowly varying and obeys a certain rate of convergence condition. Here, we prove that the rate of convergence condition is not needed and the result holds more generally. We further show convergence of a sequence of nonstandardly scaled measure valued state descriptors to a point mass at one such that the total mass fluctuates randomly in accordance with the diffusion limit for the workload process. This is a sharp concentration result which shows that, under this nonstandard scaling, there are a very small number of tasks in the system and the remaining work for each such task is large and of the same order of magnitude as that of other tasks. This is due to the prioritization of the task with the least remaining work, and is in contrast to the case of heavy tailed processing times studied in Banerjee, Budhiraja, and Puha (2022). There it is shown that, while there is some concentration, the remaining times of the very small number of tasks in the system spread out over the nonnegative real line according to a random profile under this nonstandard scaling. Thus, this work completes the description of the two fundamentally different behaviors of SPRT by characterizing it in the case of light tailed processing time distributions.
引用
收藏
页数:58
相关论文
共 25 条
[1]   A SKOROKHOD MAP ON MEASURE-VALUED PATHS WITH APPLICATIONS TO PRIORITY QUEUES [J].
Atar, Rami ;
Biswas, Anup ;
Kaspi, Haya ;
Ramanan, Kavita .
ANNALS OF APPLIED PROBABILITY, 2018, 28 (01) :418-481
[2]   HEAVY TRAFFIC SCALING LIMITS FOR SHORTEST REMAINING PROCESSING TIME QUEUES WITH HEAVY TAILED PROCESSING TIME DISTRIBUTIONS [J].
Banerjee, Sayan ;
Budhiraja, Amarjit ;
Puha, Amber L. .
ANNALS OF APPLIED PROBABILITY, 2022, 32 (04) :2587-2651
[3]  
BILLINGSLEY P., 1999, Convergence of probability measures, V2nd, DOI [10.1002/9780470316962, DOI 10.1002/9780470316962]
[4]  
Bingham NH., 1987, Regular Variation. Encyclopedia of Mathematics and its Applications, DOI [10.1017/CBO9780511721434, DOI 10.1017/CBO9780511721434]
[5]  
Chen Y, 2021, Arxiv, DOI arXiv:2105.10499
[6]   SRPT Scheduling Discipline in Many-Server Queues with Impatient Customers [J].
Dong, Jing ;
Ibrahim, Rouba .
MANAGEMENT SCIENCE, 2021, 67 (12) :7708-7718
[7]  
Down D., 2009, San Diego ACM-Sigmetrics Perform. Eval, V27, P75, DOI [10.1145/1639562.1639593, DOI 10.1145/1639562.1639593]
[8]   Fluid Limits for Shortest Remaining Processing Time Queues [J].
Down, Douglas G. ;
Gromoll, H. Christian ;
Puha, Amber L. .
MATHEMATICS OF OPERATIONS RESEARCH, 2009, 34 (04) :880-911
[9]  
Ethier SN., 2009, MARKOV PROCESSES CHA, DOI [10.1002/9780470316658, DOI 10.1002/9780470316658]
[10]  
Gromoll HC., 2011, STOCH SYST, V1, P1