New linear program performance bounds for closed queueing networks

We develop new linear program performance bounds for closed reentrant queueing networks based on an inequality relaxation of the average cost equation. The approach exploits the fact that the transition probabilities under certain policies of closed queueing networks are invariant within certain regions of the state space. This invariance suggests the use of a piecewise quadratic function as a surrogate for the differential cost function. The linear programming throughput bounds obtained are provably fighter than previously known bounds at the cost of increased computational complexity. Functional throughput bounds parameterized by the fixed customer population N are obtained, along with a bound on the limiting throughput as N →+∞. We show that one may obtain reduced complexity bounds while still retaining superiority.