Chapter 11

Table of Contents
Chapter 11 (Queueing Models)
Elements of a Queueing Model (Section 11.1) 11.2–11.12

Some Examples of Queueing Systems (Section 11.2) 11.13–11.15
Measures of Performance for Queueing Systems (Section 11.3) 11.16–11.19
A Case Study: The Dupit Corp. Problem (Section 11.4) 11.20–11.22
Some Single-Server Queueing Models (Section 11.5) 11.23–11.32
Some Multiple-Server Queueing Models (Section 11.6) 11.33–11.40
Priority Queueing Models (Section 11.7) 11.41–11.48
Some Insights about Designing Queueing Systems (Section 11.8) 11.49–11.51
Economic Analysis of the Number of Servers to Provide (Section 11.9) 11.52–11.55
Queueing Models (UW Lecture) 11.56–11.74

These slides are based upon a lecture from the MBA elective course “Modeling with Spreadsheets” at the
University of Washington (as taught by one of the authors).
Queueing Applications (UW Lecture) 11.75–11.88

These slides are based upon a lecture from the MBA elective course “Modeling with Spreadsheets” at the
University of Washington (as taught by one of the authors).
McGraw-Hill/Irwin 11.1 © The McGraw-Hill Companies, Inc., 2008

A Basic Queueing System
Served Customers
Queueing System
Queue
C S
Customers CCCCCCC C S Service
C S facility
C S
Served Customers

Herr Cutter’s Barber Shop
• Herr Cutter is a German barber who runs a one-man barber shop.
• Herr Cutter opens his shop at 8:00 A.M.
• The table shows his queueing system in action over a typical morning.
Time of Haicut Duration Haircut

Customer Arrival Begins of Haircut Ends
1 8:03 8:03 17 minutes 8:20
2 8:15 8:20 21 minutes 8:41
3 8:25 8:41 19 minutes 9:00
4 8:30 9:00 15 minutes 9:15
5 9:05 9:15 20 minutes 9:35
6 9:43 — — —

Arrivals
• The time between consecutive arrivals to a queueing system are called the
interarrival times.
• The expected number of arrivals per unit time is referred to as the mean
arrival rate.
• The symbol used for the mean arrival rate is

 = Mean arrival rate for customers coming to the queueing system
where  is the Greek letter lambda.
• The mean of the probability distribution of interarrival times is

1 /  = Expected interarrival time
• Most queueing models assume that the form of the probability distribution of
interarrival times is an exponential distribution.

Evolution of the Number of Customers
Number of
Customers 3
in the
System
0 20 40 60 80 100
Time (in minutes)

The Exponential Distribution for Interarrival Times
0 Mean Time

Properties of the Exponential Distribution
• There is a high likelihood of small interarrival times, but a small chance of a

very large interarrival time. This is characteristic of interarrival times in
practice.
• For most queueing systems, the servers have no control over when customers
will arrive. Customers generally arrive randomly.
• Having random arrivals means that interarrival times are completely

unpredictable, in the sense that the chance of an arrival in the next minute is
always just the same.
• The only probability distribution with this property of random arrivals is the
exponential distribution.
• The fact that the probability of an arrival in the next minute is completely
uninfluenced by when the last arrival occurred is called the lack-of-memory
property.

The Queue
• The number of customers in the queue (or queue size) is the number of
customers waiting for service to begin.
• The number of customers in the system is the number in the queue plus the
number currently being served.
• The queue capacity is the maximum number of customers that can be held in
the queue.
• An infinite queue is one in which, for all practical purposes, an unlimited
number of customers can be held there.
• When the capacity is small enough that it needs to be taken into account, then
the queue is called a finite queue.
• The queue discipline refers to the order in which members of the queue are
selected to begin service.
– The most common is first-come, first-served (FCFS).
– Other possibilities include random selection, some priority procedure, or even last-
come, first-served.

Service
• When a customer enters service, the elapsed time from the beginning to the
end of the service is referred to as the service time.
• Basic queueing models assume that the service time has a particular
probability distribution.
• The symbol used for the mean of the service time distribution is
1 /  = Expected service time
where  is the Greek letter mu.
• The interpretation of  itself is the mean service rate.
 = Expected service completions per unit time for a single busy

server

Some Service-Time Distributions
• Exponential Distribution
– The most popular choice.
– Much easier to analyze than any other.
– Although it provides a good fit for interarrival times, this is much less true for
service times.
– Provides a better fit when the service provided is random than if it involves a fixed
set of tasks.
– Standard deviation:  = Mean
• Constant Service Times

– A better fit for systems that involve a fixed set of tasks.
– Standard deviation:  = 0.

Labels for Queueing Models
To identify which probability distribution is being assumed for service times (and
for interarrival times), a queueing model conventionally is labeled as follows:
Distribution of service times
—/—/— Number of Servers
Distribution of interarrival times
The symbols used for the possible distributions are

M = Exponential distribution (Markovian)
D = Degenerate distribution (constant times)
GI = General independent interarrival-time distribution (any distribution)
G = General service-time distribution (any arbitrary distribution)

Summary of Usual Model Assumptions
1. Interarrival times are independent and identically distributed according to a

specified probability distribution.
2. All arriving customers enter the queueing system and remain there until
service has been completed.
3. The queueing system has a single infinite queue, so that the queue will hold an
unlimited number of customers (for all practical purposes).
4. The queue discipline is first-come, first-served.
5. The queueing system has a specified number of servers, where each server is
capable of serving any of the customers.
6. Each customer is served individually by any one of the servers.
7. Service times are independent and identically distributed according to a
specified probability distribution.

Examples of Commercial Service Systems
That Are Queueing Systems
Type of System Customers Server(s)

Barber shop People Barber
Bank teller services People Teller
ATM machine service People ATM machine
Checkout at a store People Checkout clerk
Plumbing services Clogged pipes Plumber
Ticket window at a movie theater People Cashier
Check-in counter at an airport People Airline agent
Brokerage service People Stock broker
Gas station Cars Pump
Call center for ordering goods People Telephone agent
Call center for technical assistance People Technical representative
Travel agency People Travel agent
Automobile repair shop Car owners Mechanic
Vending services People Vending machine
Dental services People Dentist
Roofing Services Roofs Roofer
Examples of Internal Service Systems

