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:
What fraction of the time is each server idle?
What is the expected number of customers present in the queue?
What is the expected time that a customer spends in the queue?
What is the probability distribution of the number of customers present in the queue?
What is the probability distribution of a customer’s waiting time?
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?
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
Arrivals are called
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
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
future. Models in which arrivals are drawn from a small population are called
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
The phenomenon of balking was de-
scribed by Yogi Berra when he said, “Nobody goes to that restaurant anymore; it’s too
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
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
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
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.
To describe a queuing system completely, we must also describe the queue discipline and
the manner in which customers join lines.
describes the method used to determine the order in which cus-
tomers are served. The most common queue discipline is the
first served), in which customers are served in the order of their arrival. Under the
(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-
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
Naval shipyard Ships at sea break down Ships are repaired and
and are sent to shipyard return to sea