UNIT 6 QUEUEING THEORY

Structure
6.1 Introduction
Objectives
6.2 Basic Concepts of Queueing Theory
Poisson Process
Birth and Death Process
6.3 Fundamental Structure of a Queueing System
6.4 Operating Characteristics of a Queueing System
Operating Characteristics
Classification of Queueing Systems
6.5 M/M/1 Queueing Model
Arrival-Departure Equations for M/M/1 Queueing Model
Operating Characteristics for the M/M/1 Queueing Model
6.6 Summary
6.7 Solutions /Answers

6.1 INTRODUCTION
Queueing is a common phenomenon in everyday life. We wait in queues in
post offices, banks, restaurants, railways and airline reservation counters.
Vehicles wait at traffic lights and aeroplanes circle around airports while
waiting to land. You can think of many more examples. In all such cases, there
are customers who require some sort of services after waiting in a queue for
some time. The customer may be a person, machine, vehicle or anything else
which requires service. In fact, waiting for service is an integral part of our
daily life and that too at considerable cost most of the times.
We would like to find ways of reducing the time spent in waiting by the
customer and at the same time optimising the cost to the service provider. This
is where the queueing theory, also known as the waiting line theory helps us.
It was developed in 1909 when A. K. Erlang made an effort to analyse
telephone traffic congestion. The purpose of queueing analysis is to provide
information to determine an acceptable level of service and service capacity
since providing too much service capacity is costly (owing to idle employees
or equipment). However, providing too little service capacity is also costly
(owing to waiting members in the queue). For example, when a hospital
consistently has a long queue in its emergency room, a large number of
waiting patients may aggravate the injury or illness.
In this unit, we first discuss the basic concepts of queueing theory in
Sec. 6.2, which would help you understand the techniques of queueing models.
In Secs. 6.3 and 6.4, we explain the fundamental structure and operating
characteristics of a queueing system. We describe the M/M/1 queueing model
and its applications in Sec. 6.5.
In the next unit, we shall discuss the sequencing problems and explain the
n-jobs, 2-machine and 2-jobs, m-machines, sequencing problems.
Objectives
After studying this unit, you should be able to:
 explain the Poisson process and the birth and death process in queueing
theory; 23
Optimisation Techniques-II  explain the fundamental structure of a queueing system;
 describe the operating characteristics of a queueing system;
 explain a single server queueing model with Poisson input and exponential
service time; and
 solve problems based on the M/M/1 queueing model.

6.2 BASIC CONCEPTS OF QUEUEING THEORY

For understanding queueing systems, you have to be familiar with the
probability theory. The concept of random variable and its probability
distribution such as Poisson distribution, Exponential distribution and Poisson
process play a significant role in describing queueing systems. You have
studied probability theory, random variable, Poisson and Exponential
distributions in the course MST-003 on Probability Theory. However, the
Poisson process is a new concept for you and we explain it, in brief. Let us
quickly recall a few basic definitions.
Consider an experiment whose outcome is not uniquely determined. In such a
situation an observed outcome of the experiment is one from a set of possible
outcomes. An outcome of an experiment is called a sample point and the set
of all possible outcomes of a random experiment is called a sample space.
Subsets of the sample space are called events. A random variable is a
function that associates a point of the sample space with a real number. A
random process or stochastic process is a family (or collection) of random
variables. For example, if a die with six faces numbered 1, 2, …, 6 is thrown,
the set of all possible outcomes is S={1, 2, 3, 4, 5, 6}. The set S is a sample
space. A function X that assigns to an outcome or sample point, the number
written on it, is the random variable. The event that an even number is
observed corresponds to the set {2, 4, 6} which is a subset of S.
Let us consider another simple experiment such as throwing a fair die.
1. Suppose Xn is the outcome of the nth throw, n ≥ 1. Then { Xn, n ≥ 1} is a
family of random variables, such that for a distinct value of n, one gets a
distinct random variable Xn. The sequence { Xn, n ≥ 1} constitutes a
random (stochastic) process known as the Bernoulli process.
2. Suppose Xn is the number of sixes in the first n throws. For a distinct value
of n = 1, 2, …, we get a distinct Binomial random variable. The sequence
Xn:{ Xn, n ≥ 1}, which gives a family of random variables, is a random or
stochastic process.
3. Suppose a telephone call is received at a switchboard. Let Xt be the
random variable, which represents the number of incoming calls in an
interval (0, t). Then Xt is a random variable and the family { Xt, t T}
constitutes a stochastic process, where T is the interval 0 ≤ t ≤  .
In Examples 1 and 2 above we saw that the subscript n of Xn was restricted to
non-negative integers n = 0, 1, 2, …. In these examples we observe the
outcome of a random variable at distinct time points n = 0,1, 2, …. Here, the
word „time‟ is used in a wider sense. You can visualise an infinite family of
random variables { Xt, t T} such that the state of the system is characterised at
every instant over a finite or infinite interval. The process (or collection) is
then defined for a continuous range of time and we say that we have a family
of random variables. On the other hand, the family { Xn, n =0, 1, 2, …} is
called a discrete parameter (or discrete time) stochastic process. The value of
Xn for a specific realisation of the process is called the state of the process at
24 the nth step. If the random variables Xn are discrete random variables, i.e., if
they take only integer values, it is called a discrete state process. Let us now Queueing Theory
explain the Poisson process used in the M/M/1 model being discussed in
Sec. 6.5.

