zbMATH — the first resource for mathematics

Generalized Folding algorithm for transient analysis of finite QBD processes and its queueing applications. (English) Zbl 0862.60088
Stewart, William J. (ed.), Computations with Markov chains. Proceedings of the 2nd international workshop on the numerical solution of Markov chains, Raleigh, NC, USA, January 16–18, 1995. Boston, MA: Kluwer Academic Publishers. 463-481 (1995).
Summary: We propose and implement a generalized Folding-algorithm for the transient analysis of finite QBD processes. It is a numerical method for the direct computation of \({\mathbf x}{\mathbf P}={\mathbf a}\), where \({\mathbf P}\) is the QBD generator matrix in block tridiagonal form. Define the QBD state space in two dimensions with \(N\) phases and \(K\) levels, so that \({\mathbf P}\in{\mathcal R}^{NK\times NK}\) and \({\mathbf x},{\mathbf a}\in{\mathcal R}^{J\times NK}\), \(\forall J\). The time complexity of the algorithm for solving \({\mathbf x}{\mathbf P}={\mathbf a}\) is the greater of \(O(N^3\log_2K)\) and \(O(N^2KJ)\). The algorithm is found to be highly stable with superior error performance. In numerical studies we analyze the transient performance of MMPP/M/1 queueing system with finite buffer capacity. The MMPP arrival process is constructed to reflect the diversity of the second-order input statistics. We examine the effect of the second-order input statistics on transient queueing performance.
For the entire collection see [Zbl 0940.00042].

60K25 Queueing theory (aspects of probability theory)
90B22 Queues and service in operations research