Optimal Controls for Stochastic Networks in Heavy Traffic
by
Arka Ghosh
Iowa State University
Coauthors: Amarjit Budhiraja (Univ. of North Carolina, Chapel Hill)

Stochastic networks are common in problems related to manufacturing, telecom- munications 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" 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 avail- ability 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.

Date received: October 27, 2005