11:03 AM

Chapter 04
Queuing Theory
 11:03 AM

Queueing model-The concept

A queue is formation of a waiting line by customers to get service

more effectively.

It is common in services like airlines, banks, railways, public

buses, taxi, road traffic control, manufacturing industries, etc.

If the number of counters/servers who give the service are:

 Too many– the queue will be less but expenditure will be high.
 Too small – queue become longer resulting in dissatisfaction
of the service by the customers or loss of customers.

Queueing model is a tool used to determine the optimal number of servers

so as to satisfy the customers keeping the total cost minimum..
 11:03 AM

Queueing model-The concept

Queuing system is a mathematical analysis/simulation of

queues and waiting times in stochastic systems.
 Used extensively to analyze production and service processes
exhibiting random variability in market demand (arrival times) and
service times.

It is a discrete-event model that uses random numbers to

represent the arrival and duration of events.

Thus, the queue system is made up of:

 servers
 queues of objects to be served
 11:03 AM

Queueing model-The concept

Queues arise when the demand for service exceeds the

capacity.
 Most often caused by random variation in service times and the
times between customer arrivals.

Capacity problems are very common in industry and one of

the main drivers of process redesign.
 Need to balance the cost of increased capacity against the gains of
increased productivity and service.

Thus, queuing and waiting time analysis is particularly

important in service systems or organizations.
 To avoid large costs of waiting and of lost sales due to waiting.
 11:03 AM

The cost-capacity tradeoff in services

Total
cost
Cost

Cost of
service

Cost of waiting

Process capacity
 11:03 AM

Queuing model - Application Areas

Transportation service systems

 E.g. traffic light system, trucks or ships waiting to be loaded, taxi
cabs, buses, railway station, etc.

Commercial organizations
 E.g. Banks, ATMs, gas stations, garage
…

Business-internal service systems

 Customers receiving service are internal to the organization
providing the service
E.g. Library management …

Social service systems

 E.g. Judicial process, hospital, etc.
 11:03 AM

Components of a Queuing Process

 11:03 AM

Components of a Queuing Process

The Calling Population:

The population from which customers originate.

The size can be finite or infinite (the latter is more common).

It can be homogeneous (only one type of customers/ job) or

heterogeneous (several different kinds of customers/jobs).
 11:03 AM

Components of a Queuing Process

The Arrival Process or Pattern:

It describes the way in which the customers arrive and join the
queue.
The important characteristic is the customers’ inter-arrival
times
To correctly specify the arrival process, it requires data
collection of inter-arrival times and statistical analysis.
Generally, the customers arrive in more or less random
fashion and prediction is difficult.
Thus, the arrival pattern can best be described in terms of
probabilities.
Therefore, the customers assumed to arrive in Poisson
fashion with mean arrival rate denoted by .
 11:03 AM

Components of a Queuing Process

The Poisson process arrival distribution theorem is also called as

Pure Birth Process, which states that:
• If the arrivals are completely random, then the probability
distribution of a number of arrivals in a fixed time interval, t
follows a Poisson distribution.

P ( n) 
 n  t
t e
n!
Where,
• P(n) = the probability that there are n customers in the system in
a fixed time t.
• n = number of customers arriving in a time t
•  = mean arrival rate of customers
• t = duration of time over which customers are counted
 11:03 AM

Components of a Queuing Process

Queuing theory focuses on steady state behavior.

Steady state: The probability distribution of the state of the
system remains the same over time (is stationary).
– N(t) = number of customers in the system at time t,
– E[N(t)] = represents the expected number of customers in the system.
30
Transient condition Steady State condition
25
Number of jobs in the system, N(t)

20

15 E[N(t)]
N(t)

10

0
0 5 10 15 20 25 30 35 40 45 50

time, t
 11:03 AM

The Poisson Process

Example 1: Vehicles arrive for maintenance at Moenco–Addis are

assumed Poisson distributed with an average arrival rate of 1 vehicle
every 5 minutes. What is the probability of the following:
a) Less than 2 vehicles arrive in a 15 minute interval?
b) Exactly 2 vehicles arrive in a 15 minute interval?
c) More than 2 vehicles arrive in a 15 minute interval?

Solution:   1  0.20
5

P ( n) 
t n e  t
n!
 11:03 AM

The Poisson Process

a) Less than 2:
Pn  2   P0   P1  0.1992  19.92%
e 0.215
P0   0.2 *15   0.0498
0

0!
0.215
P1  0.2 *15 
e
 0.1494
1

1!
b) Exactly 2:

P2  
0.20  15 e  0.2015 
2
 0.224  22.4%
2!
c) More than 2:
Pn  2   1  P0   P1  P2   0.5768 or 57.68%
 11:03 AM

Components of a Queuing Process

The Queue Configuration:

