Lecture on Queuing Theory

Held on: 15-11-02

Submitted on: 24-11-02

Submitted by: Sandeep Arya (1999299, Gp. # 1)

 

 

 

 

Birth and Death model

The development of a generalized model is based on steady state behavior of the queuing situation which is achieved after the system has been in operation for a sufficiently long time.

The generalized model assumes that both arrival and departure rates are state dependent i.e. they depend on the number of customers in the service facility.

A state is defined as the number of customers in system.

The rate diagram below shows all states and the rates of jumping from one state to another.

 

n = no. of customers in the system

µ_n = departure rate of customers given n in the system

λ_n = arrival rate of customers given n in the system

p_n = steady state probability of n customers in the system

 

                                        Rate diagram

 

From the axioms of Poisson process the probability of more than one event occurring during a small interval h ends to zero as h -> 0. This means that for n>0 state n can change to only to two possible states:

n -1 when a departure takes place at the rate of µ_n and n+1 when an arrival occurs at the rate of λ_n. State 0 can only change to state 1 only when an arrival occurs at a rate λ₀. µ₀ is undefined because no departure can occur if system is empty.

 

(Expected rate of flow into state n) =

 

(Expected rate of flow out of state n) =

 

 

 

 

Under steady state condition, the expected rate of flow into and out of state n must be equal. We get

 

 =         n = 1, 2…

 

 

For n = 0 we get

                                       

                       

                                   

                                       

For n = 1 we have

                               

 

Substituting   and simplifying, we get

                               

 

by induction

                                  n = 1,2,….

       

 

p₀ can be calculated from

                                       

       

 

Hence we find all p_i’s

               

               

 

If all λ are same and all µ are same, and λ > µ

Then for      n → ∞          p₀ ≈ 0

i.e. queue goes on increasing.

 

 

 

Queue is unstable.

So this quantity has to be less than ∞ for stable system.

 

 

If

λ_n =1    for all n

µ_n=2    for all n

 

p_n = (1/2)ⁿ p₀

 

p₀ = ½

 

→ p_n  = (1/2)ⁿ⁺¹

ð         probability of having 1 person in queue is 25%

ð         probability of having 2 person in queue is 12.5%

ð         so you never see more than 20 people in queue

 

 

 

 

Steady State Performance Measures

 

The commonly used measures of performance in a queuing situation are

 

L_s = Expected No. of customers in system

L_q = Expected No. of customers in queue

W_s = Expected waiting time in system

W_q = Expected number of busy servers

c = No. of servers

 

These measures are derived from the steady state probability of n in the system, p_n

 

                                     

 

                                     

 

Single Server Models

 

(M / M / 1): (GD / ∞ / ∞)

 

Customers are assumed to arrive at a constant rate λ and the service rate is also constant at µ. Using the generalized model we have,

 

λ_n= λ and µ_n= µ,        for all n = 0,1,2,….

 

Define traffic intensity,

 

The expression for p_n becomes,

                            

                                                       n = 0, 1, 2…

                            

to determine  p₀ we use

 

         

 

for stability we assume ρ < 1

 

                                      

                                     

                                                               

 

Therefore largest probability is at state 0

 

ρ = 1   →   heavy traffic condition

 

Probability of seeing more than k people = ρ^k

 

p(Q ≥ k) = ρ^k

 

 

Expected queue length

 

                  

                  

                  

 

 

For    ρ = 0.50         ,       L_s =1

ρ = 0.80         ,       L_s =4

ρ = 0.95         ,       L_s =19

ρ = 0.99         ,       L_s =99

at larger queues even small changes in traffic intensity leads to big problems of queuing.

 

 

Little’s Law

 

The relationship between L_s and W_s is known as Little’s formula

 

The parameter  is the effective arrival rate at the system. It is equal to λ when all arriving customers can join the system. If some customers cannot join because the system is full then λ_eff < λ.

 

                                                                                                               

                                               

The figure below shows the arrivals and departures for FCFS and LCFS queues.

w_i represents the waiting times for i^th customers

 

In case of FCFS the first customer gets service before the second and so on. But in case of LCFS the first customer has to wait till the others are serviced. And if someone comes when he is being serviced then he has to wait till the other person gets the service. So his waiting time is greater than the others as shown in the figure. The waiting time of 3^rd, 4^th, and 5^th customer is smallest as no other person comes during their service. This doesn’t happen in case of FCFS and the 1^st person does not have to wait for long.

 

sum of waiting time in a busy cycle

 

this remains unchanged for FCFS or LCFS.

In the above figure, N(t) = 5.

 

Dividing both sides by t, we get