Queuing Theory

Presented by
Dr. G. Somasekhar
Associate Professor
VSB, VIT-AP University
Amaravati
 What is Queuing theory?
⮚ Queuing theory (or queueing theory) refers to the mathematical study of the formation,
function, and congestion of waiting lines, or queues.

⮚ Queuing theory scrutinizes the entire system of waiting in line, including elements like
the customer arrival rate, number of servers, number of customers, capacity of the
waiting area, average service completion time, and queuing discipline.
 What is Queuing theory? Cont.
⮚A flow of customers from infinite/ finite population towards the
service facility forms a queue (Waiting Line)

⮚From a business sense, queuing theory informs the construction of

efficient and cost-effective workflow systems.

⮚Why Queue form?

⮚When no of customer exceed no of server
⮚Server do not work efficiently and take more time than prescribed
to serve the customer
 What is Queuing theory? Cont..
⮚It has two parts.

⮚Someone or something that requests a service—usually referred to as

the customer, job, or request.

⮚Someone or something that completes or delivers the services—usually

referred to as the server.

⮚Example of bank, the customers are people seeking to deposit or

withdraw money, and the servers are the bank tellers.
Examples of Queuing
 Components of Queuing system

⮚ Arrival Process
⮚ Arrival defines they way customers enter the system. Mostly the arrivals are
random intervals between two adjacent arrivals.
⮚ Queue Configuration
⮚ It refers to no. of queues in the system, their relationship to the servers. A
queue may single or multiple queue.
⮚ Queue Discipline
⮚ It indicates the order in which the member of the queue are selected for
service.
⮚ There are three main ways of queue discipline
⮚ FIFO
⮚ LIFO
⮚ SIRO
 Components of Queuing system cont.

⮚Service Process
⮚How long the service will take?
⮚How many number of servers available?
⮚Whether the servers are in series or in parallel?
 History
⮚Queuing theory was first introduced in the
early 20th century by Danish mathematician
and engineer Agner Krarup Erlang.

⮚He sought to determine how many circuits

were needed to provide an acceptable level
of telephone service, for people not to be
“on hold” (or in a telephone queue) for too
long. He was also curious to find out how
many telephone operators were needed to
process a given volume of calls.
 Queuing system cost
⮚Cost of providing the service. This is also known as the service cost .
⮚ Examples of this type of cost include wages paid to servers, the cost of buying an extra
machine, and the cost of constructing a new teller window at a bank

⮚ Cost of not providing the service. This is also known as the waiting cost
and is typically the cost of customer dissatisfaction.
⮚ Example If a facility has just a minimum number of checkout lines, pumps, or teller windows
open, the service cost is kept low, but customers may end up with long waiting times in the
queue. How many times would you return to a large department store that had only one
cash register open every time you shop? As the average length of the queue increases and
poor service results, customers and goodwill may be lost.
 Applications of Queuing theory
⮚Queuing theory has been applied, just to name a few, to:

⮚telecommunications
⮚transportation
⮚logistics
⮚finance
⮚emergency services
⮚computing
⮚industrial engineering
⮚project management
Formulas for Queuing theory
 Formulas for Queuing theory
Symbo Meaning Formula
l
λ Arrival rate (Customers/hr)
μ Service Rate (Customers/hr)
ρ Utilization Factor (λ/μ)
Ls Avg. no in the system (customers) (λ/μ-λ)

Lq Avg. no in the queue (customers) ρ*Ls

Ws Avg. Time in System (hrs) 1/μ-λ

Wq Avg. Time in queue (hrs) ρ*Ws
P0 Idle Probability 1-ρ
Pbusy Busy probability ρ
P(n>) Probability of more than n customers in the system n+1
ρ
P(n≥) Probability of more than n customers in the system n
ρ
 Problem 1

• At barbers shop, customers arrive at the average interval of 6 minutes

