Steady state analysis of level dependent quasi-birth-and-death processes with catastrophes

• Published in: Computers & operations research 2012-02, Vol.39 (2), p.413-423
• Main Authors: Baumann, Hendrik, Sandmann, Werner
• Format: Article
• Language: English
• Subjects: Algorithms; Applied sciences; Blocking; Catastrophes; Catastrophic failure analysis; Dynamical systems; Dynamics; Exact sciences and technology; Generators; Level dependent quasi-birth-and-death process; Mathematical analysis; Mathematical models; Matrix analytic algorithm; Operational research and scientific management; Operational research. Management science; Queue in random environment; Queuing theory. Traffic theory; State dependent rates; Stationary distribution
• ISSN: 0305-0548; 1873-765X
• DOI: 10.1016/j.cor.2011.05.003

Quasi-birth-and-death processes, that is multi-dimensional Markov chains with block tridiagonal transition probability or generator matrices, are appropriate models for various types of queueing systems, amongst many other population dynamics. We consider continuous-time level dependent quasi-birth-and-death processes (LDQBDs) extended by catastrophes, which means that the transition rates are allowed to depend on the process level and additionally in each state the level component may drop to zero such that the generator matrix deviates from the block tridiagonal form in that the first block column is allowed to be completely occupied. A matrix analytic algorithm (MAA) for computing the stationary distribution of such processes is introduced that extends and generalizes similar algorithms for LDQBDs without catastrophes. The algorithm is applied in order to analyze M/M/c queues in random environment with catastrophes and state dependent rates. We present a detailed steady state analysis by computing the stationary distribution for different parameter sets, thereby focusing on the marginal probabilities of the level component which represents the number of customers. It turns out that the stationary marginal distribution is bimodal in the sense that it has two local modes that significantly depend on the specific parameters and rates. We also study the efficiency of our matrix analytic algorithm (MAA). Comparisons with standard solution algorithms for Markov chains demonstrate its superiority in terms of runtime and memory requirements.