Article ID: | iaor2000482 |
Country: | United States |
Volume: | 100 |
Issue: | 3 |
Start Page Number: | 575 |
End Page Number: | 597 |
Publication Date: | Mar 1999 |
Journal: | Journal of Optimization Theory and Applications |
Authors: | Kumar P.R., Morrison J.R. |
Keywords: | queueing networks |
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 multiserver stations to further improve the bounds. The approach also extends to provide functional bounds valid for all arrival rates.