On dynamic scheduling of stochastic networks in heavy traffic and some new results for the workload process

M. Bramson and R. J. Williams

Dynamic scheduling of stochastic networks has applications to the control of modern telecommunications, manufacturing and computer systems. Most models of such networks cannot be analyzed exactly, and one is naturally led to consider more viable approximations. As one approach, J. M. Harrison proposed Brownian control problems (BCPs) as formal heavy traffic approximations to dynamic scheduling problems for stochastic networks. Subsequently, various authors combined analysis of BCPs with interpretation of their optimal solutions to suggest original and attractive policies for certain specific stochastic network control problems. Despite these successes for specific problems, there is, as yet, no general rigorous approach to analyzing BCPs, inferring good policies from their solutions, and proving asymptotic optimality of such policies. We are interested in developing such an approach. This paper is a step in that direction. In particular, we (a) provide a detailed stochastic network model, (b) give a fluid model interpretation of the notion of heavy traffic, (c) derive a formula for the dimension of the workload process in terms of basic model parameters, and (d) identify a mild condition under which the components of the workload process are all non-negative.
The paper appears in the Proceedings of the 39th IEEE Conference on Decision and Control, December 2000.
For a copy of a preprint for personal, scientific, non commercial use, click here for postscript.