Kendall Notation 1/2/3(/4/5/6) Distributions M/M/1 Queueing Model State of the system Transition from one state to an

M/M/1 MODEL IN QUEUING THEORY

November 21, 2017

ANNU

Under The Supervision Of

Dr.Geetanjali Sharma

Department of Mathematics and Statistics

2017-2018
1 / 29
Kendall Notation 1/2/3(/4/5/6) Distributions M/M/1 Queueing Model State of the system Transition from one state to an

Outlines
Kendall Notation 1/2/3(/4/5/6)
Distributions
M/M/1 Queueing Model
State of the system
Transition from one state to another state in a queuing system
Performance measures of M/M/1 queues
Minimization of Traffic Congestion by Using Queueing Theory
INTRODUCTION
Few Negative Impact Of The Traffic Congestion
Steps Preventing Traffic Congestion
Representation of The Bhagwanpur Golambar Intersection Traffic
Flow Model Using Queueing Theory
Description Of The Model(M/M/1):(∞ /Fif0)
Assumptions Of The Model
Conclusion
2 / 29
Kendall Notation 1/2/3(/4/5/6) Distributions M/M/1 Queueing Model State of the system Transition from one state to an

Kendall Notation 1/2/3(/4/5/6)

• 1 Arrival Distribution
• 2 Service Distribution
• 3 Number of servers
• 4 Total storage (including servers)
(infinite if not specified)
• 5 Population Size
(infinite if not specified)
• 6 Service Discipline(FCFS/FIFO)

3 / 29
Kendall Notation 1/2/3(/4/5/6) Distributions M/M/1 Queueing Model State of the system Transition from one state to an

Distributions

• M: stands for ”Markovian / Poisson” , implying exponential

distribution for service times or inter-arrival times.
• D: Deterministic (e.g. fixed constant)
• Ek : Erlang or gamma with parameter k
• GI: General (genric) distribution of interarrival time
• G: General service time distribution (anything)

4 / 29
Kendall Notation 1/2/3(/4/5/6) Distributions M/M/1 Queueing Model State of the system Transition from one state to an

M/M/1 Queueing Model

Features of the M/M/1 queuing system are presented in Table

Calling Population An infinite population with independent arrivals
and not influenced by the queuing system
Arrival Process Poisson distribution of arrival rate
Queuing configuration Single waiting line with unlimited space
Queue discipline First come, First serve
Service Process Exponential service time distribution

5 / 29
Kendall Notation 1/2/3(/4/5/6) Distributions M/M/1 Queueing Model State of the system Transition from one state to an

Figure : 1.1: M/M/1 queuing system

M/M/1 Queuing model following Poisson distribution of arrival

(λ) and service rate (µ) with single server is presented in Figure
1.1. There is no balking and reneging in this model. The numbers
of customers in a queue as well as in the system are represented by
Lq and Ls respectively.
To analyze M/M/1 Queuing model we require information regarding
the number of customers currently present in the system, which is
represented by the state of the system.
6 / 29
Kendall Notation 1/2/3(/4/5/6) Distributions M/M/1 Queueing Model State of the system Transition from one state to a

State of the system

• The state of queuing system is represented by a single number

n, the number of customers currently in the system.
• It utilizes memory-less property of exponential distribution.
• Consider the system to be in steady state, which means that
the system has been running for so long that the current state
doesnt depend on the starting condition.
• By computing the long run probabilities of being in each
state, we will determine the performance measures of queuing
models as long term steady state performance measures.
• Hence, the customers arrive only one customer at a time. The
system state can change only by one unit at a time.

7 / 29
Kendall Notation 1/2/3(/4/5/6) Distributions M/M/1 Queueing Model State of the system Transition from one state to an

Transition from one state to another state in a queuing

system
• If, currently there are n customers in the system, then the
following changes can happen in the system
• The state of the system increases from n to n +1, if arrival
occurs in to the service system. The rate of increase is
represented by , the arrival rate.
• The state of the system decreases from n to n-1, if departure
to the system occurs. The rate of decrease is represented by ,
the service rate.

