Queueing Process

Queueing Process:
A process of servicing facility or a process of arrivals of customer who wish to be served by the facility is known
as queueing process.

A queue or waiting line is formed when units (customers or clients) needs some kind of service arrive at a service
channel (counter) that offers such facility.

Example:
1) Patients at a doctor’s chamber waiting for the treatment.
2) A system of machine repair
3) Vehicles waiting to cross a major road.
4) Telephone calls waiting to be connected at a switchboard.
5) Airplanes waiting for takeoff (or landing) at a busy airport.

Assumptions of a Queueing Process:

1) Once served the individuals are generally assumed to leave the system.
2) The inter arrival times between two consecutive arrivals are assumed to be independently and identically
distributed (iid ) random variables.

3) The service times are also assumed to be independently and identically distributed (iid ) random

variables.

Elements of Queueing Process or the Characteristics of Queueing Process:

The four common elements or characteristics of queueing process are given below:

1) The input or arrivals: The input describes the manner in which units (customers or clients) arrive and join
in the system.

2) The service mechanism: The service mechanism describes the manner in which service is rendered. A unit
may be served either single or in a batch. The time required for servicing a unit (or a
group of unit) is called the service time.

3) The queue discipline : The queue discipline indicates the way in which the units from a queue are served.
The usual discipline is first come first served (FCFS) or first in first out (FIFO),
through sometimes other rules such as last come first served or random ordering
before service are also adopted.

4) The number of service channels: The system may have a single channel or a number of parallel channels
for service.

Queueing Process - 1 of 14
What Do We Measure in a Queuing Process?
Queueing process deals with following:
L = the average number of customers in the system.
LQ = the average number of customers waiting in the queue.

W = the average amount of time a customer spends in the system.

WQ = the average amount of time a customer spends waiting in queue.

k = number of servers in the system.

M / M / 1 Queueing Model:
An M / M / 1 single server queueing model is a servicing facility with Poisson input and exponential service lines
with FIFO queuing discipline. Here the two M refer the arrival and service distribution are memory less or
Markovian and 1 refers to that there is one server in the system.

Explanation:
Suppose that customers arrive at a single server service station according to Poisson process having rate  . Each
customer upon arrival goes directly into service if the server is free and if not the customer joints the queue. When
the server becomes empty then the customer enters the server. The successive service time are assumed to be
independent exponential random variable having rate  . Then the queuing model is given by


Pn = PN (t ) = n =  n (1 −  ) ; = 1

This is known as M / M / 1 queueing model.

Derivation of M / M / 1 Queueing Model:

In order to derive the M / M / 1 queueing model with infinite capacity, we have to consider the following
balancing equation.
v j Pj =  q kj Pk    (1)
k j

It means that the rate at which the process leaves a state equals the rate at which it enters that state and

 Pn = 1    (2)
n =0

Now by using the equation (1) we get the following set of equations.

Rate at which the process leaves = Rate at which the process enter.
State j v j Pj =  qkj Pk
k j

0 P0 = P1

1 ( +  )P1 = P0 + P2

2 ( +  )P2 = P1 + P3
 

n ( +  )Pn = Pn−1 + Pn+1

Queueing Process - 2 of 14
 Summing each equation to its preceding one we obtain
P0 = P1
P1 = P2
P2 = P3

Pn −1 = Pn
Now solving this in terms of P0 , we get,


P0 = P1  P1 = P0 =  P0


P1 = P2  P2 = P1 =  2 P0


P2 = P3  P3 = P2 =  3 P0

  

Pn −1 = Pn  Pn = Pn −1 =  n P0

So, Pn =  n P0 ; n 1    (3)
Now, from equation (2) we get

 Pn = 1
n =0

 P0 +  Pn = 1
n =1

 P0 +   n P0 = 1
n =1

 
P0 + P0  +  2 +  3 +  = 1 
 
P0 + P0  1 +  +  2
+  = 1
  
 P0 1 +  =1
 (1 −  ) 
 P0 = 1 − 

Putting this value in (3) we get,

Pn =  n (1 −  ) ; n0

Thus, the distribution Pn  of the random variable N , the number in the system in steady state, is geometric.

Properties of M / M / 1 Model:
1) In the M / M / 1 queueing model the number of customer follow geometric distribution

i.e. Pn =  n (1 −  ) ; n0 where ,  = 1