6.2.1 Poisson Process

Suppose X(t) represents the maximum temperature at a particular place. Here
we deal with discrete state, continuous time stochastic processes, i.e., X(t) is a
discrete random variable. The Poisson process is one of the representatives of
this type of stochastic processes. It plays an important role in the study of a
large number of phenomena. The Poisson process may be described as
follows: Let E be a random event such as (i) incoming telephone calls at a
switchboard, (ii) arrival of patients for treatment at a clinic, (iii) occurrence of
accidents at a certain place.
We consider the total number N(t) of occurrences of an event E in an interval
of time „t‟. Suppose Pn(t) is the probability that the random variable N(t)
assumes the value n, i.e.,
Pn(t) = P[N(t) = n] … (1)
for n = 0, 1, 2, 3, …. We have


 P t   1 , for each fixed t.

n 0
n …(2)

We can thus say from equation (2) that Pn(t) is a probability mass function of
the random variable N(t) and the family of random variables {Nt, t > 0} is a
stochastic process. From our earlier discussion, you may understand that this
family is a continuous parameter (in this case, time) stochastic process with a
discrete state space. This is called a Poisson process. Under certain conditions,
N(t) follows a Poisson distribution with mean λt (λ being constant). This is
true for most practical situations.
Assumptions in Poisson Process
i) The process has independent increments. Future changes in N(t) are
independent of past changes in it, i.e., the number of customers which
arrive in disjoint time intervals are statistically independent.
ii) The probability of more than one occurrence of event E between time t and
t+∆t is o(∆(t)), i.e., the probability of two or more arrivals of customers
during the small interval of time ∆t is negligible. Thus,
P0(∆t) + P1(∆t) + o(∆t) = 1 … (3)
iii) The probability that event E occurs between time t and ∆t is equal to
λ∆t + o(∆(t)). Thus,
P1(∆t) = λ∆t + o(∆t),
i.e., P1(∆t) is approximately proportional to the length of the interval where
λ is the expected average number of arrivals of customers per unit time and
λ > 0. Here λ is constant and ∆t is an incremental element.
Under the assumptions stated above, N(t) follows a Poisson distribution
with mean λt, i.e., Pn(t) is given by

et  t 
n

Pn  t   , n = 0, 1, 2, 3, … . …(4)
n!
25
Optimisation Techniques-II To formulate a queueing model, we have to specify the assumed form of the
probability distributions of both inter-arrival times and service times. You
have learnt that inter-arrival times follow the Poisson distribution. Similarly,
most of the times, the service times in a queueing system follow the
exponential distribution. Hence, the exponential distribution is the most
important distribution in queueing theory, which we now discuss.
Suppose a random variable T represents either inter-arrival or service times. T
is said to have an exponential distribution with parameter α if its probability
density function is given by
e t for t  0
f (t)   …(5)
0 for t  0

Let N(t) denote the number of occurrences of an event E (say arrival or

number of telephone calls) in duration ∆t. There is an associated variable: the
interval T between two successive occurrences of event E. The interval T
between two successive occurrences of a Poisson process {Nt, t ≥ 0}, having
parameter λ, has an exponential distribution with parameter λ. If the intervals
between successive occurrences of an event E are independently distributed
with a common exponential distribution with parameter λ, the events follow a
Poisson process with mean λt, i.e., the probability distribution of the number
of times these kinds of events occur over a specified duration of time has a
Piosson distribution with parameter λt.
The basic methodology discussed here was developed initially by the Russian
mathematician, A. A. Markov, around the beginning of the 20th century. The
Markov Process forms a sub-class of the set of all random processes. It is a
sub-class with enough simplifying assumptions to make them easy to handle.
Mathematically, we define the Markov Process as follows:
Let { X(t), t ≥ 0} be a continuous time stochastic process taking on values in
the set of non-negative integers. If, for all tn, tn–1, …, t0, satisfying
tn> tn–1> …>t0, and non-negative integer j,
P[X(tn) = jn/ X(tn–1) =jn–1, …, X(t0) = j0] = P[X(tn) = jn/ X(tn–1) = jn–1],
the process has the Markov property and is called a continuous time Markov
process. Now we confine to Markov processes in which time is measured
discretely. The process is described by a sequence of random variables,
{X1, X2, X3, …}. Here the probability distribution of each Xi must be
specified. But it is not enough to specify a stochastic process, since Xis are not
independent. At this point we need Markov‟s simplifying assumption: A
Markov chain is a discrete time stochastic process in which each random
variable, Xi depends on the previous one, Xi–1 and affects only the subsequent
one, Xi+1. The term chain suggests the linking of the random variable to
neighbours in the sequence.

6.2.2 Birth and Death Process

