Skip to main content

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 ' Ls ' is the average number of customers in the system,both waiting and in service.
  2. Expected number of customers in the queue denoted by 'Lq ' is the average number of customers waiting in the queue.
  3. Expected waiting time in the system denoted by ' Ws' 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 'Wq'   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 Pn(t) denote the probability of n arrivals in a time interval of length  t and mean arrival rate be λ
Then,           Pn(t)= (λt)n 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 Pn(t) of having n customers remaining after t time units is given by
   
               Pn(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)
Ek = 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)= (λ/µ)n= ρn 
  2. Average number of customers in the system, ‘Ls ‘ is given by

                                                     Ls =ρ/ (1-ρ)  = λ/(µ-λ)
    3.  Average number of customers in queue ‘Lq‘ is given by  
                                                     Lq= ρ2/ (1-ρ) = λ2/ µ(µ-λ)
                               
    4.  Average waiting time ‘ Ws ‘of a customer in the system including service time is given             by
                                                Ws= Ls /λ = λ/ µ(µ-λ)

    5. Average waiting time ‘ Wq ‘of a customer in the queue is given by
                                                    Wq= Lq/λ = 1/ (µ-λ)
The relationship between Ls  and Ws (also Lq and Wq) 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 P0 that there are no customers in the system is given by
                       P0 = n=0∑c-1 { ρn/n!   +  ρc/c!  ( 1/(1-ρ/c))}-1

    3. Probability that an arrival has to wait
                        P(n ≥ C)=( ρc cµ P0 ) / C!(Cµ-λ)
    4. Probability that an arrival enters the service without wait 
                                = 1- P(n≥C)

     5. Average queue length Lq  is given by
                           Lq = (ρcλµ P0 )/ (C-1)! (Cµ-λ)2
    6. Average number of customers in the system  Ls  is given by
                             Ls  = Lq+ λ/µ
    7. Average waiting time an arrival spends in queue Wq is given by
                                   Wq=Lq/λ
    8. Average waiting time in system Ws is given by
                     Ws=  Ls /λ
      
(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 Lq and Wq  are zero .
  2. Average number of customers in the system  Ls  =ρ .
  3. Probability that there will be n customers is given by

                                            Pn= (ρne-ρ ) / 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
        
     














Labels:

Comments

Post a Comment

Popular posts from this blog

Advantages and Disadvantages of EIS Advantages of EIS Easy for upper-level executives to use, extensive computer experience is not required in operations Provides timely delivery of company summary information Information that is provided is better understood Filters data for management Improves to tracking information Offers efficiency to decision makers Disadvantages of EIS System dependent Limited functionality, by design Information overload for some managers Benefits hard to quantify High implementation costs System may become slow, large, and hard to manage Need good internal processes for data management May lead to less reliable and less secure data
1 comment
Read more

Inter-Organizational Value Chain

The value chain of   a company is part of over all value chain. The over all competitive advantage of an organization is not just dependent on the quality and efficiency of the company and quality of products but also upon the that of its suppliers and wholesalers and retailers it may use. The analysis of overall supply chain is called the value system. Different parts of the value chain 1.  Supplier     2.  Firm       3.   Channel 4 .   Buyer
Post a Comment
Read more

Big-M Method and Two-Phase Method

Big-M Method The Big-M method of handling instances with artificial  variables is the “commonsense approach”. Essentially, the notion is to make the artificial variables, through their coefficients in the objective function, so costly or unprofitable that any feasible solution to the real problem would be preferred, unless the original instance possessed no feasible solutions at all. But this means that we need to assign, in the objective function, coefficients to the artificial variables that are either very small (maximization problem) or very large (minimization problem); whatever this value,let us call it Big M . In fact, this notion is an old trick in optimization in general; we  simply associate a penalty value with variables that we do not want to be part of an ultimate solution(unless such an outcome is unavoidable). Indeed, the penalty is so costly that unless any of the  respective variables' inclusion is warranted algorithmically, such variables will ...
Post a Comment
Read more