×

Multi-server queueing systems with multiple priority classes. (English) Zbl 1085.60070

Queueing Syst. 51, No. 3-4, 331-360 (2005); correction ibid. 99, No. 3-4, 397-398 (2021).
The authors introduce a new analytical recursive dimensionality reduction approach that provides the first near-exact analysis of the M/PH/\(k\) queue with \(m\) preemptive-resume priority classes to obtain the mean and higher moments of response times. This novel approach reduces the \(m\)-dimensional infinite state space, created by the priority classes, to a 1-dimensional infinite state space using “busy period transitions” and involves no truncation. It is applicable to a wide range of loads and variability in the job size distribution. This approach considerably reduces the computation time and generalizes several exisiting results [A. Sleptchenko, A. van Harten and M. van der Heijden, Queueing Syst. 50, 81–107 (2005; Zbl 1080.90036)].

MSC:

60K25 Queueing theory (aspects of probability theory)
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
90B22 Queues and service in operations research
90B36 Stochastic scheduling theory in operations research

Citations:

Zbl 1080.90036
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bertsimas, D.; Nakazato, D., The distributional {Little’s Law} and its applications, Operations Research, 43, 2, 298-310 (1995) · Zbl 0837.90048
[2] A. Bondi and J. Buzen, The response times of priority classes under preemptive resume in {M/G/m} queues, in: ACM Sigmetrics., (August 1984) pp. 195-201. · Zbl 0514.90027
[3] Bright, L.; Taylor, P., Calculating the equilibrium distribution in level dependent quasi-birth-and-death processes, Stochastic Models, 11, 497-514 (1995) · Zbl 0837.60081
[4] Buzen, J.; Bondi, A., The response times of priority classes under preemptive resume in {M/M/m} queues, Operations Research, 31, 456-465 (1983) · Zbl 0514.90027
[5] Cobham, A., Priority assignment in waiting line problems, Operations Research, 2, 70-76 (1954) · Zbl 1414.90098
[6] Davis, R., Waiting-time distribution of a multi-server, priority queueing system, Operations Research, 14, 133-136 (1966) · Zbl 0134.14301 · doi:10.1287/opre.14.1.133
[7] Feng, W.; Kowada, M.; Adachi, K., Analysis of a multiserver queue with two priority classes and {(M,N)}-threshold service schedule ii: preemptive priority, Asia-Pacific Journal of Operations Research, 18, 101-124 (2001) · Zbl 1042.90531
[8] Gail, H.; Hantler, S.; Taylor, B., Analysis of a non-preemptive priority multiserver queue, Advances in Applied Probability, 20, 852-879 (1988) · Zbl 0671.60095
[9] Gail, H.; Hantler, S.; Taylor, B., On a preemptive {M}arkovian queue with multiple servers and two priority classes, Mathematics of Operations Research, 17, 365-391 (1992) · Zbl 0762.90028
[10] R. Jain, The Art of Computer Systems Performance Analysis. (John Wiley and Sons, 1991). · Zbl 0824.68013
[11] Kao, E.; Narayanan, K., Modeling a multiprocessor system with preemptive priorities, Management Science, 2, 185-197 (1991) · Zbl 0732.68021
[12] Kao, E.; Wilson, S., Analysis of nonpreemptive priority queues with multiple servers and two priority classes, European Journal of Operational Research, 118, 181-193 (1999) · Zbl 0945.90014 · doi:10.1016/S0377-2217(98)00280-X
[13] Kao, E. P.C.; Narayanan, K. S., Computing steady-state probabilities of a nonpreemptive priority multiserver queue, Journal on Computing, 2, 3, 211-218 (1990) · Zbl 0760.60085
[14] Kapadia, A.; Kazumi, M.; Mitchell, A., Analysis of a finite capacity nonpreemptive priority queue, Computers and Operations Research, 11, 337-343 (1984) · Zbl 0602.60093 · doi:10.1016/0305-0548(84)90022-4
[15] Kella, O.; Yechiali, U., Waiting times in the non-preemptive priority {M/M/c} queue, Stochastic Models, 1, 257-262 (1985) · Zbl 0594.60096
[16] G. Latouche and V. Ramaswami, Introduction to Matrix Analytic Methods in Stochastic Modeling. ({ASA-SIAM}, 1999). · Zbl 0922.60001
[17] H. Leemans, {The Two-Class Two-Server Queue with Nonpreemptive Heterogeneous Priority Structures}. PhD thesis, K.U.Leuven, 1998.
[18] D. McWherter, B. Schroeder, N. Ailamaki and M. Harchol-Balter, Priority mechanisms for {OLTP} and transactional web applications, in: Proceedings of the 20th International Conference on Data Engineering (ICDE 2004). (2004) pp. 535-546.
[19] D. Miller, Steady-state algorithmic analysis of {M/M/c} two-priority queues with heterogeneous servers, in: Applied probability—Computer science, The Interface, eds., R.L. Disney and T.J. Ott, volume II, (Birkhauser, 1992), pp. 207-222.
[20] Mitrani, I.; King, P., Multiprocessor systems with preemptive priorities, Performance Evaluation, 1, 118-125 (1981) · Zbl 0459.68008 · doi:10.1016/0166-5316(81)90014-6
[21] Neuts, M., Moment formulas for the {M}arkov renewal branching process, Advances in Applied Probabilities, 8, 690-711 (1978) · Zbl 0379.60081
[22] Ngo, B.; Lee, H., Analysis of a pre-emptive priority {M/M/c} model with two types of customers and restriction, Electronics Letters, 26, 1190-1192 (1990)
[23] Nishida, T., Approximate analysis for heterogeneous multiprocessor systems with priority jobs, Performance Evaluation, 15, 77-88 (1992) · Zbl 0800.68239 · doi:10.1016/0166-5316(92)90056-M
[24] T. Osogami, Analysis of multiserver systems via dimensionality reduction of Markov chains, Ph.D. thesis. School of Computer Science, Carnegie Mellon University (2005).
[25] T. Osogami and M. Harchol-Balter, A closed-form solution for mapping general distributions to minimal {PH} distributions, in: Performance TOOLS. (2003) pp. 200-217. · Zbl 1274.60041
[26] Osogami, T.; Harchol-Balter, M.; Scheller-Wolf, A., Analysis of cycle stealing with switching costs and thresholds, Performance Evaluation, 61, 4, 347-369 (2005)
[27] A. Sleptchenko, Multi-class, multi-server queues with non-preemptive priorities. Technical Report 2003-016, EURANDOM, Eindhoven University of Technology, 2003.
[28] Sleptchenko, A.; van Harten, A.; van der Heijden, M., An exact solution for the state probabilities of the multi-class, multi-server queue with preemptive priorities, Queueing Systems, 50, 81-107 (2005) · Zbl 1080.90036 · doi:10.1007/s11134-005-0359-y
[29] Whitt, W., A review of L. = λ W. and extensions, Queueing Systems, 9, 235-268 (1991) · Zbl 0727.60112 · doi:10.1007/BF01158466
[30] A. Wierman, T. Osogami, M. Harchol-Balter and A. Scheller-Wolf, How many servers are best in a dual-priority {M/PH/k} system, {Unpublished Manuscript. In submission}, 2005. · Zbl 1085.60070
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.