The birth and death process is a special case of the general continuous time
Markov process. A birth and death process is characterised as a Markov
process in which all transitions are to be to the next state, immediately above
(a “birth”) or immediately below (a “death”) in the natural integer ordering
states, i.e., a birth and death process does not „jump‟ states. The Poisson
process is a special case of the birth-death process. It might be more
appropriate to call it a pure birth process since the death rates (μi) are all zero.
The birth rates, λi, are all equal to a constant value λ. The Poisson process is
26
often used to model the kind of situation in which a count is made of the Queueing Theory
number of events occurring in a given time. For example, it will be used in the
discussion of queueing models to represent the arrivals of customers to a
service facility. The state at time t would correspond to the number of arrivals
by time t. Pn (t) denotes the probability that there are n customers in the
system at any time t, both waiting and being served and Pn stands for time
independent probability that there are n customers in the system, both waiting
and being served. Arrivals can be considered as births. If the system is in state
En and an arrival occurs, the state is changed to En+1. Similarly, a departure can
be looked upon as death. A departure occurring while the system is in state En
changes the system to the state En–1. This type of process is generally referred
to as a birth-death process.
Assumptions in the Birth-Death Process
The assumptions of the birth-death process are as follows:
i) If the system is in state En, the current probability distribution of the time t
until the next arrival (birth) is exponential with parameter λn, where
n = 0, 1, 2, … .
ii) If the system is in state En, the current probability distribution of the time t
until the next departure or service completion (death) is exponential with
parameter μn, where n = 0, 1, 2, … .
iii) Only one birth or death can occur in a small interval of time, i.e., ∆t.
Having discussed the basic concepts and techniques for studying queueing
systems, we now explain the fundamental structure of a queueing
system.

6.3 FUNDAMENTAL STRUCTURE OF A

QUEUEING SYSTEM
Queueing theory is concerned with the mathematical study of queues or
waiting lines (seen in banks, post offices, hospitals, airports, etc.). The
formation of waiting lines usually occurs whenever the current demand for a
service exceeds the current capacity to provide that service.
In many cases, the customer‟s arrival and his or her service time are not
known in advance or cannot be predicted accurately. Otherwise, the operation
of the service facility could be scheduled in a manner that would eliminate
waiting completely. Both arrival and departure phenomena are random. This
necessitates mathematical modelling or queueing systems/ models to alleviate
waiting. It involves reducing excessive costs that result from creating excess
service capacity and at the same time ensuring that the system has enough
service capacity to avoid long waiting lines. There has to be a balance between
service capacity and waiting time. Therefore, an industry or an agency would
like to provide such services and also maintain balance between the cost of
service and the cost associated with waiting for the service.

A simple queueing system has the following fundamental structure:

Customers Served Output

Input Queue Service Source
Source Mechanism Customers

Fig. 6.1: Queueing system. 27

Optimisation Techniques-II A queueing system is described by the following elements:
1. Input or arrival process of customers;
2. Service mechanism; and
3. Queue discipline.
We now give a brief description of each of these components.
1. Input or Arrival Process of Customers
This is the element concerned with the pattern in which the customers arrive
and join the system. An input process is characterised by its size, the arrival
time distribution, and the attitude of the customers. We describe these, in brief.
i) Size: It may be finite or infinite according as the arrival rate is affected or
not affected by the number of customers in the service system.
ii) The arrival time distribution: In most cases, the arrivals occur in
accordance with a Poisson distribution.
iii) Customer behaviour:
 The customer may stay in the system until served. Such a customer is
known as Patient Customer.
 The customer may wait for a certain time and leave the system if
service is not commenced by that time. This kind of departure from the
queue without receiving the service is known as impatient or
reneging behaviour.
 When a customer arrives at a queueing system and perceives that the
number of customers already in the queue is too large, s/he does not
join the queue. This behaviour of the customers is known as balking
behaviour.
 When a customer moves from one waiting line to another because
he/she thinks that his/her queue is moving slower, the behaviour of the
customer is known as queue jockeying.
Generally, it is assumed that the customers arrive into the system one at a time.
But, sometimes, customers may arrive in groups and such arrival is called
bulk arrival.
2. Service Mechanism
Service time distributions are generally exponential distributions. A service
facility can be any one of the following types:
i) Single channel facility, i.e., one queue-one service station facility;
ii) One queue-several station facilities (e.g., booking at a service station that
has several service mechanisms);
iii) Several queues-one service station (e.g., railway station ticket counters);
iv) Multi-channel facility (e.g., several counters); and
v) Multistage Channel facility (e.g., various medical tests of a patient).

3. Queue Discipline
Queue discipline refers to the order in which the service station selects the
next customer from the waiting line to be served. It may be any one of the
following:
i) First In, First Out (FIFO) or in other words First Come First Served
(FCFS);
28
ii) Last In, First Out (LIFO); and Queueing Theory

iii) Service In Random Order (SIRO).

In this unit, we consider the FCFS queue discipline.
So far you have learnt the fundamental structure of a queueing system. We
now describe its operating characteristics.

6.4 OPERATING CHARACTERISTICS OF A

QUEUEING SYSTEM
We have set up a set of equations to study the queueing system. We have to
solve these equations to determine the operating characteristics. There are two
types of solutions of these equations: transient and steady state. The time
dependent solutions are known as transient solutions. For a complete
description of a queueing process, we need transient solutions. However, it is
difficult to obtain such solutions. Moreover, in many practical situations, we
usually need to know the system‟s behaviour in steady state, i.e., the behaviour
of the system when it reaches its equilibrium state after being in operation for
a long time. The steady state solution is independent of time and represents the
probability of the system being in a particular state in the long run.
A birth and death process gradually attains steady state after a sufficiently
large time has elapsed, provided that the parameters of the process permit
reaching the steady state. For example, queues with arrival rate λ higher than
the departure rate µ will not reach a steady state as the queue size will increase
with time. The ultimate objective of analysing queueing situations is to
develop measures of performance for evaluating the real system. Here we shall
be analysing the system under the steady state condition since the time
dependent analysis is beyond the scope of this course. Let us now list the
operating characteristics of a queueing system.

