12
Queuing Models
Queue is a common word that means a waiting line or the act of joining a line. It is formed when the number of customers arriving is greater than the number of customers being served during a period of time.
Various queuing situations are:
Examples  Members of Queue  Server(s) 

Airport runways  Planes  Runways 
Petrol bunk  Vehicles  Bank employee 
Library  Students  Counter clerk 
Bank counter  Account holders  Counter clerk 
Hospital  Patient  Doctor 
Telephone booth  Customers  Telephone attendant 
Traffic signal  Vehicles  Signal point 
Barber shop  Customers  Barber 
Ration shop  Ration card holders  Shop clerk 
Depending on the server status, the incoming customer either waits at the queue or gets served. If the server at the counter is free at the time of arrival, the customer can get served without a waiting time. In this process, over a period of time, the system may experience ‘customer waiting’ and/or ‘server idle time’. In any service system involving queuing situation, the objective is to design the system in such a manner that the average waiting time of the customers is minimised and the percentage utilization of the server is maintained above at a desired level.
A queuing system can be described by
 the input (or arrival pattern)
 the service mechanisms (or service pattern)
 the queue discipline
 customer behavior
FIGURE 12.1 Queuing system
12.1 CHARACTERISTICS OF QUEUING MODELS
A queuing system consists of one or more servers, an arrival pattern of customers, service pattern, queue disciple, the order in which the service is provided and customer behavior. The word ‘queue’ is sometimes used to describe the whole system, but it is, in fact, part of the system that holds the excess customers who cannot be immediately served. Hence, the total number of customers in the system at any given time will be equal to the number of customers in the queue plus the number of customers being served. Of course, these numbers will vary with time due to customer’s arrival and departure, so they are random process.
 The input (or arrival pattern): It represents the pattern in which customers arrive at the system. Arrivals may also be represented by the interarrival time, which is the time period between two successive arrivals. Arrivals may be separated by equal intervals of time, or unequal but definitely known intervals of time, or by unequal intervals of time whose probabilities are known; these are called random arrivals. The rate at which customers arrive at the service station, that is, the number of customers arriving per unit of time is called arrival rate.
The assumption regarding the distribution of arrival rate has a great impact on the mathematical model. If the number of customers is very large, the probability of an arrival in the next interval of time does not depend upon the customers already in the system. Hence, the arrival is completely random and it follows the Poisson process with mean equals the average number of arrivals per unit time, represented by λ.
 The service mechanism (or service pattern): The service pattern is similar to the arrival pattern, but there are some important differences. Service time may be a constant or a random variable. Distributions of service time which we are following are ‘negative exponential distribution’, which is characterised by a single parameter, the mean rate μ or its mean service time .
The servicing system in which the customers may be saved in batches of fixed size or of variable size by the same server is termed as bulk service system. The system in which service depends on the number of waiting customers is termed as statedependent system.
 Capacity of the system: Some of the queuing processes admit physical limitations to the amount of waiting room, so that when the waiting line exceeds a fixed length, no further customers are allowed to enter until space becomes available by a service completion. This type of situation is termed as finite source queues.
 Service arrangements: For providing service to the incoming customers, one or more service points are established. The number depends on the number of customers, rate of arrivals, time taken for providing service to a single customer, and so on. Depending on these variables, a service channel is single or multiple.
When there are several service channels available to provide service, much depends upon their arrangements. They may be arranged in parallel or in series or a more complex combination of both, depending on the design of the system’s service mechanism.
Series channels: A customer must pass successively through all the ordered channels before service is completed, for example, in public offices where parts of the service are done at different service counters.
Parallel channels: A number of channels providing identical service facilities so that several customers may be serviced simultaneously.
FIGURE 12.2 (a) Queuing system with single queue and single service station Departure
FIGURE 12.2 (b) Queuing system with single queue and several service stations, parallel servers Departure
FIGURE 12.2 (c) Queuing system with several queues and several service stations
FIGURE 12.2 (d) Queuing system with series servers
A queuing system is called a oneserver model when the system has one server only, and a multipleserver model when a system has a number of parallel channels with one server.
 Service time: The time required for servicing a customer is called service time. Service time may be constant or it may vary with the customer. However, for sake of simplicity, it is assumed that the time required for servicing for all customers is constant. Moreover, since the arrival pattern is assumed to be random, the service time is also taken as random. Hence, the service time follows exponential distribution with mean equal to reciprocal of the mean rate of service. In cases where the assumption of service time following distribution fails, Erlang distribution is applied.
 Queue discipline: It is a rule determining the formation of the queue, the manner of customer’s behavior while waiting, and the manner is which they are chosen for service. The following are queue discipline.
 First In First Out (FIFO): According to it, the customers who come first will be served first. Example: Customers served in ration shop, at the cinema ticket counter.
 Last In First Out (LIFO): According to it, the service of customers is done in the reverse order in which they arrive, that is, the person entering last is served first.
Example: In a big godown, the items which are stored on top (last arrival) are taken out first.
 Service In Random Order (SIRO): The selection of customer for servicing is random at any particular time.
 Service in Priority (SIP): Certain Customers are given priority over others in selection for service. It is of two types: nonemptive priority and, emptive priority.
