Ph.D Thesis | |

Ph.D Student | Shaikhet Gennady |
---|---|

Subject | Control of Many Server Queueing Systems in Heavy Traffic |

Department | Department of Industrial Engineering and Management |

Supervisors | PROF. Rami Atar |

PROFESSOR EMERITUS Avishai Mandelbaum | |

Full Thesis text |

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.