Queuing Theory
Each of us has spent a great deal of time waiting in lines. In this chapter, we develop mathe-
matical models for waiting lines, or queues. In Section 20.1, we begin by discussing some ter-
minology that is often used to describe queues. In Section 20.2, we look at some distributions
(the exponential and the Erlang distributions) that are needed to describe queuing models. In
Section 20.3, we introduce the idea of a birth–death process, which is basic to many queu-
ing models involving the exponential distribution. The remainder of the chapter examines sev-
eral models of queuing systems that can be used to answer questions like the following:
1
What fraction of the time is each server idle?
2
What is the expected number of customers present in the queue?
3
What is the expected time that a customer spends in the queue?
4
What is the probability distribution of the number of customers present in the queue?
5
What is the probability distribution of a customer’s waiting time?
6
If a bank manager wants to ensure that only 1% of all customers will have to wait more
than 5 minutes for a teller, how many tellers should be employed?
20.1
Some Queuing Terminology
To describe a queuing system, an input process and an output process must be specified.
Some examples of input and output processes are given in Table 1.
The Input or Arrival Process
The input process is usually called the
arrival process.
Arrivals are called
customers.
In
all models that we will discuss, we assume that no more than one arrival can occur at a
given instant. For a case like a restaurant, this is a very unrealistic assumption. If more
than one arrival can occur at a given instant, we say that
bulk arrivals
are allowed.
Usually, we assume that the arrival process is unaffected by the number of customers
present in the system. In the context of a bank, this would imply that whether there are
500 or 5 people at the bank, the process governing arrivals remains unchanged.
There are two common situations in which the arrival process may depend on the num-
ber of customers present. The first occurs when arrivals are drawn from a small popula-
tion. Suppose that there are only four ships in a naval shipyard. If all four ships are be-
ing repaired, then no ship can break down in the near future. On the other hand, if all four
ships are at sea, a breakdown has a relatively high probability of occurring in the near
1052
CHAPTER
20
Queuing Theory
future. Models in which arrivals are drawn from a small population are called
finite
source models.
Another situation in which the arrival process depends on the number of
customers present occurs when the rate at which customers arrive at the facility decreases
when the facility becomes too crowded. For example, if you see that the bank parking lot
is full, you might pass by and come another day. If a customer arrives but fails to enter
the system, we say that the customer has
balked.
The phenomenon of balking was de-
scribed by Yogi Berra when he said, “Nobody goes to that restaurant anymore; it’s too
crowded.”
If the arrival process is unaffected by the number of customers present, we usually de-
scribe it by specifying a probability distribution that governs the time between successive
arrivals.
The Output or Service Process
To describe the output process (often called the service process) of a queuing system, we
usually specify a probability distribution—the
service time distribution
—which governs
a customer’s service time. In most cases, we assume that the service time distribution is
independent of the number of customers present. This implies, for example, that the server
does not work faster when more customers are present.
In this chapter, we study two arrangements of servers:
servers in parallel
and
servers
in series.
Servers are in parallel if all servers provide the same type of service and a cus-
tomer need only pass through one server to complete service. For example, the tellers in
a bank are usually arranged in parallel; any customer need only be serviced by one teller,
and any teller can perform the desired service. Servers are in series if a customer must
pass through several servers before completing service. An assembly line is an example
of a series queuing system.
Queue Discipline
To describe a queuing system completely, we must also describe the queue discipline and
the manner in which customers join lines.
The
queue discipline
describes the method used to determine the order in which cus-
tomers are served. The most common queue discipline is the
FCFS discipline
(first come,
first served), in which customers are served in the order of their arrival. Under the
LCFS
discipline
(last come, first served), the most recent arrivals are the first to enter service. If
we consider exiting from an elevator to be service, then a crowded elevator illustrates an
LCFS discipline. Sometimes the order in which customers arrive has no effect on the or-
TABLE
1
Examples of Queuing Systems
Situation                                                      Input Process                                        Output Process
Bank                                   Customers arrive at bank              Tellers serve the customers
Pizza parlor                        Requests for pizza delivery           Pizza parlor sends out
are received                                    truck to deliver pizzas
Hospital blood bank           Pints of blood arrive                      Patients use up pints of
blood
Naval shipyard                   Ships at sea break down                Ships are repaired and
and are sent to shipyard                return to sea
for repairs