Nonemptive priority: The customer already getting service is allowed to continue till it is completed even if a priority customer comes midway during the service. Emptive priority: The service to nonpriority customer is stopped as soon as a priority customer arrives.
Example: Treatment for a patient who is critical.
 Customer behavior: Customers generally behave in four ways:
 Balking: A customer may leave the queue because it is too long and he has no time to wait or there is no sufficient waiting space.
 Reneging: Some customers wait for some time in the queue but leave due to impatience without getting the service.
 Collusion: Some of the customers join together and only one of them, instead of all, stay in the queue. However, when their turn comes for service, the customers who were in collusion demand service.
 Jockeying: Some customers keep shifting from one queue to another to improve their position and to get immediate service.
12.2 TRANSIENT AND STEADY STATES
A system is said to be in transient state when its operating characteristics are dependent on time. A system is said to be in steady state when the behaviour of the system is independent of time. Let P_{n}(t) denote the probability that there are n units in the system at time t; then, in steady state,
12.3 ROLE OF EXPONENTIAL DISTRIBUTION
In queuing systems, the arrival of customers occurs in a random manner. That is, the occurrence of an event is not influenced by the length of time that has elapsed since the occurrence of last event. The exponential distribution, which is defined as f(t) = λe^{−λt}, t > 0, with , is completely random. Moreover, exponential distribution has forgetful property. That is, if S is the interval between two consecutive arrivals, then
P(t > T + S/t > S) = P(t > T).
To prove the result, note that
P(t > T) = 1 − P(t < T) = e^{−λT}
So
It is noted that random interarrival and service times are described in queuing models by exponential distribution, because of forgetfulness or lack of memory property.
12.4 KENDALL’S NOTATION FOR REPRESENTING QUEUING MODELS
A convenient notation for summarising the characteristics of the queuing models is given by: (abc): (de)
where
a = Arrival distribution
b = Departure (service time) distribution
c = Number of parallel servers
d = Capacity of the system
e = Queue discipline
Remark:
The standard notation for representing the arrival and departure distributions (i.e. a and b) are M, Markovian (or Poisson) arrival or departure distribution (equivalently exponential interarrival or service time distribution).
12.5 CLASSIFICATION OF QUEUING MODELS
Model I : (MM1): (∞FIFO)
Poisson arrival, Poisson departure (exponential service time), single server, infinite capacity and queue discipline is first in, first out.
This model takes the number of service channel as s.
Model III: (MM1): (N FIFO)
The capacity of the system is limited (finite), say, N.
Model IV: (MMs): (N FIFO)
This model is essentially the same as model II, except the maximum number of customers in the system is limited to N, where N > s.
12.6 PURE BIRTH AND DEATH MODELS
This deals with the relationship between exponential and Poisson distributions. We discuss two situations. One is pure birth (arrivals are only allowed) and the other is pure death (departures are only allowed). The exponential distribution is used to describe the interarrival time in the pure birth model and the interdeparture time in the pure death model.
12.6.1 Pure Birth Model
Make the following assumptions:
 Assume there are n units in the system at time t, and the probability that exactly one arrival (birth) will occur during the small time interval Δt be given by l Δt.
 Δt is considered to be so small that the probability of more than one arrival in time Δt is almost zero.
 The process has independent increments.
To determine the probability of n arrivals in a time interval of length t, denoted by P_{n}(t):
Case 1: When n > 0, there may be two mutually exclusive ways of having n units at time t + Δt.
 There are n units in the system at time t and no arrival takes place during Δt.
 There are (n − 1) units in the system at time t and one arrival takes place during Δt.
Adding (a) and (b) we get
P_{n}(t + Δt) = P_{n}(t)(1 − λΔt) + P_{n − 1}(t)λΔt
⇒
⇒
Case 2: When n = 0,
P_{0}(t + Δt) = P_{0}(t)(1 − λΔt)
⇒
⇒
(or)
Integrating (12.6.2) with respect to t,
The constant A can be found by the condition
Substituting P_{0}(0) = 1 in (12.6.3), we get
log P_{0}(0) = log (1) = A ⇒ A = 0
So (12.6.3) becomes
log P_{0}(t) = −λt (or) P_{0}(t) = e^{−λt}
Substituting n = 1 in (12.6.1), we get
P_{1}′(t) = −λP_{1}(t) + λP_{0}(t)
⇒ , a differential equation of order one. Multiplying throughout by integrating factor I.F. = , we get
⇒
⇒
⇒
e^{λt}P_{1}(t) = λt + B
Substitute t = 0; then P_{1}(0) = 0 and hence B = 0. So the above equation becomes
Similarly, we prove
In general, by induction, we prove
which follows Poisson distribution.
12.6.2 Pure Death Model
In the pure death model, the system starts with N customers at time 0; and no other arrivals are allowed. Departures occur at the rate of μ customers per unit time. As we proceed as in the case of pure birth model, we get
P_{N}(t + Δt) = P_{N}(t)(1 − μΔt)
P_{n}(t + Δt) = P_{n}(t)(1 − μΔt) + P_{n + 1} μΔt, 0 < n < N
P_{0}(t + Δt) = P_{0}(t) + P_{1}(t)μΔt
As Δt → 0, we get
The solution yields
12.7 MODEL I: (MM1): (∞FIFO) (BIRTH AND DEATH MODEL)
With usual notation, let P_{n}(t) denote the probability that there will be n units in the system. P_{n}(t + Δt) may be expressed as the sum of four probabilities.
because of the following situations:
(12.7.1) implies
In the steady state , so (12.7.2) becomes
Probability that there will be no units at time (t + Δt) is given by
because of the following situations:
⇒
In steady state P_{0}′(t) → 0, P_{0}(t) → P_{0}, (12.7.5) becomes
Substituting n = 1 in (12.7.3), we get
In general,
We know which gives
⇒
⇒
Now (12.7.7) becomes
12.7.1 Measures of Model I
 Expected number of units in the system L_{S}
