Module 2 – Queuing

Analysis

1
Queuing Models
• Queuing models are mathematical representations of waiting lines for
analyzing system performance and understanding customer wait
times, service efficiency, and resource utilization.

• Queuing systems consist of 3 main components:

e.g. Exponential, uniform, triangular
• Arrivals: Inputs of the system following specific probability
distributions of inter-arrival time.

• Queue: Where customers wait according to a queue discipline (e.g.

FIFO or LIFO)e.g. by priority such as in medical system

• Servers: The process customers go through following specific

probability distributions of service time.
e.g. Exponential, uniform, triangular 2
Applications of Queuing Models
• Healthcare (patient flow management): Optimize patient wait times
and resource allocation in hospitals, reducing bottlenecks in
emergency rooms and clinics.

• Telecommunications (network traffic management): Manage data

packet flow in networks to prevent congestion and improve quality of
service.

• Manufacturing (production line optimization): Minimize machine

downtime and optimize workflows in assembly lines.

• Transportation (airport operations): Streamline passenger check-in,

security screening, and baggage handling processes.

3
Applications of Queuing Models
• Retail (customer service efficiency): Reduce wait times at checkout
counters and improve customer satisfaction.

• Call centers (call handling efficiency): Balance agent availability with

incoming call volume to minimize customer wait times.

• Banking (branch service optimization): Optimize teller service

efficiency to reduce customer wait times in bank branches.

• Public services (queue management): Improve service delivery and

reduce waiting times for services like DMV or passport issuance.

4
 A Queuing Model

Arrive at System

Queue Service Exit System

In the System

System = Queue + Service

5
Arrival Characteristics
Arrival follows Poisson distribution <-> Inter-
• Arrival process: arrival time follows normal distribution
• Customers arrive randomly over time following a probability
distribution (e.g. Poisson distribution).
• Arrival rate (λ): Average number of arrivals per time unit.
• Interarrival time:
• Time between consecutive arrival following a probability
distribution (e.g. exponential distribution).
• Mean Interarrival Time (1/λ): Average time between arrivals.
• Batch arrivals:
• Multiple customers may arrive simultaneously.
• May be easier to analyze using simulation.

6
 A discrete probability distribution is used
to model counts of events (arrivals), but
Poisson Distribution lambda can be in decimals as it’s average
arrival rate
• Poisson distribution is commonly used to model the number of
arrivals in a fixed period (i.e. a discrete distribution).

• Assumes the events (arrivals) occur independently and at a constant

average rate (λ).
Input variable
𝑒 −𝜆 𝜆𝑥 (lambda) is the
𝑃 𝑋 = arrival rate, which
𝑥! is used to
calculate
• 𝑃 𝑋 : probability of x arrivals probability P(X) of
• 𝑥 : number of arrivals per unit of time any number of
arrivals in a
• 𝜆: average arrival rate period
• 𝑒: 2.7183

7
Poisson Distribution

High probabilities are near the average rate of arrival

(lambda). Low lambda values result in high
probabilities of low x-values in the Poisson distribution.
This is quite common in many industries (such as
insurance) where most periods don’t have many
occurrences (e.g. accidents)

8
Exponential Distribution
• Exponential distribution is a continuous probability distribute
commonly used to model the time between events in a Poisson
process.

• Exponential distribution is memoryless: the probability of an event

occurring in the future is independent of the past.
1
• Mean: The input variable is still lambda (arrival rate), whose
𝜆
1
inverse in the parameter in exponential distribution
• Variance:
𝜆2
• Probability Density Function (PDF): 𝑓 𝑡 = 𝜆𝑒 −𝜆𝑡
• 𝑡: Time between events
• 𝜆: Rate parameter (average number of events per time unit)

9
Exponential Distribution

The graphs show high probabilities for low inter-arrival

times (most people arrive within short time gaps)

