Dynamic control of stochastic networks: A fluid model approach
Costis Maglaras, Electrical Engineering Department,
Stanford University, July 1998.
Abstract:
Today's communication, computer and manufacturing industries
offer many examples of technological systems in which ``units of work'' visit a
number of different ``servers'' in the course of their processing, and in which
the workflow is subject to stochastic variability. Our work focuses on dynamic
control for these ``stochastic processing networks.'' In general, stochastic
processing networks are difficult to analyze and control, and, with very few
exceptions, problems of realistic scale quickly become analytically and
computationally intractable. One promising approach in addressing these
problems that has emerged from research over the past 10-15 years, uses a
hierarchy of approximate models that provide tractable ``relaxations'' of the
original problem as the basis for analysis and synthesis of ``good'' control
policies. In particular, the analytical theory associated with fluid
approximations and with Brownian approximations has produced important insights
in understanding how the performance of a multiclass network depends on
different design and control parameters.
The work in this dissertation follows along the same
lines. Specifically, the approach taken here is based on approximating (or
replacing) the stochastic network by its fluid analog, this is a model with
deterministic and continuous dynamics, solving an associated fluid optimal
control problem, and then using the derived fluid control policy in order to
define an implementable policy in the original stochastic network. A major
obstacle in this policy design methodology is in translating the information
derived from analysis of the tractable approximate model into an implementable
policy in the stochastic system in a way that guarantees stability and optimal
or ``near-optimal'' performance. This problem has been recognized by many
researchers in relation to both fluid and Brownian (diffusion) approximations
in the past. The main contribution of this thesis will be in proposing and
analyzing a family of discrete-review policies that addresses and solves this
problem. Each policy in this family translates the solution of an associated
fluid optimal control problem in an implementable policy for the stochastic
network, in a way that guarantees stability and achieves asymptotically optimal
performance under fluid scaling.
Thereafter, several extensions to this framework are
presented. First, the family of fluid control policies is greatly generalized
to allow arbitrary trajectory tracking policies as well as a general family of
greedy control laws motivated by the solution of the fluid optimal control
problems studied above. Second, the class of networks under consideration is
extended in order to allow routing and input (or admission) control capability,
as well as other features often excluded from mainstream queueing theory, such
as multi-server or batch-processing stations, and setup (or switchover) times.
Download: thesis.ps.zip
(424KB) or thesis.pdf (924KB)