Summary
An algorithmic method for computing the probability vector of finite irreducible Markov chains is developed. The block elimination scheme used is especially well suited for highly structured and/or sparse transition matrices. Special variants for block Hessenberg and tridiagonal matrices often occurring in queueing theory are derived. The algorithm is then applied to the embedded Markov chain describing the queue length in a discrete-time queue with state-dependent arrival rates.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
P. J. COURTOIS, Analysis of Large Markovian Models by Parts; Applications to Queueing Network Models in: H. Beilner (ed.), Messung, Modellierung und Bewertung von Rechensystemen, 1–10 Springer, New York-Heidelberg-Berlin 1985
G.H. GOLUB, C.F. VAN LOAN, Matrix Computations Johns Hopkins University Press, Baltimore 1983
W.K. GRASSMANN, M.I. TAKSAR, D.P. HEYMAN, Regenerative Analysis and Steady State Distributions for Markov Chains Oper. Res. 33 (1985), 1107–1116
J.J. HUNTER, Mathematical Techniques of Applied Probability Vol. 2 Discrete Time Models: Techniques and Applications Academic Press, New York-London 1983
H. KOBAYASHI, Discrete-Time Queueing Systems in: G. Louchard, G. Latouche (eds.), Probability Theory and Computer Science, 53–84 Academic Press, New York-London 1983
M.F. NEUTS, Matrix-Geometric Solutions in Stochastic Models Johns Hopkins University Press, Baltimore 1981
S.N. RAJU, U.N. BHAT, Recursive Relations in the Computation of the Equilibrium Results of Finite Queues TIMS Studies in Man. Sci. 7 (1977), 247–270
T.J. SHESKIN, A Markov Chain Partitioning Algorithm for Computing Steady State Probabilities Oper. Res. 33 (1985), 228–235
R. SCHASSBERGER, An Aggregation Principle for Computing Invariant Probability Vectors in Semi-Marlcovian Models in: G. Iazeolla (ed.), Mathematical Computer Performance and Reliability, 259–272 North-Holland, Amsterdam-New York-Oxford 1984
E. SENETA, Non-Negative Matrices and Markov Chains Springer, New York-Heidelberg-Berlin 1981
D. WIKARSKI, An Algorithm for the Solution of Linear Equation Systems with Block Structure E.I.K. 16 (1980), 615–620
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1987 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kramer, M. (1987). Computational Methods for Markov Chains Occurring in Queueing Theory. In: Herzog, U., Paterok, M. (eds) Messung, Modellierung und Bewertung von Rechensystemen. Informatik-Fachberichte, vol 154. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-73016-0_11
Download citation
DOI: https://doi.org/10.1007/978-3-642-73016-0_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-18406-5
Online ISBN: 978-3-642-73016-0
eBook Packages: Springer Book Archive