10
Queue (Waiting Line) Characteristics
• Queue structure:
• FIFO (First-In, First-Out): Most common discipline.
• LIFO (Last-In, First-Out): Used in stack-like systems.
• Priority Queuing: Customers are served based on priority.
• Queue length:
• Infinite Queue: No limit to the number of customers waiting.
• Finite Queue: Maximum number of customers allowed.
• Customer behavior:
• Balking: Customers may not join if the queue is too long.
• Reneging: Customers may leave after joining the queue.
• Jockeying: Moving between queues to reduce wait time.

The more complex customer behavior need to be

analyzed with other more complex methods such as
simulation
11
Service Characteristics
• Service process:
• Time taken to serve a customer.
• Service rate (μ): Average number of customers served per period
following a probability distribution (exponential, uniform, etc.)
• Service mechanisms:
• Single Server: One server attending to customers.
• Multiple Servers: Multiple servers, each with their queue or
shared queue.
• Service discipline:
• FCFS (First-Come, First-Served): Common in most systems.
• Preemptive Priority: Higher priority customers interrupt service.

The more complex service behavior need to be

analyzed with other more complex methods such as
simulation
12
Little’s Law in Queuing Models
• Queueing models analyze the steady-state of a system (with
continuous input and output).

• Little’s Law can be applied for the entire system:

𝐿 = 𝜆𝑊 = 𝐿𝑞 + 𝐿𝑠
System = Queue + Service
• Or part of the system:
An important
assumption of
Queue (Waiting Line): 𝐿𝑞 = 𝜆𝑊𝑞 queuing models is
that service rate >
arrival rate, so arrival
Service: 𝐿𝑠 = 𝜆𝑊𝑠 rate won’t change in
the queue or service

13
Types of Queuing Models
• Queuing models are described using the A/B/c notation.

• A: Distribution of time between arrivals

• M: Exponential inter-arrival or service time distribution
• D: Uniform distribution (constant inter-arrival or service time)

• B: Distribution of service times

• c: Number of parallel servers (e.g. cashiers)

14
Types of Queuing Models
• Examples:

• M/M/1: Single server, exponential inter-arrival and service times

• M/M/c: Multiple servers, exponential inter-arrival and service times

• M/M/ꝏ: Multiple servers, exponential inter-arrival and service times

• M/D/1: Single server, exponential inter-arrival times and uniform

service times

• Each of the above can have finite or infinite queue.

15
M/M/1
• Single server queue with Poisson arrivals (exponential inter-arrival
times) and exponential service times.

• An infinite population arrives in a Poisson process, waits in a FIFO

queue, and gets served with following an exponential distribution.
service times.

• 𝜆: Arrival rate (average number of arrivals per period)

• 𝜇: Service rate (average number served per period)

• 𝜇 > 𝜆: Service rate must be greater than arrival rate to avoid building
up the queue. These formulas will not work if service rate < arrival rate (in
this case, use simulation to analyze the system)
16
 The formulas are derived from Markov chain models
M/M/1 (for those interested in learning more)

𝜆 This is a ratio of arrival

• Server utilization (traffic intensity): 𝜌 = rate to service rate
𝜇
𝜆
• Average number of customers in system: 𝐿 =
𝜇−𝜆
𝐿 1
• Average time in System: 𝑊 = =
𝜆 𝜇−𝜆
𝜌2 𝜆2
• Average number of customers in queue: 𝐿𝑞 = =
1−𝜌 𝜇(𝜇−𝜆)

𝐿𝑞 𝜆 Many formulas here

• Average waiting time in queue: 𝑊𝑞 = = can be derived from
𝜆 𝜇(𝜇−𝜆)
the Little’s Law

• Average number of customers in service: 𝐿𝑠 = 𝐿 − 𝐿𝑞 = 𝜆/𝜇

17
M/M/c
• Multi-server queue with 𝑐 servers, Poisson arrivals (exponential inter-
arrival times) and exponential service times.

• Server utilization:
𝜆 With c servers, the service
𝜌= capacity (rate) is multiplied by c
𝑐𝜇

• Probability of zero customers in system:

−1
𝑐−1 𝑛 𝑐
1 𝜆 1 𝜆 𝑐𝜇
𝑃0 = ෍ +
𝑛! 𝜇 𝑐! 𝜇 𝑐𝜇 − 𝜆
𝑛=0

18
M/M/c
𝜆 𝑐
𝑃0 𝜌
𝜇
• Average number of customers in queue: 𝐿𝑞 =
𝑐! 1−𝜌 2

𝐿𝑞 Many formulas here can be

• Average waiting time in queue: 𝑊𝑞 = derived by the Little’s Law
𝜆

• Average number of customers in service: 𝐿𝑠 = 𝜆/𝜇

𝜆 2
𝑃0 𝜇 𝜌
• Average number of customers in system: 𝐿 = 𝐿𝑞 + 𝐿𝑠 = + 𝜆/𝜇
𝑐! 1−𝜌 2

• Average waiting time in system: 𝑊 = 𝑊𝑞 + 1/𝜇

19
M/D/1
• Single server queue with Poisson arrivals and constant (deterministic)
service times.

𝜆
• Server utilization: 𝜌 =
𝜇
𝜌2 𝜆2
• Average number of customers in queue: 𝐿𝑞 = =
2(1−𝜌) 2𝜇(𝜇−𝜆)

• Average number of customers in system: 𝐿 = 𝐿𝑞 + 𝜌 = 𝐿𝑞 + 𝜆/𝜇

𝐿𝑞 𝜆 Many formulas
• Average waiting time in queue: 𝑊𝑞 = = here can be
𝜆 2𝜇(𝜇−𝜆)
derived by the
Little’s Law
𝐿
• Average waiting time in system : 𝑊 =
𝜆
20
M/M/ꝏ
• Queue with an infinite number of servers, Poisson arrivals, and
exponential service times.

• Average number of customers in system:

𝜆
𝐿=
𝜇

• Average waiting time in system:

𝐿 1
𝑊= =
𝜆 𝜇

21
M/M/1/K
• Single server queue with Poisson arrivals, exponential service times,
and a finite system capacity 𝐾 (e.g. A clinic can only accommodate up
to 10 people being treated and waiting).

𝜆
• Server utilization: 𝜌 =
𝜇

1−𝜌 𝜌𝑛
• Probability of 𝑛 customers in the system: 𝑃𝑛 = = 𝑃0 𝜌𝑛
1−𝜌𝐾+1

1−𝜌
• Probability of 0 customers in the system: 𝑃0 =
1−𝜌𝐾+1

1−𝜌
• Probability of 𝐾 customers in the system: 𝑃𝐾 = 𝐾+1 𝜌𝐾
1−𝜌

22
M/M/1/K
• Average number of customers in the system:

Intuitively, this is the

𝐾
𝜌 𝐾 + 1 𝜌𝐾+1 expected # of
𝐿 = ෍ 𝑛𝑃𝑛 = − customers in the
1−𝜌 1 − 𝜌𝐾+1
𝑛=0 system

• Average number of customers in the queue: 𝐿𝑞 = 𝐿 − 1 − 𝑃0

Here, 𝐿𝑆 is the expected # of customers in service: 1 1 − 𝑃0 + 0(𝑃0 ) = 1 1 − 𝑃0

𝐿
• Average time in the system: 𝑊 = The effective arrival rate is
𝜆 1−𝑃𝐾
𝜆 multiplied by the
probability of less than K
𝐿𝑞
• Average time in the queue: 𝑊𝑞 = customers (K is maximum
𝜆 1−𝑃𝐾
allowed).

23
Other Scenarios
• Single queues with a sequence of multiple servers:

Queue Servers

Servers

Queue

Servers

24
Other Scenarios
• Not entering the system (balking), leaving the system while waiting
(reneging), or cutting into lines (jockeying)
• Other types of queue discipline (LIFO, prioritization in healthcare
systems, etc.)
• Other distributions of service time (e.g. normal distribution, triangular
distribution)
• Other distributions of arrivals

• Arrivals in batches

• Finite population

• More complex systems such as the ones above are solved more
efficiently using simulation.

25