Figure : Transition of state in a queuing system

8 / 29
Kendall Notation 1/2/3(/4/5/6) Distributions M/M/1 Queueing Model State of the system Transition from one state to an

• At any given point,

If the system is in the state n,
• i. The state of the system moves from n-1 to n at the rate of
(Pn−1 )(λ)
• ii.The state of the system moves from n to n-1 at the rate of
(Pn )(µ)
Where, (Pn−1 )(λ) and (Pn )(µ) are the probabilities of being in n-1
and n state respectively
As per the stability condition
(Pn−1 )(λ)=(Pn )(µ)
or
λ

(Pn−1 ) = (Pn )
µ
or
(Pn−1 ) = (ρ)(Pn )

9 / 29
Kendall Notation 1/2/3(/4/5/6) Distributions M/M/1 Queueing Model State of the system Transition from one state to an

Performance measures of M/M/1 queues

The memory less property is utilized to define the state of the queu-
ing system. To determine the performance measures, first we will
find the probability of having n number of customers in the queuing
system.
Probability of having 1 customer (i.e. n=1) in the service system is:
P1 =ρP0
Similarly,
P2 =ρP1
P2 =ρ2 P0
.
.
Pn =ρn P0
We also know that the sum of the probabilities is 1 i.e.,
P0 + P1 + P2 + .... = 1
P0 +ρP1 +ρ2 P2 + .... = 1
(1+ρ+ρ2 +...)P0 = 1 10 / 29
Kendall Notation 1/2/3(/4/5/6) Distributions M/M/1 Queueing Model State of the system Transition from one state to an

Hence P0 = 1−ρ
i.e. Probability of no customer in the system
To determine performance measures Ls , Lq , Ws , Wq in the queu-
ing system we need to determine the average number of customers
in the system.
• The average number of customers, Ls in the system can be written as,
Ls = ∞
P
n=0 n × Pn

Where Pn =ρn P0 and P0 = (1−ρ)

Ls = (1 − ρ) ∞ n
P
n=0 nρ

= ρ(1 − ρ) ∞ n−1
P
n=0 nρ
∂ n
We know that (ρ )=nρn−1
∂ρ
∂ P
Ls = ρ(1 − ρ) ( ∞ n
n=0 ρ )
∂ρ
11 / 29
Kendall Notation 1/2/3(/4/5/6) Distributions M/M/1 Queueing Model State of the system Transition from one state to an

∂ 1
Ls = ρ(1 − ρ) ( )
∂ρ 1 − ρ
or
λ
Ls =
(µ − λ)
Using Littles law, according to which the average number of cus-
tomers in the service system is the product of arrival rate and average time
a customer spends in the system.

•Average time a customer spends in the system, Ws can be written

using Littles law as given below

Ls
Ws =
λ

We have determined Ls and we know , hence

Ls
Ws =
λ
12 / 29
Kendall Notation 1/2/3(/4/5/6) Distributions M/M/1 Queueing Model State of the system Transition from one state to an

λ 1 1
Ws = ( )×( )=( )
µ−λ λ µ−λ
Average time a customer spends in the queue, Wq, can be deter-
mined by subtracting expected service time or average service time
from average time a customer spends in the system, Ws

Wq = Ws - Expected service time

1
= Ws −
µ
1 1
= −
(µ − λ) µ
µ − (µ − λ)
=
µ × (µ − λ)
λ
=
µ × (µ − λ)

Using Littles law to determine the average number of customers in

the queue, Lq = λWq
13 / 29
Kendall Notation 1/2/3(/4/5/6) Distributions M/M/1 Queueing Model State of the system Transition from one state to an

λ2
Wq =
µ × (µ − λ)

The Performance measures of a M/M/1 Queue can be written

