This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Dai, J. G. Articles by Lin, W. Search for Related Content

Maximum Pressure Policies in Stochastic Processing Networks

School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332-0205
School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332-0205
dai{at}isye.gatech.edu
linwq{at}isye.gatech.edu

Complex systems like semiconductor wafer fabrication facilities (fabs), networks of data switches, and large-scale call centers all demand efficient resource allocation. Deterministic models like linear programs (LP) have been used for capacity planning at both the design and expansion stages of such systems. LP-based planning is critical in setting a medium range or long-term goal for many systems, but it does not translate into a day-to-day operational policy that must deal with discreteness of jobs and the randomness of the processing environment.

A stochastic processing network, advanced by J. Michael Harrison (2000, 2002, 2003), is a system that takes inputs of materials of various kinds and uses various processing resources to produce outputs of materials of various kinds. Such a network provides a powerful abstraction of a wide range of real-world systems. It provides high-fidelity stochastic models in diverse economic sectors including manufacturing, service, and information technology.

We propose a family of maximum pressure service policies for dynamically allocating service capacities in a stochastic processing network. Under a mild assumption on network structure, we prove that a network operating under a maximum pressure policy achieves maximum throughput predicted by LPs. These policies are semilocal in the sense that each server makes its decision based on the buffer content in its serviceable buffers and their immediately downstream buffers. In particular, their implementation does not use arrival rate information, which is difficult to collect in many applications. We also identify a class of networks for which the nonpreemptive, non-processor-splitting version of a maximum pressure policy is still throughput optimal. Applications to queueing networks with alternate routes and networks of data switches are presented.

Subject classifications: production/scheduling: sequencing; stochastic; queues: networks.
History: Received May 2003; revision received January 2004; accepted March 2004.

This article has been cited by other articles:

				S. Andradottir, H. Ayhan, and D. G. Down Compensating for Failures with Flexible Servers Operations Research, July 1, 2007; 55(4): 753 - 768. [Abstract] [PDF]