12. Queuing Models – Operations Research, 2nd Edition

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

  1. the input (or arrival pattern)
  2. the service mechanisms (or service pattern)
  3. the queue discipline
  4. 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.

  1. The input (or arrival pattern): It represents the pattern in which customers arrive at the system. Arrivals may also be represented by the inter-arrival 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 λ.

  2. 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 state-dependent system.

  3. 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.
  4. 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 one-server model when the system has one server only, and a multiple-server model when a system has a number of parallel channels with one server.

  5. 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.
  6. 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.
    1. 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.
    2. 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.

    3. Service In Random Order (SIRO): The selection of customer for servicing is random at any particular time.
    4. Service in Priority (SIP): Certain Customers are given priority over others in selection for service. It is of two types: non-emptive priority and, emptive priority.

      Non-emptive 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 non-priority customer is stopped as soon as a priority customer arrives.

      Example: Treatment for a patient who is critical.

  7. Customer behavior: Customers generally behave in four ways:
    1. 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.
    2. Reneging: Some customers wait for some time in the queue but leave due to impatience without getting the service.
    3. 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.
    4. 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 Pn(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 inter-arrival 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: (a|b|c): (d|e)

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 inter-arrival or service time distribution).

12.5 CLASSIFICATION OF QUEUING MODELS

Model I : (M|M|1): (∞|FIFO)

Poisson arrival, Poisson departure (exponential service time), single server, infinite capacity and queue discipline is first in, first out.

Model II: (M|M|s): (∞|FIFO)

This model takes the number of service channel as s.

Model III: (M|M|1): (N |FIFO)

The capacity of the system is limited (finite), say, N.