as below
• Probability of n customers in the service system (1 − ρ) × ρ2
λ
• Average number of customers in the system Ls =
(µ − λ)
λ2
• Average number of customers in the queue Lq =
µ × (µ − λ)
1
• Average time a customer spends in the system Ws = ( )
µ−λ
• Average time a customer spends in the queue
λ
Wq =
µ × (µ − λ)

14 / 29
Kendall Notation 1/2/3(/4/5/6) Distributions M/M/1 Queueing Model State of the system Transition from one state to an

Minimization of Traffic Congestion by Using Queueing

Theory

ABSTRACT
Traffic congestion is a phenomenon of increased disruption of the
traffic movement. In India, with increasing vehicles on the road,
traffic congestion is quickly increasing. Much has been written
about the queueing theory technique and its powerful application.
This paper is an attempt to analyze the contribution and
application of queueing theory in the field of traffic congestion. For
this Bhagwanpur Golambar intersection of Muzaffarpur city
(located in India) is chosen.
The paper summarizes a range of queueing theory results in the
following areas: waiting time, utilization analysis and system
design. The traffic congestion follows a repeatable pattern during
the day, and the locals accept it as a daily routine.
15 / 29
Kendall Notation 1/2/3(/4/5/6) Distributions M/M/1 Queueing Model State of the system Transition from one state to an

I.INTRODUCTION

Traffic research still cannot fully predict under which condition traf-
fic jam may suddenly occur. Because of the poor correlation of
theoretical models to actual observed traffic flows, transportation
planners and highway engineers attempt to forecast traffic flow using
empirical models. Their working traffic models typically use a com-
bination of macro micro mesoscopic features and may add matrix
entropy effects by platooning group of vehicles and by randomising
the flow pattern within individual segments of the network. These
models are then calibrated by measuring actual traffic flows on the
links in the network and the baseline flows are adjusted accordingly.

16 / 29
Kendall Notation 1/2/3(/4/5/6) Distributions M/M/1 Queueing Model State of the system Transition from one state to an

II. Few Negative Impact Of The Traffic Congestion

• time of drivers and passengers in blocked traffic affect the

economic health of the nations.
• Wasted fuel increasing air pollution and carbon dioxide
emission owing to increased idling, acceleration and braking.
• Due to blocked traffic, emergency vehicles may delay in
reaching to their destination where they are urgently needed.
• Spill over effect from congested main routes to secondary
roads and side street as alternative routes are attempted
which affect colony amenity and real estate prices.
• Delays, which may result in late arrival for employment,
meetings and education, resulting in lost business, disciplinary
action or other personal losses.

17 / 29
Kendall Notation 1/2/3(/4/5/6) Distributions M/M/1 Queueing Model State of the system Transition from one state to an

III. Steps Preventing Traffic Congestion

It consists of the amalgamation of a number of procedures listed below:-

TRAFFIC FLOW MEASUREMENT

↓
TRAFFIC CONGESTION ANALYSIS
↓
PREVENTION TECHNIQUE
↓
FINAL EVALUATION
↓
RESULTS

18 / 29
Kendall Notation 1/2/3(/4/5/6) Distributions M/M/1 Queueing Model State of the system Transition from one state to an

IV. Representationof The Bhagwanpur Golambar

Intersection Traffic Flow Model Using Queueing Theory

Figure : Typical representation of the Golambar intersection

In the above figure, round shape in the middle represents the Bhag-
wanpur Golambar and incoming arrows to the Golambar represent
the arrival of vehicles.

19 / 29
Kendall Notation 1/2/3(/4/5/6) Distributions M/M/1 Queueing Model State of the system Transition from one state to an

• NORTH indicates the channel, Rewa Road to Bhagwanpur

Golambar Intersection.
• SOUTH indicates the channel, Gobarsahi to Bhagwanpur
Golambar Intersection.
• EAST indicates the channel, Bairiya to Bhagwanpur Golambar
Intersection and
• WEST indicates the channel, Maripur to Bhagwanpur
Golambar Intersection

