Operations Research

Chapter 5: Queueing Theory

Sonia REBAI
Tunis Business School
University of Tunis
Introduction
ü Waiting phenomena are commonly observed in our daily lives (in
supermarkets, in banks, etc.).
ü In this chapter, we develop mathematical models for waiting lines, or
queues.
ü First, some terminology and distributions, often used to describe queues,
are introduced.
ü Then, we introduce the idea of a birth–death process, which is basic to
many queuing models involving the exponential distribution.
Introduction - continued
ü Then we examine several 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. How many tellers should be employed to ensure some characteristics
for the station?
Some Queuing Terminology
Arrival Process

ü We assume that no more than one arrival can occur at a given instant. If
more than one arrival can occur at a given instant, we say that bulk arrivals
are allowed (such as for restaurant).

ü For most models, we assume that the arrival process is unaffected by the
number of customers present in the system.
Some Queuing Terminology - continued
ü There are two common situations in which the arrival process may depend
on the number of customers present in the system:
§ when arrivals are drawn from a small population. Models in which
arrivals are drawn from a small population are called finite source
models (such as the phenomenon of machines break down in a plant).
§ when the rate at which customers arrive at the facility decreases when it
becomes too crowded. The system is full, the customer arrives but fails
to enter the system we say that the customer has balked.
Some Queuing Terminology - continued
ü If the arrival process is unaffected by the number of customers present, we
usually describe it by specifying a probability distribution that governs the
time between successive arrivals.

Service Process
ü In most cases, we assume that the service time distribution is independent
of the number of customers present. This means that the server does not
work faster when more customers are present.
Some Queuing Terminology - continued
Number of servers
ü The number of available servers may be one server or multiple servers.

§ Single server queue

Some Queuing Terminology - continued
ü In case of multiple service queue, two arrangements of servers are
considered: servers in parallel and servers in series.
§ Servers are in parallel if all servers provide the same type of service
and a customer need only pass through one server to complete service.
Some Queuing Terminology - continued
§ Servers are in series if a customer must pass through several servers
before completing service.
Some Queuing Terminology - continued
Queue Discipline

ü The queue discipline describes the method used for the order in which
customers are served. The most common queue disciplines are

§ First come, first served discipline (FCFS), in which customers are

served in the order of their arrival.

§ Last come, first served discipline (LCFS), the most recent arrivals are
the first to enter service.
Some Queuing Terminology - continued

§ Service in random order discipline (SIRO), the next customer to

enter service is randomly chosen from those customers waiting for
service.

§ Priority queuing disciplines: a priority discipline classifies each

arrival into one of several categories. Each category is then given a
priority level, and within each priority level, customers enter service
on an FCFS basis (like emergency rooms to receive treatment).
Some Queuing Terminology - continued
Method Used by Arrivals to Join Queue

ü In cases with multiple servers, in some facilities customers may join a

single line.
Some Queuing Terminology - continued
ü When there are several lines, customers may choose the line they want to
join. In general, customers join the shortest line. Jockeying between lines
may be permitted.
Modeling Arrival and Service Processes
Arrival Process
ü Let’s denote by Xt the number of arrivals during a period of time t. The
most frequently used distribution for Xt is the Poisson distribution with
parameter lt.
Arrival Process -continued
ü The probability, P(Xt=k), of having k arrivals at the station during time t
is
(lt )k e-lt
P( X = k ) =
t k!

ü l is the average number of arrivals per unit time called also the arrival
rate.

ü E(Xt) = V(Xt) = lt
Arrival Process -continued
Example 1

80 customers on average come to a bank branch every day. Determine the

probability that 6 customers arrive to the bank during one hour.

l = 80 customers / day = 10 customers/hour

(λ𝑡)" e#$% 10" e#&'

P X! = 6 = = = 0.063
6! 6!
Arrival Process -continued
ü When the number of arrivals in interval of length t follow a Poisson

distribution with parameter lt, then interarrival times, Ta, are exponential.

with parameter l. P T( ≥ 𝑡 = )!"#

Indeed,

(λ𝑡)' e#$%
P 𝑇* > 𝑡 = P X! = 0 = = e#$%
0!
Arrival Process -continued
ü Figure below shows the density function for exponential distribution
Arrival Process -continued
ü The exponential distribution has the no-memory property. Suppose we are
told that there has been no arrival for the last t hours and asked what the
probability is that there will be no arrival during the next h hours.

P 𝑇* > 𝑡 + ℎ/𝑇* > 𝑡 = 𝑃(𝑇* > ℎ)

ü It implies that if we want to know the probability distribution of the time

until the next arrival, then it does not matter how long it has been since the
last arrival.
Arrival Process -continued
Example 2

Let's go back to the previous example and determine the probability that the

time between two successive arrivals does not exceed 6 minutes.

t = 6 min = 0.10 hour.

