Alternating priority versus FCFS scheduling in a two-class queueing system. (English) Zbl 1262.90045

Summary: For the single-server two-class queueing system studied in the classical text of R. W. Conway et al. [Theory of scheduling. Reading, Mass.: Addison-Wesley Publishing Company (1967; Zbl 1058.90500)], we compare the mean flow times for First-Come, First-Served (FCFS) and Alternating Priority (AP) scheduling rules assuming zero setup costs for switching between classes. We show that the condition for the superiority of AP over FCFS stated in that text is incorrect, provide the correct conditions, and establish a lower bound on the difference between the mean flow times under the two rules.


90B22 Queues and service in operations research
90B36 Stochastic scheduling theory in operations research


Zbl 1058.90500
Full Text: DOI


[1] Avi-Itzhak, B.; Maxwell, W. L.; Miller, L. W., Queuing with alternating priorities, Oper. Res., 13, 2, 306-318 (1965) · Zbl 0131.16705
[2] Conway, R. W.; Maxwell, W. L.; Miller, L. W., Theory of Scheduling (1967), Addison-Wesley: Addison-Wesley Reading, Mass · Zbl 1058.90500
[7] Takács, L., Two queues attended by a single server, Oper. Res., 16, 3, 639-650 (1968) · Zbl 0155.24603
[8] Takagi, H., Analysis of Polling Systems (1986), MIT Press: MIT Press Cambridge, Mass
[9] Wolff, W., Stochastic Modeling and the Theory of Queues (1989), Prentice Hall: Prentice Hall Englewood Cliffs, NJ · Zbl 0701.60083
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.