1st Edition

Analysis of Queues Methods and Applications

By Natarajan Gautam Copyright 2012
    802 Pages 141 B/W Illustrations
    by CRC Press

    802 Pages 141 B/W Illustrations
    by CRC Press

    Written with students and professors in mind, Analysis of Queues: Methods and Applications combines coverage of classical queueing theory with recent advances in studying stochastic networks. Exploring a broad range of applications, the book contains plenty of solved problems, exercises, case studies, paradoxes, and numerical examples.

    In addition to the standard single-station and single class discrete queues, the book discusses models for multi-class queues and queueing networks as well as methods based on fluid scaling, stochastic fluid flows, continuous parameter Markov processes, and quasi-birth-and-death processes, to name a few. It describes a variety of applications including computer-communication networks, information systems, production operations, transportation, and service systems such as healthcare, call centers and restaurants.

    Introduction
    Analysis of Queues: Where, What, and How?
    Systems Analysis: Key Results
    Queueing Fundamentals and Notations
    Psychology in Queueing
    Reference Notes
    Exercises

    Exponential Interarrival and Service Times: Closed-Form Expressions
    Solving Balance Equations via Arc Cuts
    Solving Balance Equations Using Generating Functions
    Solving Balance Equations Using Reversibility
    Reference Notes
    Exercises

    Exponential Interarrival and Service Times: Numerical Techniques and Approximations
    Multidimensional Birth and Death Chains
    Multidimensional Markov Chains
    Finite-State Markov Chains
    Reference Notes
    Exercises

    General Interarrival and/or Service Times: Closed-Form Expressions and Approximations
    Analyzing Queues Using Discrete Time Markov Chains
    Mean Value Analysis
    Bounds and Approximations for General Queues
    Matrix Geometric Methods for G/G/s Queues
    Other General Queues but with Exact Results
    Reference Notes
    Exercises

    Multiclass Queues under Various Service Disciplines
    Introduction
    Evaluating Policies for Classification Based on Types: Priorities
    Evaluating Policies for Classification Based on Location: Polling Models
    Evaluating Policies for Classification Based on Knowledge of Service Times
    Optimal Service-Scheduling Policies
    Reference Notes
    Exercises

    Exact Results in Network of Queues: Product Form
    Acyclic Queueing Networks with Poisson Flows
    Open Jackson Networks
    Closed Jackson Networks
    Other Product-Form Networks
    Reference Notes
    Exercises

    Approximations for General Queueing Networks
    Single-Server and Single-Class General Queueing Networks
    Multiclass and Multiserver Open Queueing Networks with FCFS
    Multiclass and Single-Server Open Queueing Networks with Priorities
    Reference Notes
    Exercises

    Fluid Models for Stability, Approximations, and Analysis of Time-Varying Queues
    Deterministic Fluid Queues: An Introduction
    Fluid Models for Stability Analysis of Queueing Networks
    Diffusion Approximations for Performance Analysis
    Fluid Models for Queues with Time-Varying Parameters
    Reference Notes
    Exercises

    Stochastic Fluid-Flow Queues: Characteristics and Exact Analysis
    Introduction
    Single Buffer with Markov Modulated Fluid Source
    First Passage Times
    Reference Notes
    Exercises

    Stochastic Fluid-Flow Queues: Bounds and Tail Asymptotics
    Introduction and Preliminaries
    Performance Analysis of a Single Queue
    Multiclass Fluid Queues
    Reference Notes
    Exercises

    Appendix A: Random Variables
    Appendix B: Stochastic Processes
    References
    Index

    Biography

    Natarajan Gautam

    "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