Thesis (Ph.D.)--The University of North Carolina at Chapel Hill, 2005
Stochastic network models are common in manufacturing, telecommunications and computer systems. In this dissertation, I consider systems that are in "heavy traffic", i.e., on the average, processing resources are balanced with the system load. Jobs enter the system with different service requirements and servers with different service capabilities serve these jobs. The goal of the system manager is to dynamically sequence jobs at each server in a way that it minimizes some suitable cost function. The problem of determining optimal control policies for even simple network models is, in general, quite intractable. Thus one seeks approximations to the model that are more amenable to analysis. One such approximation scheme based on diffusion limit theory has been an active area of research in recent years. In this approach, one formally replaces the control problem for the queueing network by a singular control problem (with state constraints) for diffusion processes. The solution of the diffusion control problem is then suitably interpreted to obtain a control policy for the physical queueing network. Finally the choice of the control policy is validated either via simulation studies or by obtaining rigorous asymptotic optimality properties
One of the main challenges in the diffusion limit approach to control of networks is to identify natural network models for which the corresponding diffusion control problem is explicitly solvable and interpreting the solution to obtain provable asymptotically optimal policies. All such results in the literature, prior to our work, correspond to settings where the associated diffusion control problem is effectively 1-dimensional. With a view towards higher dimensional problems, the first part of my dissertation studies the "crisscross network", which corresponds to a 2-dimensional diffusion control problem, and has eluded a full analysis for almost a decade. Using the solution of the diffusion control problem, a simple threshold policy is proposed. It seems to outperform the classical priority rule in simulation studies. Using basic large deviation estimates and weak convergence techniques, the policy is shown to be asymptotically optimal. Even though the diffusion approximation approach for stochastic networks has led to some very useful heuristics for policy synthesis, there is no rigorous mathematical result that relates the control problem for the network with that of the approximating diffusion model, for a general class of queueing networks. As a first step towards such a result, in the later part of my dissertation, I consider a broad family of stochastic networks (multi-class queueing networks) in heavy traffic and establish that the minimum asymptotic cost for the network control problem is bounded below by the value function of the corresponding diffusion control problem. Such a result provides a useful bound on the best achievable performance for any control policy for a broad class of networks