and the barber takes on an average 5 minutes for serving the person:
Calculate:
⮚Counter utilization level
⮚Average number of customers in the service
⮚Average number of customers in the queue
⮚Average waiting time of customers in the system
⮚Expected average waiting time in the queue
⮚Probability that the barber is idle
⮚Probability that the barber is busy
 Problem 1 cont.

⮚Arrival rate λ=60/6=10 customer per hour

⮚Service rate μ= 60/5=12 customer per hour
⮚Counter utilization level ρ=(λ/μ)=10/12=5/6=0.833
⮚Average number of customers in the service Ls= (λ/μ-λ)=(10/12-10)=5 Customers
⮚Average number of customers in the queue Lq = ρ*Ls = 0.833*5=4.17 Customers
⮚Average waiting time of customers in the system Ws =(1/μ-λ)= (1/12-10)=0.5 Hr.
⮚Expected average waiting time in the queue Wq = ρ*Ws =0.833*0.5=25 Mins
⮚Probability that the barber is idle P0=1-ρ
⮚Probability that the barber is busy Pbusy =ρ =0.833
 Problem 2
• At barbers shop, customers arrive at the average interval of 6 minutes
and the barber takes on an average 5 minutes for serving the person:
Calculate:
⮚Probability of finding more than 3 customers in system
⮚Probability of finding more than 3 ore more than 3 customers in system
⮚Chances that customer is required to wait more than 30 minutes in the
system
⮚Chances that customer is required to wait more than 30 minutes in the queue
 Problem 2 cont.

⮚Arrival rate λ=60/6=10 customer per hour

⮚Service rate μ= 60/5=12 customer per hour
⮚Probability of finding more than 3 customers in system P(n>)=ρn+1 = 0.8334=0.482
⮚Probability of finding more than 3 or more than 3 customers in system= P(n≥)=
ρ=.587
• Chances that customer is required to wait more than 30 minutes in the system=
=ε-(μ-λ)t = ε-(12-10)0.5=0.3678
⮚Chances that customer is required to wait more than 30 minutes in the queue = ρ
ε-(μ-λ)t
⮚ 0.3066
 Poisson Distribution
⮚The probability distribution that is used to show how many times an
event is likely to occur over a specified period.
⮚A Poisson distribution is a discrete probability distribution. It gives the
probability of an event happening a certain number of times (k)
within a given interval of time or space. The Poisson distribution has
only one parameter, λ (lambda), which is the mean number of events
Where:

⮚ X is a random variable following a Poisson distribution

⮚ k is the number of times an event occurs
⮚ P(X = k) is the probability that an event will occur k times
⮚ e is Euler’s constant (approximately 2.718)
⮚ λ lambda is the average number of times an event occurs
⮚ ! is the factorial function
 Poisson Distribution example

⮚Text messages per hour

⮚Machine malfunctions per year
⮚Website visitors per month
⮚Influenza cases per year
Poisson Distribution cont.
 Poisson Distribution cont.
An average of 0.61 soldiers died by horse kicks per year in each Russian army corps. You want
to calculate the probability that exactly two soldiers died in the 7 Army Corps in 1898, assuming
that the number of horse kick deaths per year follows a Poisson distribution.

Solution:
k = 2 deaths by horse kick
λ = 0.61 deaths by horse kick per year
e = 2.718

P(X = k) =

P(X = 2) =

P(X = 2) =

P(X = 2) = 0.101

The probability that exactly two soldiers died in the VII Army Corps in 1898 is 0.101.
 Poisson Distribution cont.
A road transport company has one reservation clerk on duty at a time He handles information of
bus schedule & makes reservations. Customers arrive at a rate of 8 per hour and the clerk can
service 12 customers on average per hour. Answer the following

1. What is the average no of customers waiting for service of the clerk?