2) Average number of customers in the system is L =
1− 

2
3) Average number of customers waiting in the queue is LQ = WQ =
 ( −  )
L 1
4) Average amount of time that a customers spend in the system is W = =
  −

Queueing Process - 3 of 14
 5) Average amount of time that a customers spends for waiting in the queue is
WQ = W − E (s ) Where , s = service time
1 1 1
= w− = −
  − 

WQ =
 ( −  )

6) The proportion of time the server is idle is P0 = 1 − = 1− 


7) The proportion of time the server is busy is 1 − P0 = 1 − (1 −  ) =  =


 
Theorem: Average number of customers in the system is L = E (N ) = and V (N ) =
1−  (1 −  )2
Proof:

L = E (N ) =  nPn
n =0

 

=  n n (1 −  ) = (1 −  )  + 2  2 + 3 3 + 
n =0


= (1 −  ) 1 + 2  + 3 2 + 

=
(1 −  ) =

(1 −  )2 (1 −  )

  
So, L = = =
(1 −  ) 1−   −

We know,

( )
V (N ) = E N 2 − E (N )2

E (N ) =  n

2 2
Pn
n =0

 

=  n 2  n (1 −  ) = (1 −  )  + 4  2 + 9  3 + 
n =0


= (1 −  ) 1 + 4  + 9  2 +  
= (1 −  ) 1 + 3 + 6  2
+ +  + 3 2
+ 
 1    (1 +  )
= (1 −  )  +  =
 (1 −  )3
(1 −  )3  (1 −  )2
 (1 +  )
 ( )
E N2 =
(1 −  )2
 (1 +  )
( )
V (N ) = E N 2 − E (N )2 = −
2
=

1 +  −  
(1 −  ) 2
(1 −  ) 2
(1 −  )2

 V (N ) =
(1 −  )2
2 2
Theorem: Average number of customers waiting in the queue is LQ = =
(1 −  )  ( −  )
Proof:

Queueing Process - 4 of 14
  
LQ =  (n − 1)Pn =  (n − 1) n (1 −  )
n =1 n =1


= (1 −  )  2 + 2  3 + 3 4 +  
= (1 −  ) 1 + 2  + 3
2
 2
+ 

=
(1 −  ) 2
=
2
(1 −  )2 (1 −  )
2
  
   2
2
So, L = = =
(1 −  ) 1−   ( −  )


Distribution of Time a Customer Has to Spend or Waiting Time in the Queue or Distribution of
Queueing Time:
Suppose X represent the amount of time customer spent in the queue and f (x ) is its function, then

 ( −  ) − ( −  )x
f (x ) = e ; x0

Where,  is the rate of arrivals and  is the rate of departure.


Here  f (x )dx = 
0



+ f (x )dx = 1
 0
So, for the p.d . f . we have to consider 1−

That is, the p.d . f . of queueing time is

  ( −  ) −( − )x
g (x ) = 1 − + e ; x0
 

Derivation:
In order to derive the distribution of queueing time X , let us consider, there are n arrivals in the system of time.
(n − 1) services are ensured during x , and 1 service is completed in  x for all n = 1, 2, . So

f (x ) x = Pn Customers , (n − 1) services , 1 services in  x


e −  x ( x )n −1
f (x ) x =  Pn  x
n =1 (n − 1)!
   e −  x ( x )n −1
 n

=    1 −   x
n =1      (n − 1)!
=
 − 
 e − x 

( x )n −1  x
  n =1 (n − 1)!

  −   − x  x
 f (x ) x =    e e x
  
  −   − (  −  )x
 f (x ) =    e ; x0
  


Now  f (x )dx = 
0

So, for the p.d . f . we have to consider

Queueing Process - 5 of 14
 

+ f (x )dx = 1
 0
1−

That is, the p.d . f . of queueing time is

  ( −  ) −( − )x
g (x ) = 1 − + e ; x0
 

 
Theorem: Average amount of time that a customers spends for waiting in the queue is WQ = =
 ( −  )  (1 −  )

Proof:
Average amount of time a customer spent in the queueing is given by

WQ = E ( X = x ) =  xf (x )dx
0

 ( −  ) −( − )x  ( −  ) 2−1 −( − )x

 
=x e dx = x e dx
0
  0

 ( −  ) 2
