SEMINAR NOTICE

Statistical Laboratory
Iowa State University
 
DATE AND TIME: Monday, January 24, 2005, 4:10 p.m.
 
PLACE: 319 Snedecor
 
SPEAKER: Arka P. Ghosh, Department of Statistics and Operations Research, University of North Carolina, Chapel Hill, North Carolina
                                            
TITLE:  Optimal Controls for Stochastic Networks in Heavy Traffic
 

ABSTRACT

 
Stochastic networks are common in problems related to manufacturing, telecommunications and computer systems. The network models considered here have a system manager, who can exercise dynamic control in the form of sequencing of jobs. The goal of a system manager is to allocate service times of each server appropriately among different pending jobs so as to minimize some suitable cost function.  This cost could be given in terms of holding costs in the  buffer, server idleness, etc.  The conventional controlled queueing models that correspond to these situations are far too complex to be analyzed directly. Thus one seeks tractable approximations, one such being the so called “heavy traffic approximation”.  Roughly speaking, heavy traffic means that the server capabilities are approximately balanced by the system load.  Under such circumstances, using tools from diffusion limit theory, one can formally replace the network control problem by an analogous diffusion control problem (the so called Brownian control problem (BCP), Harrison [1988]).  This formulation leads to the following main steps in the policy synthesis for the network:
-  (a) Solve the BCP either explicitly, or by some numerical procedure.
-  (b) Interpret the solution of the BCP to guess a policy for the network.
-  (c) Validate the policy by establishing suitable (asymptotic) optimality results.
Although there are several results in the literature which carry out the first two steps outlined above for a variety of network control problems, there are very few works where step (c) is successfully carried out. Indeed, prior to the work to be presented in this talk, all the available results on part (c) above correspond to situations where the corresponding diffusion control problems can be reduced to a 1-dimensional stochastic control problem.
 
In the first part of the talk, we consider the simplest non-trivial example of a sequencing control problem where the effective diffusion control problem is 2 dimensional. By first obtaining an explicit solution of the BCP, a threshold type control policy for the network is proposed.  The proposed policy is seen to out-perform the myopic "c\mu" policy in simulation studies. Finally, it is shown that the policy is asymptotically optimal in a suitable sense.
 
The study of the above two dimensional problem critically relies on the availability of an explicit solution of the BCP. In general, explicit solutions are rarely available, and completing the program outlined above for a general class of network control problems is a challenging open issue. In the second part of the talk, as a first step towards this goal, I will discuss a quite general class of queueing networks and show that the value function of the network control problem is, asymptotically, bounded below by that of the associated diffusion control problem.
 
COFFEE: 10:40 a.m., 104 Snedecor Hall