Maximum Pressure Policies in Stochastic Processing Networks
August 29, 2009, Stanford University

• Abstract

  Stochastic processing networks have been introduced in a series of three papers by Harrison (2000, 2002, 2003). These networks are much more general than multi-class queueing networks. The added generality allows one to model skill-based routing in call centers, operator-machine interactions in semiconductor wafer fabrication facilities, and combined input- and output-queued data switches.

  We introduce a family of maximum pressure policies that can be used to operate a stochastic processing network. Such a policy is shown to be throughput optimal for a wide class of networks. When the holding cost rate is a quadratic function of the buffer contents, we show that a maximum pressure policy asymptotically minimizes the holding cost under a heavy traffic condition and a complete resource pooling condition. This talk is based on the joint work with Wuqin Lin at Northwestern University.

• Slides

• References
• J. M. Harrison (2000), Brownian models of open processing networks: canonical representation of workload. Annals of Applied Probability , 10, 75--103. Correction: 1313, 390--393 (2003).
• J. G. Dai and W. Lin, "Maximum pressure policies in stochastic processing networks," Operations Research, Vol 53, 197-218, 2005.
  [full paper (242 Kbytes)]
• J. G. Dai and W. Lin, "Asymptotic optimality of maximum pressure policies in stochastic processing networks," Annals of Applied Probability, Vol 18, 2239--2299, 2008.
  [full paper (567K bytes)]

• B. Ata and W. Lin (2008), Heavy traffic analysis of maximum pressure policies for stochastic processing networks with multiple bottlenecks. Queueing Systems, 59, 191--235.