Ph.D Thesis

Ph.D StudentShaikhet Gennady
SubjectControl of Many Server Queueing Systems in Heavy Traffic
DepartmentDepartment of Industrial Engineering and Management
Supervisors PROF. Rami Atar
Full Thesis textFull thesis text - English Version


 This thesis is about control of queueing systems with several many-server stations and several customer classes, in which a system administrator dynamically controls scheduling and routing. The queueing model is considered in the Halfin - Whitt heavy traffic parametric regime, where both the arrival rates and the number of servers in the system increase to infinity, while keeping a critically balanced system. Both the model and the parametric regime have recently received much attention, especially in relation to large telephone call centers.

When studying queueing models in heavy traffic, one considers a sequence of models parameterized by n that, under a Law of Large Numbers limit, give rise to a fluid model, which is critically loaded. Typically, an attempt is then made to prove that appropriately scaled fluctuations of the queueing model about the fluid model converge to diffusion. If a control problem is associated to the queueing model, then a similar approach gives rise to a controlled diffusion model (CDM). As it often occurs, solving the diffusion model for optimal controls helps understand how to construct control schemes for the queueing model that are asymptotically optimal. We take a similar approach and discover that the stochastic differential equation describing the CDM has a singular control term, which may be used to constrain the diffusion to lie in certain subsets of the state space. This has lead us to unusual “heavy traffic” result, that we call null controllability, namely that one can construct control policies under which, for any given finite time interval, all queues in the system are kept empty, with probability approaching one. In particular, a critically loaded system operates with empty queues, as if it is underloaded.

Another part of the thesis deals with limiting diffusion models of queueing systems and their formulation as the controlled diffusions. By imposing conditions on the service rates, significant simplifications of the controlled diffusion model arise, and, in particular, the model process lives in one dimension. We then indicate particular cases when an exact solution is available, and describe how to construct control schemes for the original queueing model that are conjectured to be asymptotically optimal.