Queuing Theory

Key words: queue, waiting time, customer, server, service time, queue discipline, expected waiting time,

expected service time, arrival process, service time distribution, departure process, steady-state system.

Suggested readings:

1. Swarup, K., Gupta, P.K. and Man Mohan (2001), Operations research, Sultan Chand and Sons.

2. Medhi, J. (1996), Stochastic Processes, New Age International (P) Ltd.

3. Feller, W.(1968), An introduction to Probability Theory and its Applications, Vol. I ,Wiley, New

York, 3rd edition.

4. Karlin, S. and Taylor, H.M.(1975), A first course in Stochastic Processes, Academic Press.

5. Parzen, E.(1962), Introduction to Stochastic Processes, Universal Book Stall.

6. Ross, S.M.(1983), Stochastic Processes, John Wiley.

7.1 Introduction

As discussed earlier, a flow of customers from an infinite/finite source (population) towards a service facility

forms a queue (waiting line) on account of lack of capability to serve them all at a time. Thus a queuing system

may be described as the flow of units towards a system in the hope of getting service, forming or joining a queue,

if service is not immediately available and leaving the system after being served.

Waiting phenomenon is the direct consequence of randomness in the phenomenon of interaction between the

system and the customers and in the operation of service facilities. In general, the customers' arrival and their

service times are not known in advance, for otherwise the operation of the facility could be scheduled in such a

manner that would eliminate waiting completely.

The objective of the queuing theory is the study of the operations of a service facility under random conditions in

order to secure some characteristics that measure the performance of the system under study. For example, a

logical measure of performance is how long a customer is expected to wait before being served. Another measure

is the percentage of time the service facilities are not in use. The first measure looks at the system from the

customers' point of view whereas the second measure evaluates the degree of utilization of the service facility,

i.e., from the management's point of view. Obviously, the larger the customers' waiting time, the smaller is the

percentage of time the facility will remain idle, and vice-versa. A longer waiting time may have a negative impact

on the new arrivals as the customers may be reluctant to very long waiting periods. However, if the service facility

is not utilized to its optimum capacity, it may increase the cost of service operations. Then the objective of the

queuing theory is to strike a balance between the two.

7.2 Queuing systems: Some general concepts

Basic elements of a queuing model: A queuing model may be described as follows:

A customer arrives at a service facility and joins a queue. The server chooses a customer from the queue to begin

service. Upon the completion of a service, the process of choosing a new customer from the queue is repeated. It

is assumed that no time is lost between the release of a serviced customer and admission of a new one from the

waiting line.
Two principal components of a queuing model, viz., the customer and the server interact only for the period of

time the customer needs to complete his service. The basic elements of a queuing model depend on the following

factors:

1. Input processes:

1. Arrival distribution (single or bulk arrivals).

2. Queue size (finite or infinite).

3. Calling source (finite or infinite).

4. Human behavior (jockeying, balking or reneging).

2. Service processes:

1. Service-time distribution (single or bulk service).

2. Design of service facility (series, parallel or network stations).

3. Service discipline (FCFS, LCFS, SIRO) and service priority.

1. Input processes: Various components of input processes of a queuing model can be described as follows:

1. Arrival distribution: In queuing models, the customer arrivals are summarized in terms of a

probability distribution, which is known as the arrival distribution. The customers may arrive at the service

facility in batches of fixed sizes or of variable sizes or one-by-one. If two or more customers arrive the system

simultaneously, the arrival is said to be in bulk.

2. Queue size: The queue size may be finite or infinite depending upon the capacity of the system. If the

queue size is finite and the queue fills to the capacity, new arrivals are denied service. These arrivals may be

lost forever.

3. Calling source: This is the source from which calls for service (arrival of customers) are generated. The

calling source may be of finite or infinite capacity. In case of a finite source, an arrival affects the rate of

arrival of new customers.

 4. Human behavior: Queuing models representing the situations in which human beings take the role of

customers and/or servers must be designed to account for the effect of human behavior. A "human" server

may speed up the rate of service when the queue builds up in size. A "human" customer may jockey from one

queue to another in the hope of reducing waiting time. Some "human" customers may also balk from joining

a queue because they anticipate a long waiting or they may renege after being in queue for a while because

their wait has been too long. However, a long wait for one person may not be as long as for another. All