6.4.1 Operating Characteristics

The operating characteristics of a queueing systems are determined by two
statistical properties, namely, the probability distribution of inter-arrival times
and the probability distribution of service times. In the analysis of a queueing
system, we would like to compute various operating characteristics, i.e., the
measures of performance. These include:
1. The average number of customers in the queueing system (Ls), i.e., those
waiting to be served and those being served.
2. The average time each customer spends in the queueing system from
entry into the queue to completion of the service (Ws), i.e., the time spent
waiting in the queue and during the service.
3. The average number of customers in the queue waiting to get service
(Lq), i.e., this excludes customers undergoing service.
4. The average time each customer spends waiting in the queue to get
service (Wq), i.e., this excludes time spent during the service.
5. The relative frequency with which the service system is idle is called
service idle time. Though the idle time is directly related to the cost, its
reduction may have adverse effects on other characteristics.
These equations can be used to study the time dependent behaviour as well .
We now state the equations for each of the operating characteristics listed
above under steady state condition. 29
 Optimisation Techniques-II By definition of expectation, we have

Ls   nPn … (6)
n 1

Suppose that arrivals follow Lq   n  cP

n  c 1
n … (7)
the Poisson distribution, and
the inter-arrival times follow where there are c parallel servers so that c customers can be served
exponential distributions simultaneously. With λ arrival rates for those who join the system, we have
[Chapter 4 of Stochastic
Process by J. Medhi]. The Ls = λWs and Lq = λWq … (8)
exponential distribution has 1
memoryless property, which If µ is the service rate, the expected service time is and we have
means that the future is 
independent of the past. It 1
depends only on the present Ws  Wq  …(9)
and hence the Markov property 
[Unit 15, Block 4 of MST-003:
Probability Theory and
Multiplying both sides of equation (9) with λ, we get
Chapter 3 of Stochastic Process 
by J. Medhi] is satisfied by the Ls  L q  …(10)
inter-arrival times. Therefore, 
symbol 'M' has been used in
place of 'a' to represent the 6.4.2 Classification of Queueing Systems
Markov property. Also, if
service times follow the
A queueing system is usually described by five symbols and denoted as
exponential distribution, then a / b / c: d / e or separated by slashes as a / b / c / d / e. The first symbol „a‟
the service time distribution describes the arrival process. The second symbol „b‟ describes the service time
too has the Markov property distribution. The third symbol „c‟ stands for the number of servers. The
and hence symbol 'M' can be symbols „d‟ and „e‟ stand for system capacity and queue discipline,
used in place of 'b'.
respectively. If the system has FCFS queue discipline, the queueing system
may be described as a / b / c / d, i.e., the fifth symbol may be omitted in this
case. If a system has infinite capacity with FCFS queue discipline, the
queueing system may be described as a/b/c : ∞ / FCFS or simply a/b/c.
Note: If arrivals follow the Poisson distribution, the symbol M is used in
place of „a‟. If departures are exponential, the symbol M is used in place of
„b‟. The explanation for using the symbol M is given in the margin for the
sake of interest.
So far you have learnt about the operating characteristics of a queueing
system. We now discuss the M/M/1 queueing model and determine its
operating characteristics.

6.5 M/M/1 QUEUEING MODEL

As the symbol indicates, the M/M/1 queueing model deals with a queueing
system having a single service channel with Poisson input, exponential
distribution for services and there is no limit on the system capacity while the
customers are served on a “First Come First Served” basis.
For this model, arrivals follow Poisson distribution and hence inter-arrival
times have an exponential distribution. Let  denote the average arrival rate.
Therefore, 1/  is the mean arrival time. For example, if customers arrive at a
rate of 15 per hour, it means that on an average, 1 customer arrives in every 4
1
minutes, i.e., the mean arrival time is hr or 4 minutes (the reciprocal of the
15
arrival rate). The service times for this model follow an exponential
distribution. Let µ denote the average service rate. Hence, 1/ µ is the mean
service time.
30
Then the ratio Queueing Theory


 … (11)


is called the traffic intensity or the utilisation factor. It is a measure of the

degree to which the capacity of the service station is utilised. For example, if
customers arrive at a rate of 15 per minute and the service rate is 20 per
15
minute, the utilisation of the service facility is  75% , i.e., the service
20
facility is kept busy 75% of the time and remains idle 25% of the time.

6.5.1 Arrival-Departure Equations for M/M/1 Queueing Model

In this section, we obtain the arrival-departure equations for M/M/1 queueing
model. But before doing so, it is necessary to state the postulates of the
Poisson process, which are as follows:
i) The number of occurrences of an event in an interval of duration t are
independent of the number of occurrences in an interval prior to the
interval (0, t), i.e., future changes are independent of past changes.
ii) The probability of n customers in 't' depends only on the duration 't' of
the interval and is independent of where this interval is situated. Let
Pn (t) be the probability of n customers in an interval t. Then Pn (t) also
gives the probability of a number of occurrences of an event in the
interval (a, t + a), which is of duration t for every 'a'. For example, the
interval may be (5, 5 + t) (7, 7 + t) or any other interval of duration t. For
all these intervals, the probability will have homogeneity in time, i.e., it
will remain Pn (t) for all intervals of duration t.
iii) In an interval of infinitesimal duration t , i.e., for very small t , the
probability of exactly one occurrence is t  o  t  and that of more than
one occurrences is o  t  , where o  t  is a function of t which tends to
0 more rapidly than t . The function o  t  contains the terms of squares
o(t)
and higher powers of t . Thus, as t  0 ,  0 . In other words,
t
P1 (t) = t  o  t  , … (12)

