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 multi-server stations to further improve the bounds. The approach also extends to provide functional bounds valid for all arrival rates.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Kumar, S., and Kumar, P. R., Performance Bounds for Queueing Networks and Scheduling Policies, IEEE Transactions on Automatic Control, Vol. 39, pp. 1600–1611, 1994.
Bertsimas, D., Paschalidis, I. C., and Tsitsiklis, J. N., Optimization of Multiclass Queueing Networks: Polyhedral and Nonlinear Characterizations of Achievable Performance, Annals of Applied Probability, Vol. 4, pp. 43–75, 1994.
Kumar, P. R., and Meyn, S. P., Stability of Queueing Networks and Scheduling Policies, IEEE Transactions on Automatic Control, Vol. 40, pp. 251–260, 1995.
Kumar, P. R., and Meyn, S. P., Duality and Linear Programs for Stability and Performance Analysis of Queueing Networks and Scheduling Policies, IEEE Transactions on Automatic Control, Vol. 41, pp. 4–17, 1996.
Jin, H., Ou, J., and Kumar, P. R., The Throughput of Irreducible Closed Markovian Queueing Networks: Functional Bounds, Asymptotic Loss, Efficiency, and the Harrison-Wein Conjectures, Mathematics of Operations Research, Vol. 22, pp. 886–920, 1997.
Humes, C., Jr., Ou, J., and Kumar, P. R., The Delay of Open Markovian Queueing Networks: Uniform Functional Bounds, Heavy Traffic Pole Multiplicities, and Stability, Mathematics of Operations Research, Vol. 22, pp. 921–954, 1997.
Kumar, P. R., and Varaiya, P. P., Stochastic Systems: Estimation, Identification, and Adaptive Control, Prentice-Hall, Englewood Cliffs, New Jersey, 1986.
Hasenbein, J. J., Necessary Conditions for Global Stability of Multiclass Queueing Networks. Report J-96-01, Industrial and Systems Engineering, Georgia Institute of Technology, 1996.
Dai, J., and Vate, J. H. V., Virtual Stations and the Capacity of Two-Station Queueing Networks, Preprint, School of Industrial and Systems Engineering, Georgia Institute of Technology, 1996.
Dai, J., and Vate, J. H. V., Global Stability of Two-Station Queueing Networks, Preprint, School of Industrial and Systems Engineering, Georgia Institute of Technology, 1996.
Cottle, R. W., Habetler, G. J., and Lemke, C. E., On Classes of Copositive Matrices, Linear Algebra and Its Applications, Vol. 3, pp. 295–310, 1970.
Andersson, L., Chang, G., and Elfving, T., Criteria for Copositive Matrices and Nonnegative Bezier Patches, Technical Report LiTH-MAT-R-93-27, Linkoping University, 1993.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Morrison, J.R., Kumar, P.R. New Linear Program Performance Bounds for Queueing Networks. Journal of Optimization Theory and Applications 100, 575–597 (1999). https://doi.org/10.1023/A:1022638523391
Issue Date:
DOI: https://doi.org/10.1023/A:1022638523391