This Article Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Google Scholar Articles by Down, D. G. Articles by Puha, A. L.

Fluid Limits for Shortest Remaining Processing Time Queues

Department of Computing and Software, McMaster University, Hamilton, Ontario L8S 4K1, Canada
Department of Mathematics, University of Virginia, Charlottesville, Virginia 22903
Department of Mathematics, California State University San Marcos, San Marcos, California 92096
downd{at}mcmaster.ca, http://www.cas.mcmaster.ca/downd/
gromoll{at}virginia.edu, http://www.faculty.virginia.edu/gromoll/
apuha{at}csusm.edu, http://www.csusm.edu/puha

We consider a single-server queue with renewal arrivals and i.i.d. service times in which the server uses the shortest remaining processing time policy. To describe the evolution of this queue, we use a measure-valued process that keeps track of the residual service times of all buffered jobs. We propose a fluid model (or formal law of large numbers approximation) for this system and, under mild assumptions, prove the existence and uniqueness of fluid model solutions. Furthermore, we prove a scaling limit theorem that justifies the fluid model as a first-order approximation of the stochastic model. The state descriptor of the fluid model is a measure-valued function whose dynamics are governed by certain inequalities in conjunction with the standard workload equation. In particular, these dynamics determine the evolution of the left edge (infimum) of the state descriptor's support, which yields conclusions about response times. We characterize the evolution of this left edge as an inverse functional of the initial condition, arrival rate, and service time distribution. This characterization reveals the manner in which the growth rate of the left edge depends on the service time distribution. By considering varying examples, the authors show that the rate can vary from logarithmic to polynomial.

Key Words: shortest remaining processing time; fluid model; fluid limit; measure-valued process; response time
History: Received: June 22, 2008; revision received: February 20, 2009;