Asymptotically Optimal Controls for Multiclass Queuing Networks in Heavy Traffic

• Activity Number: 90
• Type: Contributed
• Date/Time: Monday, August 4, 2003 : 8:30 AM to 10:20 AM
• Sponsor: IMS
• Author(s): Arka Prasanna Ghosh*+
• Companies: University of North Carolina, Chapel Hill
• Keywords: multiclass queuing networks ; "crisscross network" ; singular controls ; Brownian control problems (BCP) ; heavy traffic analysis ; large deviations

Abstract

Stochastic networks arise in manufacturing, communication and computer systems. Seminal work by Harrison (1989,1997) introduces a framework to obtain optimal control of such networks by studying the solution to the limiting BCP. These policies perform quite well in simulations, but there are few theoretical results proving asymptotic optimality of such policies. Some recent work by Harrison (1998) and Bell & Williams (2001) uses large deviation ideas for addressing asymptotic optimality questions. In this work, we study a heavily loaded multiclass controlled queuing network commonly known as the "crisscross network." It has been studied by Harrison et al. (1989), Chen et al. (1994), and in great detail by Martins, Shreve & Soner (1996). The last paper proposes a control policy and proves its asymptotic "near optimality" using techniques from viscosity solution analysis of HJB equations. In our work, using techniques similar to Bell & Williams (2001), we propose a simple threshold-type scheduling policy for this model. The proposed policy is easy to interpret and implement in real situations. Using large deviation techniques, we prove the asymptotic optimality of the policy.