Fluid Limits for Shortest Remaining Processing Time Queues

Douglas G. Down · H. Christian Gromoll · Amber L. Puha

71 citations0/0 files storedMathematics of Operations Research

No readable copy stored yet — this record is metadata only.

No open-access location is known for this record yet.

Literature note Cite in a project Citation map

Advanced Queuing Theory Analysis Stochastic processes and statistical mechanics Age of Information Optimization

Abstract

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.

Paper brief

Loading…

Cite this work

Citation unavailable for this work.

BibTeX RIS CSL-JSON

No public copy is stored for this record, so only the metadata is cited.

Citations in this library

Citation map →

Stored only when both papers are in the corpus — 71 citations exist upstream.

References

1968Letter to the Editor—A Proof of the Optimality of the Shortest Remaining Processing Time Discipline 1970Multiple channel queues in heavy traffic. I 1966The Queue M/G/1 with the Shortest Remaining Processing Time Discipline 2001Analysis of SRPT scheduling 2003Classifying scheduling policies with respect to unfairness in an M/GI/1 2001Real-time queues in heavy traffic with earliest-deadline-first queue discipline 2002The fluid limit of a heavily loaded processor sharing queue 1971Weak convergence theorems for priority queues: preemptive-resume discipline

Cited by

2011Heavy traffic analysis for EDF queues with reneging 2011Size- and state-aware dispatching problem with queue-specific job sizes 2018Heavy traffic analysis for EDF queues with reneging 2018SRPT for multiserver systems 2011Heavy-traffic analysis of mean response time under Shortest Remaining Processing Time 2015Diffusion limits for shortest remaining processing time queues under nonstandard spatial scaling

Explore the map →

Papers that cite the same references — the relational fallback while embeddings are still backfilling.

Imported from OpenAlex (CC0) — nothing here is generated.