IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v63y2015i3p733-749.html
   My bibliography  Save this article

M/M/c Queue with Two Priority Classes

Author

Listed:
  • Jianfu Wang

    (Nanyang Business School, Nanyang Technological University, Singapore, 639798)

  • Opher Baron

    (Rotman School of Management, University of Toronto, Toronto, Ontario M5S 3E6, Canada)

  • Alan Scheller-Wolf

    (Tepper School of Business, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213)

Abstract

This paper provides the first exact analysis of a preemptive M/M/c queue with two priority classes having different service rates. To perform our analysis, we introduce a new technique to reduce the two-dimensionally infinite Markov chain (MC), representing the two class state space, into a one-dimensionally infinite MC, from which the generating function (GF) of the number of low-priority jobs can be derived in closed form . (The high-priority jobs form a simple M/M/c system and are thus easy to solve.) We demonstrate our methodology for the c = 1, 2 cases; when c > 2, the closed-form expression of the GF becomes cumbersome. We thus develop an exact algorithm to calculate the moments of the number of low-priority jobs for any c ≥ 2. Numerical examples demonstrate the accuracy of our algorithm and generate insights on (i) the relative effect of improving the service rate of either priority class on the mean sojourn time of low-priority jobs; (ii) the performance of a system having many slow servers compared with one having fewer fast servers; and (iii) the validity of the square root staffing rule in maintaining a fixed service level for the low-priority class. Finally, we demonstrate the potential of our methodology to solve other problems using the M/M/c queue with two priority classes, where the high-priority class is completely impatient.