So,
 Expected queue length
 Expected waiting line in the queue
 Expected waiting line in the system
 Expected waiting time of a customer who has to wait
 Expected length of a nonempty queue
 Probability of queue size ≥ N = ρ^{N}
 Probability of waiting time in the system ≥
 Probability of waiting time in the queue ≥
 Traffic intensity
12.7.2 Little’s formula
So,
Now
That is,
(12.7.8)–(12.7.11) are said to be Little’s formula.
Example 1
A selfservice store employs one cashier at its counter. An average of nine customers arrive every 5 minutes while the cashier can serve 10 customers in 5 minutes. Assuming Poisson distribution for arrival rate and exponential distribution for service rate, find
 Average number of customers in the system.
 Average number of customers in queue or average queue length.
 Average time a customer spends in the system.
 Average time a customer waits before being served.
Solution: Arrival rate customers/minute
 Average number of customers in the system
 Average number of customers in the queue
 Average time a customer spends in the system minutes
 Average time a customer spends in the queue
At what average must a clerk at a supermarket work in order to ensure a probability of 0.90 that the customer will not have to wait longer than 12 minutes? It is assumed that there is only one counter to which customers arrive in a Poisson fashion at an average rate of 15 per hour. The length of service by the clerk has an exponential distribution.
Solution: Given customer/minute
P [waiting time ≥ 12] = 1 − 0.90 = 0.10
Therefore,
or,
Example 3
Customers arrive at a onewindow driveinbank according to Poisson distribution with mean 10 per hour. Service time per customer is exponential with mean 5 minutes. The space in front of the window including that for the serviced care can accommodate a maximum of 3 cars. Others can wait outside this space.
 What is the probability that an arriving customer can drive directly to the space in front of the window?
 What is the probability that an arriving customer will have to wait outside the indicated spce?
 How long is the arriving customer expected to wait before starting service?
Solution: We know
P_{n} = ρ^{n} (1 − ρ)
 The probability that an arriving customer can drive directly to the space in front of the window = P_{0} + P_{1} + P_{2}
 Probability that an arriving customer will have to wait outside the indicated space = 1 − 0.42 = 0.58
 Average waiting time of a customer in the queue
Example 4
On an average 96 patients per 24hours day require the service of an emergency clinic. Also, on an average, a patient requires 10 minutes of active attention. Assume that the facility can handle only one emergency at a time. Suppose that it costs the clinic 100 per patient treated to obtain an average servicing time of 10 minutes, and that each minute of decrease in this average time would cost 10 per patient treated. How much would have to be budgeted by the clinic to decrease the average size of the queue from 1 patients to patient.
Solution: Given patient/minute
Expected number of patients in the waiting line
But is reduced to . Then, substituting in the formula,
⇒
Hence, the average rate of treatment required is minutes. Consequently, the decrease in the average rate of treatment minutes and the budget per patient .
So, in order to get to required size of the queue the budget should be increased from 100 to 125.
In a supermarket, the average arrival rate of customer is 10 in every 30 minutes, following Poisson process. The average time taken by the cashier to list and calculate the customer’s purchase is 2.5 minutes, following exponential distribution. (a) What is the probability that the queue length exceeds six? What is the expected time spent by a customer is the system?
Solution: Here the mean arrival rate per minute and mean service rate per minute.
So,
 Probability of queue size > n = ρ^{n}.
Thus n = 6 ⇒ (0.833)^{6} = 0.3348
Example 6
At a telephone booth, arrivals are considered to be Poisson with an average interarrival time of 12 minutes. The length of the phone call may be assumed to be distributed exponentially with an average of 4 minutes. Calculate the following:
 The probability that a fresh arrival will not have to wait for the phone
 The probability that an arrival will have to wait for more than 10 minutes before the phone is free
 The average length of queues formed from time to time
Solution: Mean arrival rate
Mean service rate
 Probability that a fresh arrival will not have to wait = P_{0} = ρ^{0}(1 − ρ) = 1 − ρ = 0.67
 Probability that an arrival will have to wait for more than 10 minutes
 The average length of queue from time to time
12.8 MODEL II: MULTISERVICE MODEL (MMS): (∞FIFO)
When there are n units in the system, the following two cases will arrive:
 n ≤ s, all the customers may be served simultaneously. There will be no queue. (s − n) number of servers remain idle. In this case μ_{n} = nμ, n = 0, 1, 2, …, s.
 n ≥ s, all the servers are busy and the maximum number of customers waiting in queue will be (n − s). Then μ_{n} = sμ, λ_{n} = λ, for n = 0, 1, 2, …
