New linear program performance bounds for queueing networks

J. R. Morrison, P. R. Kumar

Research output: Contribution to journalArticlepeer-review

38 Scopus citations


We obtain new linear programs for bounding the performance and proving the stability of queueing networks. They exploit the key facts that the transition probabilities of queueing networks are shift invariant on the relative interiors of faces and the cost functions of interest are linear in the state. A systematic procedure for choosing different quadratic functions on the relative interiors of faces to serve as surrogates of the differential costs in an inequality relaxation of the average cost function leads to linear program bounds. These bounds are probably better than earlier known bounds. It is also shown how to incorporate additional features, such as the presence of virtual multi-server stations to further improve the bounds. The approach also extends to provide functional bounds valid for all arrival rates.

Original languageEnglish
Pages (from-to)575-597
Number of pages23
JournalJournal of Optimization Theory and Applications
Issue number3
StatePublished - Mar 1999


  • Performance evaluation
  • Queueing networks
  • Scheduling
  • Stability


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

Cite this