Technical Note—A New Proof of the Optimality of the Shortest Remaining Processing Time Discipline

Donald R. Smith
Additional contact information
Donald R. Smith: Columbia University, New York, New York

Operations Research, 1978, vol. 26, issue 1, 197-199

Abstract: We present a new proof of the fact that for a work-conserving queue, the queuing discipline that always serves a job with the shortest remaining processing time minimizes the number of jobs in the system. A key feature of the proof is a definition of work dominance, allowing comparison of two systems based on the remaining service times of jobs present. Work dominance is both necessary and sufficient for stochastic comparison of the number of jobs present under identical but arbitrary arrival processes.

Date: 1978
References: Add references at CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.26.1.197 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:26:y:1978:i:1:p:197-199

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().