=
 ( −  )2

 
 WQ = =
 ( −  )  
 1 − 
  

=
 (1 −  )
 
 WQ = =
 ( −  )  (1 −  )

Example: Suppose in a super market there is only one cashier. Customers arrive at random at a rate of 12 per hours
and the service time has negative exponential distribution. At what rate should a customer work to ensure
that at most 90% of customers do not have to wait for more than 4 minutes?
Solution:
Suppose X represents the amount of time a customer has to wait in the queue. Also let the customers arrive at the
rate  and the service time has the negative exponential distribution with the rate  . Thus the distribution of X

is given by
 ( −  ) − ( −  )x
f (x ) = e ; x0

  ( −  ) − ( −  )x
The completion of the function 1− + e =1
 

1
We are given here,  = 12 per hour = per Minute
5

Queueing Process - 6 of 14
 So, we have
P( X  4 ) = 0.90
 ( −  ) −( − )x
4

 0
 1− + e dx = 0.90

 ( −  ) −( −  )x

  
e dx = 0.1
4

 ( −  )  e − ( − )x 
   = 0 .1
  − ( −  )  4

 −


 
0 − e −( −  )4 = 0.1

4
1 −4 5
 e e = 0 .1
5
1 −4
 e = 0.225


1
 e −4


0.51 0.255
0.52 0.240
0.53 0.226
0.54 0.214
0.55 0.201

So, at the rate of 0.53 the cashier work to ensure that 90% of customers do not have to wait for more than 4
minutes.

Distribution of Waiting Time in the System (or Sojourn Time or Response Time):
The random variable “time spent in the system” (or sojourn time) by a customer includes the service time besides
its queueing time.

Suppose X represent the amount of time customer spend in the system then the distribution of waiting time X in
the system is

f (x) = ( −  )e −( − )x ; x0

Where,  is the rate of arrivals and  is the rate of departure.

Derivation:
A customer has to wait in the system even if the system is empty (n = 0) , the time spent being equal to his service

time. Given that there are n ( 0) customers in the system, its waiting time is X = S n +1 .

Where S n+1 = v1 + v 2 + v3 +  + v n + v n+1 , v1 being the residual service time of the customer being served and

v 2 , v3 ,  , v n , v n +1 being the service times for the customers waiting in the system..

Queueing Process - 7 of 14
 Here v1 , v 2 , v3 ,  , v n , v n +1 are exponentially distributed random variable and so S n+1 is a gamma variate

having density
 n +1
f S (x ) = e −  x x n +1−1 ; x0
n +1

 n +1
= e − x x n ; x0
n +1

Hence we have for x  0

f X (x ) x = P(x  X  x +  x )
= P(x  S n +1  x +  x | there are n units in the system ) PThere are n units in the system 
 

 n +1e −  x x n
=  Pn  n +1
 x

n =0
 
     n +1e −  x x n 
 n

=    1 −    x
n =0        n! 
  −   − x  n x n 
( x )n
=   e x  = ( −  )e −  x  x
   n = 0 n! n =0 n!
= ( −  )e − x  x
e x
− ( −  ) x
 f X (x ) x = ( −  )e x
− ( −  ) x
 f X (x ) = ( −  )e ; x0

1 1
Theorem: The average amount of time that a customers spends for waiting in the system is W = =
( −  )  (1 −  )

Proof:
Average amount of time a customers spends in the system is given by
 
W = E(X = x) =  xf (x )dx =  x( −  )e − ( −  )x dx
0 0
 2
= ( −  ) x 2 −1 e −( − )x dx = ( −  )
0 ( −  )2
1 1 1
 W= = =
( −  )    (1 −  )
 1 − 
 
1 1
W= =
 ( −  )  (1 −  )

Relationship between L, LQ , W , WQ :
We know,

L=    (1)
1− 
2
LQ =    (2)
1− 

WQ =    (3)
 (1 −  )

W=
1
   (4)
 (1 −  )

Queueing Process - 8 of 14
 Now, from equation (1) we have,

 
L= =
1−   (1 −  )

=
1
= W From (4)
 (1 −  )
 L = W
L
 W=

L
W=

Again, we have from equation (2)

2  
LQ = =
1−   1− 

= =  WQ From (3)
 (1 −  )
 LQ =  WQ
LQ
 WQ =

LQ
 WQ =