2. What is the average time customer has to wait before getting service?
3. The management is planning to install a computer system to serve customers. This is
expected to reduce service time from 5 minutes to 3 minutes. The additional cost of having
the new system works out to Rs. 50/day. If the cost of goodwill of having a customer to wait
is estimated to be 12 paisa/minute spent waiting before served, should the company install
new computer system. Assume 8 hours of work hours per day.

⮚Arrival rate λ=8 customer per hour

⮚Service rate μ= 12 customer per hour
⮚Counter utilization level ρ=(λ/μ)=8/12=0.666
 Poisson Distribution cont.
⮚Arrival rate λ=8 customer per hour
⮚Service rate μ= 12 customer per hour
⮚Counter utilization level ρ=(λ/μ)=8/12=0.666 8*8*10
⮚Average number of customers in the service Ls= (λ/μ-λ)=(8/12-8)=2 Customers
⮚Average number of customers in the queue Lq = ρ*Ls = 0.666*2=1.332 Customers

⮚Average waiting time of customers in the system Ws =(1/μ-λ)= (1/12-8)=0.25 Hr.

⮚Expected average waiting time in the queue Wq = ρ*Ws =0.666*0.25=0.1665 Hr.
⮚Expected waiting for all customers in a day=8* λ* Wq= 8*8*0.1665= 10.65Hr.
 Exponential Distribution cont.
The Exponential Distribution is one of the widely used continuous distributions. It
describes the times in between events, a process in which events occur
continuously and independently at a constant average rate.
 Poisson Distribution cont.
Arrival rate of telephone calls at a telephone booth follows Poisson Distribution with an average
times of 9 minutes between two consecutive calls. The length of the call is assumed to be
exponentially distributed with mean of 3 minutes:
1. Determine the probability that a person arriving at the telephone booth have to wait
2. Find the average queue length that is formed from time to time
3. The telephone company will install a second booth when convinced that an arrival would
expect to have to wait at least 4 minutes for the phone. Find increase in rate of arrival.

⮚ Arrival rate λ=
⮚ Service rate μ=
⮚ Counter utilization level ρ=(λ/μ)=
⮚ Average number of customers in the service Ls= (λ/μ-λ)
⮚ Average number of customers in the queue Lq = ρ*Ls = Average waiting time of customers in the system
Ws =(1/μ-λ)=
⮚ Expected average waiting time in the queue Wq = ρ*Ws =
⮚ Probability that the barber is idle P0=1-ρ
 Kendall’s Notation
⮚ Queuing theory uses the Kendall notation to classify the different types of queuing systems, or
nodes. Queuing nodes are classified using the notation A/S/c/K/N/D where:

⮚ A is the arrival process

⮚ S is the mathematical distribution of the service time
⮚ c is the number of servers
⮚ K is the capacity of the queue, omitted if unlimited
⮚ N is the number of possible customers, omitted if unlimited
⮚ D is the queuing discipline, assumed first-in-first-out if omitted

⮚ For example, think of an ATM.

⮚ It can serve: one customer at a time; in a first-in-first-out order; with a randomly-distributed
arrival process and service distribution time; unlimited queue capacity; and unlimited number
of possible customers.
 Little’s law
⮚Little's Law states that the average number of items within a system
equals the average arrival rate of items into and out of the system
multiplied by the average amount of time an item spends in the system.

⮚The Little's Law formula is: L = λ x W

⮚L is the average number of customers in the system

⮚λ (lambda) is the average arrival rate into the system
⮚W is the average amount of time spent in the system
 Example of Little’s law

⮚For example, if you’re waiting in line at a Starbucks, Little’s Law can

estimate how long it would take to get your coffee.
⮚Assume there are 15 people in line, one server, and 2 people are
served per minute. To estimate this, you’d use Little’s Law in the form:
⮚The Little's Law formula is: L = λ x W
⮚L is the average number of customers in the system
⮚λ (lambda) is the average arrival rate into the system
⮚W is the average amount of time spent in the system
⮚The Little's Law formula is: W=L/ λ =15/2=7.5
 Classification of Queuing models
