Technical Note—A New Proof of the Optimality of the Shortest Remaining Processing Time Discipline
Donald R. Smith
Source 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.
Evidence graph
No public relationships recorded yet.
Integrity note: This page is a factual metadata record created by deterministic ingestion. It is not a claim that the work moves a mathematical frontier or has been independently verified.