Queuing Theory

Queuing Theory

A flow of "customers" from infinite/finite population towards the service facility forms a queue or waiting line on account of lack of capability to serve them all at a time.These "customers" may be persons waiting at a railway booking office,these may be machines waiting to be repaired or letters arriving at a typist's desk.

Queuing Theory is the mathematical study of waiting lines,or queues.It examines every component of waiting in line to be served, including the arrival process, service process, number of servers, number of system places and the number of customers.

It is used to develop more efficient queuing systems that reduce customer wait times and increase the number of customers that can be served.

Applications

Queuing theory has its origins in research by Agner Krarup Erlang when he created models to describe the Copenhagen telephone exchange. The ideas have since seen applications including telecommunications, traffic engineering, computing and the design of factories, shops, offices and hospitals.

Some other examples of areas where queuing theory is used are :

• Traffic flow-avoiding congestion and trying to maintain a steady flow
• Computer scheduling
• Facility design and employee management
• Printer queues
• Manufacturing processes
• Commercial organizations serving external customers – Ex. Dentist, bank, ATM, gas stations, plumber, garage

Queuing System

A queuing system can be described as consisting of customers arriving for service,waiting for service if it is not immediate,and leaving the system after being served.

Elements of a queuing system

The basic elements of a queuing system are as follows:

• Arrival process:  This element is concerned with the pattern in which customers arrive for service.
• Service process: This element is concerned with service time and service facilities.
• Server channel: This element is concerned with providing service.
• Queue discipline: It is a rule according to which customers are selected for service when a queue has been formed.Some queue disciplines are- SIRO(Service in Random Order) ,FCFS (First Come First Served) or FIFO(First In First Out) ,LCFS(Last Come First Served) or LIFO(Last In First Out) ,priority schemes such as pre-emptive or non pre-emptive.
• Calling population: It is the source from which customers seeking service are generated.This could be finite or infinite.
• System capacity : It is the maximum no. of people allowed in the system.
• Customer's behaviour: 

         (i) Balking: customers deciding not to join the queue if it is too long.

         (ii)Jockeying: customers switch between queues if they think they will get served 
               faster by doing so.

         (iii)Reneging: customers leave the queue if they have waited too long for service.

Operating characteristics of a queuing system

Some of the operational characteristics of a queuing system used for evaluation of the performance of an existing queuing system and to design a new system are as follows:

1. Expected number of customers in the system denoted by ' L_s ' is the average number of customers in the system,both waiting and in service.
2. Expected number of customers in the queue denoted by 'L_q ' is the average number of customers waiting in the queue.
3. Expected waiting time in the system denoted by ' W_s' is the average total time spent by a customer in the system.It is generally taken to be the waiting time plus servicing time.
4. Expected waiting time in queue denoted by 'W_q'   is the average time spent by the customer in the queue before the commencement of service.
5. The server utilization factor(or busy period) denoted by 'P'(= λ/µ)  is the proportion of time that a server actually spends with the customers.Here, 'λ' stands for the average no. of customers arriving per unit of time and ' µ' stands for the average number of customers completing service per unit of time.

         The server utilization factor is also known as traffic intensity or the clearing ratio.

Deterministic Queuing System

A queuing system wherein the customers arrive at regular intervals and the service time for each customer is known and constant, is known as a deterministic queuing system.

Let the arrival rate be λ customers per unit time and the service rate be µ customers per unit time.Then,

• if λ > µ ,the waiting line(queue) shall be formed and will increase indefinitely;the service facility would always be busy and the service system will eventually fail.In such situations,the problem can be resolved by providing additional service facilities,like opening parallel counters.
• if λ ≤ µ ,there shall be no queue and hence no waiting time;the proportion of time the service facility would be idle is 1-λ/µ.

Probability distributions in queuing systems

It is assumed that customers joining the queuing system arrive in a random manner and follow a Poisson distribution or equivalently the inter-arrival times obey exponential distribution. In most of the cases,service times are also assumed to be exponentially distributed.It implies that the probability of service completion in any short time period is constant and independent of the length of time that the service has been in progress.

Pure birth and death models

Pure birth model

The model in which only arrivals are counted and no departure takes place are called pure birth models. An example of the pure birth model is the creation of birth certificates for newly born babies.

Let P_n(t) denote the probability of n arrivals in a time interval of length  t and mean arrival rate be λ

Then,           P_n(t)= (λt)ⁿ e^-λt  / n! ,for n≥0

Pure death model

The model in which only departures are counted and no other arrivals are allowed are called pure death models. 

    The system starts with N customers at time t=0 and no new arrivals are allowed.Departures occur at the rate µ customers per unit time.The probability P_n(t) of having n customers remaining after t time units is given by

   

               P_n(t)= (µt)^N-n  e^-µt  / (N-n)!  , n=1,2,3…,N

