Abstract
Our object of study is a multiclass queueing network (MQNET) which consists of acollection of (connected) single‐server stations. Exogenous arrivals into the system formindependent Poisson streams, service times are exponential and we have Markovian routingof customers between stations. Recent results concerning linear programming (LP) basedapproaches enable us to establish a simple and intuitive stability condition. This is of interestin its own right, but also enables us to progress with a study of optimal scheduling andperformance analysis. Our methodology here is also based on LP. A primal‐dual approachexploits the fact that the system satisfies (approximate) conservation laws to yield perform-anceguarantees for a natural index‐based scheduling heuristic. We are also able to analysethe performance of an arbitrary priority policy.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
D. Bertsimas, The achievable region in the optimal control of queueing systems; formulations, bounds and policies, Queueing Systems 21(1995)337-389.
D. Bertsimas and J. Niño-Mora, Optimization of multiclass queueing networks with changeover times via the achievable region approach: Part I, the multi-station case. Working Paper, Operations Research Center, M.I.T., 1996.
D. Bertsimas and J. Niño-Mora, Conservation laws, extended polymatroids and multi-armed bandit problems; a polyhedral approach to indexable systems, Mathematics of Operations Research 21 (1996)257-306.
D. Bertsimas, I. Paschalidis and J. Tsitsiklis, Optimisation of multiclass queueing networks: Polyhedral and nonlinear characterizations of achievable performance, Annals of Applied Probability 4(1994) 43-75.
P.J. Burke, The output of a queueing system, Operations Research 4(1956)699-704.
J.A. Buzacott and J.G. Shanthikumar, Stochastic Models of Manufacturing Systems, Prentice-Hall, Englewood Cliffs, NJ, 1993.
J.G. Dai and G. Weiss, Stability and instability of fluid models for reentrant lines, Mathematics of Operations Research 21(1996)115-134.
P.D. Finch, On the distribution of queue size in queueing problems, Acta Mathematica Hungarica 10(1959)327-336.
E. Gelenbe and I. Mitrani, Analysis and Synthesis of Computer Systems, Academic Press, London, 1980.
K.D. Glazebrook and R. Garbe, Reflections on a new approach to Gittins indexation, Journal of the Operational Research Society 47(1996)1301-1309.
K.D. Glazebrook and R. Garbe, Almost optimal policies for systems which almost satisfy conservation laws, Annals of Operations Research 92(1999), this volume.
M.X. Goemans and D.P. Williamson, The primal-dual method for approximation algorithms and its application to network design problems, Approximation Algorithms (1996)144-191.
J.M. Harrison and L.M. Wein, Scheduling networks of queues: Heavy traffic analysis of a simple open network, Queueing Systems 5(1989)265-280.
G.P. Klimov, Time sharing service systems I, Theory of Probability and its Applications 19(1974) 532-551.
P.R. Kumar and S.P. Meyn, Duality and linear programs for stability and performance analysis of queueing networks and scheduling policies, IEEE Transactions on Automatic Control 41(1996)4-16.
S. Kumar and P.R. Kumar, Performance bounds for queueing networks and scheduling policies, IEEE Transactions on Automatic Control 39(1994)1600-1611.
C.H. Papadimitriou and J.N. Tsitsiklis, The complexity of optimal queueing network control, Working Paper, Laboratory for Intelligent Decision Systems, 1993.
Rights and permissions
About this article
Cite this article
Glazebrook, K., Niño‐Mora, J. A linear programming approach to stability, optimisationand performance analysis for Markovian multiclassqueueing networks. Annals of Operations Research 92, 1–18 (1999). https://doi.org/10.1023/A:1018922412074
Issue Date:
DOI: https://doi.org/10.1023/A:1018922412074