Fluid Limits for Shortest Remaining Processing Time Queues

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.

Fluid Limits for Shortest Remaining Processing Time Queues Journal Articles