Page 344 - A First Course In Stochastic Models

CHAPTER 9

Algorithmic Analysis of

Queueing Models

9.0 INTRODUCTION
Queueing models have their origin in the study of design problems of automatic
telephone exchanges and were first analysed by the queueing pioneer A.K. Erlang in
the early 1900s. In planning telephone systems to meet given performance criteria,
questions were asked such as: How many lines are required in order to give a certain
grade of service? What is the probability that a delayed customer has to wait more
than a certain time before getting a connection? Similar questions arise in the design
of many other systems: How many terminals are needed in a computer system so
that 80% of the users get access to a terminal within 20 seconds? What will be
the effect on the average waiting time of customers when changing the size of a
maintenance staff to service leased equipment? How much storage space is needed
in buffers at workstations in an assembly line in order to keep the probability of
blocking below a specified acceptable level?
These design problems and many others concern, in fact, facilities serving a
community of users, where both the times at which the users ask for service and
the durations that the requests for service will occupy facilities are stochastic, so
that inevitably congestion occurs and queues may build up. In the first stage of
design the system engineer usually needs quick answers to a variety of questions
like those posed above. Queueing theory constitutes a basic tool for making first-
approximation estimates of queue sizes and probabilities of delays. Such a simple
tool should in general be preferred to simulation, especially when it is possible to
have a large number of different configurations in the design problem.
In this chapter we discuss a number of basic queueing models that have proved to
be useful in analysing a wide variety of stochastic service systems. The emphasis
will be on algorithms and approximations rather than on mathematical aspects.
We feel that there is a need for such a treatment in view of the increased use
of queueing models in modern technology. Actually, the application of queueing
theory in the performance analysis of computer and communication systems has

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)