The steady state difference equations are:
P_{0}(t + Δt) = P_{0}(t)(1 − λΔt) + P_{1}(t) μΔt, for n = 0
P_{n}(t + Δt) = P_{n}(t)(1 − (λ + nμ)Δt) + P_{n−1}(t)λΔt + P_{n+1}(t)(n+1)μΔt, for n = 1, 2, …, s − 1
and
P_{n}(t + Δt) = P_{n}(t)[(1 − (λ + sμ)Δt)] + P_{n−1}(t)λΔt + P_{n+1}(t) μΔt, for n = s, s + 1, …
Dividing these equations by Δt and taking limit as Δt → 0, the difference equations are
In steady state condition, when t → ∞, P_{n}(t) → P_{n} , for all n. So, the above equations become
From (12.8.1) it follows that
Substituting n = 1 in (12.8.2), we get
Substituting n = 2 in (12.8.2), we get
In general, we get
From (12.8.3) we get
⇒
Similarly, we get
In general,
Moreover,
That is,
⇒
⇒
⇒
Hence, the steady state distribution of arrivals is
12.8.1 Measures of Model ii
 Average length of queue
 Average number of units in the system
 Expected waiting time in the system
 Expected waiting time in the queue
 Expected length of the nonempty queue
 Expected waiting time of a customer who has to wait
 Probability of waiting time of a customer who has to wait
 Probability that there will be someone waiting
 Average number of idle servers = s − (average number of customers served)
 Efficiency =
Example 1
A supermarket has two girls looking after the sales at the counters. If the service time for each customer is exponential with mean 4 minutes and if people arrive in a Poisson fashion at the rate of 10 per hour,
 what is the probability of having to wait for service?
 what is the expected percentage of idle time for each girl?
 if a customer has to wait, what is the expected length of the waiting time?
Solution: Given

 The fraction of the time the service is busy so, the fraction of the time the service remains idle
 Excepted length of waiting time
Example 2
A petrol station has two pumps. The service time follows exponential distribution with mean 4 minutes and cars arrive for service in a Poisson process at the rate of 10 cars per hour. Find the probability that a customer has to wait for service. For what proportion of time does the pump remain idle?
Solution: Given s = 2; λ = 10 per hour, per minute = 5 per hour
The proportion of time the pump remains idle = 1 − 1/3 = 2/3.
Example 3
Given an average arrival rate of 20 per hour, is it better for a customer to get a service at a single channel with mean service rate of 22 customers or at one of the two channels in parallel, with the mean service rate of 11 customers for each of the two channels? Assume that both queues are (M/M/s: ∞/FIFO).
Solution: For a single channel,
λ = 20 arrivals per hour
μ = 22 customers
Probability of no customer is 0.09.
Average waiting time for a customer in the queue
When s = 2, λ = 20 and μ = 11, .
Now
On comparison, we see that it is better for a customer to wait for two channels instead of a single channel.
Example 4
Four counters are being run on the frontier of a country to check the passports and necessary papers of the tourists. The tourists choose a counter at random. If the arrival at the frontier is Poisson at the rate of λ and the service time is exponential with parameter , what is the steady state average queue at each counter?
Solution: Given s = 4, λ = λ; μ =
Expected queue length
where
Example 5
A bank has two tellers working on savings accounts. The first teller handles only withdrawals. The second teller handles only deposits. It has been found that the service time distribution for both the deposits and the withdrawals is exponential with a mean service time of 3 minutes per customer. Depositors are found to arrive in a Poisson fashion throughout the day with a mean arrival rate of 16 per hour. Withdrawers also arrive in a Poisson fashion with a mean arrival rate of 14 per hour.
 What would be the effect on the average waiting time for depositors and withdrawers if each teller could handle both withdrawals and deposits?
 What would be the effect if this could be accomplished by increasing the service time to 3.5 minutes?
Solution:
 Average waiting time for depositors:
Average waiting time for withdrawers:
Combining the above cases,
In this case, s = 2, so
 If
The average waiting time is increased from 3.86 minutes to 11.4 minutes when the service time is increased to 3.5 minutes.
12.9 MODEL III: (M/M/1): (N/FIFO)
This model differs from (M/M/1): (∞/FIFO) in that there is a limit N on the number in the system (Maximum queue length = N − 1).
Using the generalised model in Section 12.7 gives
The value of P_{0} is determined from the equation P_{n} . That is, _{P}_{0}[1 + ρ + ρ^{2} + … + ρ^{N}] = 1
Thus
Note that the value of need not be less than 1 in this model, because arrivals at the system are controlled by the system limit N.
The expected number of customers in the system is computed as
Example 1
If for period of 2 hours in a day (8 − 10 a.m.) trains arrive at a yard every 20 minutes but the service time continues to remain 36 minutes, then calculate for this period
 the probability that the yard is empty
 average queue length on the assumption that the line capacity of the yard is limited to 4 trains only.
Solution: and N = 4.
 Average queue size = trains.
= 0.04{ρ + 2ρ^{2} + 3ρ^{3} + 4ρ^{4}}
= 0.04 × 72
= 2.9
≅ 3 trains.
In a railway marshaling yard, goods trains arrive at a rate of 30 trains per day. Assume that the inter arrival time follows an exponential distribution and the service time distribution is also exponential with an average of 36 minutes. Calculate
 The probability that the yard is empty.
 Average queue length assuming that the line capacity of the yard is 9 trains.
Solution: Given
 The probability that the queue size is Zero is given by
 Average queue length is given by the formula