Relation between  and  :

We know that
P0  0
 1−   0

 1− 0


 1   1

 
That is the service rate must be greater than arrival rate.

Example: Suppose that customers arrive (at a super market) at a Poisson rate of 1 per every 12 minutes and that the
service time is exponential at a rate of 1 per every 8 minutes. Then find
1) Find the proportion of time that there is no customer in the super market
2) Find the proportion of time the super market is busy
3) Average number of customer in the super market
4) Average amount of time a customer spent in that queue to get into the super market.

Solution:
Suppose  represents the rate of arrival and  represents the rate of service time. Here, the customers arrive at a

1 1
Poisson rate of  = per minute. The service time is exponential at a rate of  = per minute.
12 8
  2
So, we have,  = = =
 12 3
Queueing Process - 9 of 14
 The queueing model M / M / 1 that there are n customers in the super market is given by

Pn =  n (1 −  ) ; n0
1) There is no customer in the super market is given by
2 1
P0 = 1 −  = 1− =
3 3
Comment: So, about 33% time the super market will be free from customers.
2) Proportion of time the supermarket is busy is given by

1 − P0 = 1 − (1 −  )
2
= =
3
Comment: So, about 66% time the super market will be busy.
3) Average number of customers is given by
2
 3
L= = =2
1−  2
1−
3
Comment: So, on average there will be 2 customers per minute in the super market.
4) Average amount of time spend in the queue is given by

2
(2 3 ) 2

LQ 1−  1− 2
WQ = = = 3 = 16
  1
12
Comment: So, average amount of time a customer spend in the queue to get into the super market is 16 .

Example: Suppose that in the above problem, the arrival rate increases 20% , then what is the corresponding change in
L and W ?
Solution:
1 1 20 1
The arrival rate increases as =  20% = = Per Minute
12 12 100 60
1 1 1
Then the present arrival rate is  = + = Per Minute
12 60 10
 8 4
So, we have  = = =
 10 5
4
 5
1) So, we have, L = = =4
1−  4
1−
5
Hence, an increase of 20% in the arrival rate doubled the average number of customers in the system is 4 .

L 4
2) Again, we have W = = = 40
 1
10
Hence, in an increase of 20% in the arrival rate, the average amount of time a customer has to spend in the
system is 40 .

Queueing Process - 10 of 14
Example: The arrivals at a counter in a bank occur in accordance with the Poisson process at an average rate of 8 per
hour. The duration of service of a customer has an exponential distribution with a mean of 6 minutes that
6
is hours.
60
1) Find the probability that an arriving customer has to wait on arrival
2) Find the probability that 4 customers are in the system
3) Find the probability that an arriving customer has to spend less than 15 minutes in the bank.
4) Estimate also the fraction of time that the counter is busy.

Solution:
Here, the customers arrive at a Poisson rate of  = 8 per hour. The service time is exponential at a rate of  = 10

per hour.
 8
So, we have  = = = 0 .8
 10

1) An arrival customer has to wait on arrival if the system is not empty

P(N  1) = 1 − P(N = 0)
= 1 − P0
= = 0.8
Hence, the probability that an arriving customer has to wait is given by 0.8 .

2) Again, we have P4 = (1 −  ) 4 = 0.2  (0.8)4 = 0.08192

Hence, the probability that 4 customers in the system is given by 0.08192 .

3) Again,
0.25
− ( −  )x
P ( X  0.25) =  ( −  )e dx
0


= − e − ( −  )x 
0.25
0 = 1 − e − ( −  )0.25
= 1 − e − (10−8 )0.25
= 0.3935

Hence, the probability that an arriving customer has to spend less than 15 minutes in the bank.

4) Again we get, 1 − P0 =  = 0.8

So, the function of time the counter will busy is 0.8 .

A Single Server Exponential Queuing System M / M / 1 Having Finite Capacity:

Assumption:
1) There is always a finite system capacity N .

2) Once there are already N customers in the system the (N + l )th (l = 1, 2, ) customer will not enter the

system.

Queueing Process - 11 of 14
Statement:
Suppose Pn ; (0  n  N ) represents the limiting probability that there are n customers in the system. Then the

M / M / 1 model for finite capacity is given by

 n (1 −  )
Pn = ; n = 0, 1, 2,  , N
1 −  N +1

