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

Kramer, Steven B.; Assad, Arjang A.

Oper. Res. Lett. 40, No. 6, 506-509 (2012).

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.

MSC:

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

Keywords:

scheduling; priority classes; queueing

Citations:

Zbl 1058.90500

References:

[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