ABSTRACT
CONTENTS 6.1 Introduction and Brief History . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289 6.2 Basic Concepts of Queueing Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290
6.2.1 Arrival (Input) Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290 6.2.2 Service Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291 6.2.3 Number of Servers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291 6.2.4 Queue Discipline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291 6.2.5 System Capacity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292 6.2.6 Performance Measures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292
6.3 Stochastic Processes: Basic Concepts and Poisson Process . . . . . . . . . . . . . . . . . . . . . 293 6.3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293 6.3.2 Poisson Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294
6.3.2.1 Superposition of Poisson Processes . . . . . . . . . . . . . . . . . . . . . . . . . 295 6.3.2.2 Decomposition of a Poisson Process . . . . . . . . . . . . . . . . . . . . . . . . 296 6.3.2.3 Uniform Distribution and Poisson Process . . . . . . . . . . . . . . . . . . . . 296
6.4 Renewal Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296 6.4.1 Renewal Reward Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298
6.5 Markov Chains and Continuous-Time Markov Chains . . . . . . . . . . . . . . . . . . . . . . . . 299 6.5.1 Markov Chains . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299
6.5.1.1 Unconditional State Probabilities . . . . . . . . . . . . . . . . . . . . . . . . . . . 300 6.5.1.2 Chapman-Kolmogorov Equations . . . . . . . . . . . . . . . . . . . . . . . . . . 300 6.5.1.3 Matrix Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301 6.5.1.4 Unconditional State Probabilities . . . . . . . . . . . . . . . . . . . . . . . . . . . 301 6.5.1.5 Expected Number of Visits to a State . . . . . . . . . . . . . . . . . . . . . . . . 301 6.5.1.6 Sojourn Times . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302 6.5.1.7 First Passage and Return Probabilities . . . . . . . . . . . . . . . . . . . . . . . 302 6.5.1.8 Limiting Probabilities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302 6.5.1.9 Calculation of Limiting Probabilities . . . . . . . . . . . . . . . . . . . . . . . . 303
6.5.2 Continuous-Time Markov Chains . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304 6.5.2.1 Kolmogorov Differential Equations . . . . . . . . . . . . . . . . . . . . . . . . . 306 6.5.2.2 Unconditional State Probabilities . . . . . . . . . . . . . . . . . . . . . . . . . . . 306 6.5.2.3 Steady-State Probabilities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307
6.5.3 Birth and Death Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307 6.6 Queueing Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308
6.6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308 6.6.1.1 Little’s Law . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309
6.6.2 The M/M/1 Queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310 6.6.2.1 Probability Distribution of Waiting Times . . . . . . . . . . . . . . . . . . . . . 311
6.6.3 M/M/s Queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 312 6.6.3.1 Waiting Time Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314
6.6.4 M/M/s/N Queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315 6.6.5 M/M/1/N Queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316 6.6.6 M/M/s/s Queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316 6.6.7 M/M/∞ Queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317 6.6.8 M/M/1/N/N Queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318 6.6.9 M/G/1 Queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319
6.6.9.1 M/D/1 Queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322 6.6.9.2 M/Ek /S Queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322
6.6.10 G/M/1 Queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323 6.6.10.1 Ek /M/1 Queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324
6.6.11 GI/G/s Queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325 6.6.12 Queues with Phase-Type Distributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325
6.6.12.1 Phase-Type Distributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325 6.6.12.2 M/PT/1 Queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327
6.7 Queueing Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 328 6.7.1 Series Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329 6.7.2 Open Jackson Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329 6.7.3 Closed Jackson Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331 6.7.4 BCMP Network . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331 6.7.5 G Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332 6.7.6 Finite Buffer Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332
6.8 Remarks and Extensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333 6.8.1 Single Stage Queues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333
6.8.1.1 Transient Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333 6.8.1.2 Queue Discipline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333 6.8.1.3 Priority Queues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333 6.8.1.4 Impatient Customers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334 6.8.1.5 Retrial Queues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334 6.8.1.6 Polling Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334 6.8.1.7 Vacation Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334 6.8.1.8 Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334
6.8.2 Network of Queues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335 6.8.3 Further Resources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335
Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335 Appendix A: Review of Probability Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 336
A.1 Partitioning and Bayes’ Rule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337 A.2 Expected Values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 338 A.3 Moments of Random Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 338 A.4 Moment Generating Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 338 A.5 Probability Generating Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 338 A.6 Laplace Transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339 A.7 Some Important Distributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339 A.8 Some Properties of Exponential Distributions . . . . . . . . . . . . . . . . . . . . . . . . 341 A.9 Jointly Distributed Random Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342 A.10 Conditional Probability Distributions and Conditional Expectation . . . . . . . . . . 343
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343
ABSTRACT Queueing theory is concerned with the quantitative modeling of dynamic systems that generate waiting lines, and the analysis of the behavior of such systems in the short and long time spans. In this chapter, we present a brief overview of the history of queueing theory and the basic concepts of it. The aim of this chapter is to expose the reader to one of the most instrumental and widely applicable topics of stochastic analysis, to provide the basic concepts of it, and to stimulate further interest in it. Some motivating examples of stochastic processes are discussed followed by the main topics in a standard course of stochastic processes. These include the renewal processes, Markov chains, and continuous-time Markov chains. Queueing models are then discussed in more detail, where the focus is mainly restricted to Markovian queues. A more complicated topic of queueing networks is also briefly discussed. Most of the topics discussed are also supported by illustrative examples. The methods are presented mainly under the assumption of a single queue, where a single type of service is provided by possibly several servers under the FIFO (first in first out) service protocol and under the traditional assumption that once a customer enters a queue, she/he stays there until the service has been completed. In an extensive section, we pointed out relaxation of such assumptions and extensions in several directions regarding the queue discipline, service protocol, customer behavior, several service types, estimation of major system parameters, as well as the current research interests in the field. In an appendix, we included a brief review of the background material in probability theory.