Birth-Death model( Generalized model)

This model deals with a queuing system having single service channel ,Poisson input with no limit on the system capacity .Arrivals can be considered as births to the system,whereas a departure can be looked upon as a death. This model is the basis for the derivation of specialized Poisson models.

The development of this model is based on steady-state and transient-state behaviour of queuing situation.

Steady state behaviour in a queuing situation is achieved after a system has been in operation for a sufficiently long time.This means the operating characteristics become independent of time.

Transient state behaviour in a queuing system is when its operating characteristics(like input,output,mean queue length,etc.) are dependent upon time.Such behaviour prevails during the early operation of the system.

Classification of queuing models

Generally queuing model may be completely specified in the following symbolic form:

                                             (  a / b /c ) : ( d / e )

where,

 a = arrivals distribution

 b = departures (service) distribution

 c = Number of parallel servers (=1,2,3...)

 d = system capacity

 e =  queue discipline

The first three elements of the notation (a/b/c) were devised by D.G. Kendall in 1953 and are known as Kendall's Notation. 

a and b can be represented as:

M = Markovian(or Poisson) arrivals or departures distribution (or equivalently exponential inter-arrival or service time distribution)

E_k = Erlangian or Gamma distribution of time

GI = General(generic) distribution of inter- arrival time

G = General(generic) service time distribution 

Poisson Queuing Systems

Queues that follow the Poisson arrivals are called Poisson queues.The following section explains some models that follow this system.

(M/M/1) : (∞/ FIFO) -Single Server Model
 This model deals with a queuing system having single service channel,Poisson input,Exponential Service and there is no limit on the system capacity while the customers are served on a "first in,first out" basis.

Characteristics of this model:

1. Probability of queue size being greater then or equal to 'k',the number of customers is given by                                            P(n≥k)= (λ/µ)ⁿ= ρⁿ 
2. Average number of customers in the system, ‘Ls ‘ is given by

                                                     L_s =ρ/ (1-ρ)  = λ/(µ-λ)
    3.  Average number of customers in queue ‘L_q‘ is given by  
                                                     L_q= ρ²/ (1-ρ) = λ²/ µ(µ-λ)

                               
    4.  Average waiting time ‘ W_s ‘of a customer in the system including service time is given             by
                                                W_s= L_s /λ = λ/ µ(µ-λ)

    5. Average waiting time ‘ W_q ‘of a customer in the queue is given by
                                                    W_q= L_q/λ = 1/ (µ-λ)

The relationship between L_s  and W_s (also L_q and W_q) is known as Little’s formula.

(M/M/C) : (∞/ FIFO) - Multiple Servers Model
In this model ,there are 'c' parallel servers.The arrival rate is λ and the service rate per service channel is µ.

Characteristics of this model:

1. The effect of using C parallel service channels is a proportionate increase in the service rate of the facility to nµ if n ≤ C and Cµ if n > C.Thus ,                                                            µn=nµ if 1 ≤  n ≤ C  and  Cµ if n ≥ C.

    2.Probability P₀ that there are no customers in the system is given by

                       P₀ = _n=0∑^c-1 { ρⁿ/n!   +  ρ^c/c!  ( 1/(1-ρ/c))}^-1

    3. Probability that an arrival has to wait
                        P(n ≥ C)=( ρ^c cµ P₀ ) / C!(Cµ-λ)

    4. Probability that an arrival enters the service without wait 
                                = 1- P(n≥C)

    5. Average queue length L_q  is given by
                           L_q = (ρ^cλµ P₀ )/ (C-1)! (Cµ-λ)²

    6. Average number of customers in the system  L_s  is given by
                             L_s  = L_q+ λ/µ
    7. Average waiting time an arrival spends in queue W_q is given by
                                   W_q=L_q/λ
    8. Average waiting time in system W_s is given by
                     W_s=  L_s /λ
      


(M/M/∞) : (∞/ FIFO) - Self Service Model
In this model,the number of servers is unlimited because the customer is also the server.In this case the service rate increases with increase in queue length and hence is known as a queuing problem with infinite number of channels.This model is a special case of Multiple servers model.

Characteristics of this model:

1. Since it is a self service model there can be no queues,hence L_q and W_q  are zero .
2. Average number of customers in the system  L_s  =ρ .
3. Probability that there will be n customers is given by

                                            P_n= (ρⁿe^-ρ ) / n!

                    where µ_n=nµ, λ_n=λ

Non-Poisson Queuing Systems

Queues in which arrivals and/or departures may not follow the Poisson axioms, are called non-Poisson queues. The development of these queuing systems is more complicated, mainly because the Poisson axioms no longer hold good. Some of the techniques which are usually employed in studying the non-Poisson queues:

1. Phase Technique
2. The technique of Imbedded Markov Chain
3. The Supplementary variable technique