×

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.

MSC:

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

Citations:

Zbl 1058.90500
PDFBibTeX XMLCite
Full Text: DOI

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
[3] M. Eisenberg, Multi-queues with changeover times, Dissertation, Massachusetts Institute of Technology, 1967.; M. Eisenberg, Multi-queues with changeover times, Dissertation, Massachusetts Institute of Technology, 1967.
[4] S. Kramer, Evaluation of setup economies in cellular manufacturing, Dissertation, University of Maryland, 2004.; S. Kramer, Evaluation of setup economies in cellular manufacturing, Dissertation, University of Maryland, 2004.
[5] W.L. Maxwell, An investigation of multi-product, single-machine scheduling and inventory problems, Dissertation, Cornell University, 1961.; W.L. Maxwell, An investigation of multi-product, single-machine scheduling and inventory problems, Dissertation, Cornell University, 1961.
[6] L.W. Miller, Alternating priorities in multi-class queues, Dissertation: Cornell University, 1964.; L.W. Miller, Alternating priorities in multi-class queues, Dissertation: Cornell University, 1964.
[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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.