TY - JOUR
T1 - On dynamic scheduling of stochastic networks in heavy traffic and some new results for the workload process
AU - Bramson, M.
AU - Williams, R. J.
PY - 2000/12
Y1 - 2000/12
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=0034440066&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0034440066&partnerID=8YFLogxK
U2 - 10.1109/CDC.2000.912816
DO - 10.1109/CDC.2000.912816
M3 - Article
AN - SCOPUS:0034440066
SN - 0191-2216
VL - 1
SP - 516
EP - 521
JO - Proceedings of the IEEE Conference on Decision and Control
JF - Proceedings of the IEEE Conference on Decision and Control
ER -