New linear program performance bounds for closed queueing networks

J. R. Morrison, P. R. Kumar

Research output: Contribution to journalArticlepeer-review

12 Scopus citations


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.

Original languageEnglish
Pages (from-to)291-317
Number of pages27
JournalDiscrete Event Dynamic Systems: Theory and Applications
Issue number4
StatePublished - Oct 2001


  • Asymptotic loss
  • Closed networks
  • Closed reentrant lines
  • Efficiency
  • Performance evaluation
  • Queueing networks
  • Scheduling
  • Throughput


Dive into the research topics of 'New linear program performance bounds for closed queueing networks'. Together they form a unique fingerprint.

Cite this