Specifies the number of queues/waiting lines.
Could be single or multiple lines to a number of service
stations.
Has effect on customer behavior.
 11:03 AM

Components of a Queuing Process

The service mechanism (or service pattern):

Can involve one or several parallel service channels (servers)
 11:03 AM

Components of a Queuing Process

The service provided by a server is characterized by its

service time (constant or random)

It is specified if the following are known:

• How many customers can be served at a time?
• What the statistical distribution of the service time is?,
and
• When the service is available?

Distribution of service time which is important in practice is

the negative exponential distribution with mean service rate
denoted by .
 11:03 AM

Components of a Queuing Process

The Queue discipline:

Specifies the order by which customers in the queue are
being served.

It is the rule determining the manner in which customers are

chosen for service.

The queue service disciplines include:

• FIFO (First in, First out) or (FCFS) – Most common
• LIFO (Last in, First out) or (LCFS)
• SIRO (service in random order)
 11:03 AM

Customers’ behavior in a queue Process

Customers generally behave in four ways:

• Balking: An arriving customer may refuse to enter the
service if there is no space (or the queue is too long).

• Reneging: when the waiting customer leaves the queue

due to impatience.

• Priorities: some customers are served before others

regardless of their order of arrival.

• Jockeying: customers may jump from one waiting line to

another.
 11:03 AM

Queuing Model Representation

Generally queuing model is specified in the following symbolic form

(Kendall Notation):
(a/b/c): (d/e)
Where,
a = probability law for the arrival
b = probability law according to which customers are served
c = number of channels (or, service stations or servers)
d = capacity of the system
e = Queue discipline
Example: (M/M/1):(/FCFS) - Markovian arrival process
(Poisson)/Markovian service times (exponential)/one server:
infinite capacity/First Come First Serve discipline
 11:03 AM

Common Types of Queue Models

Model I – Birth and Death Model
(M/M/I):(/FCFS)
E.g. Railway station
Model II– Multi-Service Model
(M/M/S):(/FCFS)
E.g. Gas station/air lines
Model III – Single server Fixed Capacity Model
(M/M/I):(N/FCFS)
E.g. Hospital/ car park
Model IV – Multi-service fixed capacity Model
(M/M/S):(N/FCFS)
E.g. Hospital
 11:03 AM

Queuing Theory Applications

M/M/1 or M/M/N
 General case for 1 or many servers

M/D/1
 General arrival rate, but service time is deterministic
 Relevant for many applications
Example: Traffic light system

D/D/1
 Deterministic arrival rate and service times
 Not typically observed in real applications but reasonable for
approximations/ to improve the efficiency of service.
 11:03 AM

The Birth and Death Model (M/M/1)

• Birth - to refer Arrival

• Death - to refer Departure

Assumptions:
 Infinite calling population
Independence between arrivals
 The arrival process is Poisson with an expected arrival rate 
Independent of the number of customers currently in the system
 The queue configuration is a single queue with possibly infinite
length
No reneging or balking
 The service mechanism consists of a single server with
exponentially distributed service times
 = expected service rate when the server is busy
 11:03 AM

The Birth and Death Model (M/M/1)

1. The average (expected) number of customers in the system:


Ls 
1 
where,
=/< 1 (= the utilization factor for the service or, the expected
fraction of the time that the service facility is being used/
steady condition to make the service smooth)
 is mean arrival rate
 is mean service rate

2. The average length of queue, Lq,

 2
Lq  Ls  
 1 
 11:03 AM

The Birth and Death Model (M/M/1)

Ls 1
3. Expected waiting time in the system, Ws  
  

Lq 
4. Expected waiting time in the queue, Wq  
     

5. Probability of queue size in the system PLS  N    N

≥ N is


6. Traffic intensity/utilization factor is 

 11:03 AM

The Birth and Death Model (M/M/1)

Example 1: In a railway station, trains arrive at a rate

of 30 trains per day. Assuming the inter-arrival time
follows an exponential distribution and the service
time distribution is also exponential, with an average
of 36 minutes. Calculate:
a) The mean queue size in the system.
b) The probability that queue size exceeds 10
c) If the input of the train increases to an average 33
per day, what will be the changes in a) and b)?
 11:03 AM

The Birth and Death Model (M/M/1)

Solution:
30 1 1
  ,   trains per min ute
60  24 48 36
 36
    0.75
 48
 0.75
a ) Ls    3 trains
1   1  0.75

b) P ( Ls  10)   N  0.7510  0.056 or 5.6%

c) if 33 trains per day,   1 / 43.63 and   1 / 36    0.825

Accordingly, Ls  5 trains and P ( N  10)  0.1460 or 14.6%
 11:03 AM

Queuing Analysis (M/D/1)

as
applied to road traffic control
 11:03 AM

