Talk by Amber Puha (Cal State San Marcos)
Date and Time: Thursday, October 31, 2013, 10:00 AM in AP&M 6402
Title: Performance Analysis of Shortest Remaining Processing Time Queues
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