Abstract
We consider a multi-server queue with K priority classes. In this system, customers of the P highest priorities (P<K) can preempt customers with lower priorities, ejecting them from service and sending them back into the queue. Service times are assumed exponential with the same mean for all classes.
The Laplace–Stieltjes transforms of waiting times are calculated explicitly and the Laplace–Stieltjes transforms of sojourn times are provided in an implicit form via a system of functional equations. In both cases, moments of any order can be easily calculated. Specifically, we provide formulae for the steady state means and the second moments of waiting times for all priority classes. We also study some approximations of sojourn-time distributions via their moments. In a practical part of our paper, we discuss the use of mixed priorities for different types of Service Level Agreements, including an example based on a real scheduling problem of IT support teams.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Abate, J., Whitt, W.: A unified framework for numerically inverting Laplace transforms. INFORMS J. Comput. 18(4), 408–421 (2006)
Adiri, I., Domb, I.: A single-server queueing system working under mixed priority disciplines. Oper. Res. 30, 97–115 (1982)
Buzen, J., Bondi, A.: The response times of priority classes under preemptive resume in M/M/m queues. Oper. Res. 31, 456–465 (1983)
Chang, W.: Queuing with nonpreemptive and preemptive-resume priorities. Oper. Res. 13, 1020–1022 (1965)
Cobham, A.: Priority assignment in waiting line problems. Oper. Res. 2, 70–76 (1954)
Davis, R.: Waiting-time distribution of a multi-server, priority queueing system. Oper. Res. 14, 133–136 (1966)
Drekic, S., Stanford, D.A.: Threshold-based interventions to optimize performance in preemptive priority queues. Queueing Syst. 35, 289–315 (2000)
Feldman, Z., Mandelbaum, A., Massey, W., Whitt, W.: Staffing of time-varying queues to achieve time-stable performance. Manag. Sci. 54(2), 324–338 (2008)
Gail, H., Hantler, S., Taylor, B.: Analysis of a non-preemptive priority multiserver queue. Adv. Appl. Probab. 20, 852–879 (1988)
Gail, H., Hantler, S., Taylor, B.: On a preemptive Markovian queue with multiple servers and two priority classes. Math. Oper. Res. 17, 365–391 (1992)
Gans, N., Koole, G., Mandelbaum, A.: Telephone call centers: a tutorial and literature review. Invited review paper. Manuf. Serv. Oper. Manag. 5(2), 79–141 (2003)
Hall, R.W.: Queueing Methods: For Services and Manufacturing. Prentice Hall, New York (1997)
Harchol-Balter, M., Osogami, T., Scheller-Wolf, A., Wierman, A.: Multi-server queueing systems with multiple priority classes. Queueing Syst. Theory Appl. 51, 331–360 (2005)
van der Heijden, M., van Harten, A., Sleptchenko, A.: Approximations for Markovian multi-class queues with preemptive priorities. Oper. Res. Lett. 32(3), 273–282 (2004)
Jagerman, D.L., Melamed, B.: Models and approximations for call center design. Methodol. Comput. Appl. Probab. 5, 159–181 (2003)
Kella, O., Yechiali, U.: Waiting times in the non-preemptive priority M/M/c queue. Stoch. Models 1, 257–262 (1985)
Neuts, M.F.: Matrix-Geometric Solutions in Stochastic Models. The Johns Hopkins University Press, Baltimore and London (1981)
Osogami, T., Harchol-Balter, M.: Closed form solutions for mapping general distributions to quasi-minimal PH distributions. Perform. Eval. 63, 524–552 (2006)
Osogami, T.: Online code repository. Available at http://www.cs.cmu.edu/~osogami/code/index.html
Rosenshmidt, L.: On priority queues with impatient customers: stationary and time-varying analysis. M.Sc. thesis, Technion. Available at http://iew3.technion.ac.il/serveng/References/references.html (2007)
Segal, M.: A multiserver system with preemptive priorities. Oper. Res. 18, 316–323 (1970)
Simon, B.: Priority queues with feedback. J. ACM 31(1), 134–149 (1984)
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 Syst. Theory Appl. 50(1), 81–107 (2005)
Tatashev, A.G.: Calculation of the distribution of the waiting time in a multiple-channel queueing system with fixed priorities. Eng. Cybern. 6, 59–62 (1984)
Wasserkrug, S., Taub, S., Zeltyn, S., Gilat, D., Lipets, V., Feldman, Z., Mandelbaum, A.: Creating shift schedules for IT delivery center workers. Int. J. Serv. Oper. Inform. 3, 242–257 (2008)
Wolff, R.W.: Poisson arrivals see time averages. Oper. Res. 30, 223–231 (1982)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Zeltyn, S., Feldman, Z. & Wasserkrug, S. Waiting and sojourn times in a multi-server queue with mixed priorities. Queueing Syst 61, 305–328 (2009). https://doi.org/10.1007/s11134-009-9110-4
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11134-009-9110-4