Paper #276

Títol:

On the throughput-WIP trade-off in queueing systems, diminishing returns and the threshold property: A linear programming approach

Autor:

José Niño-Mora

Data:

Març 1998

Resum:

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.

Paraules clau:

Throughput-WIP (Work-in-Process) optimal queueing control, threshold optimality, achievable performance region

Codis JEL:

C61, C63, M11

Àrea de Recerca:

Gestió de la Producció i de les Operacions

Descarregar el paper en format PDF