An Extremal Property of the FIFO Discipline Via An Ordinal Version of L =lambdaW

We apply the relation L = lambdaW 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 a customer's residency (the period a customer spends in the system). This relation can be regarded as an ordinal version of L = lambdaW, arising when we measure time solely in terms of the number of arrivals that occur. We apply the ordinal version of L = lambdaW to obtain a conservation law for single- server queues. We use this conservation law to show that in a G/GI/1 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.