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

J. Michael Harrison () and Assaf Zeevi ()
Additional contact information
J. Michael Harrison: Graduate School of Business, Stanford University, Stanford, California
Assaf Zeevi: Graduate School of Business, Columbia University, New York, New York 10027

Operations Research, 2004, vol. 52, issue 2, 243-257

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: scheduling; queueing; diffusion approximations; many server limits; Halfin-Whitt regime; stochastic control; numerical methods (search for similar items in EconPapers)
Date: 2004
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (37)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1030.0084 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:52:y:2004:i:2:p:243-257

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().