P T( ≤ 0.1 = 1 − 𝑒 #&'×'.& = 1 − 𝑒 #& = 0.6321

Arrival Process -continued
Remark
If interarrival times do not appear to be exponential, they are often modeled
by an Erlang distribution. An Erlang distribution is a continuous random
variable whose density function f(t) is specified by two parameters: a rate
parameter kl and a shape parameter k.
Modeling Arrival and Service Processes -continued
Service Process
ü Let’s denote by Yt the number of customers served during a period of time
t. The most frequently used distribution for Yt is the Poisson distribution
with parameter 𝜇𝑡. The probability, P(Yt=k), of having k customers served
during time t is k - µt
P(Yt = k) =
( µt ) e
k!
ü 𝜇 is the average number of customers served per unit time called also the
service rate. 1/𝜇 is the average time to serve a customer.
Service Process -continued
ü Similarly to arrivals process, the service times, Ts, are exponential. with

parameter 1/𝜇.

ü The probability, P(TS≤t), that this time is less than or equal to t is:

P T- ≥ 𝑡 = )!$#
Service Process -continued
Example 3
Given that 15 customers are served per hour, determine
1. the probability that 8 customers will be served in one hour.
2. the probability that a customer will be served in less than 3 minutes.
µ = 15 customers/hour.
&.% / !&'×&
1. P Y& = 8 = = 0.0194
0!

2. P T- ≤ 0.05 = 1 − 𝑒 #&.×'.'. = 0.5276

The Kendall–Lee Notation for Queuing Systems
ü The standard notation developed by Kendall (1951) is used to describe a

queuing system in which all arrivals wait in a single line until one of s

identical parallel servers is free.

ü Each queuing system is described by six characteristics: 1/2/3/4/5/6

(1) specifies the nature of the arrival process.

(2) specifies the nature of the service times

The Kendall–Lee Notation for Queuing Systems
(3) specifies the number of parallel servers

(4) describes the queue discipline

(5) specifies the maximum allowable number of customers in the system

(6) gives the size of the population from which customers are drawn

M is used to indicate interarrival and service times are iid and exponentially

distributed.
The Kendall–Lee Notation for Queuing Systems - continued

ü As an illustration of this notation, M/M/2/FCFS/¥/¥ represents a

queueing system with 2 servers, exponential interarrival times,

exponential service times, FCFS queue discipline, an illimited capacity of

the system and the population size is considered to be infinite.

ü In many important models 4/5/6 is FCFS/∞/∞. If this is the case, 4/5/6 is

often omitted.
Transient and Steady states

ü A system is said to be in a transient state when its behavior depends on the

observation time. In general, this is the case for the first phases of

operation of the system.

ü A system is said to be in a steady state when its behavior becomes

independent of time. This is the long-term behavior of the system.

Notations

ü Pn: The probability of having n customers (queue and service) in the

system.

ü ln: The average arrival rate to the system when there are already n
customers in the system.

ü µn: The average service rate of the system when there are already n
customers in the system.
Birth–Death Processes
ü Waiting phenomena suppose that arrivals and departures in a system take

place according to a dead birth process.

ü A birth and death process is a continuous-time stochastic process whose

states take on positive integer values.

ü The transition from state i to state i+1 is called birth while the transition

from state i to state i-1 is called death.

Birth–Death Processes - continued

ü In waiting phenomena, we are interested in studying the behavior of the

system in a steady state.

ü The steady state can only be established if the rate of arrivals to the
system is less than the rate of departures from the system, otherwise the
queue will lengthen over time and theoretically could become infinite.

ü To determine the probability of having n customers in the system, we use

the following transition diagram:
Birth–Death Processes - continued
l0P0 l1P1 ln-1Pn-1 lnPn

…
0 1 2 n-1 n n+1

µ1P1 µ2P2 µnPn µn+1Pn+1

ü When steady state is reached, the sum of the incoming flows to a given state
of the system is equal to the sum of the outgoing flows from this state.

-l0P0 + µ1P1 = 0 (1)

ln-1Pn-1 – (ln+ µn)Pn + µn+1Pn+1 = 0 ∀n¹0 (2)

Queuing System Performance Metrics

Some of these performance measures include:

ü The average number of customers waiting in the system (LS)

ü The average number of customers waiting in the queue (Lq)

ü The average waiting time per customer in the queue (Wq)

ü The average waiting time per customer in the system (WS)

ü Server utilization rate

Queuing System Performance Metrics - continued
Let’s denote by:
S: The number of servers;
leff: The average effective rate of arrival at the station

¥ ¥ ¥ ¥
LS = å nPn Lq = å (n - S ) P
n = s +1
n = å nP
n = s +1
n -S åP
n = s +1
n
n=0
¥
= LS - (0 ´ P0 + 1´ P1 + ... + S ´ PS + S åP )
n = s +1
n

