Queuing Theory

Have you ever experienced this???

 Introduction to Queuing Theory
• It is estimated that Americans spend a total of 37 billion
hours a year waiting in lines.
• Places we wait in line...
- stores - hotels - post offices
- banks - traffic lights - restaurants
- airports - theme parks - on the phone
• Waiting lines do not always contain people...
- returned videos
- subassemblies in a manufacturing plant
- electronic message on the Internet
• Queuing theory deals with the analysis and management
of waiting lines.
 The Purpose of Queuing Models

• Queuing models are used to:

– describe the behavior of queuing systems
– determine the level of service to provide
– evaluate alternate configurations for providing
service
 Queuing Costs
$

Total Cost

Cost of providing service

Cost of customer dissatisfaction

Service Level
Common Queuing System Configurations
 Characteristics of Queuing Systems:
The Arrival Process
• Arrival rate - the manner in which customers arrive at
the system for service.

▪ Arrivals are often described by a Poisson random

variable:
x e − 
P( x ) = , for x = 0, 1, 2, ...
x!

where  is the arrival rate (e.g., calls arrive at a

rate of =5 per hour)
 Characteristics of Queuing Systems:
The Service Process
• Service time - the amount of time a customer spends
receiving service (not including time in the queue).

▪ Service times are often described by an

Exponential random variable:
t2

P ( t 1  T  t 2 ) =  e − x
dx = e − ut1
−e − t 2
, for t1  t 2
t1
where  is the service rate (e.g., calls can be
serviced at a rate of =7 per hour)
▪ The average service time is 1/.
 Comments
• If arrivals follow a Poisson distribution with mean ,
inter-arrival times follow an Exponential distribution
with mean 1/.
– Example
• Assume calls arrive according to a Poisson
distribution with mean =5 per hour.
• Inter-arrivals follow an exponential distribution
with mean 1/5 = 0.2 per hour.
• On average, calls arrive every 0.2 hours or every 12
minutes.
• The exponential distribution exhibits the Markovian
(memory less) property.
 Kendall Notation
• Queuing systems are described by 3 parameters:
1/2/3
– Parameter 1
M = Markovian interarrival times (exponential probability
density (Poisson Distribution))
D = Deterministic interarrival times ( jobs arrive at fixed
instants)
– Parameter 2
M = Markovian service times
G = General service times (Service rate is processed
consistently)
D = Deterministic service times
– Parameter 3
A number Indicating the number of servers.
• Examples,
M/M/3 D/G/4 M/G/2
 Operating Characteristics
Typical operating characteristics of interest include:
U - Utilization factor, % of time that all servers are busy.
P0 - Prob. that there are no zero units in the system.
Lq - Avg number of units in line waiting for service.
L - Avg number of units in the system (in line & being
served).
Wq - Avg time a unit spends in line waiting for service.
W - Avg time a unit spends in the system (in line & being
served).
Pw - Prob. that an arriving unit has to wait for service.
Pn - Prob. of n units in the system.
Key Operating Characteristics
of the M/M/1 Model

1
W=
−

L = W
1
Wq = W −


L q =  Wq
 The Q.xls Queuing Template

• Formulas for the operating characteristics of a

number of queuing models have been derived
analytically.
• An Excel template called Q.xls implements the
formulas for several common types of models.
• Q.xls was created by Professor David Ashley of the
Univ. of Missouri at Kansas City.
 The M/M/s Model

• Assumptions:
– There are s servers.
– Arrivals follow a Poisson distribution and occur at
an average rate of  per time period.
– Each server provides service at an average rate of
 per time period, and actual service times follow
an exponential distribution.
– Arrivals wait in a single FIFO queue and are
serviced by the first available server.
– < s.
 An M/M/s Example: Bitway Computers