customers in the queue are expected to behave equally while in the facility.

2. Service processes: These are the processes related to the service providing mechanism of the system and can

be described as follows:

1. Service-time distribution: Service-time distribution represents the service offered in terms of service

time. The service may be offered individually (as in banks) or in groups (as in restaurants). The queues in the

later case are called the bulk queues.

2. Design of the service facility: The service facility may include one or more servers. If there are infinite

number of servers then all the arriving customers are serviced instantaneously on arrival and there will be no

queue. In case all the servers offer the same service, the system is said to have parallel channels. On the other

hand, the service may comprise of a number of series stations through which the customer has to pass before

the service is completed (e.g., processing of a product on a sequence of machines). In this case, waiting lines

may or may not be allowed between the stations. Such queues are called the queues in series or the queues in

tandem. The most general design of a service facility includes both series and parallel processing stations.

Such systems are called network queues.

3. Service discipline: This is the rule according to which customers are selected for the service when a

queue has been formed. The most common disciplines are the FCFS (first come, first served) and SIRO

(service in random order). Another service discipline is LCFS (last come, first served). The customers arriving

at the facility may be put in priority queues such that those with a higher priority will receive preference to

start service with (pre-emptive service) or a customer of low priority is serviced before a customer of higher
 priority (non pre-emptive service). Another service discipline is processor sharing, when m customers receive

1
service simultaneously at the rate each.
m

In case of parallel channels, FSR (fastest service rule) is adopted, i.e., on customer's arrival if only one server

is free, then the incoming customer is assigned to that server and if more than one server are free, then the

customer is assigned to a server having the largest service rate among the free ones.

7.3 Stochastic nature of queuing models

As we discussed earlier also, queuing models are stochastic models and they need probability distributions to be

explained and analyzed.

(i) Probability distributions associated with the queuing models:

We have seen that if a sequence of events (arrivals or departures in case of queuing models) occur according

to a Poisson process, then the inter-event time is distributed exponentially with the same parameter as that of

the occurrence process. A queuing system may be identified as a birth (-death) process.

Arrival process: In this model, events are pure arrivals and no departures are there, i.e., once a unit joins the

system as a customer, it never departs. This is a pure birth process. Examples are registrations of birth, deaths

or other vital events. If the rate of arrival is , then

( t )
n
− t
p ( t ) = P ( n arrivals in an interval of length t ) = e , n = 0,1, 2...
n n

Departure process: This is a pure death process, which assumes that the system starts with a given number

of customers who leave the facility at a rate  after being serviced while no fresh arrivals are allowed to join

the system. As an example, consider an inventory stock where N items have been made available at the

beginning of the stocking period. No fresh stock are added to the inventory till the next period starts and

existing stock is used sequentially at a rate of  units per unit of time, i.e., if

q ( t ) = P ( n departures in an interval of length t ) ,

n

then
 − h
q (h) = e 1 −  h , for very small h .
0

q (h) = 1 − q (h) h
1 0

q ( t + h ) = q ( t )(1 −  h ) + q ( t )  h; 1  n  N
n n n −1

= q (t ) + q (t ) h ; n = N
N N −1
− t
e
 q ( t ) = ( t )
n
; n = 0,1, 2,... N − 1
n n
N −1
= 1 −  q ( t ); n = N
n =0 n

and

p ( t ) = P ( n customers after time t )

n
− t
N −n e
= q ( t ) = ( t ) ; n = 1, 2,..., N
N −n N −n
N
= 1 −  p ( t ); n = 0
n =1 n

Arrival-departure process: This is the general birth-death process where arrivals and departure occur

simultaneously. Customers arrive (births occur) at a rate  and after getting service, they depart (deaths occur)

at rate  per unit of time.

(ii) Operating characteristics of a queuing model:

These characteristics provide a measure for the evaluation of efficiency of a queuing model and are needed

to design a new system. A queuing model can be a transient system or a steady-state system.

Transient system: If the operating characteristics of the system are functions of time, then the system is

called a transient system

Steady-state system: If the operating characteristics of the system are independent of time, then the system

is called a steady-state system. Most of the queuing systems are designed to be steady-state systems, i.e., the

systems will attain stability after a sufficiently long period of time.

