Work-conserving priorities

Abstract

In many situations, it is reasonable to assume that a priority rule does not affect the total time spent in service of any job. Rules with this property are said to be work-conserving. This concept unifies and simplifies the analysis of a variety of priority queues. Some results are obtained for rules applied to the GI/G/1 queue. Some special properties of Poisson arrivals are discussed, and a new proof of the equivalence of averaging over all time with averaging over arrival epochs is presented. In this case, explicit results for particular rules are obtained in examples. In another example, the optimal rule (from a very restrictive class) is determined without specializing the arrival stream.