and P2 (t)  P3 (t)  P4 (t)  P5 (t)  ...  o  t  … (13)

Since the sum of probabilities for occurrence/non-occurrence of an event is 1,

we have
P0 (t)  P1 (t)  P2 (t)  P3 (t)  P4 (t)  ...  1 … (14)
Therefore,
P0 (t)  1  P1 (t)  {P2 (t)  P3 (t)  P4 (t)  ...}
 1  {t  o  t }  {o  t } … (15)
 1  t  o  t 
Since o(∆t) is a fuction containing squares and higher powers of
(∆t), o(∆t) + o(∆t) is very small and has been written as o(∆t) in equation (15).
31
Optimisation Techniques-II Now, we can write the arrival-departure equations for the M/M/1 queueing
model as follows:
If n  1, the probability of n customers in the system at time t + t
= [{Probability of n – 1 customers in the system at time t and (1 arrival, no
departure in time t or 2 arrivals, one departure in time t or 3 arrivals,
two departures in time t or . . .)} + {Probability of n – 2 customers in the
system at time t and (2 arrivals, no departure in time t or 3 arrivals, one
departure in time t or 4 arrivals, two departures in time t or . . .)}+
{Probability of n – 3 customers in the system at time t and (3 arrivals, no
departure in time t or 4 arrivals, one departure in time t or 5 arrivals,
two departures in time t or . . .)}+ ...]
+ [{Probability of n + 1 customers in the system at time t and (1
departure, no arrival in time t or 2 departures, one arrival in time t
or 3 departures, two arrivals in time t or . . .)} + {Probability of n + 2
customers in the system at time t and (2 departures, no arrival in time t
or 3 departures, one arrival in time t or 4 departures, 2 arrivals in time
t or . . .)} + {Probability of n + 3 customers in the system at time t and
(3 departures, no arrival in time t or 4 departures, one arrival in time
t or 5 departures, two arrivals in time t or . . .)}+ ...] + [{Probability
of n customers in the system at time t and (no arrival, no departure in
time t or 1 arrival, one departure in time t or 2 arrivals, 2 departures
in time t or . . .)]

 Pn 1 (t). {t  o  t }{1  t  o  t }  The terms equal to o  t  

 Pn 2  t  . {o  t }{1  t  o  t }  The terms equal to o  t  
 Pn 3  t  .o  t   The terms equal to o  t 
 Pn 1 (t). {t  o  t }{1  t  o  t } The terms equal to o  t  
 Pn  2  t  . {o  t }{1  t  o  t }  The terms equal to o  t  
 Pn 3  t  .o  t   The terms equal to o  t 
 Pn (t).[{1  t  o  t }{1  t  o  t }  {t  o  t }{t  o  t }
 The terms which ultimately become equal to o  t ]

Notice that t.o  t  ,o  t  .o  t  ,o  t   o  t  ,o  t   o  t  , t. t are

very small and may be taken as equal to o  t  .
We deal with the case n = 0 separately because there cannot be any possibility
of less than zero customers. However, in the above equation, the case of less
than n customers is included.
The probability of 0 customers in the system at time t + t
= [{Probability of 1 customer in the system at time t and (1 departure, no
arrival in time t or 2 departures, one arrival in time t or 3 departures,
two arrivals in time t )} + {Probability of 2 customers in the system at
time t and (2 departures, no arrival in time t or 3 departures, one
arrival in time t or 4 departures, 2 arrivals in time t )}+ {Probability
of 3 customers in the system at time t and (3 departures, no arrival in
time t or 4 departures, one arrival in time t or 5 departures, two
32 arrivals in time t )}+ ...] + [{Probability of 0 customers in the system at
 time t and (no arrival, no departure in time t or 1 arrival, one Queueing Theory

departure in time t or 2 arrivals, 2 departures in time t )]

 P1 (t). {t  o  t }{1  t  o  t }

 The terms which ultimately become equal to o  t  
 P2  t  . {o  t }{1  t  o  t }
 The terms which ultimately become equal to o  t  
 P3  t  .o  t   The terms which ultimately become equal to o  t 
 P0 (t).[{Probability of no departure which is1as there is no customer
in system and hence no chance of departure}.{1  t  o  t }
 {t  o  t }{t  o  t }  The terms which ultimately become equal to o  t ]
Therefore, the arrival-departure equations for the M/M/1 queueing model are:
 Pn  t  t   Pn 1 (t). t  o  t    Pn 1  t  t  o  t  

  Pn  t  t  o  t   t  o  t  

  Pn  t  1  t 1  t   o  t  , n  1

 P0  t  t   P1  t  t  o  t    P0  t  t  o  t   …(16)
  P0  t  1  t  .1  o  t  , n  0

 Pn  t  t   Pn 1  t  .t  Pn 1  t  t

  Pn  t  1  t  t   o  t  , n 1 ...(17)

 P0  t  t   P1  t  t  P0  t  1  t   o  t 

Dividing equation (16) by t and taking the limit as t tends to zero, we have
pn  t    Pn 1  t    Pn 1  t        Pn  t 
Pn  t  t   Pn  t 
[lim  pn  t   derivative of Pn  t ] ...(18)
n t

and p0  t    P0  t    P1 (t) ...(19)

When steady state, i.e., the equilibrium state, is reached, pn (t) becomes
independent of time, say pn , and the rate of its change with respect to time
becomes zero, i.e.,
pn (t)  0
Therefore, the steady-state solution is given by

 Pn 1   Pn 1       Pn  0, n  1


 P1  P0
 ...(20)

Now, from equation (20), we have

 Pn 1  Pn   Pn   Pn 1 … (21)
33
Optimisation Techniques-II This implies that

 Pn  Pn1   Pn1   Pn2 (changing n to n  1)

 Pn1  Pn2   Pn2   Pn3 (again changing n to n  1)

 Pn 2  Pn 3   Pn 3   Pn 4 (again changing n to n  1)

...
...
...
 P2  P1   P1   P0

But,  P1   P0  0 [ P1   P0 ]

Therefore,  Pn1  Pn   Pn   Pn1

  Pn1   Pn2

  P1   P0 =0

This implies that

l
Pn = Pn - 1
m

 
 ( Pn 2 )
 

 
 ( Pn 3 )
 
...

λ.λ...λ(n times)
= P0
μ.μ...μ(n times)

n
 n P0  ( / )n P0  n P0


 
Since  Pn  1 , it follows that
n 0
P 
n 0
0
n
1

 P0 (1    2  ...  n )  1
1
 P0 ( )  1  P0  1  
1 

Therefore, the probability of n customers (units) in the system is given by

Pn  1  n , n  0 … (22)

We can now determine the operating characteristics for the M/M/1queueing

model.
34
 Queueing Theory
6.5.2 Operating Characteristics for the M/M/1 Queueing
Model
1. The average number of customers in the system is given by
 
Ls  E(n)   nPn   nn (1 )
n 0 n 0


 (on simplification) ...(23)
1 

or Ls  … (24)

2. The average queue length is

Lq =Ls - Traffic intensity

r
=Ls - r = -r
1- r

r2 l2
or Lq = = … (25)
1 - r m( m- l )
3. The average time an arrival spends in the system is
Ls 1
Ws   … (26)
 
4. The average waiting time of an arrival in the queue is
Lq 
Wq   … (27)
    
Wq can also be obtained using the following result:
1
Wq = Ws - … (28)
m
5. The probability that the number of units waiting in the queue and the
number of units being serviced is greater than k is
Pn  k   k 1 … (29)

6. The probability of having a queue, i.e. 1  P0  =  … (30)

We now illustrate the M/M/1 queueing model with some examples.
Example 1: A TV repairman finds that the time spent on his job has an
exponential distribution with mean 30 minutes. If he repairs sets in the order in
which these come in, and if the arrival of sets is approximately Poisson with an
average rate of 10 per 8-hour day, what is the repairman‟s expected idle time each
day? How many jobs are ahead of the average set just brought in?
Solution: It is given that
10
Arrival rate     arrivals / hr
8
60
Service rate      2 services / hr
30
35
Optimisation Techniques-II  The probability of the repairman being idle is P0 = 1  
 5 3
or P0  1   1 
 8 8
3
Hence, the idle time in the 8-hour day =  8 hours = 3 hours
8
Now, the average number of jobs that are ahead of the set just brought in
= Average number of units in the system

10

=  8  1.67
   2  10
8
Example 2: Customers arrive at a window in a bank, according to a 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 customers can accommodate a maximum of three customers. Other
customers can wait outside this space.
a) What is the probability that an arriving customer can go directly to the
space in front of the window?
b) What is the probability that an arriving customer will have to wait outside
the indicated space?
c) How long is an arriving customer expected to wait before being served?

