Matrix-Analytic Methods in Queueing Theory

Analytical methods for tractable (Markov) queueing models commonly assume Poisson arrivals and exponential service. The assumptions are unrealistic from a modeling point of view. In this thesis, we present a set of tools that can get beyond the two assumptions while preserving the underlying Markovian structure, called matrix-analytic methods. Our approach is three-pronged. First, we propose two building blocks within the methods, phase-type distributions (PHDs) and Markovian arrival processes (MAPs), which are natural generalizations of the exponential distribution and the Poisson process. They are flexible models that fit nicely into Markov processes. Second, we propose a special framework within the methods, quasi-birth-death process (QBD), which is a matrix-generalization of the birth-death process (BDP). Exploiting the structure in the matrix can reduce computational complexity and provide algorithmic tractability. Finally, we demonstrate the applicability of the methods by examining several applied queueing models. We show that the use of PHDs and MAPs in system representation and the QBD in their analysis significantly expand the scope of queueing systems for which usable results can be obtained. The MAP/PH/1 queue is emphasized with a numerical example presented