Dynamic scheduling of a multiclass queue in the Halfin-Whitt heavy traffic regime
Coauthor(s): J. Richard Harrison.
Adobe Acrobat PDF
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.
Source: Operations Research
Harrison, J. Michael, and Assaf Zeevi. "Dynamic scheduling of a multiclass queue in the Halfin-Whitt heavy traffic regime." Operations Research 52, no. 2 (2004): 243-257.