Example 3
A barber shop has space to accommodate 10 customers. The barber can service only one person at a time. If a customer comes to his shop and finds it full, he goes to the next shop. Customers randomly arrive at an average rate of λ = 10 per hour and the barber’s service time is negative exponential with an average of minutes per customer. Find P_{0} and P_{n}.
Solution: Given N = 10,
12.10 MODEL IV: (M/M/S): (N/FIFO)
This model differs from the (M/M/s): (∞/FIFO) model in that the system limit is finite and equal to N. This means that the maximum queue size is N − s. The arrival and service rates are λ and μ.
In terms of the generalized model, λ_{n} and μ_{n} for the current model are defined as
Taking
where
When
To determine W_{q} and hence W_{s} and L_{s}, we compute the value of λ_{lost} = λP_{N}
Example 1
A barber shop has two barbers and three chairs for customers. Assume that the customers arrive in poisson fashion at a rate of 5 per hour and that each barber services customers according to an exponential distribution with mean of 15 minutes. Further if a customer arrives and there are no empty chairs in the shop, he will leave. What is the probability that the shop is empty? What is the expected number of customers in the shop.
Solution: Given s = 2, N = 3, .
Expected number of customers in the system
where
So,
12.11 NONPOISSON QUEUES
Queues in which arrivals and/or departures may not follow the Poisson axioms are called nonPoisson queues. The following techniques are employed while studying the nonPoisson queues:
 Phase technique
 The technique of imbedded Markov chain
 The supplementary variable technique.
The phase technique is used when an arrival demands phases of service, say k in number.
The technique by which nonMarkovian queues are reduced to Markovian is called Imbedded Markov chain technique. When one or more random variables are added to convert a nonMarkovian process into a Markovian one, the technique involved in this conversion is called the supplementary variable technique. This technique involved in this conversation is called the supplementary variable technique. This technique is applied to: GIGC, MGI, GIMS, GIE_{K}1, DIE_{K}1, models.
We now consider a queuing system in which the service time has an Erlang type Kdistribution with average service time as , for each exponential phase.
Model i (M\E_{k}\1): (∞\FIFO)
This model consists of a single service channel queuing system in which there are n phases in the system (waiting or in service). Since each customer is served in Kphases onebyone and a new service does not start until all Kphases have been completed, therefore each arrival increases the number of phases by K in the system. Hence, a new arrival creates Kphases of service and departure of one customer reduces Kphases of service.
FIGURE 12.3 Service channels in series
If P_{n}(t) denotes the probability of n(>0) phases in the system at time t. At time t + Δt,
P_{n}(t + Δt) = P_{n}(t) (− λΔt − O(Δt)) (1 − KμΔt − O(Δt))
+ P_{n}(t) (λ Δt) (KμΔt) + P_{n + 1} (t) (1 − λΔt − O(Δt))
+ P_{n − K}(t) (λ Δt) (1 − KμΔt − O(Δt)), n ≥ 1
P_{0} (t + Δt) = P_{0} (t) (1 − λΔt + O(Δt)) + P_{1} (t) (KμΔt), n = 0
Here, a negative subscript indicates the term is zero. As usual, the steady state difference equations are:
0 = − (λ + kμ) P_{n} + kμ P_{n + 1} + P_{n − k}, n ≥ 1
0 = − λ P_{0} + kμP_{1}
Put
Then, we have
To solve these difference equations, we can use generating function concepts. By this definition of generating function (GF) for sequence
where, z is a formal variable.
Multiply both sides of (12.11.1) by z^{n} and taking summation over 1 to ∞ (this equation is true only when n ≥ 1), we have
⇒
⇒
⇒
⇒
⇒
⇒
Using binomial theorem
Since the sum of the series 1 + z + z^{2} + … z^{k−1} = , it follows that
Now, we find P_{0} and P_{n} from equation (12.11.5), Put z = 1, then,
⇒
On the other hand, putting z = 1 in equation (12.11.3), we get
Comparing the equations (12.11.6) and (12.11.7),
which gives
P_{0} = 1 − ρk
Substituting the value of P_{0} in (12.11.4), and letting n = m in equation (12.11.4)
But,
and,
Therefore, (12.11.8) becomes
or,
or,
Comparing the coefficients of z^{n} from both sides of equation (12.11.9) we get
where, the summation is taken over all combinations of i, j and m satisfying n = m + ik + j, for given k.
Characteristics of Model I
 Average number of phases in the system L_{sp} is given by
by using the equation (1 + ρ) P_{n} = ρP_{n − k} + P_{n + 1}, n ≥ 1
 Average waiting time of the phase in the system is given by
 Average waiting time of an arrival is given by
 Average time an arrival spends in the systems is given by
 Average number of units in the system is given by
 Average queue length is given by
Model II (ME_{K}1): (1FIFO)
This model differs from Model I in the sense that the capacity of the system is unity. That is, there is no queue and the system contains only one customer.
Let the customer be in nth phase of service such that 1 < n < k.
Like model I, the following set of steadystate difference equations govern this model:
0 = − λP_{0} + kμP_{1}, n = 0
0 = − kμ P_{k} + λP_{o,} n = k
0 = − kμ P_{n} + kμP_{n + 1}, 1 ≤ n ≤ k
These equations, provide us the following relations:
and,
P_{n + 1} = P_{n}, for 1 ≤ n < k
Now, we observe that P_{1} = P_{2} = … P_{k−1} = P_{k}, we have
To obtain the value of P_{0}, we make use of the fact that . That is,
or,
Hence,
Example 1
Prove that for the Erland distribution with parameters m and k, the mode is at .
Solution: The probability density function of the Erlangian service time distribution is defined by
Mode:
⇒
⇒
Since is negative for , the mode lies at .
Example 2
In a factory cafeteria customers have to pass through three counters. The customers buy coupons at the first counter, select and collect snacks at the second counter and collect tea at the third. The server at each counter takes on an average 1.5 minutes although the distribution of service time is approximately Poisson at an average rate of 6 per hour. Calculate
 the average time a customer spends waiting in the cafeteria.
 the average time of getting the service.
 the most probable time in getting the service.