Following characteristics are used to study the performance of the system under steady-state conditions:
1. Expected number of customers in the system: Denoted by E (n) or Ls, expected number of customers

in the system is the average number of customers, both in the queue and the service, where n is a realization

of the random variable N, the number of customers in the system.

2. Expected number of customers in the queue: Denoted by Lq, expected number of customers in the

queue is the average number of customers in the waiting or in the queue.

3. Expected waiting time in the system: Denoted by Ws, expected waiting time in the system is the average

total time a customer spends in the system. It includes his waiting as well as service time.

4. Expected waiting time in the queue: Denoted by Wq, expected waiting time in the queue is the average

total time a customer spends in the waiting on joining the system before being served.

5. Server utilization factor (busy period or traffic intensity): Denoted by , the server utilization factor

is the proportion of time that a server is actually busy in providing service to the customers.

If p is the steady-state probability of n customers in the system, then we have the following relations:
n


(i) Ls =  np
n =0 n


Lq =  ( n − c ) p ; c is the number of servers in the system.
n =c n

(ii) For arrival rate ,

Ls = Ws
Lq = Wq

(iii) If the system capacity is finite, then the effective arrival rate for those who join the system is not same

as the arrival rate as the pressure of new arrivals diminishes once the system tends to approach

saturation point and if the effective arrival rate is denoted by eff , then in general

eff =  (0    1) . Then
 Ls = eff Ws
Lq = eff Wq

1
(iv) If  is the service rate, then the expected waiting time in the service is , so


1
Ws = Wq +


or,  Ws =  Wq +



 Ls = Lq + or,  =  ( Ls − Lq )

and as the relation holds for eff in case of finite system capacity also so, ,
eff =  ( Ls − Lq )

(v) All these basic measures can be combined as

 Ls 1
p → Ls =  np → Ws = → Wq = Ws − → Lq = Wq
n n =0 n  

7.4 Representation of a queuing system: Some standard notations

As we have seen earlier, a queuing system can be identified with its major characteristics. Kendall developed a

standard set of notations to represent a queuing system, which was further modified by Lee. These notations are

now-a-days known as Kendall-Lee notations. The major characteristics of a queuing system are represented as

( a / b / c ); ( d / e / f )

where,

a  arrival distribution
b  service time (departure) distribution
c  number of parallel servers ( c = 1, 2,... )

d  service discipline (FCFS, LCFS, SIRO etc.)

e  system capacity
f  size of the calling source.

The arrival and departure distributions can be according to the following rules:
 1. If arrivals (departures) are according to a Poisson (Markovian) distribution i.e., exponential inter-arrival

(service) time, then the distribution is denoted by the letter M.

2. If inter-arrival (service) time is deterministic, then the distribution is denoted by the letter D.

3. If inter-arrival (service) time is an Erlang (gamma with parameter k) distribution, then the distribution is

denoted by the letter Ek.

4. In case, the inter-arrival times are according to some general distribution but are independent, then the

letter GI denotes the distribution.

5. In case, the inter-arrival times are according to some general distribution, then the letter G denotes the

distribution.

For example, the notation ( M / D /10); ( GD / N /  ) can be interpreted as follows:

The queuing system follows Poisson arrivals, service-time is deterministic, 10 parallel servers are there in the

system, general service discipline, system capacity is finite and the system can accommodate at the most N

customers including those in the service and arrivals are being generated from a source of infinite capacity.

7.5 Some queuing systems

Now, we study some queuing systems, which are Poisson processes. In these systems, the service discipline is

general except for the cases where waiting time distribution have been obtained in which case, the service

discipline is FCFS.

7.5.1 ( M / M /1); ( GD /  /  )

This is a single server model with infinite system capacity, where both arrival and departure process are Poisson

processes. For this system, we want to obtain steady-state probability and study the operational characteristics of

the system.

Let p (t ) = P ( n customers in the system in an interval of length t )

n

and p = lim p ( t ) is the steady-state probability of the system.

n t → n
This is a birth-death process with birth rate, say,  and death rate, say, . Then the differential-difference equations

for this process are

p '( t ) = − (  +  ) p ( t ) +  p (t ) +  p ( t ); n  0
n n n −1 n +1

p '( t ) = −  p ( t ) +  p ( t )
0 0 1