Suggested Citation

  • Jianfu Wang & Opher Baron & Alan Scheller-Wolf, 2015. "M/M/c Queue with Two Priority Classes," Operations Research, INFORMS, vol. 63(3), pages 733-749, June.
    • Handle: RePEc:inm:oropre:v:63:y:2015:i:3:p:733-749
    DOI: 10.1287/opre.2015.1375
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.2015.1375
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.2015.1375?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Dimitris Bertsimas & Daisuke Nakazato, 1995. "The Distributional Little's Law and Its Applications," Operations Research, INFORMS, vol. 43(2), pages 298-310, April.
    2. Hossein Abouee-Mehrizi & Barış Balcıoğlu & Opher Baron, 2012. "Strategies for a Centralized Single Product Multiclass M/G/ 1 Make-to-Stock Queue," Operations Research, INFORMS, vol. 60(4), pages 803-812, August.
    3. Richard H. Davis, 1966. "Waiting-Time Distribution of a Multi-Server, Priority Queuing System," Operations Research, INFORMS, vol. 14(1), pages 133-136, February.
    4. Mor Harchol-Balter & Takayuki Osogami & Alan Scheller-Wolf & Adam Wierman, 2005. "Multi-Server Queueing Systems with Multiple Priority Classes," Queueing Systems: Theory and Applications, Springer, vol. 51(3), pages 331-360, December.
    5. Douglas R. Miller, 1981. "Computation of Steady-State Probabilities for M / M /1 Priority Queues," Operations Research, INFORMS, vol. 29(5), pages 945-958, October.
    6. Constantinos Maglaras & Assaf Zeevi, 2005. "Pricing and Design of Differentiated Services: Approximate Analysis and Structural Insights," Operations Research, INFORMS, vol. 53(2), pages 242-262, April.
    7. Shlomo Halfin & Ward Whitt, 1981. "Heavy-Traffic Limits for Queues with Many Exponential Servers," Operations Research, INFORMS, vol. 29(3), pages 567-588, June.
    8. Ward Whitt, 1992. "Understanding the Efficiency of Multi-Server Service Systems," Management Science, INFORMS, vol. 38(5), pages 708-723, May.
    9. J. P. Buzen & A. B. Bondi, 1983. "The Response Times of Priority Classes under Preemptive Resume in M / M / m Queues," Operations Research, INFORMS, vol. 31(3), pages 456-465, June.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Gabor, Adriana F. & van Vianen, Lars A. & Yang, Guangyuan & Axsäter, Sven, 2018. "A base-stock inventory model with service differentiation and response time guarantees," European Journal of Operational Research, Elsevier, vol. 269(3), pages 900-908.
    2. van Vianen, L.A. & Gabor, A.F. & van Ommeren, J.C.W., 2016. "Waiting times in classical priority queues via elementary lattice path counting," Econometric Institute Research Papers EI2016-17, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    3. Opher Baron & Antonis Economou & Athanasia Manou, 2018. "The state-dependent M / G / 1 queue with orbit," Queueing Systems: Theory and Applications, Springer, vol. 90(1), pages 89-123, October.
    4. Jori Selen & Brian Fralix, 2017. "Time-dependent analysis of an M / M / c preemptive priority system with two priority classes," Queueing Systems: Theory and Applications, Springer, vol. 87(3), pages 379-415, December.
    5. Gabor, A.F. & van Vianen, L.A. & Yang, G. & Axsäter, S., 2016. "Enabling customer satisfaction and stock reduction through service differentiation with response time guarantees," Econometric Institute Research Papers EI2016-13, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Mor Harchol-Balter & Takayuki Osogami & Alan Scheller-Wolf & Adam Wierman, 2005. "Multi-Server Queueing Systems with Multiple Priority Classes," Queueing Systems: Theory and Applications, Springer, vol. 51(3), pages 331-360, December.
    2. Constantinos Maglaras & Assaf Zeevi, 2004. "Diffusion Approximations for a Multiclass Markovian Service System with “Guaranteed” and “Best-Effort” Service Levels," Mathematics of Operations Research, INFORMS, vol. 29(4), pages 786-813, November.
    3. Constantinos Maglaras & Assaf Zeevi, 2005. "Pricing and Design of Differentiated Services: Approximate Analysis and Structural Insights," Operations Research, INFORMS, vol. 53(2), pages 242-262, April.
    4. Jori Selen & Brian Fralix, 2017. "Time-dependent analysis of an M / M / c preemptive priority system with two priority classes," Queueing Systems: Theory and Applications, Springer, vol. 87(3), pages 379-415, December.
    5. Achal Bassamboo & J. Michael Harrison & Assaf Zeevi, 2006. "Design and Control of a Large Call Center: Asymptotic Analysis of an LP-Based Method," Operations Research, INFORMS, vol. 54(3), pages 419-435, June.
    6. Rouba Ibrahim & Mor Armony & Achal Bassamboo, 2017. "Does the Past Predict the Future? The Case of Delay Announcements in Service Systems," Management Science, INFORMS, vol. 63(6), pages 1762-1780, June.
    7. Andrei Sleptchenko & M. Eric Johnson, 2015. "Maintaining Secure and Reliable Distributed Control Systems," INFORMS Journal on Computing, INFORMS, vol. 27(1), pages 103-117, February.
    8. Ari Arapostathis & Hassan Hmedi & Guodong Pang, 2021. "On Uniform Exponential Ergodicity of Markovian Multiclass Many-Server Queues in the Halfin–Whitt Regime," Mathematics of Operations Research, INFORMS, vol. 46(2), pages 772-796, May.
    9. Francis de Véricourt & Otis B. Jennings, 2008. "Dimensioning Large-Scale Membership Services," Operations Research, INFORMS, vol. 56(1), pages 173-187, February.
    10. O. Garnet & A. Mandelbaum & M. Reiman, 2002. "Designing a Call Center with Impatient Customers," Manufacturing & Service Operations Management, INFORMS, vol. 4(3), pages 208-227, October.
    11. A. J. E. M. Janssen & J. S. H. van Leeuwaarden & Bert Zwart, 2011. "Refining Square-Root Safety Staffing by Expanding Erlang C," Operations Research, INFORMS, vol. 59(6), pages 1512-1522, December.
    12. J. G. Dai & Tolga Tezcan, 2011. "State Space Collapse in Many-Server Diffusion Limits of Parallel Server Systems," Mathematics of Operations Research, INFORMS, vol. 36(2), pages 271-320, May.
    13. Costis Maglaras & John Yao & Assaf Zeevi, 2018. "Optimal Price and Delay Differentiation in Large-Scale Queueing Systems," Management Science, INFORMS, vol. 64(5), pages 2427-2444, May.
    14. Josh Reed & Bo Zhang, 2017. "Managing capacity and inventory jointly for multi-server make-to-stock queues," Queueing Systems: Theory and Applications, Springer, vol. 86(1), pages 61-94, June.
    15. Sunil Kumar & Ramandeep S. Randhawa, 2010. "Exploiting Market Size in Service Systems," Manufacturing & Service Operations Management, INFORMS, vol. 12(3), pages 511-526, September.
    16. Alfonso J. Pedraza-Martinez & Sameer Hasija & Luk N. Van Wassenhove, 2020. "Fleet Coordination in Decentralized Humanitarian Operations Funded by Earmarked Donations," Operations Research, INFORMS, vol. 68(4), pages 984-999, July.
    17. Lars A. Vianen & Adriana F. Gabor & Jan-Kees Ommeren, 2016. "Waiting times in classical priority queues via elementary lattice path counting," Queueing Systems: Theory and Applications, Springer, vol. 84(3), pages 295-307, December.
    18. Ward Whitt, 2003. "How Multiserver Queues Scale with Growing Congestion-Dependent Demand," Operations Research, INFORMS, vol. 51(4), pages 531-542, August.
    19. Defraeye, Mieke & Van Nieuwenhuyse, Inneke, 2016. "Staffing and scheduling under nonstationary demand for service: A literature review," Omega, Elsevier, vol. 58(C), pages 4-25.
    20. Opher Baron & Joseph Milner, 2009. "Staffing to Maximize Profit for Call Centers with Alternate Service-Level Agreements," Operations Research, INFORMS, vol. 57(3), pages 685-700, June.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:oropre:v:63:y:2015:i:3:p:733-749. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.