20 / 29
Kendall Notation 1/2/3(/4/5/6) Distributions M/M/1 Queueing Model State of the system Transition from one state to an

V.Description Of The Model(M/M/1): (∞/Fif0)

This research is based on the M/M/1, most widely used queueing

system. This queueing system assumes Poisson arrival process with
rate λ and the service time for customers are Poisson distributed with
parameter µ. In this system, it is assumed that all customers are
independent
i.e. their decisions to use the system are independent of other users.

21 / 29
Kendall Notation 1/2/3(/4/5/6) Distributions M/M/1 Queueing Model State of the system Transition from one state to an

VI. Assumptions Of The Model

This research is based on the following assumptions

I. The arrival of a customer follows Poisson arrival process and the
service time follows negative exponential distribution.
II. The queueing discipline is general i.e. the first customer goes to
the server which is ready for the service.
III. The number of customers in the system is very large.
IV. The impact of a single customer for performance of the sys-
tem is very small, that is a single customer consumes a very small
percentage of the system resources.
V. All customers are independent.
a) Total number of car drivers or motorists on the highway is very
large.
b) A single car uses a very small percentage of the highway resources.
c) The decision to enter the highway is independently made by each
car driver.
22 / 29
Kendall Notation 1/2/3(/4/5/6) Distributions M/M/1 Queueing Model State of the system Transition from one state to an

Tabular Representation of the View of the Traffic Situation

at the Bhagwanpur Golambar Intersection

23 / 29
Kendall Notation 1/2/3(/4/5/6) Distributions M/M/1 Queueing Model State of the system Transition from one state to an

Figure : Graphical Representation of Traffic Intensity at Different

Channels Leading to Bhagwanpur Golambar Intersection

24 / 29
Kendall Notation 1/2/3(/4/5/6) Distributions M/M/1 Queueing Model State of the system Transition from one state to an

Tabular Representation of the View of the Traffic Situation

at the Bhagwanpur Golambar Intersection

25 / 29
Kendall Notation 1/2/3(/4/5/6) Distributions M/M/1 Queueing Model State of the system Transition from one state to an

Figure : Graphical Representation of Average Time Spent in the Queue

at Different Channels Leading to the Bhagwanpur Golambar Intersection

26 / 29
Kendall Notation 1/2/3(/4/5/6) Distributions M/M/1 Queueing Model State of the system Transition from one state to an

VII.Conclusion
The queueing theoryis an effective mathematical technique for solving
various acute problems of any organization or system. As queueing the-
ory focuses on representation of traffic situation by using mathematical
terms and formulas, its application cover a wide range of present situation
including the traffic congestion.
• It can be reduced by either increasing road capacity or by reducing
traffic.
• We can provide separate lanes for specific user groups.
• Variable message signs can be installed along the roadway to advice
road users.
• Increasing width of the channel of congested route or building up of
highways.
• Introducing public transport such as busses and office cabs.
• There must be parking restriction for the motor vehicles by the
roadside (i.e. at unauthorized place), so that congestion can be
reduced.
27 / 29
Kendall Notation 1/2/3(/4/5/6) Distributions M/M/1 Queueing Model State of the system Transition from one state to an

References

Kanti Swarup,P.K. Gupta and Manmohan, Operations Research, Sultan Chand

and Sons Publications,16th Edition, 2011.

L. Palaniammal, Probability and Queueing Theory, PHI, New delhi, 2012.

S.D.Sharma, Operations Research, Kedar Nath Ram Nath, 17th Edition.

Frederick S.Hiller, Gerald J.Lieberman, Bodhibrata Nag, Preetam Basu,

Introduction to Operations Research, Mc Graw Hill, 9th Edition.

28 / 29
Kendall Notation 1/2/3(/4/5/6) Distributions M/M/1 Queueing Model State of the system Transition from one state to an

Thanks

29 / 29