⮚Model I: (M/M/1);(∞/FCFS): This denotes Poisson arrival, Poisson
Departure, Single Server, Infinite Capacity and First Cum First Serve
discipline
⮚Model II: (M/M/S);(∞ /FCFS): This models takes the no of service
channel as S.
⮚Model III: (M/M/1);(N/FCFS): This denotes Poisson arrival, Poisson
Departure, Single Server, Capacity of system is finite and First Cum
First Serve discipline
⮚Model IV: (M/M/S);(N/FCFS): This models is same as model II except
the maximum no of customers in the system is limited to N.
 Queuing Theory Models
⮚Model-1 (M/M/1): (∞/FIFO)
⮚Formulae:
⮚ Utilization Rate ρ=λ/μ
⮚ Probability of n number of customers in the system= Pn=ρn (1-ρ)
⮚ Probability of customer has to wait= 1-(1-ρ)
⮚ Average number of customers in the system Ls=ρ/1-ρ
⮚ Average number of customers in the queue Lq= ρ2/1-ρ
⮚ Average waiting time of customers in the system Ws=1/μ(1-ρ)
⮚ Average number of customers in the queue Wq=ρ/μ (1-ρ)
⮚ Probability that n or more cars in the system P(N≥)=ρn+1
⮚ Probability that the waiting time of customer in the system exceeds time t is P(ws>t)= e -
(μ-λ)t
 Queuing Theory Models
⮚Model-3 (M/M/1): (K/FIFO)
⮚Formulae:
⮚Utilization Rate ρ=λ/μ
⮚Probability of no customers in the system P0=1-ρ/1-ρk+1
⮚Effective arrival rate λ’=μ (1-P0)
⮚Average number of customers in the system Ls=ρ/1-ρ – (k+1) ρk+1/1-ρk+1
⮚Average number of customers in the queue Lq= Ls-λ’/μ
⮚Average waiting time of customers in the system Ws=Ls/λ’
⮚Average number of customers in the queue Wq=Lq/λ’
⮚Probability that the customer turned away= Pk=ρk P0
 Problem 1

⮚In an (M/M/1) :(∞/FIFO) queuing system, if λ=10, and μ=15.

Compute
⮚a.) Lq,
⮚b.) Ws ,
⮚c.) P0 and
⮚d.) Probability that arriving customer has to wait in the queue
 Problem 1 Cont.
⮚Given Data: λ=10, μ=15
⮚Utilization Rate ρ= λ/ μ=10/15=0.6666
⮚Average number of customers in the queue Lq= ρ2/1-ρ = 0.66662/1-
0.6666=1.33
⮚Average waiting time of customers in the system Ws=1/μ(1-ρ) =1/15*(1-
0.6666)= 0.2
⮚Probability of n number of customers in the system Pn=ρn (1-ρ)=P3 =
0.6666^3*(1-0.666)=8/81=0.98765
⮚Probability of customer has to wait Pw= 1-(1-ρ)=0.666
 Problem 2
⮚A petrol pump has one petrol pump. The cars arrive for service
according to a Poisson process at a rate of 0.5 cars per minute and the
service time for each car follows the exponential distribution with
rate of 1 car per minute. Compute
⮚The probability that the pump station is idle
⮚The probability that 10 or more cars are in the system
⮚The average number of cars in the system Ls
⮚The average waiting time in the queue Wq and Average waiting time
in the system Ws
 Problem 2 Cont.
⮚Given data: It’s a Model-1 (M/M/1): (∞/FIFO) because they have not
mentioned the capacity details here λ=0.5 / min, μ=1 / min
⮚Utilization rate= ρ= λ/ μ = 0.5/1=0.5
⮚The probability that the pump station is idle Pidle= 1-ρ= 1-0.5= 0.5
⮚The probability that 10 or more cars are in the system P(N≥)=ρn+1
=(0.5)^11=0.000488
⮚The average number of cars in the system Ls=ρ/1-ρ= 0.5/(1-0.5)=1
⮚The average waiting time in the queue Wq=ρ/μ (1-ρ)= 0.5/1(1-0.5)=1
⮚Average waiting time in the system Ws=1/μ(1-ρ)= 1/1*(1-0.5)=2
 Problem 3