Solution: Given λ = 6 customers/hour,
Service time per phase = 1.5 minutes
μ = 1.5 × 3 (phases)
= 4.5 customers/minute
= 13.34/hour
k = 3
 Average time a customer spends waiting in the cafeteria
 Average time of getting the service is the average time what it is following the third phase of service. Thus, average time spent in getting the service is . hour or 4.50 minutes.
 The most probable time spent in getting the service is the model value of service time for the third phase of service. Thus, most probable time spent is
12.12 QUEUING CONTROL
Queuing theory is mainly used to determine the queue length, waiting time in queue, and so on. Majority of queuing literature involves prescriptive models rather than descriptive models. Prescriptive models are viewed as static optimisation models.
Static (Design) optimisation models are those in which steady state conditions are set up for the system and some longrun average criterion (such as cost and/or profit) is determined.
When the queuing systems are allowed to depend upon time and are controlled, then these systems are known as dynamic control systems. Some optimisation models are the mixture of static and dynamic categories. But, if the statedependent system is controlled, then it is called underdynamic control. Following are the objectives of dynamic control: Arrival Process Control
 To accept or reject control
 To adjust mean arrival rate
 Customer exercised control
 Self versus social optimisation
 Projection times
Service Process Control
 Varying a number of servers
 Varying the service times
Control of Queue Discipline
 Priority models
 Scheduling models
 Allocation of customers to multiserver channels.
EXERCISES
Section 12.1–12.6
1. What is a queue? Give an example. Explain the basic elements of queues.
2. Explain Poisson input, exponential service.
3. Give some applications of queuing theory.
4. State three applications of waiting line theory in business enterprises.
5. Explain (i) queue discipline, (ii) capacity of the system, (iii) holding time, (iv) balking, (v) jockeying.
6. Briefly explain the important characteristics of queuing system.
7. What do you understand by
 traffic intensity
 service channels
 steady and transient state
 utilisation factor.
8. Show that if the interarrival times is exponentially distributed, the number of arrivals in a period of time is a Poisson process and the converse is also true.
9. Draw a diagram showing the physical layout of a queuing system with multiserver multichannel service facility.
10. Briefly discuss the application of queuing theory in industrial management.
11. Explain the basic queuing process. What are the important random variates in queuing system to be investigated?
12. Explain (i) expected waiting time in queue, (ii) expected waiting time in system.
13. Show that the distribution of the number of births up to time T in a simple birth process follows the Poisson law.
14. State and prove the Markovian property of interarrival times.
15. Establish the probability distribution formula for puredeath process. If the intervals between successive arrivals are random variables which follow the negative exponential distribution with mean , then show that the arrivals form a Poisson distribution with mean λ.
16. In a single server, Poisson arrival and exponential service time queuing system show that probability P_{n} of n customers in steady state satisfies the following equations:
λP_{0} = μP_{1} n = 0
(λ + μ) P_{1} = μP_{2} n = 1
(λ + μ) P_{n} = μP_{n + 1} + λ P_{n − 1}, n ≥ 2
17. Define the cumulative probability distribution of waiting time for a customer who has to wait and show that in an (MM1): (∞  FIFO) queue it is given by (1 − ρ)e^{−μ/1 − ρ}, where .
18. Write a short note on MM1 queue and its applications.
19. What are the various queuing models available?
20. Explain the following queuing systems:
 (MMR) : (GD  K), R < K
 (M  G  1) : (∞  GD)
Section 12.7
Model I
21. The mean arrival rate to a service centre is 3 per hour. The mean service time is found to be 10 minutes per service. Assuming Poisson arrival and exponential service time, find
 utilisation factor for this service facility.
 probability of two units in the system.
 expected number of units in the queue.
 expected time in minutes that a customer has to spend in the system.
[Answer: (a) , (b) , (c) 1, (d) ]
22. At a oneman barber shop, customers arrive according to Poisson distribution with a mean arrival rate of 5 per hour and the hair cutting time is exponentially distributed, with an average hair cut taking 10 minutes. It is assumed that because of his excellent reputations, customers are always willing to wait. Calculate the following:
 Average number of customers in the shop and the average number of customers waiting for a hair cut.
 The per cent of time an arrival can walk right in without having to wait.
 The percentage of customers who have to wait prior to getting into the barber’s chair.
[Answer: (i) 5 customers in the shop and approximately 4 customers waiting for hair cut. (ii) 16.7%, (iii) 83.3%.]
23. A supermarket has a single cashier. During peak hours, customers arrive at a rate of 20 customers per hour. The average number of customers that can be processed by the cashier is 24 per hour. Calculate
 the probability that the cashier is idle.
 the average number of customers in the queuing system.
 the average time a customer spends in the system.
 the average number of customers in the queue.
 the average time a customer spends in the queue waiting for service.