Derivation:
In order to derive M / M / 1 with finite capacity we have to consider the following

v j Pj =  q kj Pk    (1)
k j

It means that the rate at which the process leaves a state equals the rate at which it enters that state and

 Pn = 1    (2)
n =0

Now by using the equation (1) we get the following set of equations.

Rate at which the process leaves = Rate at which the process enter.
State j v j Pj = qkj Pk 
k j

0 P0 = P1
1 ( +  )P1 = P0 + P2
2 ( +  )P2 = P1 + P3
 
N −1 ( +  )PN −1 = PN −2 + PN
N PN = PN −1

Summing each equation to its preceding one we obtain

P0 = P1
P1 = P2
P2 = P3

PN −1 = PN
PN = PN −1
Now solving this in terms of P0 , we get,


P0 = P1  P1 = P0 =  P0


P1 = P2  P2 = P1 =  2 P0


P2 = P3  P3 = P2 =  3 P0

  

PN − 2 = PN −1  PN −1 = PN − 2 =  N −1 P0


PN = PN −1  PN = PN −1 =  N P0

So, Pn =  n P0 ; n = 0, 1, 2, , N    (3)
Queueing Process - 12 of 14
 Now, from equation (2) we get
N
 Pn = 1
n =0

   n P0 = 1
n =0

 
P0 1 +  +  2 +  3 +  +  N = 1 
 
P0  1 +  +  +  + 
2 N
= 1
N +1
1− 
 P0 =1
1− 
1− 
 P0 =
1 −  N +1
Putting this value in (3) we get,

Pn =  n
(1 −  ) ; n = 0, 1, 2,  , N
1 −  N +1

A Multi-Server Exponential Queueing System or M / M / k Model:

M / M / k model is a multi-server queueing model in which customers arrive according to a Poisson process
having rate  , enter the system if at least 1 of the k servers is free and then spend an exponential amount of time
with rate  being serve. This model is also known as Erlang’s loss system.

Derivation:
In order to derive M / M / k model we have to consider the following balancing equation

v j Pj =  q kj Pk    (1)
k j

It means that the rate at which the process leaves a state equals the rate at which it enters that state and

 Pn = 1    (2)
n =0

Now by using the equation (1) we get the following set of equations.

Rate at which the process leaves = Rate at which the process enter.
State j v j Pj = qkj Pk 
k j

0 P0 = P1
1 ( +  )P1 = P0 + 2P2
2 ( + 2 )P2 = P1 + 3P3
 
i ( + i )Pi = Pi −1 + (i + 1)Pi +1
 
k kPk = Pk −1
Summing each equation to its preceding one we obtain
P0 = P1
P1 = 2P2
P2 = 3P3

Pk −1 = kPk
Queueing Process - 13 of 14
 Now solving this in terms of P0 , we get,


P0 = P1  P1 = P0 =  P0

 P1 P0
P1 = 2P2  P2 = = 2
 2 2
 P2 P0
P2 = 3P3  P3 = = 3
 3 3!
  
 Pk −1 P
Pk −1 = kPk  Pk = = k 0
 k k!
P0
So, Pn =  n ; n = 0, 1, 2,  , k    (3)
n!
Now, from equation (2) we get
k
 Pj = 1
j =0
k
P0
 P0 +  j j!
=1
j =1
k
j
 P0 + P0  j!
=1
j =1

1
 P0 =
 k
 j 
1 +

 
j! 
j =1 
Putting this value in (3) we get,

n
Pn = ; n = 0, 1, 2,  , k
 k
 j 
n! 1 +

 
j! 
j =1 
This is known as M / M / k finite capacity function.

M / G / 1 Queueing Model:
An M / G / 1 single server queueing model is a servicing facility with Poisson input with  and service times are
1
iid random variables having an arbitrary (general) distribution with mean . Here the M refers the arrival

distribution which is Markovian and G refers to the service distribution which is not Markovian i.e. any
distribution without Poisson and 1 refers to that there is one server in the system.

M / G / k Queueing Model:
An M / G / k single server queueing model is a servicing facility with Poisson input with  and service times are
1
iid random variables having an arbitrary (general) distribution with mean . Here the M refers the arrival

distribution which is Markovian and G refers to the service distribution which is not Markovian i.e. any
distribution without Poisson and k refers to that there are k server in the system.

Queueing Process - 14 of 14