
06480015
b
2016c.00924
Bhat, U. Narayan
An introduction to queueing theory. Modeling and analysis in applications. 2nd edition.
Statistics for Industry and Technology. Boston, MA: Birkh\"auser (ISBN 9780817684204/hbk; 9780817684211/ebook). xiv, 339~p. (2015).
2015
Boston, MA: Birkh\"auser
EN
K95
queueing theory
Markov models
Poisson processes
renewal processes
operations research
simulation
statistical inference
decision problems
Zbl 0167.17102
doi:10.1007/9780817684211
This is a wellwritten textbook for upperlevel undergraduate or graduate students in computer science or engineering who study network performance, design or other technological disciplines that include queueing theory. The reader is supposed to have a background in calculus, probability, and statistics at the undergraduate level. All necessary concepts on the theory of Markov processes as well as techniques for modeling and analysis of queueing systems are given in examples. The book contains fourteen chapters and three appendices. \indent Chapter 1 is an introduction. It explains what queueing theory is and which problems it solves. It provides classifications of queueing systems and historical material, as well as a short introduction to the methods, models and applications of the theory and typical modeling exercises. \indent Chapter 2 considers the important probability distributions that are used in queueing theory such as exponential distributions, Poisson distributions and Erlang distributions, and explains the connection between an exponential distribution and a Poisson process and exponential and Erlang distributions. It also explains how different models can be identified statistically. \indent Chapter 3 introduces different types of stochastic processes. Specifically, it explains discrete and continuous time Markov processes and renewal processes. \indent Chapter 4 studies simple Markovian queueing systems. It starts from the general birthanddeath model, for which it derives the ChapmanKolmogorov equations and a stability condition. Then special queueing systems are studied. For the $\mathrm{M}/\mathrm{M}/1$ queueing system, the author derives the results for most important characteristics such as stationary queuelength and waiting time distribution and the relation between them (Little's formula). He also studies busy periods and the departure process. A similar study is then provided for the $\mathrm{M}/\mathrm{M}/s$ queues, the $\mathrm{M}/\mathrm{M}/s/K$ queues, with the particular cases of $\mathrm{M}/\mathrm{M}/1/K$ and $\mathrm{M}/\mathrm{M}/s/s$ queues, as well as the $\mathrm{M}/\mathrm{M}/\infty$ queues. Special attention is devoted to finite source queues and finite source loss systems. The included results on Markovian queues with balking and reneging make the considerations in this chapter especially notable and not standard. \indent Chapter 5 studies imbedded Markov chain models of queues. The first of the queueing systems studied here is the $\mathrm{M}/\mathrm{G}/1$ system. For this system, the stationary queuelength distribution is derived and analysed in detail. Specifically, providing the relation between different definitions of the queuelength distribution, the author explains what the PASTA property is. Then waiting time and busy period distributions are studied. For $\mathrm{M}/\mathrm{G}/1/K$ queueing systems, the queuelength process is studied. With the aid of the imbedded Markov chain method, the queueing systems $\mathrm{G}/\mathrm{M}/1$ and $\mathrm{G}/\mathrm{M}/1/K$ are studied. For a $\mathrm{G}/\mathrm{M}/1$ queue, the author derives the results for queuelength, waiting time, and busy cycle distributions. When the author discusses the stationary queuelength distribution for the $\mathrm{G}/\mathrm{M}/1$ queue, as in the case of the $\mathrm{M}/\mathrm{G}/1$ queue, he analyses different definitions of queue length distributions. The definition of the stationary distribution immediately before arrival of a customer with large order number leads to the geometrical distribution in the limit. However, the distribution of the stationary distribution in arbitrary time $t$, as $t$ increases to infinity, is different and is given by formula (5.3.16) in the book (page 113). However, the limiting distribution does not always exist. The additional assumption that the interarrival time has a nonlattice distribution is required, and the author misses this assumption. This assumption is missed in the original research [{\it U. N. Bhat}, A study of the queueing systems $\mathrm{M}/\mathrm{G}/1$ and $\mathrm{GI}/ \mathrm{M}/1$. BerlinHeidelbergYork: SpringerVerlag (1968; Zbl 0167.17102)] as well. \indent Chapter 6 studies extended Markov and renewal models. Here the author extends the classical models of queues of Chapter 5 and considers the models with bulk arrival or service. In addition, he studies $\mathrm{M}/\mathrm{E}_k/1$ and $\mathrm{E}_k/\mathrm{M}/1$ queues, where the symbol $E_k$ stands for ``Erlang distribution of order $k$''. The chapter also studies the $\mathrm{M}/\mathrm{M}/1$ queue with different priority disciplines. \indent Chapter 7 studies Markovian queueing networks. Open and closed networks are introduced. The author introduces a routing matrix. Towards open Jackson networks, the author first studies queues in series and queues with blocking, and then he arrives at open and closed Jackson networks providing a brief and concise explanation of the results and ideas. \indent In Chapter 8 (contributing author here is S. R. Chakravarthy), the matrixanalytic queueing models are studied. Phasetype distributions and Markov arrival processes (MAPs) are explained. Numerical examples are provided and an algorithm for simulating MAPs is suggested. The chapter is dedicated to the memory of Professor Marcel Neuts, who was a pioneering contributor in the area of matrixanalytic techniques. \indent Chapter 9 discusses general queueing systems $\mathrm{G}/\mathrm{G}/1$, for which explicit results and approximations are presented. The explicit results are bounds for the mean waiting time and Little's law. The bounds for the waiting time are established by using the known recurrent relation for the waiting times (Lindley's recursions). Little's law is presented without proof. Waiting times are approximated by diffusion and fluid approximations. These approximations are not given in mathematical depth. For instance, the invariance principle is not mentioned at all and Prokhorov's important pioneering result on the application of the invariance principle to diffusion approximation of the waiting time is not mentioned either. \indent Chapter 10 studies statistical inference for queueing models. It mainly uses likelihood estimation techniques. However, other wellknown methods (e.g., hypothesis testing) are presented as well. \indent Chapter 11 discusses decision problems in queueing theory associated with performance analysis and design in decision making. \indent The chapters 12 and 13 discuss applications of queueing theory. Chapter 12 was written in cooperation with A. J. Yu and discusses applications in manufacturing systems. Chapter 13, written in cooperation with K. M. Kavi, discusses applications in communication systems. \indent Chapter 14 discusses simulations of queueing systems (written in cooperation with K. M. Kavi). It discusses standard techniques of simulation (e.g., simulating exponentially distributed random variables and, on this basis, simulating Markovian queueing systems). Lists of programs written in MATLAB are demonstrated. \indent The appendices A, B and C contain information on Poisson processes and associated probability distributions, Markov processes and important mathematical results used in this book.
Vyacheslav Abramov (Melbourne)