On extremal service disciplines in single-stage queueing systems
- 1 June 1990
- journal article
- Published by Cambridge University Press (CUP) in Journal of Applied Probability
- Vol. 27 (2) , 409-416
- https://doi.org/10.2307/3214660
Abstract
It is shown that among all work-conserving service disciplines that are independent of the future history, the first-come-first-served (FCFS) service discipline minimizes [maximizes] the average sojourn time in a G/GI/1 queueing system with new better [worse] than used in expectation (NBUE[NWUE]) service time distribution. We prove this result using a new basic identity of G/GI/1 queues that may be of independent interest. Using a relationship between the workload and the number of customers in the system with different lengths of attained service it is shown that the average sojourn time is minimized [maximized] by the least-attained-service time (LAST) service discipline when the service time has the decreasing [increasing] mean residual life (DMRL[IMRL]) property.Keywords
This publication has 7 references indexed in Scilit:
- An extremal property of FIFO discipline in G/IFR/1 queuesAdvances in Applied Probability, 1989
- Further results for dynamic scheduling of multiclass G/G/1 queuesJournal of Applied Probability, 1989
- An extremal property of the fifo discipline via an ordinal version ofCommunications in Statistics. Stochastic Models, 1989
- Scheduling Multiclass Single Server Queueing Systems to Stochastically Maximize the Number of Successful DeparturesProbability in the Engineering and Informational Sciences, 1989
- An Optimal Design Problem for Limited Processor Sharing SystemsManagement Science, 1987
- Convex ordering of sojourn times in single-server queues: extremal properties of FIFO and LIFO service disciplinesJournal of Applied Probability, 1987
- Work-conserving prioritiesJournal of Applied Probability, 1970