Structured stochastic matrices of M/G/1 type and their applications. (English) Zbl 0695.60088

Neuts, Marcel F.

Probability: Pure and Applied, 5. New York etc.: Marcel Dekker, Inc. xiv, 510 p. $ 125.00 (US and Canada); $ 150.00 (All other countries) (1989).

Investigation of the simplest non-exponential queueing systems M/G/1/\(\infty\), G/M/1/\(\infty\), resp., is usually in the first step done by the technique of unbedded Markov chains, i.e., looking on the queue length process only at departure instants, arrival instants, resp.. Therefore, the queue length between two such random times can only decrease, increase, resp., by at most one (departure, arrival, resp.). The transition matrices are therefore of the form \[ \begin{matrix} \underline{M/G/1/\infty:} & \underline{G/M/1/\infty:} \\ \\ P_1 = \left[ \begin{matrix} a_0 & a_1 & a_2 & a_3 & a_4 & \ldots \\ a_0 & a_1 & a_2 & a_3 & a_4 & \ldots \\ 0 & a_0 & a_1 & a_2 & a_3 & \ldots \\ c & 0 & a_0 & a_1 & a_2 & \ldots \\ \vdots & \vdots & \vdots & \vdots & \vdots \end{matrix} \right] & P_2 = \left[ \begin{matrix} b_0 & a_0 & 0 & 0 & 0 & \ldots \\ b_1 & a_1 & a_0 & 0 & 0 & \ldots \\ b_2 & a_2 & a_1 & a_0 & 0 & \ldots \\ b_3 & a_3 & a_2 & a_1 & a_0 & \ldots \\ \vdots & \vdots & \vdots & \vdots & \vdots \end{matrix} \right] \end{matrix} \] These internal structures call obviously for specific - but different - techniques for analytical investigations. These techniques are well-known in queueing theory.
During the last one and a half decade it was realized that the principles developed for handling \(P_ 1\) or \(P_ 2\) are guidelines for how to investigate much more complicated systems. To be more specific: If a system’s evolution over time is described by a Markov chain with transition matrix of type \(\tilde P_ 1\), \(\tilde P_ 2\), resp., where \(\tilde P_ i\) is obtained from \(P_ i\) by substituting the real values \(a_ j\), \(b_ j\), \(j\geq 0\), by matrices \(A_ j\), \(B_ j\), \(i=1,2\), its steady-state distribution can be computed in a way resembling the techniques for M/G/1/\(\infty\), G/M/1/\(\infty\), resp.. Typical examples are the systems PH/GI/1/\(\infty\), GI/PH/1/\(\infty\), resp., where the exponential interarrival time distribution, services time distribution, resp., is substituted by so called “phase-type distributions” (which are easy to handle distributions, dense in the class of all distributions on \({\mathbb{R}}_+)\). The case of matrices of type \(\tilde P_ 2\) called of G/M/1-type, is the topic of the predecessor of the book under review [see the author, Matrix-geometric solutions in stochastic models. An algorithmic approach (1981; Zbl 0469.60002)].
Systems with a governing matrix of type \(\tilde P_ 1\), called of M/G/1- type are investigated in the present book. “This book is written from the same methodological viewpoint and with the same concern as its predecessor”. But “... the material in this book is not a recipe for the computational solution of a set of probability problems, but rather a unified method for the mathematical analysis of a class of stochastic models.” (p. vi, vii)
The contents:
Chapter 1: “The M/G/1 queue and some of its variants”. Presented in a way suitable for leading to the generalization sketched above. Chapter 2: “Markov Chains of the M/G/1 type”, and Chapter 3: “Positive recurrence”, contain the structure theory for general processes governed by M/G/1 type matrices.
Chapter 4: “Application to queues with Poisson arrivals”, Chapter 5: “Versatile arrival processes”, and Chapter 6: “Selected special models” cover a great variety of more or less general examples mostly from queueing theory.
A list of approximately twelf hundred references is included partially of material surrounding the topic of this book. The book is nearly self- contained, the theory of phase-type distribution can be found in more detail in the mentioned predecessor of it. As the previous book it will be a standard reference for researchers working on the class of “stochastic models of M/G/1 type”. It is well written and, parts of the material can be included into courses on applied stochastic processes.

Reviewer: H.Daduna

MSC:

60K25	Queueing theory (aspects of probability theory)
60-02	Research exposition (monographs, survey articles) pertaining to probability theory
60J27	Continuous-time Markov processes on discrete state spaces
90B22	Queues and service in operations research
15B51	Stochastic matrices

Keywords:

non-exponential queueing systems; phase-type distributions; Markov Chains; recurrence; Poisson arrivals

Citations:

Zbl 0469.60002