Basics of
Queueing Theory
Queuing theory is a branch of mathematics that studies and
models the act of waiting in lines.
This module defines the building blocks of – and derives – basic
queuing systems.
Contents
Introduction Queueing Notation
Queueing Theory Little’s Queueing Formula
Terminology
§ Poisson Distribution The 𝑴/𝑴/𝟏 Queueing System
§ Exponential Distribution § M/M/1 With Limited Capacity
§ Erlang Distribution
§ Input Process The 𝑴/𝑴/𝒄 Queueing System
§ Output Process
Introduction
Queueing theory boils down to answering simple questions:
§ How likely is it that things will queue up and wait in line?
§ How long will the line be?
§ How long will the wait be?
§ How busy will the server/person/system servicing the line be?
§ How much capacity is needed to meet an expected level of demand?
§ etc.
Introduction
Knowing how to think about these kinds of questions will help
you anticipate bottlenecks.
As a result, you’ll build your systems and teams to be more
efficient, to have higher performance and lower cost, and
ultimately provide better service both for yourself and for your
customers.
Introduction
Let’s take a simple example. Suppose a grocery store has a
single checkout line and a single cashier. Suppose an average
of one shopper arrives at the line to pay for their groceries every
5 minutes. Scanning, bagging and paying takes 4.5 minutes on
average.
Will there be queueing and waiting? Intuition says no, there
won’t.
But that’s not what really happens. In reality, there will be lots of
shoppers waiting in line and they’ll have to wait a long time!
Introduction
Fundamentally, queueing happens due to 3 phenomena:
§ irregular arrivals – shoppers don’t arrive at the checkout line on a
regular schedule;
§ irregular job sizes – shoppers are not all processed in 45 seconds.
Some of them will take much longer;
§ waste – lost time can never be regained. Shoppers overlap because
earlier shoppers didn’t have time to finish in their “allotted” 45 secs.
Introduction
Queueing gets worse when the following holds:
§ high utilization – the busier the cashier is, the longer it takes to
recover from wasted time;
§ high variability – the more variability in arrivals or job sizes, the more
waste and the more overlap (queueing) occurs;
§ few servers – fewer cashiers means less capacity to absorb spikes of
arrivals, leading to more wasted time and higher utilization.
Introduction
All discussions of queueing theory analyze systems and
processes in terms of three key concepts:
§ customers are the units of work that the system serves (a customer
can be a real person, a web request, a database query, a part to be
milled by a machine, etc.);
§ servers are the things that do the work (this might be the cashier at
the grocery store, the web server or database server, or the milling
machine, etc.);
§ queues are where the units of work wait if the server is busy and can’t
do the work of processing them.
Queueing Theory
Terminology
Queueing Theory Terminology
To begin understanding and describing queues, we must first
have some knowledge of
§ some useful probability distributions,
§ an input process and
§ an output process.
Poisson and Exponential Distributions
Both the Poisson and Exponential distributions play a prominent
role in queuing theory:
§ the Poisson distribution counts the number of discrete events in a
fixed time period;
§ the exponential distribution measures the time between arrivals of
the events.
Poisson Distribution
Given an average arrival rate 𝜆 (in seconds, minutes, hours,
days, etc.), the probability that 𝑛 arrivals will be observed in a
time interval of length 𝑡 is:
(𝜆𝑡)! "#$
𝑃 𝑛, 𝑡 = 𝑒
𝑛!
where 𝑛 = 0,1,2, …
Poisson Distribution
On average, 50 customers
arrive in a coffee shop
every hour.
What is the probability that
exactly 20 customers will
arrive in a 30-minute
period, if the arrivals follow
a Poisson distribution?
Poisson Distribution
Poisson Distribution
Given 𝜆 = 50 customers per hour, 𝑡 = 30 minutes = 0.5 hour,
and 𝑛 = 20, we have
(50 ×0.5)%& " ((& × &.()
𝑃 20,0.5 = 𝑒 ≈ 5%.
20!
Exponential Distribution
The time between successive arrivals is the inter-arrival time.
When the number of arrivals in a given time interval has Poisson
distribution, inter-arrival times can be shown to follow an
exponential distribution
𝑓 𝑡 = 𝜇𝑒 ",$ .
Hence, the probability that no more than 𝑡 time periods are
required in order to serve a customer is
𝑃 𝑊 ≤ 𝑡 = 1 − 𝑒 ",$ .
A manager of a fast food
restaurant observes that
an average of 9 customers
are served by a waiter in a
one-hour time period.
Assuming that the service
time follows an exponential
distribution, what is the
probability that a customer
will be served within 15
Exponential Distribution
minutes?
Exponential Distribution
Let 𝑤 be the average waiting time. Given µ = 9 customers per
hour, 𝑡 = 15 minutes = 0.25 hour, we have
𝑃 𝑤 ≤ 15 minutes = 1 − 𝑒 "-×&.%( ≈ 89%.
Exponential Distribution
Memory-Less Property
𝑃 𝑋 > 𝑡 + ℎ 𝑋 > ℎ) = 𝑃 𝑋 > 𝑡 , ∀ℎ
The memory-less property of the exponential distribution
implies that the probability distribution of the time until the next
arrival is independent of the time since the last arrival …
(is that how it works for buses?)
The time 𝑤 a customer
spends waiting in a bank
queue is exponentially
distributed with mean 10
minutes, say.
Then
𝑃 𝑤 > 15 𝑤 > 10
= 𝑃 𝑤 > 5 = 𝑒 !"/$%
≈ 61%
If they’ve already waited
10 minutes, there is a 61%
Memory-Less Property
chance they’ll wait more
than 15 minutes in total.
Erlang Distribution
The exponential distribution is not always an appropriate model
of inter-arrival times; wait times are not always memory-less, for
instance (see bus example).
An alternative approach uses the Erlang distribution ℰ(𝑅, 𝑘), a
random variable with 2 parameters 𝑅 > 0, 𝑘 ∈ ℤ. , whose p.d.f. is:
𝑅(𝑅𝑡)1"2 𝑒 "/$
𝑓/,1 𝑡 = , 𝑡 > 0.
𝑘−1 !
Erlang Distribution
When 𝑘 = 1, ℰ 𝑅, 1 = Exp(𝑅). In general, we write 𝑅 = 𝑘𝜆, and
we obtain a decomposition into 𝑘 independent exponentials:
1
ℰ 𝑘𝜆, 𝑘 = Exp 𝑘𝜆 + ⋯ + Exp 𝑘𝜆 = V Exp 𝑘𝜆
342
If inter-arrival times follow an Erlang ℰ 𝑘𝜆, 𝑘 , we are assuming
that go through 𝑘 memory-less phases before being served.
Erlang Distribution
𝜇 = 1/𝑅
[By IkamusumeFan - CC BY-SA 4.0, https://commons.wikimedia.org/w/index.php?curid=37203954]
Input or Arrival Process
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.
Poisson arrival process are often assumed as many real-world
arrival processes can be modeled using a Poisson process
(but other processes can be used as well).
Output or Service Process
How long does it take to service a job or customer?
In most cases, we assume that the service time distribution is
independent of the number of customers present in the
system.
§ is this realistic?
Servers in parallel or servers in series?
Exponential service times often assumed.
§ works well for maintenance or unscheduled service situations.
Examples of Queueing Models
Situation Input Process Output Process
Bank Customers arrive at Bank Tellers serve the customers
Pizza parlor Requests for pizza delivery Pizza parlor sends out truck
are received to deliver pizzas
Hospital blood Pints of blood arrive Patients use up pints of blood
bank
Naval shipyard Ships at sea break down and Ships are repaired and sent
are sent to Shipyard for back to sea
repairs
Queueing
Notation
Queueing (Kendall) Notation
Queueing systems can be described by six characteristics:
1/2/3/4/5/6
The 1-characteristic specifies the nature of the arrival process.
The following standard abbreviations are used:
§ 𝑀 = inter-arrival times are independent, identically distributed (iid)
random variables having an exponential distribution;
§ 𝐷 = inter-arrival times are iid and deterministic;
§ 𝐸* = inter-arrival times are ℰ(𝑅, 𝑘), iid
§ 𝐺 = inter-arrival times follow a general distribution, iid
Queueing (Kendall) Notation
The 2-characteristic specifies the nature of the service times:
§ 𝑀 = service times are i.i.d. and exponentially distributed;
§ 𝐷 = service times are i.i.d. and deterministic.
The 3-characteristic represents the number of parallel servers.
The 4-characteristic describes the queue discipline:
§ FCFS = first come, first served;
§ LCFS = last come, first served;
§ SIRO = service in random order;
§ GD = general queue discipline.
Queueing (Kendall) Notation
The 5-characteristic specifies the maximum allowable number
of customers in the system.
The 6 -characteristic gives the size of the population from
which customers are drawn.
In many important models 4/5/6 is 𝐺𝐷/∞/∞. When that is the
case, 4/5/6 is usually omitted.
Queueing (Kendall) Notation
Name (Kendall Notation) Example
Simple system (𝑀/𝑀/1) Customer service desk in a store
Multi-server system (𝑀/𝑀/𝑐) Airline ticket counter
Constant service (𝑀/𝐷/1) Automated car wash
General service (𝑀/𝐺/1) Auto repair shop
Limited capacity (𝑀/𝑀/1/𝑁) Barber shop with 𝑁 waiting seats
Little’s Queuing
Formula
Little’s Queuing Formula
𝜆 = average number of arrivals entering the system per unit time
𝐿 = average number of customers present in the queuing system
𝐿5 = average number of customers waiting in line
𝐿6 = average number of customers in service
𝑊 = average time a customer spends in the system
𝑊5 = average time a customer spends in line
𝑊6 = average time a customer spends in service
Little’s Queuing Formula
For any queuing system in which a steady-state distribution
exists, the following relations hold:
§ 𝐿 = 𝜆𝑊
§ 𝐿5 = 𝜆𝑊5
§ 𝐿6 = 𝜆𝑊6
Example: if 𝜆 = 46 clients arrive at a restaurant every hour, on
average, and if they spend 𝑊 = 10 minutes before being
served, on average, then there will be 𝐿 = 46×1/6 ≈ 7.7 clients
waiting to be served at all times, on average.
The 𝑀/𝑀/1
Queuing System
The 𝑀/𝑀/1 Queuing System
An 𝑀/𝑀/1 system has exponential interarrival times with rate 𝜆,
exponential service times with rate 𝜇, and one server.
Let 𝜌 = 𝜆/𝜇 be the traffic intensity of the queuing system.
Assuming 𝜌 ≤ 1, the probability of exactly 𝑛 customers in the
system is
𝜌! (1 − 𝜌), 𝑛 = 0,1,2, …
The probability of exactly no customers in the system is thus
(1 − 𝜌)
The 𝑀/𝑀/1 Queuing System
Average number in service: 𝐿6 = 𝜌
7!
Average number waiting in line: 𝐿5 = 2"7
#
Average number waiting in the system: 𝐿 = 𝐿5 + 𝐿6 =
, "#
2
Average waiting time in service:𝑊6 =
,
8" #
Average waiting time in the line: 𝑊5 = #
= ,(, "#)
8 2
Average waiting time in the system:𝑊 = 𝑊5 + 𝑊6 = =
# , "#
The 𝑀/𝑀/1 Queuing System
Intuitively, if 𝜌 ≥ 1, then it must be that 𝜇 ≥ 𝜆, and if the arrival
rate is greater than the service rate, then the state of the system
will grow without end.
Notice that (as expected) as 𝜌 approaches 1, both 𝑊 and 𝑊5
become very large.
For 𝜌 near zero, 𝑊5 approaches zero, but for small 𝜌 , 𝑊
approaches 1/𝜇, the mean service time.
Suppose that all car
owners fill up when their
tanks are exactly half full.
At the present time, an
average of 7.5 customers
per hour arrive at a single-
pump gas station.
It takes an average of 4
minutes to service a car.
Assume that inter-arrival
times and service times
Single-Pump Gas Station are both exponential.
[Erickson, W., 1973]
Single-Pump Gas Station Example
By assumption the single-pump gas station is a 𝑀/𝑀/1 queueing
system with 𝜆 = 7.5 arrivals per hour and the capacity to serve
𝜇 = 60⁄4 = 15 vehicles per hour.
Then the
+
§ traffic intensity is 𝜌 = = 0.5;
,
+
§ average number of customers waiting in this system is 𝐿 = , !+
= 1;
- $ 0
§ average waiting time in the system 𝑊 = +
= .."
= 0.13 hour = 6 1
mins.
Suppose now that all car
owners purchase gas
when their tanks are
exactly three-quarters full
due to a gas shortage and
panic buying takes place.
Assume that the average
service time has been
$
reduced to 3 1 minutes.
How has panic buying
affected 𝐿 and 𝑊?
Single-Pump Gas Station
[Erickson, W., 1973]
Single-Pump Gas Station
With these new assumptions, we have 𝜆 = 2(7.5)=15 arrivals per
hour and the capacity to serve 𝜇 = 18 cars per hour.
Then the
"
§ traffic intensity is 𝜌 = 2
;
+
§ average number of customers waiting in this system is 𝐿 = , !+
= 5;
- "
§ average waiting time in the system 𝑊 = +
= $"
= 0.33 hour = 20 mins.
Thus, panic buying has caused longer lines.
Single-Pump 𝑳 for 𝑴/𝑴/𝟏
𝝆
Gas Station queueing model
0.30 0.43
0.60 1.50
The previous example
illustrates the fact that 0.80 4.00
as 𝜌 approaches 1, 𝐿
(and therefore 𝑊) 0.90 9.00
increase rapidly.
0.95 19.00
0.99 99.00
𝑀/𝑀/1 With Limited Capacity
In real cases, queues never become infinite, but are limited due to
space, time or service operating policy.
Examples: parking of vehicles in a supermarket is restricted to the
spaces in the parking area; limited seating arrangement in a
restaurant.
The probability of exactly no customers in such a system is
1−𝜌
𝑝! =
1 − 𝜌"#$
where 𝑁 is the maximum number allowable in the system.
𝑀/𝑀/1 With Limited Capacity
The probability of exactly 𝑛 customers in the system is
𝜌! 𝑝& , 𝑛 = 1,2, … , 𝑁
𝑝! = c
0, 𝑛 = 𝑁 + 1, 𝑁 + 2, …
The average number waiting in the system is
𝜌 1 − 𝑁 + 1 𝜌9 + 𝑁 𝜌9.2
𝐿=
1 − 𝜌 1 − 𝜌9.2
and 𝐿6 = 1 − 𝑝& , 𝐿5 = 𝐿 − 𝐿6 .
M/M/1 With Limited Capacity
Note that 𝜆 − 𝜆𝑝9 arrivals per unit time actually enter the system
on average due to the capacity limit. With this fact, we can show
that:
𝐿 𝐿5
𝑊= , 𝑊5 = .
𝜆( 1 − 𝑝9 ) 𝜆 1 − 𝑝9
As a consequence of this restriction, a steady state always
exists, because even if 𝜆 ≥ 𝜇 , there is never more than 𝑁
customers in the system.
Steady-State (Queue Equilibrium)
Measurement of Transient State Steady State
Effectiveness
Time
A 1-man barber shop has a
total of 10 waiting seats.
Inter-arrival times are
exponentially distributed, and
an average of 20 prospective
customers arrive each hour
at the shop.
The barber takes an average
of 12 minutes to cut each
customer’s hair (haircut times
are exponentially distributed).
On average, how much time
Barber Shop does an arriving customer
spend in the barber shop?
Barber Shop Example
From the statement of the problem, 𝑁 = 10, 𝜆 = 20 customers per
hour, and 𝜇 = 60/12 = 5 customers per hour. Then the traffic intensity
in the system is 𝜌 = 20/5 = 4, and we have
4 1 − (11)4$! + (10) 4$$
𝐿= $$
= 9.67,
1−4 1−4
%
so that 𝑊 = = 1.93 hours.
&
This shop is crowded, and the barber would be well advised to hire at
least one more barber – what effect would that have on 𝐿 and 𝑊?
The 𝑀/𝑀/𝑐
Queuing System
Queueing System
Servers
Population
1
Queue Enter
Arrival Service 2 Departure
𝑐
The 𝑀/𝑀/𝑐 Queuing System
Same assumptions as 𝑀/𝑀/1 except that the system now has 𝑐
servers able to serve from a single line of customers, like one
could find in a bank.
If each server completes service at rate 𝜇, the system rate is 𝑐𝜇.
#
The traffic intensity is 𝜌 =
cµ , and we again assume that 𝜌 ≤ 1.
If 𝜌 ≥ 1, no steady state exists. In other words, if the arrival rate 𝜆
is at least as large as the maximum possible service rate cµ, the
system "blows up” and the queue never empties.
The 𝑀/𝑀/𝑐 Queuing System
It can be shown that the steady-state (long-run) probability that
all servers are busy is given by:
(𝑐𝜌):
𝑃 𝑛 ≥𝑐 = 𝑝&
𝑐! (1 − 𝜌)
where 𝑝& is the probability that there is no customer in the
system (its formula is omitted for simplicity). We thus have
7
§ 𝐿5 = 𝑃 𝑛 ≥ 𝑐 , 𝑊5 = 𝐿5 ⁄𝜆
2"7
# 2
§𝐿 = ,
+ 𝐿5 , 𝑊 = ,
+ 𝑊5 .
The 𝑀/𝑀/𝒄
Queuing 𝝆 𝒄=𝟐 𝒄=𝟑 𝒄=𝟒 𝒄=𝟓 𝒄=𝟔 𝒄=𝟕
System .10 .02 .00 .00 .00 .00 .00
.30 .14 .07 .04 .02 .01 .00
𝑃 𝑛 ≥ 𝑐 for a variety
of situations. .50 .33 .24 .17 .13 .10 .08
.70 .57 .51 .43 .38 .34 .30
.80 .71 .65 .60 .55 .52 .49
.90 .85 .83 .79 .76 .74 .72
.95 .92 .91 .89 .88 .87 .85
A bank has two tellers.
An average of 80 customers
per hour arrive at the bank
and wait in a single line for
an idle teller.
The average time to serve a
customer is 1.2 minutes.
What is the expected number
of customers present in the
bank queue?
What is the expected length
Bank Tellers of time a customer spends in
the bank queue?
Bank Tellers
We are dealing with an 𝑀/𝑀/2 model with 𝜆 = 80 customers
#
per hour and 𝜇 = 50 customers per hour, whence 𝜌 = = 0.8.
%,
From the table, we have 𝑃 𝑛 ≥ 2 = 0.71.
Then
%.6
§ 𝐿5 = (0.71) = 2.84 customers per hour
$!%.6
6%
§ 𝐿= + 2.84 = 4.44 customers per hour
"%
-
§ 𝑊 = = 0.055 hours = 3.3 minutes
+