Important terms and Ideas:

 Traffic Lights/signals - traffic control devices used at road
intersections.

 Every intersection is composed of a number of approaches

which have one or more lanes.
 11:03 AM

Important terms and Ideas:

 During green light, vehicles from the observed approach can

leave the stop line and cross the intersection. The average flow
rate of vehicles that cross the stop line is known as saturation
flow.

 Undersaturated condition - If queues of vehicles

established exclusively during the red phases and are
terminated during the green phases.

 Oversaturated condition – traffic conditions in which

queue of vehicles can arrive at the u/s intersection.
 11:03 AM

Important terms and Ideas:

 Cycle length - the sum of the phase lengths of the signal

durations.

Cycle length = Red light time + Green light time

 The typical sequence of lights at the intersection approach is

Green, Amber, Red.
 11:03 AM

Important terms and Ideas:

 Theoretically, all drivers should cross the intersection during

green light. In reality, a driver hardly starts his car the moment
the green light appears.

 Similarly, at the end of green light , some drivers speed up and

cross the intersection during the amber light.

 Thus, Green time – the time interval within the cycle when
observed approach has green indication.

 Effective green – the time interval during which observed

vehicles are crossing the intersection.
 11:03 AM

The Deterministic Queuing Analysis –M/D/1

 11:03 AM

The Deterministic Queuing Analysis –M/D/1

 Let  be vehicles arrival rate, and  be the

vehicles departure rate during the green time
period,
 The cumulative number of arrivals A(t) and the
cumulative number of departures D(t) are:
A(t )   .t
D(t )   .t
 The duration of the signal cycle is:
crg
Where,
c = duration of the signal cycle
r = effective red
e = effective green
 11:03 AM

The Deterministic Queuing Analysis –M/D/1

Note:
 Queue is the longest at the beginning of effective
green.
 The queue must dissipate before the end of
effective green.
 Let go is the time necessary for queue to dissipate.
 Queue dissipation will happen in every cycle if the
following relation is satisfied.

go  g
 Or, the total number of vehicles during cycle length
c is less or equal to the total number of vehicles
departures during effective green, g
.c  .g
 11:03 AM

The Deterministic Queuing Analysis –M/D/1

 If we consider the triangle ABC in the figure,
 Vehicles arrive during time period r+go
 Vehicles depart during time period go
 Thus, the total number of vehicle arrivals
equals the total number of vehicle
departures. i.e.
.r  g o    .g o
   g o  .r
 Therefore, the time period go required for queue to dissipate is given
by:

.r  .r
go  or g o 
  1 
 11:03 AM

The Deterministic Queuing Analysis –M/D/1

 The area of the shaded triangle ABC
represents the total delay d of all vehicles
arrived during the cycle, which is given
by:
A  r  g o h  g o h  rh
1 1 1
2 2 2
 The ratio h/(r+go) is the slope which is ,

 h   r  g o 
h

r  g o 
 Thus, the total delay, A = d is given by:

1  r  1 2   
d  A  r r  g o   r  r 
1
  r 1  
2 2  1   2  1  

r 2
d
21   
 11:03 AM

The Deterministic Queuing Analysis –M/D/1

 Now, the average delay per vehicle is given by:

r 2
d 21   
d 
c c

r2
d
2c1   

Where,
r = The effective red time
 = traffic intensity
c = cycle time
 11:03 AM

The Deterministic Queuing Analysis –M/D/1

Example 1: The cycle length at the signalized intersection is

90seconds. The considered approach has the saturation flow of
2200 vehicles per hour, the green time duration of 27 seconds, and
flow rate of 600 vehicles per hour. Analyze the traffic conditions
in the vicinity of the intersection. Calculate the average delay per
vehicle. Assume that D/D/1 queuing system adequately describes
the considered intersection approach.

Answer: Under saturated traffic condition!

Average delay per vehicle = 30.33 sec.
 11:03 AM

The Deterministic Queuing Analysis –M/D/1

Solution:
Cycle length, c =90sec. and green light, g = 27sec.

The flow rate ,  and the service rate,  are:

  600veh / hr  0.167veh / sec ,

  2200veh / hr  0.611veh / sec

The traffic intensity,  is:

 0.167
    0.273
 0.611
 11:03 AM

The Deterministic Queuing Analysis –M/D/1

The duration of the red light for the approach is

r  c  g  90  27  63 sec

The number of arriving vehicles per cycle:

.c  0.167veh / s  90 s  15.03veh.

The number of departing vehicles during green light is:

 .g  0.611veh / s  27 s  16.5veh.

Since c≤g, the traffic condition is unsaturated!

The average delay per vehicle is estimated as:

r2 632
d   30.33 sec .
2c1    2  901  0.273
 11:03 AM

The Deterministic Queuing Analysis –M/D/1

Example 2 : The Cycle length at the signalized intersection is

