Module 8. Queuing theory

Lesson 17

SOLUTION OF QUEUING MODELS

17.1  Introduction

The ultimate objective of the analysis of queuing systems is to understand the behavior of their underlying processes so that informed and intelligent decisions can be made in their management. In a specified queuing system the problem is to determine the probability distribution of queue length, waiting time of customers and the busy period. Queuing theory uses queuing models to represent the various types of queuing systems that arise in practice. Formulae for each model indicate how the corresponding queuing system should perform, including the average amount of waiting time under a variety of circumstances. Therefore, these queuing models are helpful in determining how to operate a queuing system in the most effective way. Providing too much service capacity to operate the system involves excessive costs. But not providing enough service capacity results in excessive waiting and all its unfortunate consequences. The models enable finding an appropriate balance between the cost of service and the amount of waiting.

17.2  Characteristics of A Queuing System

Queuing models enable the analyst to study the effect of manipulating decision variables on the operating characteristics of a service system. The most commonly used characteristics are stated as under:

17.2.1  Queue length

The average number of customers in the queue waiting to get service is known as ‘queue length’. ‘Short queues’ could mean either good customer service or large waiting space while ‘long queues’ could indicate low service efficiency or a little waiting space.

17.2.2  System length

It is the average number of customers in the system waiting to be served and those being served. Long queues imply congestion, potential customer dissatisfaction and need for more capacity.

17.2.3  Waiting time in queue

Waiting time is the average time that a customer has to wait in the queue to get service. Long waiting times may indicate a need to adjust the service rate of the system or change the arrival rate of customers.

17.2.4  Total time in system

The average time that customer spends in the system from entry in the queue to completion of service. If this time is more then there may be a need to change the priority discipline, increase productivity or adjust the capacity.

17.2.5  Server idle time

The relative frequency with which the service system is idle which is directly related to cost. Queuing theory analysis involves the study of systems’ behavior over time.

17.2.6  Transient and Steady States

When a service system is started, it progresses through a number of changes. However, it attains stability after some time. Before the service operations start, it is very much influenced by the initial conditions (number of customers in the system) and the elapsed time. This period of transition is termed as transient state. A system is said to be in transient-state when its operating characteristics are dependent on time.

However, after sufficient time has passed, the system becomes independent of the initial conditions and of the elapsed time (except under very special conditions) and enters a steady state condition. A steady state condition is said to prevail when the behavior of the system becomes independent of time. Let Pn(t) denote the probability that are n units in the system at time t. We know that the change of Pn(t) with respect to t is described by the derivative . Then the queuing system is said to be stable eventually, in the sense that the probability Pn(t) is independent of time, i.e. remains the same as time passes (t → ∞). Mathematically, in a steady state,

             

This implies that

                 

 From the practical point of view period of the steady state behavior of the system, queuing system under the existence of steady state condition are being considered.

17.3  Notations and Symbols

The notations used in the analysis of a queuing system are as follows:

 

      n =

Number of customers in the system (waiting and in service)

 Pn (t) =

Transient state probability that n calling units are in the queuing system at time t

     En=

The state in which there are n calling units in the system

     Pn =

Steady state probability of having n units in the system

λ =

Average (expected) customer arrival rate or average number of arrivals per unit of time in the queuing system

     μ =

Average (expected) service rate or average number of customers served per unit time at the place of service

      ρ =

Traffic intensity or server utilization factor

  s =

Number of service channels (service facilities or servers)

N =

Maximum number of customers allowed in the system.

Ls =

Average (expected) number of customers in the system (waiting and in service)

Lq =

Average (expected) number of customers in the queue (queue length)

Lb =

Average (expected) length of non-empty queue

Ws =

Average (expected) waiting time in the system (waiting and in service)

Wq =

Average (expected) waiting time in the queue

Pw =

Probability that an arriving customer has to wait

17.3.1  Kendall’s notation for representing queuing models

Generally queuing model can be specified by the symbolic representation (a|b|c) : (d|e)  where,

a :

Probability distribution of the arrival (or inter-arrival) time

b :

Probability distribution of the service time.

c :

Number of channels  (or service stations)