Model IV: (M|M|s): (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 inter-arrival time in the pure birth model and the inter-departure time in the pure death model.

12.6.1 Pure Birth Model

Make the following assumptions:

  1. 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.
  2. Δt is considered to be so small that the probability of more than one arrival in time Δt is almost zero.
  3. The process has independent increments.

To determine the probability of n arrivals in a time interval of length t, denoted by Pn(t):

Case 1: When n > 0, there may be two mutually exclusive ways of having n units at time t + Δt.

  1. There are n units in the system at time t and no arrival takes place during Δt.
  2. There are (n − 1) units in the system at time t and one arrival takes place during Δt.

Adding (a) and (b) we get

 

Pn(t + Δt) = Pn(t)(1 − λΔt) + Pn − 1(t)λΔt

Case 2: When n = 0,

 

P0(t + Δt) = P0(t)(1 − λΔt)

(or)

Integrating (12.6.2) with respect to t,

The constant A can be found by the condition

Substituting P0(0) = 1 in (12.6.3), we get

 

log P0(0) = log (1) = AA = 0

So (12.6.3) becomes

 

log P0(t) = −λt (or) P0(t) = eλt

Substituting n = 1 in (12.6.1), we get

 

P1′(t) = −λP1(t) + λP0(t)

, a differential equation of order one. Multiplying throughout by integrating factor I.F. = , we get

 

eλtP1(t) = λt + B

Substitute t = 0; then P1(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

 

PN(t + Δt) = PN(t)(1 − μΔt)
Pn(t + Δt) = Pn(t)(1 − μΔt) + Pn + 1 μΔt, 0 < n < N
P0(t + Δt) = P0(t) + P1(t)μΔt

As Δt → 0, we get

The solution yields

12.7 MODEL I: (M|M|1): (∞|FIFO) (BIRTH AND DEATH MODEL)

With usual notation, let Pn(t) denote the probability that there will be n units in the system. Pn(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 P0′(t) → 0, P0(t) → P0, (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

  1. Expected number of units in the system LS

    So,

  2. Expected queue length
  3. Expected waiting line in the queue
  4. Expected waiting line in the system
  5. Expected waiting time of a customer who has to wait
  6. Expected length of a non-empty queue
  7. Probability of queue size ≥ N = ρN
  8. Probability of waiting time in the system ≥
  9. Probability of waiting time in the queue ≥
  10. Traffic intensity

12.7.2 Little’s formula

So,

Similarly,

Now

That is,

(12.7.8)(12.7.11) are said to be Little’s formula.

Example 1

A self-service 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

  1. Average number of customers in the system.
  2. Average number of customers in queue or average queue length.
  3. Average time a customer spends in the system.
  4. Average time a customer waits before being served.

Solution: Arrival rate customers/minute

  1. Average number of customers in the system
  2. Average number of customers in the queue
  3. Average time a customer spends in the system minutes
  4. Average time a customer spends in the queue

Example 2

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 one-window drive-in-bank 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.

  1. What is the probability that an arriving customer can drive directly to the space in front of the window?
  2. What is the probability that an arriving customer will have to wait outside the indicated spce?
  3. How long is the arriving customer expected to wait before starting service?

Solution: We know

 

Pn = ρn (1 − ρ)

  1. The probability that an arriving customer can drive directly to the space in front of the window = P0 + P1 + P2
  2. Probability that an arriving customer will have to wait outside the indicated space = 1 − 0.42 = 0.58
  3. Average waiting time of a customer in the queue

Example 4

On an average 96 patients per 24-hours 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.

Example 5

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,

  1. 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 inter-arrival 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:

  1. The probability that a fresh arrival will not have to wait for the phone
  2. The probability that an arrival will have to wait for more than 10 minutes before the phone is free
  3. The average length of queues formed from time to time

Solution: Mean arrival rate

Mean service rate

  1. Probability that a fresh arrival will not have to wait = P0 = ρ0(1 − ρ) = 1 − ρ = 0.67
  2. Probability that an arrival will have to wait for more than 10 minutes
  3. The average length of queue from time to time
12.8 MODEL II: MULTI-SERVICE MODEL (M|M|S): (∞|FIFO)

When there are n units in the system, the following two cases will arrive:

  1. ns, all the customers may be served simultaneously. There will be no queue. (sn) number of servers remain idle. In this case μn = , n = 0, 1, 2, …, s.
  2. ns, all the servers are busy and the maximum number of customers waiting in queue will be (ns). Then μn = , λn = λ, for n = 0, 1, 2, …

The steady state difference equations are:

 

P0(t + Δt) = P0(t)(1 − λΔt) + P1(t) μΔt, for n = 0
Pn(t + Δt) = Pn(t)(1 − (λ + t) + Pn−1(t)λΔt + Pn+1(t)(n+1)μΔt, for n = 1, 2, …, s − 1

and

 

Pn(t + Δt) = Pn(t)[(1 − (λ + t)] + Pn−1(t)λΔt + Pn+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 → ∞, Pn(t) → Pn , 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

  1. Average length of queue
  2. Average number of units in the system
  3. Expected waiting time in the system
  4. Expected waiting time in the queue
  5. Expected length of the non-empty queue
  6. Expected waiting time of a customer who has to wait
  7. Probability of waiting time of a customer who has to wait
  8. Probability that there will be someone waiting
  9. Average number of idle servers = s − (average number of customers served)
  10. 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,

  1. what is the probability of having to wait for service?
  2. what is the expected percentage of idle time for each girl?
  3. if a customer has to wait, what is the expected length of the waiting time?

Solution: Given

  1.  
  2. The fraction of the time the service is busy so, the fraction of the time the service remains idle
  3. 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

where

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

So

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.

  1. What would be the effect on the average waiting time for depositors and withdrawers if each teller could handle both withdrawals and deposits?
  2. What would be the effect if this could be accomplished by increasing the service time to 3.5 minutes?

Solution:

  1. Average waiting time for depositors:

    Average waiting time for withdrawers:

    Combining the above cases,

    In this case, s = 2, so

  2. 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 P0 is determined from the equation Pn . That is, P0[1 + ρ + ρ2 + … + ρN] = 1

or

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

  1. the probability that the yard is empty
  2. average queue length on the assumption that the line capacity of the yard is limited to 4 trains only.

Solution: and N = 4.

  1. Average queue size = trains.

    = 0.04{ρ + 2ρ2 + 3ρ3 + 4ρ4}
    = 0.04 × 72
    = 2.9
    ≅ 3 trains.

Example 2

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

  1. The probability that the yard is empty.
  2. Average queue length assuming that the line capacity of the yard is 9 trains.

Solution: Given

  1. The probability that the queue size is Zero is given by
  2. 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 P0 and Pn.

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 Ns. 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

When

To determine Wq and hence Ws and Ls, we compute the value of λlost = λPN

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 NON-POISSON QUEUES

Queues in which arrivals and/or departures may not follow the Poisson axioms are called non-Poisson queues. The following techniques are employed while studying the non-Poisson queues:

  1. Phase technique
  2. The technique of imbedded Markov chain
  3. The supplementary variable technique.

The phase technique is used when an arrival demands phases of service, say k in number.

The technique by which non-Markovian queues are reduced to Markovian is called Imbedded Markov chain technique. When one or more random variables are added to convert a non-Markovian 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: GI|G|C, M|G|I, GI|M|S, GI|EK|1, DIEK|1, models.

We now consider a queuing system in which the service time has an Erlang type K-distribution with average service time as , for each exponential phase.

Model i (M\Ek\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 K-phases one-by-one and a new service does not start until all K-phases have been completed, therefore each arrival increases the number of phases by K in the system. Hence, a new arrival creates K-phases of service and departure of one customer reduces K-phases of service.

FIGURE 12.3 Service channels in series

If Pn(t) denotes the probability of n(>0) phases in the system at time t. At time t + Δt,

 

Pn(t + Δt) = Pn(t) (− λΔtOt)) (1 − ΔtOt))
+ Pn(t) (λ Δt) (Δt) + Pn + 1 (t) (1 − λΔtOt))
+ PnK(t) (λ Δt) (1 − ΔtOt)), n ≥ 1
P0 (t + Δt) = P0 (t) (1 − λΔt + Ot)) + P1 (t) (Δt), n = 0

Here, a negative subscript indicates the term is zero. As usual, the steady state difference equations are:

 

0 = − (λ + ) Pn + kμ Pn + 1 + Pnk, n ≥ 1
0 = − λ P0 + kμP1

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 zn 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 + z2 + … zk−1 = , it follows that

Now, we find P0 and Pn 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

P0 = 1 − ρk

Substituting the value of P0 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 zn 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

  1. Average number of phases in the system Lsp is given by

    by using the equation (1 + ρ) Pn = ρPnk + Pn + 1, n ≥ 1

  2. Average waiting time of the phase in the system is given by
  3. Average waiting time of an arrival is given by
  4. Average time an arrival spends in the systems is given by
  5. Average number of units in the system is given by
  6. Average queue length is given by

Model II (M|EK|1): (1|FIFO)

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 steady-state difference equations govern this model:

 

0 = − λP0 + kμP1,    n = 0
0 = − kμ Pk + λPo,     n = k
0 = − kμ Pn + kμPn + 1,     1 ≤ n ≤ k

These equations, provide us the following relations:

and,

 

Pn + 1 = Pn,     for 1 ≤ n < k

Now, we observe that P1 = P2 = … Pk−1 = Pk, we have

To obtain the value of P0, 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

  1. the average time a customer spends waiting in the cafeteria.
  2. the average time of getting the service.
  3. 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

  1. Average time a customer spends waiting in the cafeteria
  2. 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.
  3. 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 long-run 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 state-dependent system is controlled, then it is called under-dynamic control. Following are the objectives of dynamic control: Arrival Process Control

  1. To accept or reject control
  2. To adjust mean arrival rate
  3. Customer exercised control
  4. Self versus social optimisation
  5. Projection times

Service Process Control

  1. Varying a number of servers
  2. Varying the service times

Control of Queue Discipline

  1. Priority models
  2. Scheduling models
  3. Allocation of customers to multi-server 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

  1. traffic intensity
  2. service channels
  3. steady and transient state
  4. utilisation factor.

8. Show that if the inter-arrival 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 multi-server multi-channel 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 inter-arrival times.

15. Establish the probability distribution formula for pure-death 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 Pn of n customers in steady state satisfies the following equations:

 

λP0 = μP1     n = 0
(λ + μ) P1 = μP2     n = 1
(λ + μ) Pn = μPn + 1 + λ Pn − 1,     n ≥ 2

17. Define the cumulative probability distribution of waiting time for a customer who has to wait and show that in an (M|M|1): (∞ | FIFO) queue it is given by (1 − ρ)eμ/1 − ρ, where .

18. Write a short note on M|M|1 queue and its applications.

19. What are the various queuing models available?

20. Explain the following queuing systems:

  1. (M|M|R) : (GD | K), R < K
  2. (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

  1. utilisation factor for this service facility.
  2. probability of two units in the system.
  3. expected number of units in the queue.
  4. expected time in minutes that a customer has to spend in the system.

[Answer: (a) , (b) , (c) 1, (d) ]

22. At a one-man 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:

  1. Average number of customers in the shop and the average number of customers waiting for a hair cut.
  2. The per cent of time an arrival can walk right in without having to wait.
  3. 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

  1. the probability that the cashier is idle.
  2. the average number of customers in the queuing system.
  3. the average time a customer spends in the system.
  4. the average number of customers in the queue.
  5. 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. Non-productive 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 slow-cheap repairman asks 2 per hour and he will service machines at the rate of 4 per hour. The fast-expensive repairman demands 8 per hour, and will repair machines at the rate of 5 per hours. Which repairman should be hired?

[Answer: Fast-expensive repairman to be hired.]

Section 12.8

Model II

26. A telephone exchange has two long-distance operators. The telephone company finds that during the peak load, long-distance 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.

  1. What is the probability that a subscriber will have to wait for his long-distance call during the peak hours of the day?
  2. If the subscribers will wait and are serviced in turn, what is the expected waiting time?

[Answer: (a) P0 = 3/13; P(W > 0) = 0.48; Wq = 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 built-up 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 eight-hour 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.

  1. How many hours per week can a claims assistant expect to service the claimant?
  2. How much time does a claimant on average spend in the goods traffic office?

[Answer: (a) 72 hours     (b) 47.2 minutes.]

29. A two-channel 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

  1. probability of an empty system
  2. 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.)

  1. Customers arrive every 5 minutes and are served at the rate of 10 customers per hour.
  2. The average inter-arrival time is 2 minutes, and the average service time is 6 minutes.
  3. 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 inter-arrival 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 hour-day. 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.

  1. How many hours a week can an adjuster expect to spend with claimants?
  2. 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: P0 = 0.53, P1 = 0.27, P2 = 0.13, P3 = 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: Pn = (0.43) (0.75)n, P0 = 0.431, LS = 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 one-window drive-in-bank 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.

  1. What is the probability that an arriving customer can drive directly to the space in front of the window?
  2. What is the probability that an arriving customer will have to wait outside the indicated space?
  3. How long is an arriving customer expected to wait before starting service?
  4. 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, ,

  1. P0 + P1 = 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

  1. waiting time of an arrival
  2. length of the waiting line
  3. 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 one-man 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:

Ws = 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: Lq = 3.09 cars, Ls = 6.06 cars, Ws = 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 check-out counters. The sign by the check-out 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 check-out time per customer is exponential with a mean of 12 minutes. Determine the following:

  1. steady-state probability Pn of n customers in the check-out area
  2. average number of busy counters
  3. 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: P0 = 0.196, Ls = 6.28 cars, Lq = 5.26 cars, Ws = 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.

  1. Find the probability that the two repairmen are idle, that one repairman is idle.
  2. 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

  1. expected number of engineers waiting to use one of the terminals
  2. 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 stock-ups 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: Wq = 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.]