Queuing Models

Omar Alsawafy
1
 Look around…

• Patients waiting for doctors

• cars waiting for mechanics
• Parts waiting to be processed by a machine
• Vehicles waiting for the green light
• Planes waiting for landing
• Programs waiting for the computer processer

2
 What is the common Characteristics?

• Customer (entity) Wait Server

Why?
It is a result in Randomness in arrivals and service
times
How to reduce the waiting?
by scheduling arrivals (reducing the variability) and
fixing the service times
3
 Why to study Queuing models?

• Simulation is often used in the analysis of queuing

systems. In addition, it may help in the verification

• Typical measures of system performance:

Server utilization, length of waiting lines, and delays of customers

4
 Basic Elements
(Characteristics of Queuing System):
• Customer (entity)
• Server

• Calling source or calling population (finite or

infinite)
Finite arrival rate depends on the number of
customers being served and waiting.
Infinite arrival rate is not affected by the number
of customers being served and waiting.
5
 Basic Elements
(Characteristics of Queuing System):
• System size or System capacity
(finite or infinite)

• Arrival Process
- Arrivals of entities(single or bulk)
- For infinite-population (Random arrivals,
Scheduled arrivals, or at least one customer is
assumed to always be present)

6
 Basic Elements:

• Queue or Service discipline

( FCFS, LCFS, random, SPT, priority)
➢ First-Come, First-Served (FCFS): Customers are served
in the order of their arrival.
➢ Last-Come, First-Served (LCFS): The last customer to
arrive is served first.
➢ Service in Random Order (SIRO): Customers are
selected for service randomly.
➢ Shortest Processing Time (SPT): The customer with
the shortest service time is served first.
➢ Priority: Customers are assigned priorities, and the
one with the highest priority is served first. 7
 Basic Elements:

• Queue Behavior (Human behavior)

– Balking: the entity leaves the system without joining the queue
– Reneging: the entity leaves after joining the queue.
– Jockeying: the entity moves from line to line.

[Link]

8
 Basic Elements:

• Servers and Service Mechanism

(Single server or multi servers)
• Design of service facility ( series or parallel)

