## Queuing Theory

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