d :

Capacity of the system

e :

Queue discipline

The first three characteristics (a|b|c) in the above notation were introduced by D. Kendall in 1953.  Later in 1966, A. Lee added the fourth (d) and fifth (e) characteristics to the notation. Traditionally, the exponential distribution in queuing problems is denoted by M. Thus, (M|M|1): (∞|FIFO) indicates a queuing system when the inter-arrival times and service times are exponentially distributed having one server in the system with first in first out discipline and the number of customers allowed in the system can be infinite.

17.4  Traffic Intensity (or Utilization factor)

An important measure of simple queue is its traffic intensity, where

             

 

             

 

The unit of traffic intensity is Erlang.

A necessary condition for a system to have settled down to steady state is that

                              

i.e. arrival rate < service rate. If ρ > 1, the arrival rate is greater than the service rate and consequently, the number of units in the queue tends to increase indefinitely as the time passes on, provided the rate of service is not affected by the length of queue.

17.5  Queuing Models   

The queuing models are categorized as ‘deterministic’ or ‘probabilistic’. If each customer arrives at known intervals and the service time is known with certainty, the queuing model will be deterministic in nature. When both arrival and service rate are unknown and assumed to be random variable then this type of queuing model is known as probabilistic.

17.6  Probability Distributions in Queuing systems

The arrival of customers at a queuing system varies between one system and another, but in practice one pattern of completely random arrivals is observed.

17.6.1  Distribution of arrivals ‘the Poisson process’ (pure birth process)

The models in which only arrivals are counted and no departure take place are called pure birth models. In terms of queuing, birth-death process that is increased by birth or arrival in the system and decreased by death or departure of serviced customer from the system. If the arrivals are completely random, then the probability distribution of number of arrivals in a fixed time–interval, follows Poisson probability distribution with parameter (mean) λt. Thus,

               

17.6.2  Distribution of Inter–Arrival times (Exponential Process)

Inter–arrival times are defined as the time intervals between two successive arrivals. It will be proved that if the arrival process follows Poisson distribution, an associated random variable defined as the time between successive arrivals (inter-arrival time) follows an exponential distribution f(t) =  λe-λt and vice-versa.

The expected (or mean) time of inter arrival is given by  where λ is the mean arrival rate. Thus, t has the exponential distribution with mean 1/λ, we would intuitively expect that if the mean arrival rate is λ, then the mean time between arrival is 1/λ. Conversely, it can also be independent and have the exponential distribution then the arrival rate follows the Poisson distribution.

17.7  Classification of Queuing Models (Listing of Four Models)

The queuing models are classified as follows:

Model I

:

(M|M|1): (∞|FCFS)

Model II

:

(M|M|s): (∞|FCFS)

Model III

:

(M|M|1): (N|FCFS)

Model IV

:

(M|M|s): (∞|FCFS)

In this lesson Model I and II have been discussed as Model III and IV are beyond the scope of this course.

17.7.1  Model I (single channel queuing model with Poisson arrivals and exponential service times)

This model is symbolically represented as by (M|M|1): (∞|FCFS). This denotes Poisson arrival (exponential inter-arrival), Poisson departure (exponential service time), single server, Infinite capacity and ‘First come, First served’ service discipline. This model is also called ‘birth and death model’. This model is one of the most widely used and simplest models. It assumes the following conditions:

(i)           Arrivals are served on a ‘first come-first served’ (FCFS) basis.

(ii)         Every arrival waits to be served regardless of the length of the line.

(iii)       Arrivals are independent of preceding arrivals, but the average number of arrivals does not change over time.

(iv)       Arrivals are described by a Poisson probability distribution and come from an infinite population.

(v)         Service times also vary from one customer to the next and are independent of one another, but their average rate is known.

(vi)       Service times occur according to the negative exponential probability distribution.

(vii)     The average service rate is greater than the average arrival rate.

17.7.1.1  To obtain the system of steady- state equations

The probability that there will be n units (n>0) in the system at time (t+∆t) may be expressed as the sum of three independent compound properties by using the fundamental properties of probability, Poisson arrivals, and of exponential service times.  

