RB/QUEUING/CN/1

QUEUING (WAITING LINE) THEORY

A queue is formed when:

  • Customers wait for service , or
  • Services wait for customer

(i.e. when total number of customers > no. of service facilities or vice-versa)

Waiting Lines if (economically) can not be completely eliminated,

  • can at least be reduced by optimizing the number of service stations, or
  • by adjusting the service times in one or more centres.

Queuing Theory deals with analysis of Queues & Queuing Behavior

Key Words: Customer, Service Station, Waiting Time, Time spent by customer in a System, No. of Customers in the System, Queue Length, and Queuing System.

ORIGIN OF QUEUING THEORY:

Developed by A K Erlang in 1909 while analyzing telephone traffic congestion at Copenhagen Exchange.

Application Areas:

  • Scheduling of aircrafts for landings and take offs
  • Scheduling for issue and return of tools at tool cribs
  • Scheduling of transport
  • Scheduling the distribution of scarce war material
  • Scheduling the work and job in production control
  • Inventory analysis and Inventory Control
  • Congestion at Banks and Telephone booths
  • Scheduling of parts and components to assembly lines etc.

Queuing Theory attempts to formulate, interpret and predict the queues

Provides models that are capable of influencing arrival pattern of customers or determine the most appropriate amount of Service or Station.

Helps in striking the balance between waiting cost & service cost.

Mathematically studies the behavior of waiting lines utilizing the concept of stochastic process.

ELEMENTS OF A QUEUING PROCESS

  • Input Process
  • Queue Discipline
  • Service Process
  • Output Process
  1. Input Process- Concerned with pattern of Arrival

Input Source is characterized by - its size

-arrival time distribution

-attitude of customers

Size: Finite/ Infinite

Finite: If the rate of generation is appreciably affected by customers in the System.

Arrival Time Distributions: Most often approximated by:

  1. Constant time, 2. Poisson, 3. Exponential , 4 Erlang

Poisson distribution is commonly used. It is used to count the number of arrivals per unit of time

Probability of x arrivals is given by:

; x = 0,1,2 ..

Customers’ Attitude

  • Deciding not to enter looking at the long queue (Balking behavior)
  • Stay in the system until served
  • Wait for a certain time and leave the system if service not commenced by that time. (reneging behavior)
  • Estimate the waiting time and then decide whether to leave
  • Move from one waiting line to another (jockeying behavior)
  1. Queuing Process: A queue refers to the customer waiting for service
  1. Does not include the customers being served.
  2. Can be Finite or Infinite
  1. Service Process: Characterized by the arrangement of facilities & service time distributions.

Arrangements:Series, Parallel, or Mixed.

Distributions: Constant, Poisson, Exponential, Erlang

Most commonly used is negative exponential distribution which isa continuous probability distribution.

Probability density function is given by:

; 0x ∞

Service Disciplines:

  • In order of their arrival
  • First Come First Serve (FCFS)
  • Last Come First Serve (LCFS)
  • At Random
  • With higher priorities first
  1. Outlet: The exit from the system

On occasion it affects service and / or arrival times

(e.g. if there is one door to the service point)

Assumptions:

  1. There is only one type of queuing discipline – i.e. FCFS
  2. There are steady state conditions – i.e. probability that n items are there in a queue at any time remains the same.
  3. Both the number of items in the queue at any instant and waiting time experienced by a particular item are random variables.
  4. Mean Service Rate (µ) is greater then Mean Arrival Rate (λ) or µ> λ

or ρ (Rho) i.e. λ /µ < 1 where ρ is Traffic Intensity or Utilization Factor

Queuing Cost Behavior

DESCRIPTION OF QUEUING SYSTEM

{a/ b/ c: d/e}

a = Arrival Process, b = Service Time Distribution, c = number of channels, d = system capacity, e = queue discipline

SINGLE CHANNEL QUEUING MODEL

  1. Probability that the service facility is idle:
  1. Probability that there are n units in the system:
  1. Expected or Average number of units in the system
  1. Expected or Average number of units in thequeue

(exp. No in the system – exp. No. in the service)

i.e.

  1. Expected waiting time in the system:

or

(exp no. in the system / exp rate of arrivalλ/(µ-λ) /λ)

  1. Expected waiting time in the queue:

or

(exp. No. in queue / exp rate of arrival i.e.

  1. Probability that queue size >= k:

p (n>=k) =

  1. Expected length of non–empty queue:
  1. Probability that waiting time in queue is greater than or equal to t:

p (WT >=t) =

MULTIPLE CHANNEL QUEUING MODEL

Two or more server or channels are available to handle customers

Assumption: Customers awaiting service forms one single line and then proceed to the first available server

Examples: Check out customers, bank tellers, airport runways, tool booths

By introducing the number of service units, the length of queue and waiting time are reduced.

Most common multi channel system contains parallel stations serving a single queue on FCFS basis

  • All service stations provide the same service
  • The single queue may separate into shorter queues in front of respective service stations
  • Also when advantageous, calling units can shift from one queue to another
  • Other things same, all servers are assumed to perform at the same rate.

MULTIPLE CHANNEL QUEUING MODEL

If the number of calling units = n

Number of channels or service stations = k

The descriptive characteristics of MCQM are as follows:

  1. Probability that there are no customer or units in the system
  1. The probability that there are n units in the system:

if 0<= n < k

if 0<=

  1. Probability that the customer will have to wait:

p () =

  1. Average (expected ) number of Customers in the system:
  1. Average (expected) number of Customers waiting in queue:
  1. Average time an arrival spends in the system:
  1. Average time an arrival spends in the queue:
  1. Utilization Rate: ; <1

Some Special Single Server Queuing Models

Model {M/M/1: N/FCFS}

(Capacity Limited to N)

Descriptive Characteristics:

  1. ; or

(Steady state solution exist for >1)

  1. ;
  1. Mean number of customers in the system:
  1. Mean Queue length
  1. Mean waiting time in the system
  1. Mean waiting time in the queue

Model {M/Ek/ 1: ∞/ FCFS}

Model consists of k identical exponential service phases in series, each with mean service time 1 / kµ

New service does not start until all k phases have been completed.

The service time distribution is defined by Erlang :

;

Expected value of T (Total Service Time) and variance of Ek is:

Characteristics of this model:

  1. Mean number of customers in the System :
  1. Mean number of customers in the queue:
  1. Mean waiting time in the System:
  1. Mean waiting time in the queue:

Dr.Rakesh Belwal, Assistant Professor, Department of Management, AAU, Ethiopia