Operations Management - Queuing Theory

OPERATIONS MANAGEMENT

Queuing Theory

 

Part A: Discussion of basic theories explaining different queuing models along with respective assumptions and formulas.

 

Part B: 15 Illustrations with solutions.

Part A

The elements of a queuing system are:

1.       Arrival process,

2.       Service system,

3.       Queue structure.

 

Arrival Process:

The arrivals may be classified on different bases as follows:

a)       Source where the customers come from may be:

i)          Finite, or

ii)        Infinite.

b)       Customers may arrive as:

i)          Individual customers, or

ii)        Group customers.

c)        Customers may arrive at:

i)          Known intervals (Deterministic Queuing Model), or

ii)        Random intervals (Probabilistic Queuing Model – the assumption is that the arrival times are Poisson distributed).

 

Service System:

There are two aspects of service system —

a)       Structure of the service system, and

b)       Speed of service.

a)     Structure of the service system

i)          A single service facility,

ii)        Multiple, parallel service facilities with single queue,

iii)     Multiple, parallel service facilities with multiple queue,

iv)     Service facilities in a series.

 

b)     Speed of service

Speed of service is measured in either of the following two ways:

i)          Service rate   = n/t

ii)        Service time  = t/n

     Where,

n   =   Number of persons serviced in t time, and

t    =   Time needed to service n persons.

(Generally, in queuing theory it is assumed that service times are exponentially distributed).

 

Queue Structure:

Possible queue structures are:

a)       First – come – first – served,

b)       Last – come – first – served,

c)        Service in random order (SIRO), and

d)       Priority service.

 

Important note:

For the queuing models that will be discussed here, it will be assumed that the customers are serviced on the first-come-first-serviced basis.

 

Operating characteristics of queuing system:

An analysis of a given queuing system involves a study of its different operating characteristics. Some of the more commonly considered characteristics are as follows:

1.               Queue length:

It is the average number of customers in the queue waiting to get service.

 

2.               System length:

It is the average number of customers in the system, those waiting to be serviced and those being serviced.

 

3.               Waiting time in the queue

It is the average time that a customer has to wait in the queue to get the service.

 

4.               Waiting time in the system

It is the average time that a customer spends in the system, from entry in the queue to the completion of service.

 

5.               Service idle time

It is the relative frequency with which the service system is idle.

 

   Deterministic Queuing Model

1	λ = Number of customers arrived per unit time
2	μ = Number of customers serviced per unit time
3	λ and μ are known and constant
4	Average system utilisation (Traffic intensity) for M servers = (1/M)*ρ = (1/M)*(λ/μ)
5	If λ > μ, waiting time shall be formed which will increase indefinitely
6	If λ ≤ μ, there shall be no waiting time
7	If ρ > 1, the system would ultimately fail
8	If ρ ≤ 1, the system works

 

   Probabilistic Queuing Model

1	Customer arrival times follow Poisson Distribution
2	Service times follow Exponential Distribution
3	λ = Mean/Average arrival rate per unit time
4	μ = Mean/Average service rate per unit time
5	Probability that ‘n’ customers will arrive in the system during a given interval ‘T’ = P (‘n’ customers during period ‘T’) = [e^ (−m)]*[(m^ n)/n!] Where, m = λ*T, and e = 2.7183
6	Probability that no more than ‘T’ periods would be required to serve a customer = P (no more than ‘T’ time period needed to service a customer) = 1 − e^ (−μ*T)

 

Three Probabilistic Queuing Models:

1.       Single server, infinite population.

2.       Single server, finite population.

3.       Multiple servers, infinite population.

 

Model – 1: Single server, infinite population

  Assumptions:

1	Customer arrival times follow Poisson distribution.
2	Service times follow Exponential Distribution.
3	λ = Mean (i.e. Average) arrival rate.
4	μ = Mean (i.e. Average) service rate.
5	Arrivals are from infinite population.
6	Customers are served on a first-come-first-served basis.
7	There is only a single service station.

 

  Formulas:

1	Average system utilisation (Traffic intensity) = ρ = λ/μ
2	Probability that the system is idle, i.e. there is no customer in the system, P0 = 1 – ρ = 1 – λ/μ
3	Probability of having exactly ‘n’ customers in the system, Pn = (ρ^ n)*(1 – ρ) = P0*[(λ/μ) ^ n]
4	Probability of having less than ‘n’ customers in the system, P<n = 1 – (λ/μ) ^ n = 1 − ρ^ n
5	Expected number of customers in the system (i.e. length of the system), Ls = Lq + ρ = λ/ (μ – λ) = ρ/ (1 – ρ)
6	Expected number of customers in the queue (i.e. length of the queue), Lq = Ls – ρ = [ρ^ 2]/ (1 – ρ) = [λ^ 2] / [μ*(μ – λ)]
7	Average length of non-empty queue Ln = 1/ (1 – ρ) = μ/ (μ – λ)
8	Mean/Average waiting time in queue, Wq = Lq * (1/λ) = ρ/ (μ – λ) = Ls/λ – 1/μ = λ/μ * [1/ (μ – λ)]
9	Mean/Average time in the system, Ws = Ls * (1/λ) = Wq + (1/μ) = 1/ (μ – λ) = Lq/λ + 1/μ
10	Probability that a customer spends more than ‘t’ units of time in the system, Ws (t) = e^ (−t/Ws)
11	Probability that a customer spends more than ‘t’ units of time in the queue, Wq (t) = ρ * e^ (−t/Ws)

 

