Working
Papers
Asymptotic
Optimality of Maximum Pressure Policies in Stochastic Processing
Networks
Download
Paper (PDF 550 K / 53 pages)
J.G. Dai,
Wuqin Lin
Abstract
We consider a class
of stochastic processing networks. Assume that the networks
satisfy a complete resource pooling condition. We prove that
each maximum pressure policy asymptotically minimizes the
workload process in a stochastic processing network in heavy
traffic. When the objective is to minimize a linear holding
cost, for any epsilon > 0, we identify a set of maximum
pressure policies and prove that they are asymptotically epsilonoptimal.
A key to the optimality proof is to prove a state space collapse
result and a heavy traffic limit theorem for the network processes
under a maximum pressure policy. We extend a framework of
Bramson (1998) and Williams (1998) from the multiclass queueing
network setting to the stochastic processing network setting
to prove the state space collapse result and the heavy traffic
limit theorem. The extension can be adapted to other studies
of stochastic processing networks.
Back
to working paper series page
