Page 194 - A First Course In Stochastic Models

CHAPTER 5

Markov Chains and Queues

5.0 INTRODUCTION

Markov chain theory has numerous applications to queueing systems. This chapter
gives a first introduction to the analysis of queues and stochastic networks. In
Section 5.1 we consider the Erlang delay model with Poisson arrivals and expo-
nential services. We first analyse the single-server M/M/1 queue and next the
multi-server M/M/c queue. Section 5.2 deals with both the Erlang loss model with
Poisson input and the Engset loss model with finite-source input. The Erlang delay
model and Erlang’s loss formula will be used in Section 5.3 to obtain a square-root
staffing rule for the design of stochastic service systems. The Erlang loss model
and the Engset loss model have the so-called insensitivity property stating that the
equilibrium distribution of the number of customers present is insensitive to the
form of the service-time distribution and requires only the mean service time. This
insensitivity property, being of utmost importance in practice, will be discussed in a
more general framework in Section 5.4. The so-called phase method is the subject
of Section 5.5. This powerful method uses the idea that any probability distribution
function of a non-negative random variable can be arbitrarily closely approximated
by a mixture of Erlangian distributions with the same scale parameters. This fun-
damental result greatly enhances the applicability of the continuous-time Markov
chain model. In Section 5.6 the theory of continuous-time Markov chains will be
used to analyse open and closed queueing networks. In particular, a product-form
formula will be established for the joint distribution of the number of customers
present at the various nodes of the network.

5.1 THE ERLANG DELAY MODEL

Consider a multi-server station at which customers arrive according to a Poisson
process with rate λ. There are c servers with a shared infinite-capacity waiting line.
If an arriving customer finds a free server, the customer immediately enters service;
otherwise, the customer joins the queue. The service times of the customers are

A First Course in Stochastic Models H.C. Tijms
c 2003 John Wiley & Sons, Ltd. ISBNs: 0-471-49880-7 (HB); 0-471-49881-5 (PB)