Analysis of Queues

"The breadth and scope of topics in this book surpass the books currently on the market. For most graduate engineering or business courses on this topic the selection is perfect. … presented in sufficient depth for any graduate class. I like in particular the "problems" presented at regular intervals, along with detailed solutions. … excellent coverage of both classical and modern techniques in queueing theory. Compelling applications and case studies are sprinkled throughout the text. For many of us who teach graduate courses in queueing theory, this is the text we have been waiting for!"
—John J. Hasenbein, The University of Texas at Austin

"Dr. Gautam has an obvious passion for queueing theory. His delight in presenting queueing paradoxes beams through the pages of the book. His relaxed conversational style makes reading the book a pleasure. His introductory comments about having to account for a large variety of educational backgrounds among students taking graduate courses indicate that he takes education very seriously. It shows throughout the book. He has made an excellent choice of topics and presented them in his own special style. I highly recommend this queueing text by an expert who clearly loves his field."
—Dr. Myron Hlynka, University of Windsor, Ontario, Canada

"… will be a good addition to my collection of books on queueing theory."
—Attahiru S. Alfa, University of Manitoba, Canada

"Queueing systems are widely used to provide stochastic modelling of many problems arising in computer, communication and transportation networks, manufacturing, and waiting lines in daily life. This book presents a survey of results and methods of queueing theory, and a basic exposition of the most commonly used stochastic processes such as discrete-time Markov chains (DTMCs), continuous-time Markov chains (CTMCs), semi-Markov and Markov regenerative processes, Brownian motion and Itˆo calculus; still, some topics, e.g. simulation and parameter fitting in queueing models, are barely mentioned. The book was conceived by its author as a book written for students, and thus an important feature of the presentation is the systematic use of solved examples.

The book is divided into ten chapters and two appendices, which could be used by instructors in two courses: a basic course, covering the appendices and Chapters 1 through 4; and an advanced course, covering Chapters 5 through 10. Each chapter is concluded by bibliographical comments and a list of exercises. The prerequisite for the book is an undergraduate course on probability. Almost all material in Chapters 1 through 6 can be found in many excellent texts, such as Queueing methods. For services and manufacturing by R. W. Hall [Prentice Hall, Englewood Cliffs, NJ, 1991], Modelling and analysis of stochastic systems by V. G. Kulkarni [Texts Statist. Sci. Ser., Chapman and Hall, London, 1995; MR1357414] and Fundamentals of queueing theory by D. Gross et al. [fourth edition, Wiley Ser. Probab. Stat., Wiley, Hoboken, NJ, 2008; MR2446330], among others. Chapters 7 through 10 are closely related to some selected papers and a few texts, including the excellent monographs Large deviations for performance analysis by A. Shwartz and A. Weiss [Stochastic Model. Ser., Chapman & Hall, London, 1995; MR1335456], Fundamentals of queueing networks by H. Chen and D. D. W. Yao [Appl. Math. (N. Y.), 46, Springer, New York, 2001; MR1835969] and Stochastic-process limits by W. Whitt [Springer Ser. Oper. Res., Springer, New York, 2002; MR1876437].

To start with, Chapter 1 presents introductory remarks about the analysis of queues, by addressing three questions: Where has analysis of queues been successfully used?What do we need as inputs to do the analysis and what can we expect as outputs?How do we plan to go about analysing queues? Chapter 1 also presents key results and fundamental queueing notations. In Chapter 2, the interest is in the use of CTMCs in the analysis of classical queueing models, and how to solve balance equations by using generating functions and reversibility principles. Unlike Chapter 2 where the focus is on exact/closed algebraic expressions, Chapter 3 explains some numerical techniques, mostly based on matrix analysis, followed by some approximations. In this setting, a fundamental structure is the quasi-birth-death (QBD) Markov chain, the matrix geometric solution of a QBD process and the computational treatment of finite-state Markov chains. Chapter 4 focusses on how to analyse queues where inter-arrival and/or service times are generally distributed. To that end, the author first describes the fundamentals involved in DTMCs and uses them in two classical systems, the M/G/1 and GI/M/1 queues, via embedded Markov chains. The mean value analysis (MVA) approach is then used to obtain approximations when the queueing system cannot easily be modelled as a suitably defined stochastic process. MVA is combined with other techniques to derive bounds and approximations for average performance measures in G/G/s queues, and exact results for various different models (M/G/∞, processor sharing service discipline, M/G/s/s) are derived by using more specific methods. For multiclass systems, Chapter 5 addresses how to evaluate performance measures of various service disciplines (for example, exhaustive polling, gated policy, limited service in polling systems; and shortest processing time, preemptive shortest job first and shortest remaining processing time schemes in the M/G/1 queue), and how to decide the order of service in terms of optimal policies. Chapter 6 explains how to deal with networks of queues by using product-form solutions for the joint distribution for the number of customers in each node, under a variety of distributional assumptions such as Jackson networks, Jackson-like networks with deterministic routing, multiclass networks and loss networks. Material in Chapters 7 through 10 can be seen as advanced and results are mainly derived from the use of more complex stochastic processes than Markov chains. In that spirit, Chapter 7 presents approximations based on reflected Brownian motions, which make it possible to model using the mean and variance of the inter-arrival time as well as service time at each queue of a general queueing network, hence making these techniques easy to implement. The notion of fluid queue is analysed in Chapters 8 through 10, but there is very little commonality between what are called fluid queues in Chapter 8 and what are called fluid queues in Chapters 9 and 10. More particularly, Chapter 8 considers deterministic fluid queues where the flow rates are mostly constant or vary deterministically over time, whereas the emphasis in Chapters 9 and 10 is on stochastic fluid queues where flow rates, from a countable set, are piecewise constant and vary stochastically over time. Two appendices act as a refresher on the topic of random variables and stochastic processes, as well as a point of clarification for notation.

Analysis of queues is written to teach students and professionals how to use basic concepts of queueing theory to solve queuing problems from the stochastic perspective, but without going into detail on the underlying stochastic processes. The book is written in simple language, the techniques are comprehensible for the reader and all important questions are illustrated with examples or a few case studies, such as staffing and work-assignment in call centres (Chapter 4), hospital emergency ward planning (Chapter 5), automobile service station (Chapter 6), and network interface card in cluster computing (Chapter 7). Understanding the contents of this book does not require a background in advanced concepts of probability, and the exercises at the end of each chapter can help the reader master queueing techniques."

{For the 2012 original see [N. Gautam, Analysis of queues: methods and applications, CRC Press, Boca Raton, FL, 2012].}

- Antonio G´omez-Corral - Mathematical Reviews Clippings - November 2018