⮚A super market has a single cash counter. During peak hours,
customers arrive at a rate of 20 per hour. The average number of
customers that can be processed by the cashier is 24 per hour.
Calculate
⮚Probability that cashier is idle
⮚The average number of customers in the queuing system
⮚The average time a customer spends in the system
⮚The average number of customers in the queue
⮚The average time a customer spends on the queue waiting line for service
 Problem 3 cont.
⮚Given data: It’s a Model-1 (M/M/1): (∞/FIFO) because they have not
mentioned the capacity details here λ=20/hour, μ=24/hour
⮚Utilization rate= ρ= λ/ μ = 20/24=0.8333
⮚Probability that cashier is idle = Pidle= 1-ρ=0.16666
⮚Average number of customers in the system Ls=ρ/1-ρ= 0.8333/(1-
0.8333)=5
⮚Average waiting time of customers in the system Ws=1/μ(1-ρ)=
⮚Average number of customers in the queue Wq=ρ/μ (1-ρ)
⮚Average waiting time of customers in the system Ws=1/μ(1-ρ)
 Problem 4
⮚Patients arrive at a clinic according to Poisson distribution at a rate of
30 patients per hour. Then waiting room does not accommodate
more than 14 patients. Examination time per patient is exponential
with mean rate of 20 per hour. Calculate
⮚The effective arrival rate at the Clinic
⮚What is the probability that arriving patient will not wait?
⮚What is expected waiting time until a patient is discharged from the Clinic?
 Problem 4 (cont.)
⮚Given data: It’s a Model-1 (M/M/1): (K/FIFO) because they have not mentioned
the capacity details here λ=30/hour, μ=20/hour, K=14+1=15
⮚Utilization rate= ρ= λ/ μ = 30/20=1.5
⮚Probability of no customers in the system P0=1-ρ/1-ρk+1 =1-1.5/1-1.5^16=0.00076
⮚Effective arrival rate λ’=μ (1-P0)= 20*(1-0.00076)=19.98
⮚Average number of customers in the system Ls=ρ/1-ρ – (k+1) ρk+1/1-ρk+1
⮚Average number of customers in the queue Lq= Ls-λ’/μ=
⮚Average waiting time of customers in the system Ws=Ls/λ’
⮚Average number of customers waiting in the queue Wq=Lq/λ’
 Problem 5
⮚A self service store employs one cashier at its counter. Consider
Poisson distribution for arrival rate with 0.75 customers per 5 minutes
and exponential distribution for service rate with 0.927
customers/minute. Calculate
⮚Probability that there are no customers in the system
⮚Average number of Customer in the system
⮚Average number of customers in the queue
⮚Average time customer spent in the system
⮚Average time customer waits before being served
⮚Probability that there are 3 customers in the system
 Problem 7
⮚The local one person barber shop accommodates a maximum of 5
people at a time (4 Waiting and 1 getting haircut service). Customers
arrive at Poisson distribution with mean 5 per hour. The barber cuts
hair at an average rate of 4 per hour.
⮚What percentage of time is the barber idle?
⮚What fraction of the potential customers turned away?
⮚What is expected number of customers waiting for a hair cut?
⮚How much can a customer expect to spend in the barber shop?
Queuing Theory Problem (M/M/1):(k/FIFO)
• Single server (M/M/1) and finite capacity (k/FIFO)
• Capacity (k)=5, Arrival rate (λ)= 5/hr, Service rate(μ)= 4/hr
• ρ= λ/μ= 5/4=1.25
• ρₒ=1- ρ/1- ρᵏᶧ¹=1-1.25/1-1.25