טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentGiat Chanit
SubjectErgodic Control and Heavy Traffic Limits
DepartmentDepartment of Electrical Engineering
Supervisor Professor Rami Atar


Abstract

We consider a problem of scheduling and routing control for a multi-class queueing system with many servers (gathered in several service stations) and impatient customers. We study a long time average (ergodic) cost associated with queue length or delay. In our model the abandonments take important role in sustaining stability (in the sense of bounded expectation over time), which is a necessary condition for the ergodic cost convergence. We consider two aspects of the problem: proving that the ergodic cost is the unique solution of a Bellman equation, and showing that, in heavy traffic asymptotics, the solution to the control problem can be obtained as the solution of a control problem of an appropriate diffusion model.

The first main result regards the ergodic Bellman equation. It shows the existence and uniqueness of solutions, and characterization of the control problem’s value as its solution. The tools we use include deriving estimates for the recurrence time by constructing a Lyapunov function; establishing a Bellman equation for a discounted cost; and using the vanishing discount approach, proving that the Bellman equation obtained as the discount factor tends to zero, is solved by the pair: the ergodic cost of the original problem (a scalar), and the cost of a related control problem (a function). The combination of continuous time and unbounded cost and space, makes this result new.

An important consequence of the above results is that the optimal control is of feedback form. Thus, in the second part of the thesis we consider only controls of this form. The main result regarding diffusion limits in heavy traffic is the convergence of the ergodic value of the queuing system (with appropriate centering and rescaling) to the ergodic cost of a diffusion control problem. This is done along the following lines. We prove the existence of a unique invariant measure for every fixed feedback control, for both rescaled queuing systems and diffusion. We show that averaging over time is equivalent to integrating against the invariant measure, and prove the convergence of the invariant measures for a fixed control as the heavy traffic parameter tends to infinity. This appears to be the first rigorous treatment of a diffusion scale limit result for ergodic costs in a control theoretic setup.