Dynamic Scheduling of a Multiclass Queue in the Halfin-Whitt Heavy Traffic Regime
- 1 April 2004
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 52 (2), 243-257
- https://doi.org/10.1287/opre.1030.0084
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.Keywords
This publication has 15 references indexed in Scilit:
- A Numerical Method for Solving Singular Stochastic Control ProblemsOperations Research, 2004
- Designing a Call Center with Impatient CustomersManufacturing & Service Operations Management, 2002
- Diffusion approximations for a single node accessed by congestion-controlled sourcesIEEE Transactions on Automatic Control, 2000
- The multiclass GI/PH/N queue in the Halfin-Whitt regimeAdvances in Applied Probability, 2000
- HEAVY TRAFFIC APPROXIMATIONS FOR A SYSTEM OF INFINITE SERVERS WITH LOAD BALANCINGProbability in the Engineering and Informational Sciences, 1999
- Heavy traffic analysis of a system with parallel servers: asymptotic optimality of discrete-review policiesThe Annals of Applied Probability, 1998
- Dynamic control of Brownian networks: state space collapse and equivalent workload formulationsThe Annals of Applied Probability, 1997
- Dynamic Scheduling with Convex Delay Costs: The Generalized $c|mu$ RuleThe Annals of Applied Probability, 1995
- Dynamic routing in open queueing networks: Brownian models, cut constraints and resource poolingQueueing Systems, 1993
- Optimal Discounted Stochastic Control for Diffusion ProcessesSIAM Journal on Control, 1967