Secretarial services Employees Secretary
Copying services Employees Copy machine
Computer programming services Employees Programmer
Mainframe computer Employees Computer
First-aid center Employees Nurse
Faxing services Employees Fax machine
Materials-handling system Loads Materials-handling unit
Maintenance system Machines Repair crew
Inspection station Items Inspector
Production system Jobs Machine
Semiautomatic machines Machines Operator
Tool crib Machine operators Clerk

Examples of Transportation Service Systems

Highway tollbooth Cars Cashier
Truck loading dock Trucks Loading crew
Port unloading area Ships Unloading crew
Airplanes waiting to take off Airplanes Runway
Airplanes waiting to land Airplanes Runway
Airline service People Airplane
Taxicab service People Taxicab
Elevator service People Elevator
Fire department Fires Fire truck
Parking lot Cars Parking space
Ambulance service People Ambulance

Choosing a Measure of Performance
• Managers who oversee queueing systems are mainly concerned with two
measures of performance:
– How many customers typically are waiting in the queueing system?
– How long do these customers typically have to wait?
• When customers are internal to the organization, the first measure tends to be
more important.
– Having such customers wait causes lost productivity.
• Commercial service systems tend to place greater importance on the second

measure.
– Outside customers are typically more concerned with how long they have to wait
than with how many customers are there.

Defining the Measures of Performance
L = Expected number of customers in the system, including those being

served (the symbol L comes from Line Length).
Lq = Expected number of customers in the queue, which excludes

customers being served.
W = Expected waiting time in the system (including service time) for an

individual customer (the symbol W comes from Waiting time).
Wq = Expected waiting time in the queue (excludes service time) for an

individual customer.
These definitions assume that the queueing system is in a steady-state condition.

Relationship between L, W, Lq, and Wq
• Since 1/ is the expected service time

W = Wq + 1/
• Little’s formula states that

L = W
and
Lq = Wq
• Combining the above relationships leads to

L = Lq + 

Using Probabilities as Measures of Performance
• In addition to knowing what happens on the average, we may also be

interested in worst-case scenarios.
– What will be the maximum number of customers in the system? (Exceeded no more
than, say, 5% of the time.)
– What will be the maximum waiting time of customers in the system? (Exceeded no
more than, say, 5% of the time.)
• Statistics that are helpful to answer these types of questions are available for
some queueing systems:
– Pn = Steady-state probability of having exactly n customers in the system.
– P(W ≤ t) = Probability the time spent in the system will be no more than t.
– P(Wq ≤ t) = Probability the wait time will be no more than t.
• Examples of common goals:

– No more than three customers 95% of the time: P0 + P1 + P2 + P3 ≥ 0.95
– No more than 5% of customers wait more than 2 hours: P(W ≤ 2 hours) ≥ 0.95

The Dupit Corp. Problem
• The Dupit Corporation is a longtime leader in the office photocopier

marketplace.
• Dupit’s service division is responsible for providing support to the customers

by promptly repairing the machines when needed. This is done by the
company’s service technical representatives, or tech reps.
• Current policy: Each tech rep’s territory is assigned enough machines so that
the tech rep will be active repairing machines (or traveling to the site) 75% of
the time.
– A repair call averages 2 hours, so this corresponds to 3 repair calls per day.
– Machines average 50 workdays between repairs, so assign 150 machines per rep.
• Proposed New Service Standard: The average waiting time before a tech rep
begins the trip to the customer site should not exceed two hours.

Alternative Approaches to the Problem
• Approach Suggested by John Phixitt: Modify the current policy by

decreasing the percentage of time that tech reps are expected to be repairing
machines.
• Approach Suggested by the Vice President for Engineering: Provide new

equipment to tech reps that would reduce the time required for repairs.
• Approach Suggested by the Chief Financial Officer: Replace the current

one-person tech rep territories by larger territories served by multiple tech
reps.
• Approach Suggested by the Vice President for Marketing: Give owners of

the new printer-copier priority for receiving repairs over the company’s other
customers.

The Queueing System for Each Tech Rep
• The customers: The machines needing repair.
• Customer arrivals: The calls to the tech rep requesting repairs.
• The queue: The machines waiting for repair to begin at their sites.
• The server: The tech rep.
• Service time: The total time the tech rep is tied up with a machine, either
traveling to the machine site or repairing the machine. (Thus, a machine is
viewed as leaving the queue and entering service when the tech rep begins the
trip to the machine site.)

Notation for Single-Server Queueing Models
•  = Mean arrival rate for customers

= Expected number of arrivals per unit time
1/ = expected interarrival time
•  = Mean service rate (for a continuously busy server)

= Expected number of service completions per unit time
 = expected service time
•  = the utilization factor

= the average fraction of time that a server is busy serving customers
= 

The M/M/1 Model
• Assumptions
1. Interarrival times have an exponential distribution with a mean of 1/ .
2. Service times have an exponential distribution with a mean of 1/ .
3. The queueing system has one server.
• The expected number of customers in the system is
L = 1 – = – 
• The expected waiting time in the system is
W = (1 / )L = 1 / ( – )
• The expected waiting time in the queue is
Wq = W – 1/ =  / [( – )]
• The expected number of customers in the queue is
Lq = Wq = 2 / [( – )] = 2 / (1 – )

The M/M/1 Model
• The probability of having exactly n customers in the system is

Pn = (1 – )n
Thus,
P0 = 1 – 
P1 = (1 – )
P2 = (1 – )2
:
:
• The probability that the waiting time in the system exceeds t is
P(W > t) = e–(1–)t for t ≥ 0
• The probability that the waiting time in the queue exceeds t is
P(Wq > t) = e–(1–)t for t ≥ 0