• The customer support hotline for Bitway Computers is currently
staffed by a single technician.
• Calls arrive randomly at a rate of 5 per hour and follow a Poisson
distribution.
• The technician services calls at an average rate of 7 per hour, but the
actual time required to handle a call follows an exponential
distribution.
• Bitway’s president, Rod Taylor, has received numerous complaints
from customers about the length of time they must wait “on hold”
for service when calling the hotline.
• Rod wants to determine the average length of time customers
currently wait before the technician answers their calls.
• If the average waiting time is more than 5 minutes, he wants to
determine how many technicians would be required to reduce the
average waiting time to 2 minutes or less.
See file: Q.xls
 Sample Problem 1:
A petrol pump has one pump which can serve 6 customers per hours. Cars
arrive at the station at a rate of 10 per hour which is exponentially distributed.
Find the pump utilization, expected waiting time in the system and queue.

µ λ δρ

λ = mean arrival rate

= 10 cars / 60 min
= 1 car / 6 min

µ = mean service rate per busy server

= 6 cars / 60 min
= 1 car / 10 min
System utilization (ρ ) = λ / µ
6
= = 0.60
10
1 1
Expected waiting time per customer in system (Ws ) =
µ−λ
=
10 − 6 = 0.25ℎ𝑟𝑠

λ 6
Expected waiting time per customer in queue (Ws ) = =
µ(µ − λ) 10(10−6)
= 0.15 ℎ𝑟𝑠
 Sample problem 2
A small railway ticket booking office has two counters – Counter 1 for enquiry and
Counter 2 for ticket booking. Customer arrival is Poisson at 5 per hour to the
enquiry and 10 per hour to the ticket booking counter. Exponentially distributed
service time in each counter is 4 minutes per customer. Find by how much the
average waiting time of a customer in the system reduces at Counter 1 (original
enquiry counter) when the office decides to go for pooling of resources – i.e. an
arriving customer will get enquiry or ticket booking facility at any of the counters.
 Solution problem 2
We have two counters (i) Enquiry counter (ii) ticket booking counter
See file: Q.xls
 Summary of Results: Bitway Computers
Arrival rate 5 5
Service rate 7 7
Number of servers 1 2

Utilization 71.43% 35.71%

P(0), probability that the system is empty 0.2857 0.4737
Lq, expected queue length 1.7857 0.1044
Ls, expected number in system 2.5000 0.8187
Wq, expected time in queue 0.3571 (21.42 min) 0.0209 (1.254 min)

Ws, expected total time in system 0.5000 0.1637

 The M/M/s Model With
Finite Queue Length
• In some problems, the amount of waiting area is limited.
• Example,
– Suppose Bitway’s telephone system can keep a maximum of 5 calls on
hold at any point in time.
– If a new call is made to the hotline when five calls are already in the
queue, the new call receives a busy signal.
– One way to reduce the number of calls encountering busy signals is to
increase the number of calls that can be put on hold.
– If a call is answered only to be put on hold for a long time, the caller
might find this more annoying than receiving a busy signal.
– Rod wants to investigate what effect adding a second technician to
answer hotline calls has on:
• the number of calls receiving busy signals
• the average time callers must wait before receiving service.
Implementing the Model

See file Q.xls

 Summary of Results:
Bitway Computers With Finite Queue
Arrival rate 5 5
Service rate 7 7
Number of servers 1 2
Maximum queue length 5 5

Utilization 68.43% 35.69%

P(0), probability that the system is empty 0.3157 0.4739
Lq, expected queue length 1.0820 0.1019
L, expected number in system 1.7664 0.8157
Wq, expected time in queue 0.2259 0.0204
W, expected total time in system 0.3687 0.1633
Probability that a customer waits 0.6843 0.1877
Probability that a customer balks 0.0419 0.0007
 The M/M/s Model With Finite Population
• Assumptions:
– There are s servers.
– There are N potential customers in the arrival population.
– The arrival pattern of each customer follows a Poisson
distribution with a mean arrival rate of  per time period.
– Each server provides service at an average rate of  per
time period, and actual service times follow an
exponential distribution.
– Arrivals wait in a single FIFO queue and are serviced by
the first available server.
 M/M/s With Finite Population Example:
The Miller Manufacturing Company
• Miller Manufacturing owns 10 identical machines that produce
colored nylon thread for the textile industry.
• Machine breakdowns follow a Poisson distribution with an
average of 0.01 breakdowns per operating hour per machine.
• The company loses $100 each hour a machine is down.
• The company employs one technician to fix these machines.
• Service times to repair the machines are exponentially
distributed with an avg of 8 hours per repair. (So service is
performed at a rate of 1/8 machines per hour.)
• Management wants to analyze the impact of adding another
service technician on the average time to fix a machine.
• Service technicians are paid $20 per hour.
 Implementing the Model

See file OR_Slides\Data Files\C13\Q.xls

 Summary of Results:
Miller Manufacturing
Arrival rate 0.01 0.01 0.01
Service rate 0.125 0.125 0.125
Number of servers 1 2 3
Population size 10 10 10

Utilization 67.80% 36.76% 24.67%

P(0), probability that the system is empty 0.3220 0.4517 0.4623
Lq, expected queue length 0.8463 0.0761 0.0074
L, expected number in system 1.5244 0.8112 0.7476
Wq, expected time in queue 9.9856 0.8282 0.0799
W, expected total time in system 17.986 8.8282 8.0799
Probability that a customer waits 0.6780 0.1869 0.0347

Hourly cost of service technicians $20.00 $40.00 $60.00

Hourly cost of inoperable machines $152.44 $81.12 $74.76
Total hourly costs $172.44 $121.12 $134.76
 The M/G/1 Model
• Not all service times can be modeled accurately using the
Exponential distribution.
– Examples:
• Changing oil in a car
• Getting an eye exam
• Getting a hair cut
• M/G/1 Model Assumptions:
– Arrivals follow a Poisson distribution with mean .
– Service times follow any distribution with mean  and
standard deviation 
– There is a single server.
 An M/G/1 Example: Zippy Lube
• Zippy-Lube is a drive-through automotive oil change business that
operates 10 hours a day, 6 days a week.
• The profit margin on an oil change at Zippy-Lube is $15.
• Cars arrive at the Zippy-Lube oil change center following a Poisson
distribution at an average rate of 3.5 cars per hour.
• The average service time per car is 15 minutes (or 0.25 hours) with a
standard deviation of 2 minutes (or 0.0333 hours).
• A new automated oil dispensing device costs $5,000.
• The manufacturer's representative claims this device will reduce the
average service time by 3 minutes per car. (Currently, employees
manually open and pour individual cans of oil.)
• The owner wants to analyze the impact the new automated device
would have on his business and determine the pay back period for this
device.
 Implementing the Model

See file OR_Slides\Data Files\C13\Q.xls

 Summary of Results: Zippy Lube

Arrival rate 3.5 3.5 4.371

Average service TIME 0.25 0.2 0.2
Standard dev. of service time 0.0333 0.0333 0.333

Utilization 87.5% 70.0% 87.41%

P(0), probability that the system is empty 0.1250 0.3000 0.1259
Lq, expected queue length 3.1168 0.8393 3.1198
L, expected number in system 3.9918 1.5393 3.9939
Wq, expected time in queue 0.8905 0.2398 0.7138
W, expected total time in system 1.1405 0.4398 0.9138
 Payback Period Calculation
Increase in:
Arrivals per hour 0.871
Profit per hour $13.06
Profit per day $130.61
Profit per week $783.63

Cost of Machine $5,000

Payback Period 6.381 weeks

 The M/D/1 Model
• Service times may not be random in some queuing systems.
– Examples
• In manufacturing, the time to machine an item might be
exactly 10 seconds per piece.
• An automatic car wash might spend exactly the same
amount of time on each car it services.
• The M/D/1 model can be used in these types of situations
where the service times are deterministic (not random).
• The results for an M/D/1 model can be obtained using the
M/G/1 model by setting the standard deviation of the service
time to 0 ( = 0).
 Simulating Queues

• The queuing formulas used in Q.xls describe the

steady-state operations of the various queuing
systems.
• Simulation is often used to analyze more complex
queuing systems.
• See file OR_Slides\Data Files\C13\Fig13-21.xls
End of Chapter 13