Under steady-state conditions, as n → 

pn '( t ) → 0, and pn ( t ) → pn

and the differential-difference equations tend to

p +p − ( +  ) p = 0; n  0
n −1 n +1 n

p −p = 0
0 1

or, (  + 1) p = p +p ; n0 (7.1)

n n −1 n +1

(  + 1) p = p +p (7.2)
0 0 1


where  = is the traffic intensity.


Multiplying (7.1) by sn, summing over all possible values of n and adding the resultant sum to (7.2), we have

  
 (  + 1)  p s + (  + 1) p =  p
n n n
s + p s +p +p
n =1 n 0 n =1 n −1 n =1 n +1 0
1

1 s −1
 (  + 1) P ( s ) =  sP ( s ) + P(s) + p
s s 0

  + 1− s − 1  P(s) = s −1 p
or,  
 s s 0

s −1 1 −1
P(s) = p = p = p (1 −  s )
or, ( s − 1) −  s ( s − 1) 0 1 − s 0 0

= p  , n = 0,1, 2...
n
 p
n 0

 
= 1 = p 
n
and as  p
n =0 n 0 n =0
 p
 0
= 1 provided   1
1− 

 p = 1−  = 1−
0 
n
    
= p  = (1 −  ) 
n n
and, p =  1 −  
n 0
    

Performance of the model:

  d 
=  n (1 −  )  =  (1 −  )  
n n
(i) Ls =  np
n =0 n n =0 d n =0

d  1 
=  (1 −  )  
d 1−  
 
= = = E (n)
1−   −

  
2 2
(ii) Lq = Ls − = =
 (1 −  )  ( −  )

Ls 1 1
(iii) Ws = = =
  (1 −  )  −

Lq  
(iv) Wq = = =
  (1 −  )  ( −  )

Some interesting properties of the model:

(ii) The probability that the queue size will be greater than or equal to n, the number of customers in the

system is given by

 
 (1 −  ) 
k
P (queue length  n ) =  p =
k =n k k =n

(1 −  ) 
n
= 
n
=
1− 

(iii) Average length of non-empty queue is

  
2
E ( n − 1) 1
E ( n − 1 | n − 1  0) = = =
P ( n  1)  ( − )    2
 −
 

2
 
P ( n  1) =  p − p − p =  
n =0 n 0 1


(iv) The fluctuation (variance) of the number of customers in the system is given by


2
 
Var ( n ) =  n p − E ( n ) =  n  (1 −  ) −
2 2 2 n

(1 −  )
2
n =0 n n =0

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

(v) We now find the waiting time of the customer, based upon FCFS discipline, who finds n customers

ahead of him when he reaches the system.

Let  be the amount of time a person just arriving must wait in the system (until his service is

completed). Then

 = t1 ' + t2 + ... + tn +1

where t1' is the time needed for the customer in service to complete the service and t2, …,tn are the

service times of n-1 customers ahead in the queue. tn+1 is the service time of the customer who has

just joined the queue.

Let  ( | n +1) be the conditional p.d.f. of  given n customers ahead in the system upon the new

arrival. Then ti ~ exp( −  ) i and due to lack of memory property

t1 ' ~ exp( −  )   ~ Gamma (  , n + 1)

− 
  e
  ( ) =   ( | n + 1) p =   (  ) (1 −  ) 
n n
n =0 n n =0 n
(  )
n

− 
= (1 −  )  e 
n =0 n
−  (1−  ) 
= (1 −  )  e ;  0

which is an exponential distribution with mean

 E ( ) =
1  = Ls 
 
 (1 −  )   

An interesting feature of the waiting time distribution is that the probability p for an
n

( M / M /1); ( GD /  /  ) system is completely independent of the service discipline and expected

waiting times in the queue as well as system are completely independent of the service discipline,

still the probability distribution of the waiting time depends on the type of service discipline used.

(See Feller). However, whatever is the service discipline, the expected waiting time must remain the

same.

Ws
(vi) P ( a customer has to wait mote than Ws ) = P (  Ws ) = 1 −   ( ) d
0

−  (1−  ) Ws −1
= e = e  0.368

i.e., under FCFS scheme, 36.8% customers will have to wait more than the average waiting time.

(vii) However, the waiting time of a customer before he gets the service is given by the probability