= LS - S
Queuing System Performance Metrics - continued

LS = Lq + S
¥
leff = å ln Pn
n =0

To calculate the average times we use the following formulas called Little
formulas

LS = leff WS

Lq = leff Wq
Queuing System Performance Metrics - continued

The average The average

Average time
waiting = waiting + to serve a
time in time in
customer
the system the queue

If µ is the average service rate then 1/µ is the average time to serve a customer.
Thus:
WS = Wq + 1/µ
Queuing System Performance Metrics - continued
Multiplying this equation by leff we get

leff WS = leff Wq + leff /µ

LS = Lq + leff /µ

leff
LS = Lq + S where S =
µ

Server utilization rate = S

S
Queuing System Performance Metrics - continued

To sum up

¥
Pn LS = å nPn LS 1
WS = Wq = WS - Lq = leff Wq
n =0 leff µ

S = LS - Lq
Queuing System Performance Metrics - continued

M/M/1/FCFS/∞/∞
To reach a steady state we need to have l < µ
ln = l
µn = µ ∀ n ¹ 0
µ0 = 0
Equations (1) et (2) become :
-lP0 + µP1 = 0
lPn-1 – (l+µ)Pn + µPn+1 = 0 ∀n¹0
M/M/1/FCFS/∞/∞ - continued
P1 = l/µ P0

lP0 – (l+ µ)P1 + µP2 = 0 Thus

P2 = (l/µ)2 P0

Similarly, we can prove that

Pn = (l/µ)n P0 = rn P0

where r = l/µ < 1

¥ ¥ ¥
1
åP = 1 Û å r P0 = 1 Û P0 å r
n n
Or we have = 1 Û P0 = 1 Û P0 = 1 - r
1- r
n
n =0 n =0 n =0
M/M/1/FCFS/∞/∞ - continued
¥ ¥ ¥ ¥
L = å nP = å n r (1 - r ) = å n r - r å n r n
n n
S n
n =0 n =0 n =0 n =0
¥
ån r n
= r + 2 r 2
+3 r 3
+ .....
n=0
¥
r ån r n = r 2
+ 2 r 3
+ .....
n=0

¥ ¥
2 3
å n r - r å n r = r + r + r + .....
n n

n=0 n=0

¥ n ¥ n ¥ n 1- r n r l
L = å n r - r å n r = å r = lim r = =
S n®+¥ 1- r 1- r µ -l
n =0 n =0 n =1
M/M/1/FCFS/∞/∞ - continued
l
L =
S µ -l

leff = l
L 1 l 1 1
W = S = ´ = W =
S l S µ -l
eff
l µ -l µ -l

W =W - =
11 1
- =
l W =
l
q S µ µ -l µ µ (µ -l ) q µ (µ -l )

l2 l2
L =l W = L =
q eff q µ (µ -l ) q µ (µ -l )
Queuing System Performance Metrics - continued

(M/M/1) : (FCFS/N/¥)
Since the capacity of the system is limited to N, the queue cannot increase
indefinitely, then the steady state can be reached whatever the values of l and µ.
ln = l ∀ n < N
lN = 0
leff =l(P0+….+PN-1) = l(1-PN)
µn = µ ∀ n ¹ 0
µ0 = 0
M/M/1/FCFS/N/∞ - continued
-lP0 + µP1 = 0

lPn-1 – (l+ µ)Pn + µPn+1 = 0 ∀ n < N

P1 = l/µ P0

lP0 – (l+ µ)P1 + µP2 = 0 then P2 = (l/µ)2 P0

Similarly, we prove that Pn = (l/µ)n P0 ∀ n ≤ N

P n = rn P 0
M/M/1/FCFS/N/∞ - continued

N N n N n If r = 1 alors P0 = 1/(N+1)
å Pn = 1 Û å r P0 = 1 Û P0 å r = 1 Then
n =0 n =0 n =0 If r ≠ 1 alors P0 = (1-r) /(1-rN+1)

[1-( N +1) N + N N +1]

ì
ïr r r
ï Si r ¹1
(1- )(1- N +1)
ï
L
S
=í r r
ï
ïN Si r =1
ï
î 2
Queuing System Performance Metrics - continued

(M/M/S) : (FCFS/¥/¥)

To ensure the steady state l<Sµ.

ln = l ∀ n

leff =l

µn = nµ ∀ n ≤S

µn = Sµ ∀ n ≥S
M/M/S/FCFS/∞/∞ - continued
S -1 r n rS
P =[ å + ]-1
0 r
n =0 n! S!(1- )
S
ì n
r
ï
ï P0 Si n £ S
= ïí n! n
ï
P
n ï r
ï P0 Si n ³ S
ï n-S
îS
ï S!

r S +1
L = P0 + r
S
(S -1)(S - r ) 2