[Answer: (i) 0.167, (ii) 5 customers, (iii) 15 minutes, (iv) 4.167 or 4 customers, (v) 12.5 minutes.]
24. A warehouse has only one loading dock manned by a 3 person crew. Trucks arrive at the loading dock at an average rate of 4 trucks per hour and the arrival rate is Poisson distributed. The loading of a truck takes 10 minutes on an average and can be assumed to be exponentially distributed. The operating cost of a truck is 20 per hour and the members of the loading crew are paid @ 6 each hour. Would you advise the truck owner to add another crew of three persons?
[Answer: Total cost (present crew) = 58 per hour,
Total cost (proposed crew) = 46 per hour
Therefore, add a crew of 3 loaders.]
25. A repairman is to be hired to repair machines which breakdown at an average rate of 3 per hour. Breakdowns are distributed in time in a manner that may be regarded as Poisson. Nonproductive time on a machine is considered to cost 5 per hour. The company has narrowed the choice to 2 repairmen—one slow, but cheap, the other fast, but expensive.
The slowcheap repairman asks 2 per hour and he will service machines at the rate of 4 per hour. The fastexpensive repairman demands 8 per hour, and will repair machines at the rate of 5 per hours. Which repairman should be hired?
[Answer: Fastexpensive repairman to be hired.]
Section 12.8
Model II
26. A telephone exchange has two longdistance operators. The telephone company finds that during the peak load, longdistance calls arrive in a Poisson fashion at an average rate of 15 per hour. The length of service on these calls is approximately exponentially distributed with a mean length of 5 minutes.
 What is the probability that a subscriber will have to wait for his longdistance call during the peak hours of the day?
 If the subscribers will wait and are serviced in turn, what is the expected waiting time?
[Answer: (a) P_{0} = 3/13; P(W > 0) = 0.48; W_{q} = 3.2 minutes.]
27. For a queuing system with k service stations, each having exponential service time distribution with mean service rate μ feed by a queue with builtup arrival rate λ, find (a) the average number of customers in the system and (b) the average waiting time of a customer in the system, if k = 2, μ = 5 per minute and λ = 8 per minute.
[Answer: (a) 4.44 (b) 0.56 minutes.]
28. A railway goods traffic section has four claims assistants. Customers with claims against the railway are observed to arrive in a Poisson fashion at an average rate of 24 per eighthour day for six days. The amount of time the claims assistant spends with the claimant is found to have an exponential distribution with a mean service time of 40 minutes. Service is given in the order of the appearance of the customers.
 How many hours per week can a claims assistant expect to service the claimant?
 How much time does a claimant on average spend in the goods traffic office?
[Answer: (a) 72 hours (b) 47.2 minutes.]
29. A twochannel waiting line with Poisson arrival has a mean arrival rate of 50 per hour and exponential service with a mean service rate of 75 per hour for each channel. Find the
 probability of an empty system
 probability that an arrival in the system will have to wait.
[Answer: (i) 0.83, (ii) 0.167.]
30. Assume that customers arrive at a small post office in Poisson fashion and service is exponentially distributed. Determine the minimum number of parallel service channels needed in each of the following situations to guarantee that the operation of the queuing situation will be stable (i.e. the queue length will not grow indefinitely.)
 Customers arrive every 5 minutes and are served at the rate of 10 customers per hour.
 The average interarrival time is 2 minutes, and the average service time is 6 minutes.
 The arrival rate is 30 customers per hour, and the service rate per server is 40 customers per hour.
[Answer: (i) s ≥ 2, (ii) s ≥ 4, (iii) s ≥ 1.]
31. A telephone company is planning to install telephone booths in a new airport. It has established the policy that a person should not have to wait more than 10% of the time to use the phone. The demand for use is estimated to be Poisson with an average rate of 30 per hour. The average phone call has an exponential distribution with mean time of 5 minutes. How many phone booths should be installed.
[Answer: 6 phone booths.]
32. Ships arrive at a port at the rate of one in every 4 hours with exponential distribution of interarrival times. The time a ship occupies a berth for unloading has exponential distribution with an average of 10 hours. If the average delay of ships waiting for berths is to be kept below 14 hours, how many berths should be provided at the port?
[Answer: Four berths must be provided at the port.]
33. A general insurance company has three claims adjusters in its branch office. People with claims against the company are found to arrive in Poisson fashion, at an average rate of 20 per 8 hourday. The amount of time that an adjuster spends with a claimant is found to have an negative exponential distribution, with mean service time 40 minutes. Claimants are processed in the order of their appearance.
 How many hours a week can an adjuster expect to spend with claimants?
 How much time, on the average, does a claimant spend in the branch office?
[Answer: (a) 22.2 hours, (b) 49 minutes.]
Section 12.9
Model III
34. At a railway station, only one train is handled at a time. The railway yard is sufficient only for two trains to wait while the other is given the 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 on an average of 12 per hour. Assuming Poisson arrivals and exponential service distribution, find the steady state probabilities for the various number of trains in the system. Also, find the average waiting time of a new train coming into the yard.
[Answer: P_{0} = 0.53, P_{1} = 0.27, P_{2} = 0.13, P_{3} = 0.07; average number of trains in the system = 0.74; average waiting time of a new train coming into the yard = 3.5 minutes.]
35. Consider a single server queuing system with Poisson input and exponential service times. Suppose the mean arrival rate is 3 calling units per hour, the expected service time is 0.25 hour and the maximum permissible calling units in the system is 2. Derive the steady state probability distribution of the number of calling units in the system, and then calculate the expected number in the system.
[Answer: P_{n} = (0.43) (0.75)^{n}, P_{0} = 0.431, L_{S} = 0.81.]
36. A car park contains 5 cars. The arrival of car is Poisson at a mean rate of 10 per hour. The length of time each car spends in the car park has negative exponential distribution with mean of 5 hours. How many cars are in the car park and what is the probability of a newly arriving customer finding the car park full and having to park elsewhere?
[Hint: N = 5, , , , , .]
37. Customers arrive at a onewindow driveinbank according to a Poisson distribution with a mean of 10 per hour. Service time per customer is exponential with a mean of 5 minutes. The car space in front of the window, including that for the serviced car, can accommodate a maximum of 3 cars. Other cars wait outside this space.
 What is the probability that an arriving customer can drive directly to the space in front of the window?
 What is the probability that an arriving customer will have to wait outside the indicated space?
 How long is an arriving customer expected to wait before starting service?
 How many spaces should be provided in front of the window so that all the arriving customers can wait in front of the window at least 20% of the time.
