Date: Wednesday, January 12
Time: Noon-1:00PM
Place: Howell 201

Abstract:

Stochastic networks are common in problems related to manufacturing, tele-communications 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 balanced by the system load. Under such circumstances, one can formally replace the network control problem by an analogous diffusion control problem (Brownian control problem or BCP). This 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) Evaluate the performance of the policy by (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 the 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 effective reduced 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. Using an explicit solution of the BCP, a threshold type control policy for the network is proposed. It out-performs 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.