Center for Operations and Supply Chain ManagementKellogg School of Management
Center InformationMEDS DepartmentContactKellogg Homepage
News & Events
Information for Students
Working Papers
Job Opportunities
Online Resources
Operations Club
Master of Management & Manufacturing (MMM) Program
Internal Site
Northwestern University

Working Papers

Asymptotic Optimality of Maximum Pressure Policies in Stochastic Processing Networks
Download Paper (PDF 550 K / 53 pages)

J.G. Dai, Wuqin Lin


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 epsilon-optimal. 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

©2001 Kellogg School of Management, Northwestern University