Solution: Arrival rate  = 10 per hour

60
Service rate   per hour = 12 per hour
5
10 5
 
12 6
a) From equation (22), the required probability = P0 + P1 + P2
= (1 - r ) +(1 - r ) r +(1 - r ) r 2  0.42
b) The required probability = P3 + P4 + P5 + ………
= 1 – (P0 + P1 + P2)
 1  0.42  0.58

c) Expected waiting time before being served = Wq 
   
10
= = 0.417 hours
12 (12 - 10)
Example 3: Arrivals of machinists at a tool crib are considered to be Poisson
distributed at an average rate 6 per hour. The length of time the machinists
must remain at the tool crib is exponentially distributed with average time of
0.05 hours.
a) What is the probability that a machinist arriving at the tool crib will have
to wait?
b) What is the average number of machinists at the tool crib?
36
c) The company will install a second tool crib when convinced that a Queueing Theory
machinist would have to spend 6 minutes in waiting and being served at
the tool crib. At what rate should the arrival of machinists to the tool crib
increase to justify the addition of a second crib?
Solution: a) Here the arrival rate  = 6/hr and the service rate  = 20/hr.
Therefore, the probability of zero customer in queue is
 6
P0 = 1 –  where   
 20

6 14 7
or P0  1  =  = 0.7
20 20 10
The probability that a machinist arriving at the tool crib will have to wait
= Probability that there is at least one machinist at the tool crib
= 1– Probability that there is no machinist at the tool crib
= 1 – P0  1  0.7  0.3
b) The average number of machinists at the tool crib is given by
 6 6
