New linear program performance bounds for queueing networks

New linear program performance bounds for queueing networks

0.00 Avg rating0 Votes
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: ,
Keywords: queueing networks
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.