Model – 2: Single server, finite population

  Assumptions:

1	Customer arrival times follow Poisson distribution.
2	Service times follow Exponential Distribution.
3	λ = Mean/Average arrival rate.
4	μ = Mean/Average service rate.
5	Arrivals are from finite population. [For this model the system structure is such that we have a total of M customers; a customer is either in the system (consisting of a queue and a single service station), or outside the system and, in a sense, arriving.]
6	Customers are served on a first-come-first-served basis.
7	There is only a single service station.

 

  Formulas:

1	Mean of inter-arrival times, i.e. average time between the arrivals = 1/λ
2	Probability that the system shall be idle, P0 = [∑ (i=0®M) {M! / (M – i)!*(λ/μ) ^ i}] ^ (−1)
3	Probability that there shall be ‘n’ customers in the system, Pn = P0 * [(λ/μ) ^ n] * [M! / (M – n)! ]
4	Expected number of customer in the queue, Lq = M – [(λ + μ)/λ]*(1 – P0)
5	Expected number of customers in the system, Ls = Lq + (1 – P0) = M – (μ/λ)*(1 – P0)
6	Expected waiting time of a customer in the queue, Wq = Lq/ [μ*(1 – P0)] = 1/μ*[M/ (1 – P0) – (λ + μ)/λ]
7	Expected time a customer spends in the system, Ws = Wq + 1/μ = 1/μ*[(M/ (1 – P0) – (λ + μ)/λ + 1]

 

Model – 3: Multiple servers, infinite population

  Assumptions:

1	The arrival of customers follows Poisson distribution, the average arrival rate being λ.
2	The service time has an Exponential distribution.
3	There are K service stations, each of which provides identical service, mean service rate of each of the servers being μ.
4	A single waiting line is formed.
5	The input population is infinite.
6	The service is on a first-come-first-served basis.
7	The arrival rate is smaller than the combined service rate of all the K service facilities.
8	Mean combined service rate of all the servers is Kμ.
9	Utilisation factor of the entire system, ρ = λ/ (Kμ).

 

  Formulas:

1	Probability that the system shall be idle, P0 = [∑ [i=0®(K–1)] [{(λ/μ) ^i}/i!] + [{(λ/μ) ^K}/ {K! (1−ρ)}]]^ (−1)
2	Probability that there shall be exactly n customers in the system, When n ≤ K — Pn = (P0) [{(λ/μ) ^n}/n!] When n > K — Pn = (P0) [{(λ/μ) ^n}/ {K! K^ (n–K)}]
3	The expected number of customers in the waiting line, Lq = [{ρ (λ/μ) ^K}/ {K! (1−ρ)^2}] (P0)
4	The expected number of customers in the system, Ls = Lq + (λ/μ)
5	The expected waiting time in the queue, Wq = Lq/λ
6	The expected time a customer spends in the system, Ws = Wq + (1/μ)

 

Part B

Operation Management

Queuing Theory

Selected Problems

 

Illustration: 1

A TV repairman finds that the time spent on his jobs has an exponential distribution with mean 30 minutes. If he repairs sets in the order in which they came in and if the arrival of sets is approximately Poisson with an average rate of 10 per 8 hours day, what is repairman’s expected idle time each day? How many jobs are ahead of the average set just brought in?

 

Illustration: 2

Let on an average 96 patients per 24 hour day require the service of an emergency clinic. Also on average, a patient requires 10 minutes of active attention. Assume that the facility can handle only one emergency at a time. Suppose that it costs the clinic Rs 100 per patient treated to obtain an average servicing time of 10 patients and that each minute of decrease in this average time would cost Rs 10 per patient treated. How much would have to be budgeted by the clinic to decrease the average size of the queue from one and one third patients to half a patient.

 

Illustration: 3

Customers arrive at a one window drive in bank according to Poisson distribution with mean 10 per hour. Service time per customer is exponential with mean 5 minutes. The space is front of the window including that for the serviced car can accommodate a maximum of 3 cars. Others can wait outside this space.

i)          What is the probability that an arriving customer can drive directly to the space in front of the window?

ii)        What is the probability that an arriving customer will have to wait outside the indicated space?

iii)     How long is an arriving customer expected to wait before starting service?

 

