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

Dynamic Scheduling of a Multiclass Queue in the Halfin-Whitt Heavy Traffic Regime

Author

Listed:
  • J. Michael Harrison

    (Graduate School of Business, Stanford University, Stanford, California)

  • Assaf Zeevi

    (Graduate School of Business, Columbia University, New York, New York 10027)

Abstract

We consider a Markovian model of a multiclass queueing system in which a single large pool of servers attends to the various customer classes. Customers waiting to be served may abandon the queue, and there is a cost penalty associated with such abandonments. Service rates, abandonment rates, and abandonment penalties are generally different for the different classes. The problem studied is that of dynamically scheduling the various classes. We consider the Halfin-Whitt heavy traffic regime, where the total arrival rate and the number of servers both become large in such a way that the system's traffic intensity parameter approaches one. An approximating diffusion control problem is described and justified as a purely formal (that is, nonrigorous) heavy traffic limit. The Hamilton-Jacobi-Bellman equation associated with the limiting diffusion control problem is shown to have a smooth (classical) solution, and optimal controls are shown to have an extremal or “bang-bang” character. Several useful qualitative insights are derived from the mathematical analysis, including a “square-root rule” for sizing large systems and a sharp contrast between system behavior in the Halfin-Whitt regime versus that observed in the “conventional” heavy traffic regime. The latter phenomenon is illustrated by means of a numerical example having two customer classes.

Suggested Citation

  • J. Michael Harrison & Assaf Zeevi, 2004. "Dynamic Scheduling of a Multiclass Queue in the Halfin-Whitt Heavy Traffic Regime," Operations Research, INFORMS, vol. 52(2), pages 243-257, April.
    • Handle: RePEc:inm:oropre:v:52:y:2004:i:2:p:243-257
    DOI: 10.1287/opre.1030.0084
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.1030.0084
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.1030.0084?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. Shlomo Halfin & Ward Whitt, 1981. "Heavy-Traffic Limits for Queues with Many Exponential Servers," Operations Research, INFORMS, vol. 29(3), pages 567-588, June.
    2. Ward Whitt, 1992. "Understanding the Efficiency of Multi-Server Service Systems," Management Science, INFORMS, vol. 38(5), pages 708-723, May.
    Full references (including those not matched with items on IDEAS)

    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. 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.
    2. 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.
    3. Francis de Véricourt & Otis B. Jennings, 2008. "Dimensioning Large-Scale Membership Services," Operations Research, INFORMS, vol. 56(1), pages 173-187, February.
    4. 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.
    5. 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.
    6. 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.
    7. 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.
    8. Ward Whitt, 2003. "How Multiserver Queues Scale with Growing Congestion-Dependent Demand," Operations Research, INFORMS, vol. 51(4), pages 531-542, August.
    9. 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.
    10. 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.
    11. R. Bekker & A. Bruin, 2010. "Time-dependent analysis for refused admissions in clinical wards," Annals of Operations Research, Springer, vol. 178(1), pages 45-65, July.
    12. René Bekker & Paulien Koeleman, 2011. "Scheduling admissions and reducing variability in bed demand," Health Care Management Science, Springer, vol. 14(3), pages 237-249, September.
    13. 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.
    14. Noa Zychlinski, 2023. "Applications of fluid models in service operations management," Queueing Systems: Theory and Applications, Springer, vol. 103(1), pages 161-185, February.
    15. Constantinos Maglaras & Assaf Zeevi, 2003. "Pricing and Capacity Sizing for Systems with Shared Resources: Approximate Solutions and Scaling Relations," Management Science, INFORMS, vol. 49(8), pages 1018-1038, August.
    16. Hassan Hmedi & Ari Arapostathis & Guodong Pang, 2022. "Uniform stability of some large-scale parallel server networks," Queueing Systems: Theory and Applications, Springer, vol. 102(3), pages 509-552, December.
    17. Ward Whitt, 2004. "A Diffusion Approximation for the G/GI/n/m Queue," Operations Research, INFORMS, vol. 52(6), pages 922-941, December.
    18. Izady, Navid & Worthington, Dave, 2012. "Setting staffing requirements for time dependent queueing networks: The case of accident and emergency departments," European Journal of Operational Research, Elsevier, vol. 219(3), pages 531-540.
    19. 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.
    20. Guodong Pang & Ward Whitt, 2009. "Service Interruptions in Large-Scale Service Systems," Management Science, INFORMS, vol. 55(9), pages 1499-1512, September.

    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:52:y:2004:i:2:p:243-257. 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.