New linear program performance bounds for closed queueing networks

We develop new linear program performance bounds for closed reentrant queue ing networks based on an inequality relaxation of the average cost equation . The approach exploits the fact that the transition probabilities under ce rtain policies of closed queueing networks are invariant within certain reg ions of the state space. This invariance suggests the use of a piecewise qu adratic function as a surrogate for the differential cost function. The lin ear programming throughput bounds obtained are provably tighter than previo usly known bounds at the cost of increased computational complexity. Functi onal throughput bounds parameterized by the fixed customer population N are obtained, along with a bound on the limiting throughput as N --> +infinity . We show that one may obtain reduced complexity bounds while still retaini ng superiority.