distribution of Wq, which on using a similar argument, is given by


− (  − ) 
 ( ') =   ( ' | n ) p = (1 −  ) e ;  0
n =0 n

Examples

(1) A worker in an assembling unit of a factory finds that a typical assembling job, on average requires 30

minutes whereas the jobs are independently distributed exponentially. The jobs are to be performed on

a FCFS basis. If jobs arrive on an average rate of 10 per 8-hour shift according to a Poisson rule, find

(i) his expected busy time per day (ii) the number of jobs ahead of the job just

arrived.

Sol: The arrival rate  = 10 jobs per day and the service rate  = 16 jobs per day.

 10
 P ( the worker remains busy) =  = = = 0.625
 16
 (i) Expected busy time per day = duration of the day   = 8  0.625 = 5 hrs/day.

(ii) The number of jobs ahead of the job just arrived is the expected number of jobs in the system

 0.625
 E (n) = =  2 (Jobs cannot be in fractions)
1−  0.375

(2) The rate of arrival of customers at a public telephone booth follows Poisson distribution with an

average inter-arrival time of 10 minutes. The duration of a phone call is assumed to be an exponential

variable with mean time of 3 minutes.

(a) What is the probability that a person arriving at the booth will have to wait?

(b) What is the average length of the non-empty queue that forms from time to time?

(c) The owner company of the booth is planning to install a second booth when convinced that

the expected waiting time for the customers is at least 3 minutes. What should be the pattern

of flow of customers in order to have a justification for the second booth?

(d) Estimate the fraction of the day the phone will be in use.

(e) What is the probability that a new arrival will have to spend 10 minutes in all in the system?

Sol: In this case,

1 1
 =  60 = 6 per hour and  =  60 = 20 per hour
10 3
 6
and  = = = 0.3
 20