Illustration: 4

In a railway marshalling yard, good train arrive at a rate of 30 trains per day. Assuming that inter arrival time and the service time distribution follows an exponential distribution with an average of 36 minutes. Calculate

(i)              The mean queue size

(ii)            The probability that queue size exceeds 10

(iii)         If the input of the train increases to an average of 33 per day, what will be the changes in (i) and (ii) above?

 

Illustration: 5

Four counters are being run on the frontier of a country to check the passports and necessary papers of the tourists. The tourists choose a counter at random. If the arrivals at the frontier are Poisson at the rate l and the service time is exponential with parameter l/2, what is the steady state average queue at each counter?

 

Illustration: 6

A super market has two girls ringing up sales at the counters. If the service time for each counter is exponential with mean 4 minutes and if people arrive in a Poisson fashion at the counter at the rate of 10 per hour, then calculate

 

(a)           The probability of having to wait for service.

(b)           The expected percentage of idle time for each girl.

(c)            If a customer has to wait, find the expected length of his waiting time.

 

Illustration: 7

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 exponential with mean 3 minutes. (i) What is the probability that a person arriving at the booth will have to wait? (ii) What is the average length of the queue that forms from time to time? (iii) The telephone department will install a second booth when convinced that an arrival would expect waiting for at least 3 minutes for phone. By how much should the flow of arrivals increase in order to justify the second booth?

 

Illustration: 8

A bank has two tellers working on savings accounts. The first teller handles withdrawals only. Second teller handles deposits only. It has been found that the service time distributions for both deposits and withdrawals are exponential with mean service time 3 minutes per customer. Depositors are found to arrive in a Poisson fashion throughout the day with mean arrival rate 16 per hour. Withdrawers also arrive in a Poisson fashion with mean arrival rate 14 per hour. What would be the effect on the average waiting time for depositors and withdrawers, if each teller could handle both withdrawals and deposits? What would be the effect if this could only be accomplished by increasing the service time to 3.5 minutes?

 

Illustration: 9

A barber shop has two barbers and three chairs for customers. Assume that the customers arrive in Poisson fashion at a rate of 5 / hour and each barber services customers according to an exponential distribution with mean 15 minutes. Further if a customer arrives and there are no empty chairs in the shop, he will leave. What is the expected number of customer in the shop?

 

Illustration: 10

In a super market, the average arrival rate of customers is 10 in every 30 minutes following Poisson process. The average time taken by a cashier to list and calculate the customer's purchase is two and a half minutes following exponential distribution. What is the probability that the queue length exceeds six? What is the expected time spent by a customer in the system?

 

Illustration: 11

An airline is planning to open a satellite ticket desk in a new shopping plaza, staffed by one ticket agent. It is estimated that requests for tickets and information will average 15 per hour, and requests will have a Poisson distribution. Service time is assumed to be exponentially distributed. Previous experience with similar satellite operations suggests that mean service time should average about three minutes per request.

 

Determine each of the following:

a.        System utilization.

b.       The expected number of customers waiting to be served.

c.        The average time customers will spend in the system.

d.       The probability of zero customers in the system, and

e.        The probability of four customers in the system.

 

Illustration: 12

Wanda’s Car Wash & dry is an automatic, five-minute operation with a single bay. On a typical Saturday morning, cars arrive at a mean rate of eight per hour, with arrivals tending to follow a Poisson distribution. Find

a.        The average number of cars in line.

b.       The average time cars spend in line and service.

 

Illustration: 13

A departmental store has one cashier. During the rush hours, customers arrive at a rate of 20 per hour. The average number of customers that can be handled by the cashier is 24 per hour. Assume the conditions for use of the single – channel queuing model. Find out average time a customer spends in the system.

 

Illustration: 14

At a tool service centre the arrival rate is two per hour and the service potential is three per hour. Simple queue conditions exist.

 

The hourly wage paid to the attendant at the service centre is Rs 1.50 per hour and the hourly cost of a machinist away from his work is Rs 4.

 

Calculate:

(i)              The average number of machinists being served or waiting to be served at any given time.

(ii)            The average time a machinist spends waiting for service.

(iii)         The total cost of operating the system for an eight – hour day.

(iv)         The cost of the system, if there were two attendants working together as a team, each paid Rs 1.50 per hour and each able to service on an average 2 machines per hour.

 

Illustration: 15

Workers come to a tool store room to enquire about special tools (required by them) for accomplishing a particular project assigned to them. The average time between two arrivals is 60 seconds and the arrivals are assumed to be in Poisson distribution. The average service time (of the tool room attendant) is 40 seconds.

 

Determine:

(i)              Average queue length,

(ii)            Average length of non-empty queues,

(iii)         Average number of workers in the system including the worker being attended,

(iv)         Mean waiting time of an arrival in the queue,

(v)           Average waiting time of an arrival in the system.