Department of Mathematics,
University of California San Diego
****************************
Math 288 - Probability & Statistics Seminar
Amber Puha
Cal State San Marcos, visiting UCSD
Performance Analysis of Shortest Remaining Processing Time Queues
Abstract:
A shortest remaining processing time (SRPT) queue is a single server queue in which the server dedicates its effort to the job that has the least remaining processing time among all jobs in the system. This is done with preemption so that when the total processing time of an arriving job is less than that remaining for the job in service, service of the job in service is paused and the newly arriving job enters service. Shortest remaining processing time is of interest because it is performance optimal in the sense that over all non-idling service disciplines it minimizes queue length. However, this may come at the expense of long delays for jobs with large total processing times. From a mathematical point of view, SRPT is challenging to analyze, in part because the preemptive nature of SRPT leads to an infinite dimensional state space. By formulating and analyzing a probabilistic model for SRPT that employs measure-valued processes, we investigate this performance trade off. The talk will begin with a discussion of a fluid limit (first order approximation) for the stochastic model. This will yield some interesting insights about the anticipated performance trade-off. Next work in progress on a diffusion limit (second order approximation) will be discussed. Various parts of this work are joint with D. Down (McMaster University), H. C. Gromoll (U Virginia), and L. Kruk (Maria Curie-Sklodowska University)
October 31, 2013
10:00 AM
AP&M 6402
****************************