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 ...
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.
+