Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Math 288 - Probability & Statistics

Amber Puha

CSU San Marcos and UC San Diego

Scaling Limits for Shortest Remaining Processing Time Queues

Abstract:

In an SRPT queue, the job with the shortest remaining processing time is served first, with preemption. The SRPT scheduling rule is of interest due to its optimality properties; it minimizes queue length (number of jobs in system). However, even with Markovian distributional assumptions on the processing times, an exact analysis is not possible. Hence, approximations in the form of a fluid (functional law of large numbers) limit or a diffusion (functional central limit theorem) limit can provide insights into system performance. It was shown by Gromoll, Kruk and Puha (2011) that, if the processing time distribution has unbounded support, then, under standard heavy traffic conditions, the diffusion limit of the queue length process is identically equal to zero. This exhibits the queue length minimization property of SRPT in sharpest relief. It also demonstrates that the SRPT queue length process is orders of magnitude smaller than the workload process in the diffusion limit. (The workload process tracks the time it will take the server to process the work associated with each job in system.) In this talk, we report on progress in characterizing this order of magnitude difference. We find that distribution dependent scaling must be used to obtain a nontrivial limit for the queue length and the associated measure valued state descriptor. The scaling captures the order of magnitude difference, and the nature of the limit is dependent on the tail decay of the processing time distribution. \\ \\ This work is joint with Sayan Banerjee (UNC) and Amarjit Budhiraja (UNC).

Host: Benson Au

December 3, 2020

10:00 AM

For zoom ID and password email: bau@ucsd.edu

****************************