M/M/1 Queueing Model for the Dupit’s Current Policy
B C D E G H
3 Data Results
4  3 (mean arrival rate) L= 3
5  4 (mean service rate) Lq = 2.25
6 s= 1 (# servers)
7 W= 1
8 Pr(W > t) = 0.368 Wq = 0.75
9 when t = 1
10  0.75
11 Prob(W q > t) = 0.276
12 when t = 1 n Pn
13 0 0.25
14 1 0.1875
15 2 0.1406
16 3 0.1055
17 4 0.0791
18 5 0.0593
19 6 0.0445
20 7 0.0334
21 8 0.0250
22 9 0.0188
23 10 0.0141

John Phixitt’s Approach (Reduce Machines/Rep)
• The proposed new service standard is that the average waiting time before
service begins be two hours (i.e., Wq ≤ 1/4 day).
• John Phixitt’s suggested approach is to lower the tech rep’s utilization factor
sufficiently to meet the new service requirement.
Lower  =  / , until Wq ≤ 1/4 day,

where
 = (Number of machines assigned to tech rep) / 50.

M/M/1 Model for John Phixitt’s Suggested Approach
(Reduce Machines/Rep)
B C D E G H
3 Data Results
6 s= 1 (# servers)
7 W= 0.5
8 Pr(W > t) = 0.135 Wq = 0.25
9 when t = 1
10  0.5
11 Prob(Wq > t) = 0.068
12 when t = 1 n Pn
13 0 0.5
14 1 0.25
15 2 0.1250
16 3 0.0625
17 4 0.0313
18 5 0.0156
19 6 0.0078
20 7 0.0039
21 8 0.0020
22 9 0.0010
23 10 0.0005

The M/G/1 Model
• Assumptions
2. Service times can have any probability distribution. You only need the mean (1/ )
and standard deviation ().
3. The queueing system has one server.
• The probability of zero customers in the system is
P0 = 1 – 
• The expected number of customers in the queue is
Lq = 22 + 2] / [2(1 – )]
• The expected number of customers in the system is
L = Lq + 
• The expected waiting time in the queue is
Wq = Lq / 
• The expected waiting time in the system is
W = Wq + 1/

The Values of  and Lq for the M/G/1 Model
with Various Service-Time Distributions
Distribution Mean  Model Lq
Exponential 1/ 1/ M/M/1 2 / (1 – )
Degenerate (constant) 1/ 0 M/D/1 (1/2) [2 / (1 – )]
Erlang, with shape parameter k 1/ (1/k) (1/) M/Ek/1 (k+1)/(2k) [2 / (1 – )]

VP for Engineering Approach (New Equipment)
• The Vice President for Engineering has suggested providing tech reps with
new state-of-the-art equipment that would reduce the time required for the
longer repairs.
• After gathering more information, they estimate the new equipment would
have the following effect on the service-time distribution:
– Decrease the mean from 1/4 day to 1/5 day.
– Decrease the standard deviation from 1/4 day to 1/10 day.

M/G/1 Model for the VP of Engineering Approach
(New Equipment)
B C D E F G
3 Data Results
4  3 (mean arrival rate) L= 1.163
5  0.2 (expected service time) Lq = 0.563
6  0.1 (standard deviation)
7 s= 1 (# servers) W= 0.388
8 Wq = 0.188
9
10  0.6
11
12 P0 = 0.4

The M/M/s Model
• Assumptions
2. Service times have an exponential distribution with a mean of 1/
3. Any number of servers (denoted by s).
• With multiple servers, the formula for the utilization factor becomes
 =  / s
but still represents that average fraction of time that individual servers are
busy.

Values of L for the M/M/s Model for Various Values of s
Steady-state expected number of customers in the queueing system
100
10 s = 25
s = 20
s = 15
s = 10
s=7
s=5
s=4
s=3
0.5 s=2
0.2 s=1
0.1
0 0.1 0.3 0.5 0.7 0.9 1.0
Utilization factor 
s

CFO Suggested Approach (Combine Into Teams)
• The Chief Financial Officer has suggested combining the current one-person
tech rep territories into larger territories that would be served jointly by
multiple tech reps.
• A territory with two tech reps:

– Number of machines = 300 (versus 150 before)
– Mean arrival rate =  = 6 (versus  = 3 before)
– Mean service rate =  = 4 (as before)
– Number of servers = s = 2 (versus s = 1 before)
– Utilization factor =  = /s = 0.75 (as before)

M/M/s Model for the CFO’s Suggested Approach
(Combine Into Teams of Two)
B C D E G H
3 Data Results
6 s= 2 (# servers)
7 W= 0.5714
8 Pr(W > t) = 0.169 Wq = 0.3214
9 when t = 1
10  0.75
11 Prob(Wq > t) = 0.087
12 when t = 1 n Pn
13 0 0.1429
14 1 0.2143
15 2 0.1607
16 3 0.1205
17 4 0.0904
18 5 0.0678
19 6 0.0509
20 7 0.0381
21 8 0.0286
22 9 0.0215
23 10 0.0161

CFO Suggested Approach (Teams of Three)
• The Chief Financial Officer has suggested combining the current one-person
tech rep territories into larger territories that would be served jointly by
multiple tech reps.
• A territory with three tech reps:

– Number of machines = 450 (versus 150 before)
– Mean arrival rate =  = 9 (versus  = 3 before)
– Mean service rate =  = 4 (as before)
– Number of servers = s = 3 (versus s = 1 before)
– Utilization factor =  = /s = 0.75 (as before)

M/M/s Model for the CFO’s Suggested Approach
(Combine Into Teams of Three)
B C D E G H
3 Data Results
6 s= 3 (# servers)
7 W= 0.4393
8 Pr(W > t) = 0.090 Wq = 0.1893
9 when t = 1
10  0.75
11 Prob(W q > t) = 0.028
12 when t = 1 n Pn
13 0 0.0748
14 1 0.1682
15 2 0.1893
16 3 0.1419
17 4 0.1065
18 5 0.0798
19 6 0.0599
20 7 0.0449
21 8 0.0337
22 9 0.0253
23 10 0.0189

Comparison of Wq with Territories of Different Sizes
Number of Number of
Tech Reps Machines   s  Wq
1 150 3 4 1 0.75 0.75 workday (6 hours)
2 300 6 4 2 0.75 0.321 workday (2.57 hours)
3 450 9 4 3 0.75 0.189 workday (1.51 hours)

Values of L for the M/D/s Model for Various Values of s
Steady-state expected number of customers in the queueing system
100
s = 25
10
s = 20
s = 15
s = 10
s=7
s=5
1.0 s=4
s=3
s=2
s=1
0.1
0 0.1 0.3 0.5 0.7 0.9 1.0
Utilization factor 
s

Priority Queueing Models
• General Assumptions:
– There are two or more categories of customers. Each category is assigned to a
priority class. Customers in priority class 1 are given priority over customers in
priority class 2. Priority class 2 has priority over priority class 3, etc.
– After deferring to higher priority customers, the customers within each priority
class are served on a first-come-fist-served basis.
• Two types of priorities

– Nonpreemptive priorities: Once a server has begun serving a customer, the
service must be completed (even if a higher priority customer arrives). However,
once service is completed, priorities are applied to select the next one to begin
service.
– Preemptive priorities: The lowest priority customer being served is preempted
(ejected back into the queue) whenever a higher priority customer enters the
queueing system.

Preemptive Priorities Queueing Model
• Additional Assumptions
1. Preemptive priorities are used as previously described.
2. For priority class i (i = 1, 2, … , n), the interarrival times of the customers in that
class have an exponential distribution with a mean of 1/i.
3. All service times have an exponential distribution with a mean of 1/, regardless of
the priority class involved.
4. The queueing system has a single server.
• The utilization factor for the server is
 = (1 + 2 + … + n) / 

Nonpreemptive Priorities Queueing Model
• Additional Assumptions
1. Nonpreemptive priorities are used as previously described.
2. For priority class i (i = 1, 2, … , n), the interarrival times of the customers in that
class have an exponential distribution with a mean of 1/i.
3. All service times have an exponential distribution with a mean of 1/, regardless of
the priority class involved.
4. The queueing system can have any number of servers.
• The utilization factor for the servers is
 = (1 + 2 + … + n) / s

VP of Marketing Approach (Priority for New Copiers)
• The Vice President of Marketing has proposed giving the printer-copiers

priority over other machines for receiving service. The rationale for this
proposal is that the printer-copier performs so many vital functions that its
owners cannot tolerate being without it as long as other machines.
• The mean arrival rates for the two classes of copiers are
– 1 = 1 customer (printer-copier) per workday (now)
– 2 = 2 customers (other machines) per workday (now)
• The proportion of printer-copiers is expected to increase, so in a couple years

– 1 = 1.5 customers (printer-copiers) per workday (later)
– 2 = 1.5 customers (other machines) per workday (later)

Nonpreemptive Priorities Model for
VP of Marketing’s Approach (Current Arrival Rates)
B C D E F G
3 Data
4 n= 2 (# of priority classes)
5  4 (mean service rate)
6 s= 1 (# servers)
7
8 Results
9 i L Lq W Wq
10 Priority Class 1 1 0.5 0.25 0.5 0.25
11 Priority Class 2 2 2.5 2 1.25 1
12 Priority Class 3 1 #DIV/0! #DIV/0! #DIV/0! #DIV/0!
14 Priority Class 5 1 1.75 1.5 1.75 1.5
15
16  3
17  0.75

Nonpreemptive Priorities Model for
VP of Marketing’s Approach (Future Arrival Rates)
B C D E F G
3 Data
6 s= 1 (# servers)
7
8 Results
9 i L Lq W Wq
10 Priority Class 1 1.5 0.825 0.45 0.55 0.3
11 Priority Class 2 1.5 2.175 1.8 1.45 1.2
14 Priority Class 5 1 1.75 1.5 1.75 1.5
15
16  3
17  0.75

Expected Waiting Times with Nonpreemptive Priorities
s When 1 2   Wq for Printer Copiers Wq for Other Machines
1 Now 1 2 4 0.75 0.25 workday (2 hrs.) 1 workday (8 hrs.)
1 Later 1.5 1.5 4 0.75 0.3 workday (2.4 hrs.) 1.2 workday (9.6 hrs.)
2 Now 2 4 4 0.75 0.107 workday (0.86 hr.) 0.439 workday (3.43 hrs.)
2 Later 3 3 4 0.75 0.129 workday (1.03 hrs.) 0.514 workday (4.11 hrs.)
3 Now 3 6 4 0.75 0.063 workday (0.50 hr.) 0.252 workday (2.02 hrs.)
3 Later 4.5 4.5 4 0.75 0.076 workday (0.61 hr.) 0.303 workday (2.42 hrs.)

The Four Approaches Under Considerations
Proposer Proposal Additional Cost

John Phixitt Maintain one-person territories, but $300 million per year
reduce number of machines assigned
to each from 150 to 100
VP for Engineering Keep current one-person territories, One-time cost of $500
but provide new state-of-the-art million
equipment to the tech-reps
Chief Financial Officer Change to three-person territories None, except

disadvantages of larger
territories
VP for Marketing Change to two-person territories None, except
with priority given to the printer- disadvantages of larger
copiers for repairs territories
Decision: Adopt fourth proposal (except for sparsely populated areas where
second proposal should be adopted).

Some Insights About Designing Queueing Systems
1. When designing a single-server queueing system, beware that giving a

relatively high utilization factor (workload) to the server provides surprisingly
poor performance for the system.
2. Decreasing the variability of service times (without any change in the mean)
improves the performance of a queueing system substantially.
3. Multiple-server queueing systems can perform satisfactorily with somewhat

higher utilization factors than can single-server queueing systems. For
example, pooling servers by combining separate single-server queueing
systems into one multiple-server queueing system greatly improves the
measures of performance.
4. Applying priorities when selecting customers to begin service can greatly

improve the measures of performance for high-priority customers.

Effect of High-Utilization Factors (Insight 1)
B C D E G H
3 Data Results
4  0.5 (mean arrival rate) L= 1
A B C D E
9 Data Table Demonstrating the Effect of
10  on Lq and L for M/M/1
Increasing
11 100
Average Line Length (L)

12  Lq L
80
13 1 0.5 1
14 0 0.01 0.0001 0.0101 60
15 0 0.25 0.0833 0.3333
16 0 0.5 0.5 1 40
17 0 0.6 0.9 1.5 20
18 0 0.7 1.6333 2.3333
19 0 0.75 2.25 3 0
20 0 0.8 3.2 4 0 0.2 0.4 0.6 0.8 1
21 0 0.85 4.8167 5.6667
22 0 0.9 8.1 9 System Utilization (r)
23 0 0.95 18.05 19
24 0 0.99 98.01 99
25 0 0.999 998.001 999

Effect of Decreasing  (Insight 2)
A B C D E F G H
1 Template for the M/G/1 Queueing Model
2
3 Data Results
4  0.5 (mean arrival rate) L= 0.8125
5  1 (expected service time) Lq = 0.3125
6  0.5 (standard deviation)
7 s= 1 (# servers) W= 1.625
8 Wq = 0.625
9
10  0.5
11
12 P0 = 0.5
13
14 Data Table Demonstrating the Effect of Decreasing s on Lq for M/G/1
15
16 Body of Table Shows L q Values
17
18 
19 0.3125 1 0.5 0
20 0.5 0.500 0.313 0.250
21  0.75 2.250 1.406 1.125
22 0.9 8.100 5.063 4.050
23 0.99 98.010 61.256 49.005

Economic Analysis of the Number of Servers to Provide
• In many cases, the consequences of making customers wait can be expressed

as a waiting cost.
• The manager is interested in minimizing the total cost.

TC = Expected total cost per unit time
SC = Expected service cost per unit time
WC = Expected waiting cost per unit time
The objective is then to choose the number of servers so as to
Minimize TC = SC + WC
• When each server costs the same (Cs = cost of server per unit time),
SC = Cs s
• When the waiting cost is proportional to the amount of waiting (Cw = waiting
cost per unit time for each customer),
WC = Cw L

Acme Machine Shop
• The Acme Machine Shop has a tool crib for storing tool required by shop
mechanics.
• Two clerks run the tool crib.
• The estimates of the mean arrival rate  and the mean service rate (per server)
 are
 = 120 customers per hour
 = 80 customers per hour
• The total cost to the company of each tool crib clerk is $20/hour, so Cs = $20.
• While mechanics are busy, their value to Acme is $48/hour, so Cw = $48.
• Choose s so as to Minimize TC = $20s + $48L.

Excel Template for Choosing the Number of Servers
B C D E F G
3 Data Results
6 s= 3 (# servers)
7 W= 0.014473684
8 Pr(W > t) = 0.02581732 Wq = 0.001973684
9 when t = 0.05
10  0.5
11 Prob(Wq > t) = 0.00058707
12 when t = 0.05 n Pn
13 0 0.210526316
14 Economic Analysis: 1 0.315789474
15 Cs = $20.00 (cost / server / unit time) 2 0.236842105
16 Cw = $48.00 (waiting cost / unit time) 3 0.118421053
17 4 0.059210526
18 Cost of Service $60.00 5 0.029605263
19 Cost of Waiting $83.37 6 0.014802632
20 Total Cost $143.37 7 0.007401316

Comparing Expected Cost vs. Number of Clerks
H I J K L M N
1 Data Table for Expected Total Cost of Alternatives
2
3 Cost of Cost of Total
4 s r L Service Waiting Cost
5 0.50 1.74 $60.00 $83.37 $143.37
6 1 1.50 #N/A $20.00 #N/A #N/A
7 2 0.75 3.43 $40.00 $164.57 $204.57
8 3 0.50 1.74 $60.00 $83.37 $143.37
9 4 0.38 1.54 $80.00 $74.15 $154.15
10 5 0.30 1.51 $100.00 $72.41 $172.41
$250
Cost of
$200
Service
Cost ($/hour)
$150 Cost of
$100 Waiting
Total Cost
$50
$0
0 1 2 3 4 5
Number of Servers (s)

Where is There Waiting?
• Service Facility
– Fast-food restaurants
– Post office
– Grocery store
– Bank
• Disneyland
• Highway traffic
• Manufacturing
• Equipment awaiting repair
• Phone or computer network
• Product orders

Why is There Waiting?
• Example #1: McDonalds

– 50 customers arrive per hour
– Service rate is 60 customers per hour
• Example #2: Doctor’s Office

– Arrivals are scheduled to arrive every 20 minutes.
– The doctor spends an average of 18 minutes with each patient.

System Characteristics
• Number of servers
• Arrival and service pattern

– rate of arrivals and service
– distribution of arrivals and service
• Maximum size of the queue
• Queue disciplince
– FCFS?
– Priority system?
• Population size
– Infinite or finite?

Measures of System Performance
• Average number of customers waiting

– in the system
– in the queue
• Average time customers wait

– in the system
– in the queue
• Which measure is the most important?

Number of Servers
• Single Server
...
Customers Service
Center
• Multiple Servers
...
... ...
Customers ...
Customers Service
Service
Centers
Centers

Arrival Pattern
• A Poisson distribution is usually assumed.
• A good approximation of random arrivals.
• Lack-of-memory property: Probability of an arrival in the next instant is

constant, regardless of the past.
Relative
Frequency
.18
.16
.14
.12
.10
.08
.06
.04
.02
0 1 2 3 4 5 6 7 8 9 10 11 12 13
Customers per time unit

Service Pattern
• Either an exponential distribution is assumed,
– Implies that the service is usually short, but occasionally long
– If service time is exponential then service rate is Poisson
– Lack-of-memory property: The probability that a service ends in the next instant is
constant (regardless of how long its already gone).
– Decent approximation if the jobs to be done are random.
– Not a good approximation if the jobs to be done are always the same.
Relative
Frequency (%)
Service Time
• Or any distribution
– Only single-server model is easily solved.

Maximum Size of Queue
• Most queueing models assume an infinite queue length is possible.
...
• If the queue length is limited, a finite queue model can be used.

Queue Discipline
• Most queueing systems assume customers are served first-come first-served.
..
. Customers
Service
Center
• If certain customers are given priority, a priority queueing model can be

used.
– Nonpreemptive: Finish customer in service before taking a new one.
– Preemptive: If priority customer arrives, any regular customer in service is
preempted (put back in the queue).
...
Regular Priority Service

Customers Customers Center

Population Source
• Most queueing models assume an infinite population source.
...
Customer Source System
• If the number of potential customers is small, a finite source model can

be used.
– Number in system affects arrival rate (fewer potential arrivals when more in
system)
– Okay to assume infinite if N > 20.
...
Customer Source System

Models
1. Single server, exponential service time (M/M/1)

2. Single server, general service time (M/G/1)
3. Multiple servers, exponential service time (M/M/s)
4. Finite queue (M/M/s/K)
5. Priority queue (nonpreemptive and preemptive)
6. Finite calling population
A Taxonomy
— / — / — (and an optional fourth element / —)
Arrival Service Number of Maximum
Distribution Distribution Servers in Queue
where
M = Exponential (Markovian)
D = deterministic (constant)
G = general distribution

Notation
• Parameters:
 = customer arrival rate

 = service rate (1/ = average service time)
s = number of servers
• Performance Measures
Lq = average number of customers in the queue

L = average number of customers in the system
Wq = average waiting time in the queue
W = average waiting time (including service)
Pn = probability of having n customers in the system
 = system utilization

Model 1 (M/M/1)
Customers arrive to a small-town post office at an average rate of 10 per hour

(Poisson distribution). There is only one postal employee on duty and he can serve
customers in an average of 5 minutes (exponential distribution).
A B C D E G H I
1 Template for the M/M/s Queueing Model
2
3 Data Results
6 s= 1 (# servers) minutes
7 W= 0.5 30
8 Pr(W > t) = 0.13533528 Wq = 0.416666667 25
9 when t = 1
10  0.833333333
11 Prob(W q > t) = 0.1127794
12 when t = 1 n Pn
13 0 0.166666667
14 1 0.138888889
15 2 0.115740741
16 3 0.096450617
17 4 0.080375514
18 5 0.066979595
19 6 0.055816329
20 7 0.046513608
21 8 0.03876134
22 9 0.032301117
23 10 0.026917597

Model 2 (M/G/1)
ABC Car Wash is an automated car wash. Each customer deposits four quarters in
a coin slot, drives the car into the auto-washer, and waits while the car is
automatically washed. Cars arrive at an average rate of 20 cars per hour (Poisson).
The service time is exactly 2 minutes.
A B C D E F G H
1 Template for the M/G/1 Queueing Model
2
3 Data Results
5  0.03333333 (expected service time) Lq = 0.667
6  0 (standard deviation) minutes
7 s= 1 (# servers) W= 0.067 4
8 Wq = 0.033 2
9
10  0.666666667
11
12 P0 = 0.333333333

Model 3 (M/M/s)
A grocery store has three registers open. Customers arrive to check out at an
average of 1 per minute (Poisson). The service time averages 2 minutes
(exponential).
A B C D E G H
2
3 Data Results
5  0.5 (mean service rate) Lq = 0.888888889
6 s= 3 (# servers)
7 W= 2.888888889
8 Pr(W > t) = 0.74131525 Wq = 0.888888889
9 when t = 1
10  0.666666667
11 Prob(Wq > t) = 0.26956918
12 when t = 1 n Pn
13 0 0.111111111
14 1 0.222222222
15 2 0.222222222
16 3 0.148148148
17 4 0.098765432
18 5 0.065843621
19 6 0.043895748
20 7 0.029263832
21 8 0.019509221
22 9 0.013006147
23 10 0.008670765

Model 4 (M/M/s/K)
A call center that handles the tech support for a software manufacturer currently
has 10 telephone lines, with three people fielding the calls. Customers call at an
average rate of 40 per hour (Poisson). A customer can be served in an average of
four minutes (exponential).
A B C D E F G
1 Template for M/M/s Finite Queue Model
2
3 Data Results
4  40 (mean arrival rate) L = 4.5577194
6 s= 3 (# servers)
7 K= 10 (max customers) W= 0.1208
8 Wq = 0.0540838
9
10  0.8888889
11
12 n Pn
13 0 0.0406825
14 1 0.1084866
15 2 0.1446488
16 3 0.1285767
17 4 0.1142904
18 5 0.1015915
19 6 0.0903035
20 7 0.0802698
21 8 0.071351
22 9 0.0634231
23 10 0.0563761

Model 5a (Nonpreemptive Priority Queue)
Consider a small-town hospital emergency room (ER) that has just one doctor on
duty. When patients arrive, they are classified as either critical or non-critical.
When the doctor is finished treating a patient, she takes the next critical patient. If
there are no critical patients, then she takes the next non-critical patient. The ER
doctor spends an average of 10 minutes (exponential) treating each patient before
they are either released or admitted to the hospital. An average of 1 critical patient
and 3 non-critical patients arrive each hour (Poisson).
A B C D E F G H
1 Template for M/M/s Nonpreemptive Priorities Queueing Model
2
3 Data
4 1 n= 2 (# of priority classes)
5 0  6 (mean service rate)
6 0 s= 1 (# servers)
7 0
8 0 Results
9 0 i L Lq W Wq Wq (minutes)
10 0 Priority Class 1 1 0.3 0.133333333 0.3 0.133333333 8
11 0 Priority Class 2 3 1.7 1.2 0.566666667 0.4 24
12 0 Priority Class 3 1 2.166666667 2 2.166666667 2
13 0 Priority Class 4 1 #DIV/0! #DIV/0! #DIV/0! #DIV/0!
14 0 Priority Class 5 1 #DIV/0! #DIV/0! #DIV/0! #DIV/0!
15 0
16 0  4
17 0  0.666666667

Model 5b (Preemptive Priority Queue)
Reconsider the same small-town hospital emergency room (ER). Now suppose
they change their policy so that if a critical patient arrives while a non-critical
patient is being treated, the doctor stops treating the non-critical patient, and
immediately starts treating the critical patient. Only when there are no critical
patients to be treated does the doctor start treating non-critical patients.
A B C D E F G H
1 Template for M/M/1 Preemptive Priorities Queueing Model
2
3 Data
6 s= 1 (# servers)
7
8 Results
9 i L Lq W Wq Wq (minutes)
10 Priority Class 1 1 0.2 0.033333333 0.2 0.033333333 2
11 Priority Class 2 3 1.8 1.3 0.6 0.433333333 26
12 Priority Class 3 1 3 2.833333333 3 2.833333333
15  4
16  0.666666667

Model 6 (Finite Calling Population)
Consider a PC-Board assembly facility. There are six automated component

insertion machines. Unfortunately, they are very prone to break down. Each
operating machine breaks down every eight hours or so (exponential distribution).
Because these machines are so prone to break down, a full-time repairperson is
kept on staff just to repair these machines. Each repair takes an average of one
hour (exponential distribution). On average, how many machines are operating at
a time? A B C D E F G
1 Template for M/M/s Finite Calling Population Model
2
3 Data Results
4  0.75 (max arrival rate) L= 1.118015082
6 s= 1 (# servers)
7 N= 6 (size of population) W= 1.832066425
8 Wq = 0.832066425
9
10  0.75
11 -bar = 0.610248115
12
13 0 n Pn
14 1 0 0.389751885
15 2 1 0.292313914
16 3 2 0.182696196
17 4 3 0.091348098
18 5 4 0.034255537
19 6 5 0.008563884
20 7 6 0.001070486
21 8 7 0
22 9 8 0
23 10 9 0

Application of Queueing Models
• We can use the results from queueing models to make the following types of
decisions:
– How many servers to employ.
– How large should the waiting space be.
– Whether to use a single fast server or a number of slower servers.
– Whether to have a general purpose server or faster specific servers.

Total Cost
• The goal is to minimize total cost = cost of servers + cost of waiting
Cost
Total Cost
Cost of Service
Capacity
Cost of customers
waiting
Optimum
Service Capacity

Example #1: How Many Servers?
• The MIS department of a high tech company handles employee requests for
assistance when computer questions arise. Employees requiring assistance
phone the MIS department with their questions (but may have to wait on hold
if all of the tech support staff are busy).
• The MIS department receives an average of 40 requests for assistance per hour
(Poisson).
• The average question can be answered in 3 minutes (exponential).
• The MIS staff is paid an average of $15 per hour.
• The average employee earns $25 per hour.
Question: What is the optimal size of the MIS tech support staff?

Example #1: How Many Servers
A B C D E F G
1 Template for Economic Analysis of M/M/s Queueing Model
2
3 Data Results
6 s= 4 (# servers)
7 W= 0.054347826
8 Pr(W > t) = 0.4083219 Wq = 0.004347826
9 when t = 0.05
10  0.5
11 Prob(Wq > t) = 0.02353657
12 when t = 0.05 n Pn
13 1 0 0.130434783
14 2 Economic Analysis: 1 0.260869565
15 2 Cs = $15.00 (cost / server / unit time) 2 0.260869565
16 1 Cw = $25.00 (waiting cost / unit time) 3 0.173913043
17 0 4 0.086956522
18 0 Cost of Service $60.00 5 0.043478261
19 0 Cost of Waiting $54.35 6 0.02173913
20 0 Total Cost $114.35 7 0.010869565
21 0 8 0.005434783
22 0 9 0.002717391
23 0 10 0.001358696
24 0 11 0.000679348
25 0 12 0.000339674
26 0 13 0.000169837
27 0 14 8.49185E-05
28 0 15 4.24592E-05
29 0 16 2.12296E-05
30 0 17 1.06148E-05
31 0 18 5.3074E-06
32 0 19 2.6537E-06

A Data Table for Example #1: How Many Servers?
I J K L M N
1 Data Table for Example #1
2
3 s Lq Wq (min) Cost of Service Cost of Waiting Total Cost
4 0.174 0.261 $60.00 $54.35 $114.35
5 3 0.889 1.333 $45.00 $72.22 $117.22
6 4 0.174 0.261 $60.00 $54.35 $114.35
7 5 0.040 0.060 $75.00 $51.00 $126.00
8 6 0.009 0.014 $90.00 $50.23 $140.23

• A McDonalds franchise is trying to decide how many registers to have open

during their busiest time, the lunch hour.
• Customers arrive during the lunch hour at a rate of 98 customers per hour
(Poisson distribution).
• Each service takes an average of 3 minutes (exponential distribution).
Question #1: If management would not like the average customer to wait
longer than five minutes in line, how many registers should they open?
Question #2: If management would like no more than 5% of customers to

wait more than 5 minutes, how many registers should they open?

A B C D E G H I
2
3 Data Results
7 W= 0.075094814 4.51
8 Pr(W > t) = 0.34895764 minutes Wq = 0.025094814 1.51
9 when t = 0.08333333 5
10  0.816666667
11 Prob(W q > t) = 0.08826736 minutes
12 when t = 0.08333333 5 n Pn
K L M
1 Data Table for Example #2
2
3 s Wq (min) Pr(Wq > 5 min)
4 1.5057 0.08827
5 5 28.510 0.80443
6 6 1.506 0.08827
7 7 0.430 0.00908
8 8 0.148 0.00087
9 9 0.053 0.00008

Example #3: How Much Waiting Space?
• A photo development shop operates a drive-through lane where customers can

drop off film to be developed and pick up developed photos.
• Customers arrive at an average rate of 40 per hour (Poisson).
• Each service takes an average of 1 minute (exponential).
• They are remodeling the parking area and drive-through lane. They would like
the drive-through lane to hold all of the customers at least 95% of the time.
Question: How many cars must the drive-through lane be able to hold?

Example #3: How Much Waiting Space?
A B C D E G H I
2
3 Data Results
6 s= 1 (# servers)
7 W= 0.05
8 Pr(W > t) = 2.0612E-09 Wq = 0.033333333
9 when t = 1
10  0.666666667
11 Prob(W q > t) = 1.3741E-09
12 when t = 1 n Pn cumulative
13 0 0.333333333 0.3333
14 1 0.222222222 0.5556
15 2 0.148148148 0.7037
16 3 0.098765432 0.8025
17 4 0.065843621 0.8683
18 5 0.043895748 0.9122
19 6 0.029263832 0.9415
20 7 0.019509221 0.9610
21 8 0.013006147 0.9740
22 9 0.008670765 0.9827
23 10 0.00578051 0.9884

Example #4: One Fast Server or Many Slow Servers
• A McDonalds is considering changing the way that they serve customers.
• Customers arrive at an average rate of 50 per hour.
• Current System: For most of the day (all but their lunch hour), they have
three registers open. Each cashier takes the customer’s order, collects the
money, and then gets the burgers and pours the drinks. This takes an average
of 3 minutes per customer (exponential distribution).
• Proposed System: They are considering having just one cash register. While
one person takes the order and collects the money, another will pour the
drinks, and another will get the burgers (like Wendys). The three together
think they can serve a customer in an average of 1 minute.
Question: Should they switch to the proposed system?

3 Slow Servers (McDonalds)
B C D E G H I
3 Data Results
7 W= 0.120224719 7.21
8 Pr(W > t) = 0.46194225 Wq = 0.070224719 4.21
9 when t = 0.1
10  0.833333333
1 Fast Server (Wendys)

B C D E G H I
3 Data Results
7 W= 0.1 6
8 Pr(W > t) = 4.54E-05 Wq = 0.083333333 5
9 when t = 1
10  0.833333333

Example #5: General or Specific Servers
• A small bank in a mall has two tellers.
• The bank handles two kinds of customers: merchant customers and regular
customers. Each arrive at an average rate of 20 customers per hour (for a total
arrival rate of 40 customers per hour).
• Current System (Specific Servers): Currently one teller handles only

merchant customers and one teller handles only regular customers. The service
time for both tellers averages 2 minutes (exponential).
• Proposed System (General Servers): The bank manager is considering

changing the setup to allow each teller to handle both merchant customers and
regular customers. Since the tellers would have to handle both types of jobs,
their efficiency would decrease to a mean service time of 2.2 minutes.
Question: Should they switch to the proposed system?

Current (Specific Servers)
B C D E G H I
3 Data Results total in bank
4  20 (mean arrival rate) L= 2 4
5  30 (mean service rate) Lq = 1.333333333 2.667
7 W= 0.1 6
8 Pr(W > t) = 4.54E-05 Wq = 0.066666667 4
9 when t = 1
10  0.666666667
Proposed (General Servers)

B C D E G H I
3 Data Results total in bank
4  40 (mean arrival rate) L= 3.173076923 3.173
5  27.27 (mean service rate) Lq = 1.706410256 1.706
7 W= 0.079326923 4.760
8 Pr(W > t) = 6.4082E-07 Wq = 0.042660256 2.560
9 when t = 1
10  0.733333333

LL Bean
• LL Bean’s mail order business

– Mail order phone lines open 24 hours per day, 365 days per year
– 78,000 calls per week (average)
– Seasonal variations as well as variability during each day
• How LL Bean estimates the number of servers needed

– Each of the week’s 168 hours in a week is modeled separately as a period to be
staffed
– Each hour modeled as an M/M/s queue
– Arrival rates and service rates estimated from historical data
– Service standard: no more than 15% of calls wait more than 20 seconds
– Full-time, part-time, and temporary workers scheduled to meet service standard

Chapter 11

Uploaded by

Copyright:

Available Formats

Chapter 11

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Chapter 11

Uploaded by

Copyright:

Available Formats

Table of Contents

Chapter 11 (Queueing Models)

Elements of a Queueing Model (Section 11.1) 11.2–11.12

Queueing Models (UW Lecture) 11.56–11.74

Queueing Applications (UW Lecture) 11.75–11.88

McGraw-Hill/Irwin 11.1 © The McGraw-Hill Companies, Inc., 2008

McGraw-Hill/Irwin 11.2 © The McGraw-Hill Companies, Inc., 2008

• Herr Cutter is a German barber who runs a one-man barber shop.

• Herr Cutter opens his shop at 8:00 A.M.

Time of Haicut Duration Haircut

McGraw-Hill/Irwin 11.3 © The McGraw-Hill Companies, Inc., 2008

• The symbol used for the mean arrival rate is

where  is the Greek letter lambda.

• The mean of the probability distribution of interarrival times is

McGraw-Hill/Irwin 11.4 © The McGraw-Hill Companies, Inc., 2008

McGraw-Hill/Irwin 11.5 © The McGraw-Hill Companies, Inc., 2008

McGraw-Hill/Irwin 11.6 © The McGraw-Hill Companies, Inc., 2008

• There is a high likelihood of small interarrival times, but a small chance of a

• Having random arrivals means that interarrival times are completely

McGraw-Hill/Irwin 11.7 © The McGraw-Hill Companies, Inc., 2008

McGraw-Hill/Irwin 11.8 © The McGraw-Hill Companies, Inc., 2008

1 /  = Expected service time

where  is the Greek letter mu.

• The interpretation of  itself is the mean service rate.

 = Expected service completions per unit time for a single busy

McGraw-Hill/Irwin 11.9 © The McGraw-Hill Companies, Inc., 2008

• Constant Service Times

McGraw-Hill/Irwin 11.10 © The McGraw-Hill Companies, Inc., 2008

Distribution of service times

—/—/— Number of Servers

Distribution of interarrival times

The symbols used for the possible distributions are

McGraw-Hill/Irwin 11.11 © The McGraw-Hill Companies, Inc., 2008

1. Interarrival times are independent and identically distributed according to a

McGraw-Hill/Irwin 11.12 © The McGraw-Hill Companies, Inc., 2008

Type of System Customers Server(s)

Type of System Customers Server(s)

McGraw-Hill/Irwin 11.14 © The McGraw-Hill Companies, Inc., 2008

Type of System Customers Server(s)

McGraw-Hill/Irwin 11.15 © The McGraw-Hill Companies, Inc., 2008

• Commercial service systems tend to place greater importance on the second

McGraw-Hill/Irwin 11.16 © The McGraw-Hill Companies, Inc., 2008

L = Expected number of customers in the system, including those being

Lq = Expected number of customers in the queue, which excludes

W = Expected waiting time in the system (including service time) for an

Wq = Expected waiting time in the queue (excludes service time) for an

These definitions assume that the queueing system is in a steady-state condition.

McGraw-Hill/Irwin 11.17 © The McGraw-Hill Companies, Inc., 2008

• Since 1/ is the expected service time

• Little’s formula states that

• Combining the above relationships leads to

McGraw-Hill/Irwin 11.18 © The McGraw-Hill Companies, Inc., 2008

• In addition to knowing what happens on the average, we may also be

• Examples of common goals:

McGraw-Hill/Irwin 11.19 © The McGraw-Hill Companies, Inc., 2008

• The Dupit Corporation is a longtime leader in the office photocopier

• Dupit’s service division is responsible for providing support to the customers

McGraw-Hill/Irwin 11.20 © The McGraw-Hill Companies, Inc., 2008

• Approach Suggested by John Phixitt: Modify the current policy by

• Approach Suggested by the Vice President for Engineering: Provide new