Page 288 - Schaum's Outlines - Probability, Random Variables And Random Processes

Chapter 9

Queueing Theory

9.1 INTRODUCTION
Queueing theory deals with the study of queues (waiting lines). Queues abound in practical situ-
ations. The earliest use of queueing theory was in the design of a telephone system. Applications of
queueing theory are found in fields as seemingly diverse as traffic control, hospital management, and
time-shared computer system design. In this chapter, we present an elementary queueing theory.

9.2 QUEUEING SYSTEMS
A. Description:
A simple queueing system is shown in Fig. 9-1. Customers arrive randomly at an average rate of
A,. Upon arrival, they are served without delay if there are available servers; otherwise, they are
made to wait in the queue until it is their turn to be served. Once served, they are assumed to leave
the system. We will be interested in determining such quantities as the average number of customers
in the system, the average time a customer spends in the system, the average time spent waiting in the
queue, etc.

Arrivals Departures
+ Queue b Service b

Fig. 9-1 A simple queueing system.

The description of any queueing system requires the specification of three parts:
1. The arrival process
2. The service mechanism, such as the number of servers and service-time distribution
3. The queue discipline (for example, first-come, first-served)

B. Classification :
The notation A/B/s/K is used to classify a queueing system, where A specifies the type of arrival
process, B denotes the service-time distribution, s specifies the number of servers, and K denotes the
capacity of the system, that is, the maximum number of customers that can be accommodated. If K is
not specified, it is assumed that the capacity of the system is unlimited. For example, an M/M/2
queueing system (M stands for Markov) is one with Poisson arrivals (or exponential interarrival time
distribution), exponential service-time distribution, and 2 servers. An M/G/l queueing system has
Poisson arrivals, general service-time distribution, and a single server. A special case is the M/D/1
queueing system, where D stands for constant (deterministic:) service time. Examples of queueing
systems with limited capacity are telephone systems with limited trunks, hospital emergency rooms
with limited beds, and airline terminals with limited space in which to park aircraft for loading and
unloading. In each case, customers who arrive when the systeim is saturated are denied entrance and
are lost.

C. Useful Formulas
Some basic quantities of queueing systems are