An extremal property of the fifo discipline via an ordinal version of

Abstract

We apply the relation to prove that in great generality the long-run average number of customers in a queueing system at an arrival epoch is equal to the long-run average number of arrivals during the period a customer spends in the system. This relation can be regarded as an ordinal version of , arising when we measure time solely in terms of the number of arrivals that occur. We apply the ordinal version of to obtain a conservation law for single-server queues. We use this conservation law to establish an extremal property for the FIFO service discipline: We show that in a G/GI/I system the FIFO discipline minimizes (maximizes) the long-run average sojourn time per customer among all work-conserving disciplines that are non-anticipating with respect to the service times (may depend on completed service times, but not remaining service times) when the service-time distribution is NBUE (NWUE). Among the disciplines in this class are round robin, processor sharing and shortest expected remaining processing time