9
 Queuing Notation (Kendall's notation):

• A notation system for parallel server queues:

A/B/c/N/K
Component Description Examples
A Interarrival time distribution M (Markovian/Exponential), D
(Deterministic), G (General)
B Service time distribution M (Markovian/Exponential), D
(Deterministic), G (General)
c Number of parallel servers 1, 2, 3, ...
N System capacity A positive integer or ∞
K Size of the calling population A positive integer or ∞
M /M /1/∞/ ∞ ??
M /M /1
10
 Measures of Performance :

– 𝑳𝒔 : Expected number of customers in the system,

– 𝑳𝒒 : Expected number of customers in the queue,

– 𝑾𝒔 : Expected time spent in system per customer,

– 𝑾𝒒 : Expected time spent in queue per customer.

– 𝝆: Utilization of the server

11
 Measures of Performance :

– Consider a queuing system over a period of

time T

12
 Measures of Performance :

• time-weighted-average number of customers in a

system is defined by:
∞ ∞
1 𝑇𝑖
𝐿෠ = ෍ 𝑖𝑇𝑖 = ෍ 𝑖
𝑇 𝑇 13
𝑖=0 𝑖=0
 Measures of Performance :
A: Arrival Event
A4 D2 D: Departure Event

A3 D3

A1 D1 A2 D4

1 01 1 0 1
time-weighted-average number of customer in a
system is defined by:
Lˆ = [0(3) + 1(12) + 2(4) + 3(1)] / 20 = 23 / 20 = 1.15 customers
14
 Measures of Performance :
– Consider the total area under the function is L(t), then
∞
1 1 𝑇
𝐿෠ = ෍ 𝑖𝑇𝑖 = න 𝐿(𝑡)𝑑𝑡
𝑇 𝑇 0
𝑖=0

– As T gets large, approaches a limiting value L which is called the long-

run time-average number of customers in system, with probability 1:
1 𝑇
𝐿෠ = න 𝐿(𝑡)𝑑𝑡 → 𝐿 as 𝑇 → ∞
𝑇 0
– Similarly, the time-weighted-average number of customers in queue is:
∞ 𝑇
1 𝑄 1
𝐿෠ 𝑄 = ෍ 𝑖𝑇𝑖 = න 𝐿𝑄 (𝑡)𝑑𝑡 → 𝐿𝑄 as 𝑇 → ∞
𝑇 𝑇 0
𝑖=0

15
 Measures of Performance :

Suppose that figure 6 shown in slide 11 refers to a

single server G/G/1/N/K queuing system where
N ≥ 3, K ≥ 3. Then the number of customers waiting
in queue is given by:
0, if 𝐿(𝑡) = 0
𝐿𝑄 (𝑡) = ቊ
𝐿(𝑡) − 1, if 𝐿(𝑡) ≥ 1

ˆ 0(15) + 1(4) + 2(1)

LQ = = 0.3 customers
20 16
 Measures of Performance :

• The average time spent in system per customer, called the average
system time, is: N
1
wˆ =
N i =1Wi

– For stable systems: wˆ → w as N → 

W1 + W2 + ... + W5 2 + (8 − 3) + (10 − 5) + (14 − 7) + (20 − 16)
wˆ = = = 4.6 time units
5 5

– The same can be done for the queue

17
 Measures of Performance :

• What about Utilization of the server? How can you find it?

18
 General Queuing Model:

• 𝝀: mean arrival rate,

𝟏
• mean Inter- arrival time,
:
𝝀
• 𝝁 : mean service rate (departure rate) of one
server,
𝟏
• :
mean service time (Inter-departure time) of
𝝁
one server,
• 𝑪 : number of parallel servers,
• 𝑪𝝁: mean service rate of C servers,
• 𝑷𝒏 : steady-state probability of having n customers
in system,
19
 General Queuing Model:

– The Conservation Equation (Little’s law):

𝑳𝒔 = 𝝀 𝑾𝒔
𝑳𝒒 = 𝝀 𝑾𝒒

– Server Utilization (𝜌):

𝜆
𝜌= Single server
𝜇
𝜆
𝜌= C parallel servers
𝐶𝜇

– 𝜌 < 1 ----> reach steady state (not accumulating)

20
 General Queuing Model:

Example:
• Consider 40 customers/hour visit a supermarket
• Average customer spend 15 minutes in the supermarket
• What is average number of customers at given time?

• 𝜆 = 40 𝑐𝑢𝑠𝑡𝑜𝑚𝑒𝑟𝑠/ℎ𝑟
• 𝑊𝑠 = 15 𝑚𝑖𝑛

𝟏𝟓
• 𝑳𝒔 = 𝝀 𝑾𝒔 = 𝟒𝟎 ∗ = 𝟏𝟎 𝒄𝒖𝒔𝒕𝒐𝒎𝒆𝒓𝒔
𝟔𝟎

21
Parallel Queuing Model:

22
Parallel Queuing Models:

23
Parallel Queuing Models:

24
 Parallel Queuing Models:

the steady-state time average number of customers in the shop

25
Parallel Queuing Models:

26
Parallel Queuing Models:

 The probability that system is empty (all servers

are idle)

• The probability that there are three customers in

the system (the system is full)

27
Parallel Queuing Models:

28
Parallel Queuing Models:

29
 M/M/1: Derivation

• balance equations
• For n = 0: R𝑎𝑡𝑒𝑜𝑢𝑡 = 𝑅𝑎𝑡𝑒𝑖𝑛 → 𝜆𝑃0 = 𝜇𝑃1
• For n ≥ 1: R𝑎𝑡𝑒𝑜𝑢𝑡 = 𝑅𝑎𝑡𝑒𝑖𝑛 → (𝜆 + 𝜇)𝑃𝑛 = 𝜆 · 𝑃𝑛−1 + 𝜇 · 𝑃𝑛+1
𝜆
• Solving the first equation gives 𝑃1 = 𝜇 𝑃0 = 𝜌𝑃0

• By recursively solving the general balance equation, we can establish a pattern:

𝑃𝑛 = 𝜌 ⋅ 𝑃𝑛−1 = 𝜌2 ⋅ 𝑃𝑛−2 =. . . = 𝜌𝑛 ⋅ 𝑃0

• To find 𝑃0 , we use the normalization condition that all probabilities must sum to 1:
∞ ∞

෍ 𝑃𝑛 = 1 → 𝑃0 ⋅ ෍ 𝜌𝑛 = 1
𝑛=0 𝑛=0
This is a geometric series, which converges to 1/(1-ρ) provided that ρ < 1. Therefore:
• 𝑃0 = 1 − 𝜌
𝑃𝑛 = 1 − 𝜌 𝜌𝑛 , 𝑓𝑜𝑟 𝑛 = 0,1,2, . . .
30
 M/M/1: Derivation

𝑃𝑛 = 1 − 𝜌 𝜌𝑛

∞ ∞
𝜌 𝜌 𝜆
𝐿𝑠 = ෍ 𝑛𝑃𝑛 = 1 − 𝜌 ෍ 𝑛𝜌𝑛 = 1 − 𝜌 . 2
= =
1−𝜌 1−𝜌 𝜇−𝜆
𝑛=0 𝑛=0

Using Little’s Law (L = λw):

𝐿 𝜆 1
𝑤= = =
𝜆 𝜆(𝜇 − 𝜆) 𝜇 − 𝜆

𝐿𝑞
Same concept for queue 𝐿𝑞 = σ∞
𝑛=𝑐(𝑛 − 𝑐)𝑃𝑛 and 𝑤 = 𝜆

31
 M/M/c: Derivation
Expected time in the system=expected time in the queue+ mean service time
1
𝑊𝑠 = 𝑊𝑞 +
𝜇
Multiply by 𝜆
𝜆 𝑳𝒔 = 𝝀 𝑾𝒔
𝜆𝑊𝑠 = 𝜆𝑊𝑞 +
𝜇 𝑳𝒒 = 𝝀 𝑾 𝒒
𝜆
𝐿𝑠 = 𝐿𝑞 +
𝜇
𝜆
(𝜇 is the expected number of busy servers)
∞

𝐿𝑠 = ෍ 𝑛𝑃𝑛
𝑛=0
∞

𝐿𝑞 = ෍ (𝑛 − 𝑐)𝑃𝑛
𝑛=𝑐 32
 M/M/c: Derivation
𝜆
𝐶 = + 𝐶𝑖
𝜇
𝜆
( is the expected number of busy servers)
𝜇
(𝐶𝑖 is the expected number of Idle servers)
𝑐

𝐶𝑖 = ෍ (𝑐 − 𝑛)𝑃𝑛
𝑛=0
Utilization of servers:
𝐶 − 𝐶𝑖 𝜆
= ∗ 100% = ∗ 100%
𝐶 𝐶𝜇

33
 Steady – State Equations for Systems with limited
capacity (N) :
𝜆 = 𝜆𝑒𝑓𝑓 + 𝜆𝑙𝑜𝑠𝑡 = 𝜆𝑒𝑓𝑓 + 𝜆𝑃𝑁
1 𝑷𝑵 : probability of lost entity (Balking),
𝑊𝑠 = 𝑊𝑞 +
𝜇 𝝀𝒆𝒇𝒇 : effective mean arrival rate,
Multiply by 𝜆𝑒𝑓𝑓 𝝀𝒆𝒇𝒇 = 𝝀(𝟏 − 𝑷𝑵 )

𝜆𝑒𝑓𝑓
𝜆𝑒𝑓𝑓 𝑊𝑠 = 𝜆𝑒𝑓𝑓 𝑊𝑞 +
𝜇
𝑳𝒔 = 𝝀𝒆𝒇𝒇 𝑾𝒔
𝜆𝑒𝑓𝑓
𝐿𝑠 = 𝐿𝑞 + 𝑳𝒒 = 𝝀𝒆𝒇𝒇 𝑾𝒒
𝜇
𝜆𝑒𝑓𝑓
( is the expected number of busy servers)
𝜇

34
 Steady – State Equations for Systems with limited
capacity :
𝑁

𝐿𝑠 = ෍ 𝑛𝑃𝑛
𝑛=0
𝑁

𝐿𝑞 = ෍ (𝑛 − 𝑐)𝑃𝑛
𝑛=𝑐
𝜆𝑒𝑓𝑓
𝐶= + 𝐶𝑖
𝜇
𝜆𝑒𝑓𝑓
( is the expected number of busy servers)
𝜇
(𝐶𝑖 is the expected number of Idle servers)
𝑐

𝐶𝑖 = ෍ (𝑐 − 𝑛)𝑃𝑛
𝑛=0
Utilization of servers:
𝐶 − 𝐶𝑖 𝜆𝑒𝑓𝑓
= ∗ 100% = ∗ 100% 35
𝐶 𝐶𝜇
 Steady – State Equations for Systems with limited
capacity :
Example:
Cars arrive to an automated car wash station at rate of 5
cars per hour. The carwash station has only one service
lane. The expected service time for one car is 10 minutes.
The capacity of the station is 7 cars only (M/M/1/7/∞).
Whenever a car arrive and find the station full it will go to
another station. Given that the probability of having n cars
in the station is:
𝒏
𝜆
𝑷𝟎 , 𝒏 = 𝟎, 𝟏, 𝟐, … , 𝟕
• 𝑷𝒏 = ቐ 𝝁
𝟎, 𝒐𝒕𝒉𝒆𝒓𝒘𝒊𝒔𝒆

36
 Steady – State Equations for Systems with limited
capacity :
Example:
• Find the probability of having n cars in the station:
Arrival rate 𝝀=5 cars/hr
1 1
Departure or service rate 𝝁 = = = 𝟔 cars/hr
𝑠𝑒𝑟𝑣𝑖𝑐𝑒 𝑡𝑖𝑚𝑒 10 ℎ𝑜𝑢𝑟𝑠
60
𝑷𝟎 𝟎. 𝟖𝟑𝟑 𝒏 , 𝒏 = 𝟎, 𝟏, 𝟐, … , 𝟕
𝑷𝒏 = ቊ
𝟎, 𝒐𝒕𝒉𝒆𝒓𝒘𝒊𝒔𝒆
n 0 1 2 3 4 5 6 7
0.833^n 1 0.83 0.69 0.58 0.48 0.40 0.33 0.28 4.60
𝟕

෍ 𝑷𝒏 = 𝟏 −−→ 𝟒. 𝟔𝑷𝟎 = 𝟏 −−→ 𝑷𝟎 = 0.217

𝒏=𝟎
𝟎. 𝟐𝟏𝟕 𝟎. 𝟖𝟑𝟑 𝒏 , 𝒏 = 𝟎, 𝟏, 𝟐, … , 𝟕
𝑷𝒏 = ቊ
𝟎, 𝒐𝒕𝒉𝒆𝒓𝒘𝒊𝒔𝒆 37
 Steady – State Equations for Systems with limited
capacity :
Example:
• Find the probability of lost car (balking)?
= 𝑷𝑵 = 𝑷𝟕 = 𝟎. 𝟐𝟏𝟕 𝟎. 𝟖𝟑𝟑 𝟕 = 𝟎. 𝟎𝟔𝟏

• Find the effective arrival rate?

𝝀𝒆𝒇𝒇 = 𝝀 𝟏 − 𝑷𝑵 = 𝟓 𝟏 − 𝟎. 𝟎𝟔𝟏 = 𝟒. 𝟕 cars/hr

• Find the utilization of the station?

One lane = single server➔ C=1
𝜆𝑒𝑓𝑓 4.7
• 𝜌= = = 0.783 = 78.3%
𝐶𝜇 1∗6 38
 Steady – State Equations for Systems with limited
capacity :
Example:
• Find the average number of cars in the Station?
𝑁

𝐿𝑠 = ෍ 𝑛𝑃𝑛
𝑛=0
= 0 ∗ 𝑃0 + 1 ∗ 𝑃1 + 2 ∗ 𝑃2 + 3 ∗ 𝑃3 + 4 ∗ 𝑃4 + 5 ∗ 𝑃5 + 6 ∗ 𝑃6 + 7 ∗ 𝑃7 = 2.58

• Find the average number of cars waiting for service (average

number in the queue, waiting)?
𝑁 7

𝐿𝑞 = ෍ (𝑛 − 𝑐)𝑃𝑛 = ෍ (𝑛 − 1) 𝑃𝑛
𝑛=𝑐 𝑛=1
= 0 ∗ 𝑃1 + 1 ∗ 𝑃2 + 2 ∗ 𝑃3 + 3 ∗ 𝑃4 + 4 ∗ 𝑃5 + 5 ∗ 𝑃6 + 6 ∗ 𝑃7
= 1.79 39
 Steady – State Equations for Systems with limited
capacity :
Example:
• Find the average waiting time of a car in the Station?
𝑳𝒔 = 𝝀𝒆𝒇𝒇 𝑾𝒔
𝑾𝒔 =? ?

• Find the average waiting time of a car waiting for service

(average time in the queue, waiting)?
𝑳𝒒 = 𝝀𝒆𝒇𝒇 𝑾𝒒
OR
𝟏
𝑾𝒔 = 𝑾𝒒 +
𝝁
40