(i) The product of three probabilities (Fig. 17.1)  

a)      that there are n units in the system at time t = Pn(t) 

b)      that there is no arrival in time ∆t = P0 (∆t) = 1 - λ∆t

c)      that there is no service in time ∆t = φ∆t (0) = 1 - μ∆t is given by

 

 

Fig. 17.1

 

Fig. 17.2

 

Fig. 17.3

 

(ii) The product of three probabilities (Fig. 17.2)

a)      that there are (n-1) units in the system at time t = Pn-1(t)

b)      that there is one arrival in time ∆t = P1 (∆t) = λ∆t

c)      that there is no service in time ∆t = φ∆r (0) = 1 - μ∆t is given by

(iii) The product of probabilities (see Fig. 17.3)

a)      that there are (n+1) units in the system at time t = Pn+1(t)

b)      that there is no arrival in time ∆t = P0 (∆t) = 1 - λ∆t

c)      that there is one service in time ∆t = φ∆t (1) = μ∆t is given by

Now, by adding above three independent compound probabilities, we obtain the probability of n units in the system at time (t + ∆t), i.e.,

            Pn (t+∆t) = Pn (t) [1- (λ+ μ) ∆t] + Pn-1 (t) λ∆t + Pn+1 (t) μ∆t +O(∆)                                                                                                                                                    ………(Eq. 17.1)

Where O(∆t) = O1 (∆t) + O2 (∆t) + O3 (∆t)

The equation may be written as    

           

Now, taking limit as ∆t → 0 on both sides,

           

            or

                                                                                                                                      ………(Eq. 17.2)           

In  a similar fashion, the    probability that there will be no unit (i.e. n = 0) in   the system at time (t + ∆t) will be the sum of the following two independent probabilities:

      (i) P[that there is no unit in the system at time t and no arrival in time

       

(ii)   P[that there is one unit in the system at time t, one unit serviced in ∆t  and no arrival in time ∆t] = P1(t) μ∆t (1 - λ∆the) ≡ P1 (t) μ∆t + O(∆t)

    Now, adding these two probabilities we get

            P0 (t+∆t) = P0 (t) [1- λ∆t] + P1(t) μ∆t + O(∆)                                                                                                                                                                         ………(Eq. 17.3)

                          

Now, taking limit as ∆t→0 on both sides,

                                                                                                                                                                                                         ………(Eq. 17.4)

Consequently the equations (17.2) and (17.4) can be written as

                                                                                                                                                                                                          ……… (Eq. 17.5)

                                                                                                                                                                                                              ……… (Eq. 17.6)
Equations (17.5) and (17.6) constitute  the system of steady state difference equations for the model.  

17.7.1.2  To solve the system of difference equations

We solve the difference equations given in (17.5) and (17.6) by the method of successive substitution. Since P0 = P0 and putting n=0 in equation (17.5) we get

                                                                                                                                ………(Eq. 17.7)

Now using the fact that  

               

                                                                                                                            .........(Eq. 17.8)

                                                                        

Now, substituting the value of P0 from (17.8) in (17.7), we get   

                                                                                                                                                                                                                  ……… (Eq. 17.9)

The equations (17.8) and (17.9) give the probability distribution of queue length

17.7.1.3  Measure of model 1

Expected (average) number of units in system (Ls) is given by

           

                                                                                                                                                               ……… (Eq. 17.10)

 

Expected (average) queue length (Lq) is given by:

Since there are (n-1) units in the queue excluding one being serviced

           
Substituting the value of P0 from equation 17.8

                                                                                                                                                                       ………(Eq. 17.11)

 

Expected (average) waiting time in the queue (excluding service time) (Wq) is given by:

                                                                                                                                                                                                                                        ……… (Eq. 17.12)

Expected (average) waiting time in the system (including service time) (Ws) is given by:

                                                                                                                                                                                                                             ……… (Eq. 17.13)

Expected (average) length of non-empty queue, (L/L > 0) is given by:

           
Expected variance of queue length is given by:

                          

Example 1

Customers arrive at a milk parlour being manned by a single Individual at rate of 25 per hour. The time required to serve a customer has exponential distribution with a mean of 30 per hour. Discuss the various characteristics of the queuing system, assuming that there is only one server.

Solution

Arrival rate (λ) = 25 per hour,  Service rate (μ) = 30 per hour

               

Expected number of units in system (Ls) =  

Expected queue length (Lq) =

Expected waiting time in the queue  

 Example 2

In a service department manned by one server, on an average 8 customers arrive every 5 minutes while the server can serve 10 customers in the same time assuming Poisson distribution for arrival and exponential distribution for service rate. Determine:

a)      Average number of customers in the system.