Ls =    0.428  0.43
   20  6 14
c) The company is ready to install a second tool crib when convinced that a
machinist would have to spend 6 min. in waiting and being served. Let the
increased arrival rate be ’.
1
Waiting time in the system = 6 min. = hr. We have
10
1 1

   ' 10
1 1
or  or 10 = 20  
20   ' 10
  = 20  10= 10/hr.
The increase is, therefore, (10 – 6)/hr = 4/hr.
Example 4: A repairman is to be hired to repair machines which break down
at an average rate of 3 per hour. The breakdown follows a Poisson distribution.
Nonproductive time of a machine is considered to cost `10 per hour. Two
repairmen have been interviewed of whom one is slow but charges less and the
other is fast but more expensive. The slow repairman charges `5 per hour and
services breakdown machines at the rate of 4 per hour. The fast repairman
demands `7 per hour, but services breakdown machines at an average rate of 6
per hour. Which repairman should be hired?
Solution: The data given is summarised below:
Slow/Less expensive Repairman Fast/ More expensive Repairman
 = 3/hr,  = 4/hr, Labour cost = `5/hr  = 3/hr,  = 6/hr, Labour cost = `7/hr

Case of Slow/Less expensive Repairman

Cost of engaging slow repairman for 8 hours
= Breakdown cost + Labour cost for 8-hour working day.
37
Optimisation Techniques-II = (No. of breakdowns per hr) × 8 hours × Av. time spent in the system
× (Breakdown cost/ cost for non-productive time )
+ Labour cost per hr × 8 hours
= ()× 8 × Ws × 10 + 5 × 8
1 1
Since the average time spent in the system is Ws =   1,
 43
the total cost for engaging the slow repairman is
3 × 8 × 1 × 10 + 5 × 8 = 240 + 40 = `280
Case of Fast/More expensive Repairman
The cost of engaging fast repairman for 8 hours
= Breakdown cost + Labour cost in 8-hour working day.
= (No. of breakdowns per hr) × 8 hours × Av. time spent in the system
× (Breakdown cost/ cost for non-productive time )
+ Labour cost per hr × 8 hours
= ()  8  Ws  10 + 7  8
1 1 1
Since the average time spent in the system is Ws =   ,
  63 3
the total cost for engaging the fast repairman is
1
3´ 8´ ´ 10 + 7 ´ 8 = 80 + 56 = `136
3
Since the total cost of engaging the fast repairman is less, we should engage
the fast repairman.
You should now apply the M/M/1 model to solve the following exercises.

E1) Customers arrive at a box office window being served by a single

individual according to a Poisson input process with a mean rate of 30
per hour. The time required to serve a customer has an exponential
distribution with a mean of 90 seconds. Find the average waiting time of
a customer in the queue.
E2) Arrivals at a telephone booth are considered to be Poisson with an
average time of 10 minutes between one arrival and the next. The length
of a phone call is assumed to be distributed exponentially with mean 3
minutes.
a) What is the probability that a person arriving at the booth will have
to wait?
b) The telephone company will install a second booth when convinced
that an arrival would be expected to wait at least 3 minutes for the
phone. By how much should the flow arrivals increase in order to
justify the setting up of a second booth?
E3) A fertiliser company distributes its products by trucks loaded at its only
loading station. Both company trucks and contractor‟s trucks are used for
this purpose. It was noticed that on an average one truck arrived every 5
minutes and the average loading time was 3 minutes. Forty percent of the
trucks belong to the contractor. Determine the expected waiting time of
contractor‟s trucks per day.
E4) In a railway marshalling yard, goods trains arrive at a rate of 36 trains
38 per day. Assuming that the inter-arrival time follows exponential
 distribution and the service time distribution is also exponential with an Queueing Theory
average of 30 minutes, calculate the following:
a) The mean line length (mean length of the system).
b) The probability that the queue size exceeds 10.
c) If the input increases to an average of 42 per day, what will the
change in (a) and (b) be?
E5) A road transport company has one reservation clerk on duty at a time.
She handles information of bus schedules and makes reservations.
Customers arrive at a rate of 8 per hr and on an average the clerk can
service 12 customers per hr.
i) What is the average waiting time of a customer in the system?
ii) The management is contemplating to install a computer system to
handle the information and reservations. This is expected to reduce
the service time from 5 to 3 minutes. The additional cost of having
the new system works out to be `50/- per day. If the cost of the
goodwill of having a customer to wait is estimated to be 12 paise per
minute spent waiting before being served, should the company install
the computer system? Assume an 8-hour working day.
iii) What is the expected waiting time of all the customers in an 8-hour
day?

Let us summarise the concepts that we have discussed in this unit.