60seconds. The considered approach has the saturation flow of
2200 vehicles per hour, the green time duration of 20 seconds,
and flow rate of 400 vehicles per hour. Analyze the traffic
conditions in the vicinity of the intersection. Assume that
M/D/1 queuing system adequately describes the considered
intersection approach.
Calculate:
a) The average delay per vehicle.
b) The longest queue length
c) Percentage of stopped vehicle

Answer: a) 16.3sec
b) 4.44 veh.
c) 81.53 %
 11:03 AM

The Deterministic Queuing Analysis –M/D/1

Solution:
a) The average delay:
c =60sec. and g = 20sec.
r  c  g  60  20  40 sec

The flow rate ,  and the service rate,  are:

  400veh / hr  0.111veh / sec ,
  2200veh / hr  0.611veh / sec

Therefore,

r2 40 2
d   16.3 sec .
2c1    2  601  0.182 
 11:03 AM

The Deterministic Queuing Analysis –M/D/1

b) The longest queue length, Lmax,

Lmax   .r  (0.111veh / sec)  40 sec  4.44vehicles

c) Vehicles arrive all the time during the cycle. The total
number of vehicles arrived A(t) during the cycle equals:

A  .c  0.111veh / sec  60 sec  6.66vehicles

All vehicles that arrive during time interval (r+go) are stopped.
The total number of stopped vehicles equals:

S   .r  g o 
 11:03 AM

The Deterministic Queuing Analysis –M/D/1

The time period go required for queue to dissipate is:

.r
go 
 

Thus, S is:

 r   0.111 40 
S   . r    0.111  40    5.43vehicles
     0.611  0.111 

Therefore, the percentage of stopped vehicles:

S 5.43
P  100   100  81.53%
A 6.66
 11:03 AM

The Deterministic Queuing Analysis –M/D/1

Example 3: A simple T intersection is signalized. There are

two approaches as indicated in the figure below. The Cycle
length at the signalized intersection is 50seconds.
 11:03 AM

The Deterministic Queuing Analysis –M/D/1

Approach 1 has the saturation flow of 2200 vehicles per hour,

the effective green time duration of 35 seconds, and flow rate
of 600 vehicles per hour. And, approach 2 has the saturation
flow of 2000 vehicles per hour, the effective green time
duration of 15 seconds, and flow rate of 550 vehicles per hour.
Assume that M/D/1 queuing system adequately describes the
considered intersection approach.
Calculate:
a) The average delay per vehicle for every approach.
b) Allocate effective red and green time among approaches in
such a way that the total delay of the T intersection will be
minimized.
 11:03 AM

The Deterministic Queuing Analysis –M/D/1

Solution:
a) Approach 1
c =50sec. and g1 = 35sec.
r1  c  g1  50  35  15 sec

The flow rate ,  and the service rate,  are:

1  600veh / hr  0.167veh / sec ,
1  2200veh / hr  0.611veh / sec

Therefore,

r12 152
d1    3.09 sec .
2c1  1  2  501  0.273
 11:03 AM

The Deterministic Queuing Analysis –M/D/1

Solution:
Approach 2
c =50sec. and g1 = 15sec.
r2  c  g 2  50  15  35 sec

The flow rate ,  and the service rate,  are:

2  550veh / hr  0.153veh / sec ,
 2  2000veh / hr  0.555veh / sec

Therefore,

r22 352
d2    16.92 sec .
2c1   2  2  501  0.276 
 11:03 AM

The Deterministic Queuing Analysis –M/D/1

b) The total delay per cycle of all vehicles on both

approaches is the sum of the delays of every approach:
r12 r22
TD  1.d1  2 .d 2  1.  2 .
2c1  1  2c1   2 

Since c = r1+r2 or r2 =c-r1, substituting in the above equation:

TD  1.d1  2 .d 2  1.
r12
 2 .
c  r1 
2

2c1  1  2c1   2 

The total delay is minimal, if d(TD)/d(r1) = 0. Thus,

r1 c  r1
1.  2 . 0
c1  1  c1   2 
 11:03 AM

The Deterministic Queuing Analysis –M/D/1

Substituting all the values and solve for r1,

0.167 
r1
 0.153 
50  r1   0
50  1  0.273 50  1  0.276 
Thus,

r1  24 sec
g1  c  r1  50  24  26 sec
r2  26 sec
g 2  24 sec

These are the optimal values of green and red times to

minimize the intersection delay.
 11:03 AM

The Deterministic Queuing Analysis –M/D/1

Now, the average delay per vehicle is:

Approach 1:

r12 24 2
d1    7.92 sec .
2c1  1  2  501  0.273

Approach 2:

r22 26 2
d2    9.34 sec .
2c1   2  2  501  0.276 
 11:03 AM

THANK YOU