b)      Average number of customers in the queue.

c)      Average time a customer spends in the system.

d)     Average time a customer waits before being served.

Solution

Arrival rate (λ) = 8/5 =1.6 customers per minute.

Service rate (μ) = 10/5 = 2 customers per minute.

               

a)      Average number of customer in the system.

b)      Average number of customer in the queue.

c)      Average time a customer spends in the system.

    

d)      Average time a customer waits before being served

 

17.7.2  Model II (A) general erlang queuing model (Birth-Death Process)

This model is also represented by (M|M|1): (∞|FCFS), but this is a general model in which the rate of arrival and the service depend on the length n of the line.

17.7.2.1  To obtain the system of steady state equation

Let arrival rate λ = λn service rate μ = μn ; [depending upon n]

Then, by the same argument as for equations 17.1 and 17.3

            Pn (t+∆t) = Pn (t) [1- (λn + μn) ∆t] + Pn-1 (t) λn-1 ∆t + Pn+1 (t) μn+1 ∆t + O(∆t), n>0                                                                                                              ………(Eq. 17.14)

            P0 (t+∆t) = P0 (t) [1- λ0 ∆t] + P1 (t) μ1 ∆t + O(∆t), n = 0                                                                                                                                                         ……… (Eq. 17.15)

Now dividing equations (17.14) and (17.15) by ∆t, taking limits as ∆t → 0 and following the same procedure as in Model I, obtain

                                                                                                                                                                       ………(Eq. 17.16)

                                                                                                                                                                                                ………(Eq. 17.17)

 

The above written two equations are differential equations which could be solved if a set of initial values P0 (0), P1 (0),…, is given. Such a system of equations can be solved if the time dependent solution is required. But, for many problems it suffices to look at the steady state solution. 

In the case of steady state, the boundary conditions are

 

               

So the equations (17.16) and (17.17) become,

 

                                                                                                                                                                                      ……… (Eq. 17.18)

                                                                                                                                                                                                                               ……… (Eq. 17.19)

The equations (17.18) and (17.19) constitute the system of steady state difference equations for this model.

To solve the system of difference equations.

Since P0 = P0

                               

               

                 

             

            …        …        …

                                                                                                                                                                                                                                             ………(Eq. 17.20)

Now, in order to find P0, use the fact that

             

Where                                                                                                                                                                                                                     ………(Eq. 17.21)

 

 The result obtained above is a general one and by suitably defining μn and λn many interesting cases could be studied. Now two particular cases may arise:

Case 1
           

In this case, the series S becomes

                                                     

Therefore, from equation 17.21 and 17.20

               

Here, it is observed that this is exactly the case of Model 1.

Case 2  
           

The case, in which the arrival rate λn depends upon n inversely and the rate of service μn is independent of n, is called the case of ‘Queue with Discouragement’. In this case, the series S becomes

             

The equation 17.21 gives 

               

           

           

             …        …        …

             

It is observed in this case that Pn follows the Poisson distribution, where λ/μ = ρ is constant, however ρ ˃ 1 or ρ < 1 but must be finite. Since the series S is convergent and hence sum able in both the cases.

17.7.3  Model II (B) : (M|M|1):(∞ |SIRO)

This model is actually the same as Model I, except that the service discipline follows the Service in Random Order (SIOR) rule in place of FCFS rule. Since the derivation of Pn in Model I is independent of any specific queue discipline, so for the SIOR rule also

               

Consequently, the average number of customers in the customers in the system will be the same whether queue discipline follows SIRO rule or FCFS rule.