On dynamic scheduling of stochastic networks in heavy traffic
and some new results for the workload process
M. Bramson and R. J. Williams
Abstract
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.