6.6 SUMMARY
1. The purpose of queueing theory is to provide information for determining
an acceptable level of service since providing too much service capacity is
costly (owing to idle employees or equipment) and providing too little
service capacity is also costly (owing to waiting members of the queue). A
queueing system is described by three elements: (1) Input or arrival
process of customers, (2) Service mechanism, and (3) Queue discipline.
2. Input process is concerned with the pattern in which the customers arrive
and join the system. An input process is characterised by its size, the
arrival time distribution, and the attitude of the customers.
3. Service time distributions are generally exponential distributions. Service
facility can be 'Single channel facility' or 'One queue-several station
facilities' or 'Several queues-one service station', 'Multi-channel facility' or
'Multi-Stage Channel facility'.
4. Queue discipline refers to the order in which the service station selects the
next customer from the waiting line to be served. It may be FCFS, LIFO or
SIRO. In this unit, the FCFS queue discipline has been considered.
5. The time dependent solutions are known as transient solutions. Steady
state solution is independent of time and represents the probability of the
system being in the equilibrium state.
6. A queueing system is usually described by five symbols such as a/b/c : d/e
or a/b/c/d/e. The first symbol „a‟ describes the arrival process. The second
symbol „b‟ describes the service time distribution. The third symbol „c‟
stands for the number of servers. The symbols „d‟ and „e‟ stand for system
39
Optimisation Techniques-II capacity and queue discipline, respectively. If arrivals are Poisson, symbol
M is used in place of „a‟ If departures are exponential, symbol M is used
in place of „b‟.
7. The M/M/1 queueing model deals with a queueing system having single
service channel, Poisson input, and exponential services. There is no limit
on the system capacity while the customers are served on a “First Come
First Served” basis. The probability of n customers (units) in the system
for this model is

Pn  1  n , n  0 ,

where  = ,  is the average arrival rate and µ, the average service rate.

Some important characteristics of this model are:

 Average number of customers in the system ( Ls ) 

2
 Average queue length (Lq )  Ls   
    
Ls 1
 Average time an arrival spends in the system (Ws )  
 
 Average waiting time of an arrival in the queue

Lq  1
(Wq )   = Ws 
      

6.7 SOLUTIONS/ANSWERS
E1) Arrival rate () = 30/hr
1 60  60
Service rate () = /seconds = /hr
90 90
Therefore, the average waiting time of a customer in a queue is
 30 3
Wq = =  hours
(  ) 40(40  30) 40
3
= ´ 60 minutes = 4.5 minutes
4
E2) We are given that
1
Arrival rate () = per minute
10
1
Service rate () = person/minute
3
a) The probability that a person arriving at a booth will have to wait
= Probability that there is at least one customer
= P(n > 0) = 1 – P0 = /
1 3
=  = 0.3
10 1
40
 b) The installation of the second booth will be justified only if the Queueing Theory
arrival rate is more than the waiting time. Let  be the increased
arrival rate.
Then the expected waiting time in queue is
' '
Wq   3
(   ') 1 1
(   ')
3 3
1
Thus  = per minute
6
Hence, the increase in the arrival rate is
1 1 1
= – = per minute
6 10 15
E3) We are given that
60
Arrival rate () = 1/5 per minute  = 12 per hour
5
1 60
Service rate ()  per minute = = 20 per hour
3 3
The expected waiting time of contractor‟s trucks per day
= Expected waiting time for a truck  Number of contractor‟s
trucks per day

=  (40 per cent of the total number of trucks per day)
(  )

=  [40 per cent of (Arrival rate per hr  24 hours)]
(  )
 40
=   (12  24)
(  ) 100
12 40
=   (12  24) = 8.64 hours
20(20  12) 100
E4) We are given that
Arrival rate () = 36 trains/day
Service rate () =1 per 30 minutes
60 60
= per hour =  24 per day = 48 trains/day
30 30

Therefore, traffic intensity    0.75

a) Mean length of system
 36 36
Ls    = 3 trains
   48  36 12
b) Probability that the queue size exceeds 10
= Probability that the system size exceeds 11

i.e., P(n > 11) = 111 = (0.75)12

41
Optimisation Techniques-II c) If the input increases to an average of 42 per day, then
the arrival rate ( )= 42/day.
42 7
Hence, the new traffic intensity  '  
48 8
' 42 42
Therefore, in this case, Ls    = 7 trains
   ' 48  42 6
12
7
and the probability that the queue size exceeds 10 is ( ')111   
8
E5) We are given that
Arrival rate () = 8/ hr,
Service rate () = 12/ hr
i) Average waiting time of customers in the system is
1 1 1
Ws    hr
   12  8 4
ii) An arrival waits for Wq hours before being served and there are 
arrivals per hour. Thus, the expected waiting time for all customers
in an 8-hour day with one system
= 8  Wq
With the existing system, the waiting time for the customers,
therefore, is
l 8
= 8´ 8´ = 8´ 8´
mm-
( l) 12(12 - 8)
64
= hours = 640 min.
6
The goodwill cost per day with the existing system
12
 640  = ` 76.80
100
If a computer system is installed, the service rate is 1 per 3 minutes or
20 per hr. Hence, the expected waiting time in this case = 8  Wq
8 1
=8´ 8´ =8´ 8´ hr = 128 min.
20(20 - 8) 30
The goodwill cost per day when the computer system is installed
12
= 128 ´ ` = ` 15.36
100
The additional cost of computer system = ` 50
Therefore, the total cost of having the computer system
= ` (50 + 15.36) = ` 65.36
Since this amount is less than the goodwill cost to be incurred with the
existing system, the management should install a computer system.

42