[Hint: λ = 10, ,
 P_{0} + P_{1} = 0.30. There should be at least one car space for waiting at least 20% of the time.]
38. A stenographer has 5 persons for whom she performs stenographic work. Arrival rate is Poisson and service times are exponential. Average arrival rate is 4 per hour with an average service time of 10 minutes. Cost of waiting is 8 per hour while the cost of servicing is 2.50 each. Calculate the average
 waiting time of an arrival
 length of the waiting line
 time which an arrival spends in the system
[Answer: (i) 12.4 minutes, (ii) 0.8 ≃ 1 stenographer, (iii) 22.4 minutes.]
39. At a oneman barber shop, the customers arrive following Poisson process at an average rate of 5 per hour and they are served according to exponential distribution with an average service rate of 10 minutes. Assuming that only 5 seats are available for waiting customers, find the average time a customer spends in the system.
[Answer:
W_{s} = 0.26 hours ≃ 16 minutes.]
Section 12.10
Model IV
40. Let there be an automobile inspection station with three inspection stalls. Assume that cars wait in such a way that when a stall becomes vacant, the car at the head of the line pulls up to it. The station can accommodate at most four cars waiting (seven in station) at one time. The arrival pattern is Poisson with a mean of one car every minute during peak hours. The service time is exponential with a mean of 6 minutes. Find the average number of customers in the system during peak hours, the average waiting time and the average number per hour that cannot enter the station because of full capacity.
[Answer: L_{q} = 3.09 cars, L_{s} = 6.06 cars, W_{s} = 12.3 minutes, expected number of cars per hour that cannot enter the station = 30.3 cars per hour.]
41. An international airport operates with three checkout counters. The sign by the checkout area advises the customers that an additional counter will be opened any time the number of customers in the queue exceeds 3. This means that for fewer than 4 customers, only one counter will be in operation. For 4 to 6 customers, two counters will be open. For more than 6 customers, all three counters will be open. The customers arrive at the counters area according to a Poisson distribution with a mean of 10 customers per hour. The average checkout time per customer is exponential with a mean of 12 minutes. Determine the following:
 steadystate probability P_{n} of n customers in the checkout area
 average number of busy counters
 average number of idle counters.
[Hint: λ_{n} = λ = 10 customers per hour, n = 0, 1, 2, …
42. A car servicing station has two boys who offer service simultaneously. Due to space limitation, only four cars are accepted for servicing. The arrival pattern is Poisson with 12 cars per day. The service time of both the boys is exponentially distributed with μ = 8 car per day per boy. Find the average number of cars in the service station, the average number of cars waiting to be serviced and the average time a car spends in the system.
[Answer: P_{0} = 0.196, L_{s} = 6.28 cars, L_{q} = 5.26 cars, W_{s} = 35.8 minutes.]
43. Two repairmen are attending to 5 machines in a workshop. Each machine breaks down according to a Poisson distribution with a mean of 3 per hour. The repair time per machine is exponential with mean 15 minutes.
 Find the probability that the two repairmen are idle, that one repairman is idle.
 What is the expected number of idle machines not being serviced?
[Answer: (a) 0.0405, 0.16144 (b) 0.911.]
44. A group of engineers has two terminals available to aid in their calculations. The average computing job requires 20 minutes of terminal time, and each engineer requires some computation about once every 0.5 hours, that is, the mean time between a call for service is 0.5 hours. Assume these are distributed according to an exponential distribution. If there are 6 engineers in the group find are distributed according to an exponential distribution. If there are 6 engineers in the group find the
 expected number of engineers waiting to use one of the terminals
 total lost time per day.
[Answer: (a) 1.40 or 1 engineer approx., (b) 11.2 hours per day.]
Section 12.11
45. At a certain airport it takes exactly 5 minutes to load an aeroplane, once it is given the signal to land. Although incoming planes have scheduled arrival time, the wide variability produces an effect which makes the incoming planes appear to arrive in a Poisson fashion at an average rate of 6 per hour. This produces occasional stockups at the airport which can be dangerous and costly. Under these circumstances, how much time will a pilot expect to spend circuling the field waiting to land?
[Answer: .]
46. In a car manufacturing plant, a loading crane takes exactly 10 minutes to load a car into a wagon and again come back to position to load another car. If the arrival of cars is a Poisson stream at an average of 1 every 20 minutes, calculate the average waiting time of a car.
[Answer: W_{q} = 5 minutes.]
47. Describe the use of Erlangian distribution in queuing process.
48. Repairing a certain type of machine which breaks down in a given factory consists of 5 basic steps that must be performed sequentially. The time taken to perform each of the 5 steps is found to have an exponential distribution with a mean of 5 minutes and is independent of the other steps. If these machines breakdown in Poisson fashion at an average rate of 2 per hour and if there is only 1 repairman, what is the average idle time for each machine that has broken down?
[Answer: .]
49. A barber takes exactly 25 minutes to complete one hair cut. If customers arrive in a Poisson fashion at an average rate of 1 every 40 minutes, how long, on an average, must be customer wait for service?
[Answer: 20.8 minutes.]