SELECTION DISCIPLINES IN A SINGLE-SERVER QUEUEING SYSTEM,
Abstract
The report presents a unified analysis and comparison of job selection rules applied to the M/G/1 queueing system. Laplace-Stieltjes transforms and means of the steady-state distributions of waiting time are obtained. Selection disciplines may be based on relative arrival times (processing time independent rules), job classes (priority rules), and processing time requirements. Priority disciplines may include a preemptive feature allowing a new arrival to interrupt the processing of another job. Performance, as measured by average time in system, can be improved by using a rule that favors shorter jobs. Even relatively crude rules with this characteristic can bring significant improvement. The shortest remaining processing time discipline is optimal when preemption without loss is possible. When changeovers between job classes are accompanied by setup delays, the alternating priorities rule has the highest capacity. An elementary knowledge of probability theory is assumed and introductory material on the Poisson distribution and the Laplace-Stieltjes transform is included. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Oct 01, 1966
- Accession Number
- AD0641357
Entities
People
- Louis W. Miller
Organizations
- RAND Corporation