This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Harrison, J. M. Articles by Zeevi, A. Search for Related Content

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

Graduate School of Business, Stanford University, Stanford, California
Graduate School of Business, Columbia University, New York, New York 10027
harrison_michael{at}gsb.stanford.edu
assaf{at}gsb.columbia.edu

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.

Subject classifications: scheduling; queueing; diffusion approximations; many server limits; Halfin-Whitt regime; stochastic control; numerical methods.
History: Received January 2002; revision received July 2002; accepted March 2003.

This article has been cited by other articles:

				K. D. Glazebrook, C. Kirkbride, and J. Ouenniche Index Policies for the Admission Control and Routing of Impatient Customers to Heterogeneous Service Stations Operations Research, July 1, 2009; 57(4): 975 - 989. [Abstract] [PDF]

				O. Baron and J. Milner Staffing to Maximize Profit for Call Centers with Alternate Service-Level Agreements Operations Research, May 1, 2009; 57(3): 685 - 700. [Abstract] [PDF]

				A. Bassamboo and A. Zeevi On a Data-Driven Method for Staffing Large Call Centers Operations Research, May 1, 2009; 57(3): 714 - 726. [Abstract] [PDF]

				I. Gurvich and W. Whitt Scheduling Flexible Servers with Convex Delay Costs in Many-Server Service Systems MSOM, April 1, 2009; 11(2): 237 - 253. [Abstract] [PDF]

				A. Mandelbaum and P. Momcilovic Queues with Many Servers: The Virtual Waiting-Time Process in the QED Regime Mathematics of Operations Research, August 1, 2008; 33(3): 561 - 586. [Abstract] [PDF]

				I. Gurvich, M. Armony, and A. Mandelbaum Service-Level Differentiation in Call Centers with Fully Flexible Servers Management Science, February 1, 2008; 54(2): 279 - 294. [Abstract] [PDF]

				F. de Vericourt and O. B. Jennings Dimensioning Large-Scale Membership Services Operations Research, January 1, 2008; 56(1): 173 - 187. [Abstract] [PDF]

				N. Gans and Y.-P. Zhou Call-Routing Schemes for Call-Center Outsourcing MSOM, January 1, 2007; 9(1): 33 - 50. [Abstract] [PDF]

				A. Bassamboo, J. M. Harrison, and A. Zeevi Design and Control of a Large Call Center: Asymptotic Analysis of an LP-Based Method Operations Research, May 1, 2006; 54(3): 419 - 435. [Abstract] [PDF]

				C. Maglaras and A. Zeevi Pricing and Design of Differentiated Services: Approximate Analysis and Structural Insights Operations Research, March 1, 2005; 53(2): 242 - 262. [Abstract] [PDF]

				J. M. Harrison and A. Zeevi A Method for Staffing Large Call Centers Based on Stochastic Fluid Models MSOM, January 1, 2005; 7(1): 20 - 36. [Abstract] [PDF]

				C. Maglaras and A. Zeevi Diffusion Approximations for a Multiclass Markovian Service System with "Guaranteed" and "Best-Effort" Service Levels Mathematics of Operations Research, November 1, 2004; 29(4): 786 - 813. [Abstract] [PDF]