(a) P (a new arrival will have to wait ) = P ( '  0) = 1 − p

0

 
= 1 − 1 −  = 0.3
 


(b) Average length of non-empty queue E ( m | m  0) = = 1.43
 −

(c) The second booth will be installed if the expected waiting time is at least 3 minutes, i.e.,

the arrival rate has to be more than the current arrival rate. Let ' be the new arrival rate.

Then

' 3 '
E ( ') =  =
 (  −  ') 60 20(20 −  ')
  ' = 10 per hour.
 (d) The fraction of time the phone is busy is the traffic intensity  = 0.3.


  − (  − )t
(e) P (  0) =   1 − e dt = 0.03
10  

i.e., on average 3% of the arrivals will have to spend 10 or more minutes before leaving

the system after making a call.

(3) In the production shop of a company, the break down of machines is found to be Poisson with an

average rate of 3 machines per hour. Break down time at one-machine costs Rs. 40 per hour to the

company. There are two choices before the company for hiring the repairman. One of the repairman is

slow but cheap, the other is fast but expensive. The slow-cheap repairman demands Rs.20 per hour and

will repair the broken down machines exponentially at a rate of 4 per hour. The fast-expensive

repairman demands Rs. 30 per hour and will repair the machines exponentially at a rate of 6 machines

per hour. Which repairman the company should hire?

Sol: Case I: Slow-cheap repairman

3
 = 3 machines / hour ;  = 4 machines / hour   =
4

1 1
and average down-time of a machine = Lq = = = 1hr .
 (1 −  )
4 ()
1
4

So average down-time of 3 machines which arrive in 1 hr . = 3  1 = 3 hrs .

 down-time cost = Rs .40  3 = Rs .120

charges paid to the repairman = Rs .20  3 = Rs .60

 Total cost = Rs .120 + Rs .60 = Rs .180

Case II: Fast-expensive repairman

 1
 = 3 machines / hour ;  = 6 machines / hour   =
2

1 1 1
and average down-time of a machine = Lq = = = hrs .
 (1 −  )
6
1 3

2

1
So average down-time of 3 machines which arrive in 1 hr . = 3  = 1hr .
3

 down-time cost = Rs .40  1 = Rs .40

charges paid to the repairman = Rs .30  1 = Rs .30

 Total cost = Rs .40 + Rs .30 = Rs .70

So the company should hire the second repairman.

7.5.2 ( M / M /1); ( GD / N / )

This is a single server model with finite system capacity N, i.e., maximum permissible queue length is N-1 and

all the new arrivals either balk or are not allowed to join the system. As a result, the effective arrival rate eff

becomes a function of number of customers present in the system and is less than the rate  at which the customers

are generated. Arrival and departure, both processes are Poisson processes. For this system, we want to obtain

steady-state probability and study the operational characteristics of the system.

The differential-difference equations for this process are

p '( t ) = −  p ( t ) +  p ( t ); n = 0
0 0 1

p '( t ) = − (  +  ) p ( t ) +  p (t ) +  p ( t ); 0  n  N − 1
n n n −1 n +1

p '( t ) = −  p ( t ) +  p ( t ); n = N
N N N −1

( as p ( t + h ) = p ( t )(1 −  h ) + p ( t )(  h )(1 −  h ))
N N N −1
Under steady-state conditions, as n →  , the differential-difference equations tend to

− p + p = 0
0 1

− (1 +  ) p + p + p = 0; 0  n  N − 1
n n +1 n −1

−p +p = 0; n = N
N N −1

N N −1 N
 (  + 1)  p s s + p s + p + p s
n n n N
=  p
n =1 n n =1 n +1 n =1 n −1 0 N

 (  + 1) P ( s ) =
1
s
(P(s) − p ) + s (P(s) − p
0 N
s
N
)+ p 0
+ p s
N
N

1   1
=  +  s  P ( s ) + 1 −  p + ( s − 1)  p s
N

s   s 0 N

or,

−1 N +1 −1
P ( s ) = p (1 −  s ) −p s (1 −  s )
0 N
n
 p = coefficient of s in P ( s )
n


 p 0  , n = 0,1, 2...  N
n

= 
n− N
 p0  − p N  , n  N + 1
n


n− N n− N
p  −p  = p  −p  
n n N
and as = 0
0 N 0 0

= p  ; n = 0,1, 2,..., N
n
 p
n 0
N +1
N 1−  
and as p  
n
= 1  p   = 1
0 n =0 0
 1−  
1−   1−   n
 p = N +1
; and p =  N +1 
 ; n = 0,1, 2,..., N
0 1−  n
1−  
  1−   n
  1 −  N +1   ;   1,

 p =  n = 0,1, 2,..., N
 1
n

 ;  =1
N +1


In this case,  = need not be less than 1 as  is controlled the number of customers in the system


and not by the relative sizes of  and .

 Performance of the model:

N +1

1−  N
1−  d  1−  
(i) Ls =  npn =
1− 
N +1  n n
=
1− 
N +1
  
d  1−  
n =0 n =0

  (1 − ( N + 1)  N + N  N +1 )
 ;  1
 (1 −  )(1 − 
N +1
)
= 
 N
;  =1

 2

Now, P ( a customer does not join the system ) = p

N

 eff =  (1 − p )
N

eff  (1 − p )
(ii) Lq = Ls − = Ls − N

 

Lq Lq
(iii) Wq = =
eff  (1− p )
N

1 Ls
(iv) Ws = Wq + =
  (1− p N )

Example:

(4) At a railway station only one train is handled at one time. The railway yard is sufficient only for two

trains to wait while the other is given signal to leave the station. Trains arrive at the station at an average

rate of 6 per hour and the railway station can handle them at a rate of 12 per hour. Assuming Poisson

arrivals and exponential service time distributions, find the steady-state probabilities for various numbers

of trains in the system and the average waiting time of a new train coming into the yard.

Sol: In this case,

 = 6, and  = 12   = 0.5
N = 2 +1 = 3

1−  0.5
p = P ( no train in the system) = = = 0.53
0 1−  N +1 1−(0.5)4

= p 
n
and p
N 0

3
 Ls =  np n = p  (1 + 2  + 3  ) = 0.74
2
n =0 0
 0.74
and Ws = = 3.8 minutes.
6(1− p3 )

7.5.3 ( M / M / c ); ( GD /  /  )

This is a multi-server model with infinite system capacity with arrival rate . Arrival and departure, both processes

1
are Poisson processes. The mean service time for a customer is . The c servers simultaneously serve c


customers, provided c or more customers are there in the system. In that case, the service rate will be c. If the

number of customers n in the system is less than c, then n servers will be busy and remaining c-n servers will be

idle. In that case, the service rate will be n. For this system, we want to obtain steady-state probabilities and

study the operational characteristics of the system.

Under steady-state conditions, the differential-difference equations for this process are

−( +  ) p +  p + p = 0; n  0
n n n n +1 n +1 n −1 n −1

− p + p = 0; n = 0
0 0 1 1

0
 p = p
1 1 0
 + 
and, p = n n p − n −1 p ; n  0
n +1 n +1 n n +1 n −1

1 + 1  1 + 1 0 
Now, p = p − 0 p = p − 0 p
2 2 1 2 0 2 1 0 2 0

0 1
= p
1  2 0

0 1 n −1
Let p = p
n 12 n 0

n + n 0 1 n −1 n −1 0 1 n − 2
Then, p = − p
n +1 n +1 12 n n +1 12  n −1 0

0 1 n −1n
= p
12  n  n +1 0
 n −1
 i
i =0
Thus, for n  1 p = n
p
 i
n 0
i =1

 n −1 
    i
 
And  pn = 1  p 1+  i =n 0  = 1

n=0 0 n =0
  i 
 i =1 

1
 p = n −1
0  
   i
 
1+  i = 0 
 n=0 n 
  i 
 i =1 

Now, for this model

n =  n
n , n  c
n = 
c , n  c

 n
 p , n c
  (2  )...( n ) 0

 p =  n
  (2  )...(( c −1)  ) ( c )( c )...( c ) p 0 , n  c
( )
n

 ( n−c ) times


 n
 p , n c
n n 0
= 
 n
 n n −c p 0 , n  c
 c c

 n
 p , n c
 n 0
=  n
 
 n −c p 0 , n  c
c c

−1
 
 c −1 n 
  c  
and p =  +  where 1  1    c
0  n=0 n    c c
 c1−  
  c 

Performance of the model:

  c +1 c
(i) Lq = p = p
( c−1)( c−  ) 2 0 ( c −  )2 c

(ii) Ls = Lq + 

Lq
(iii) Wq =


1
(iv) Ws = Wq +


 c +1
For  much smaller than 1, p  1 −  ; Lq =
0 c2

 ( c−  ) ( c−1) 
And for close to 1, p  ; Lq 
c 0 cc c− 

Example

(5) A small town is being serviced by two cab companies. Both the companies own two cabs and are known

to share the market almost equally. The calls arrive at each company's office at a rate of 10 per hour. The

average time per ride is 11.5 minutes. Arrivals of calls follow a Poisson distribution, whereas ride times

are exponential. In an effort to consolidate two companies, it was observed that utilization factor for each

company (ratio of hourly arriving calls to rides) is

 10
100  = 100  = 95.8%
c 2
60
11.5

Is consolidation worth?

Sol: Before consolidation:

We have two independent ( M / M / 2); ( GD /  /  ) with  = 10 calls/hr. and  = 5.217 rides/hr. The

utilization factor for each of the queue is given by

 10
100  = 100  = 95.8% i.e., it is the same for both the queues.
c 2
60
11.5

The expected waiting time in the queue Wq for any of the queue is obtained as follows:
  10
 = = 1.917
 5.217
−1
 
 1.917 0  1.917 1 (1.917)2 
p =   +  + 0.0212
21−
0  0   1  1.917  

  2  
1  (1.917)3 0.0212 
 Wq =   2.16 hrs.
10  1(2−1.917)2 

After consolidation:

We have one ( M / M / 4); ( GD /  /  ) with  = 2  10 = 20 calls/hr. and  = 5.217 rides/hr. The

utilization factor for the queue is

 20
100  = 100  = 95.8%
c 4
60
11.5

which is same as the utilization factor for the earlier system. The expected waiting time in the queue Wq

for the queue is

 20
 = = 3.83
 5.217
−1
 
 3.83 0  3.83 1  3.83 2  3.83 3 (3.83) 
4
p =   +  +  +  + 0.0042
41−
0  0   1   2   3  3.83  

  4  
1  (3.83)5 0.0042 
 Wq =   1.05 hrs.
20  3(4−3.83)2 

Thus consolidation will reduce the expected waiting time by almost 50% whereas the utilization factor

remains unchanged. Hence it is worth to consolidate.