On the Throughput-WIP Trade-off in Queueing Systems, Diminishing Returns and the Threshold Property: A Linear Programming Approach

Abstract

We present a new unifying framework for investigating throughput-WIP (Work-in-Process) optimal control problems in queueing systems, based on reformulating them as linear programming (LP) problems with special structure: We show that if a throughput-WIP performance pair in a stochastic system satisfies the Threshold Property we introduce in this paper, then we can reformulate the problem of optimizing a linear objective of throughput-WIP performance as a (semi-infinite) LP problem over a polygon with special structure (a threshold polygon). The strong structural properties of such polygones explain the optimality of threshold policies for optimizing linear performance objectives: their vertices correspond to the performance pairs of threshold policies. We analyze in this framework the versatile input-output queueing intensity control model introduced by Chen and Yao (1990), obtaining a variety of new results, including (a) an exact reformulation of the control problem as an LP problem over a threshold polygon; (b) an analytical characterization of the Min WIP function (giving the minimum WIP level required to attain a target throughput level); (c) an LP Value Decomposition Theorem that relates the objective value under an arbitrary policy with that of a given threshold policy (thus revealing the LP interpretation of Chen and Yao's optimality conditions); (d) diminishing returns and invariance properties of throughput-WIP performance, which underlie threshold optimality; (e) a unified treatment of the time-discounted and time-average cases.