Transcript SOpS 4 Queueing Models in Operations

Queuing Models in Operations
35E00100 Service Operations and Strategy
#4 Fall 2015
Topics
Principles of queuing theory
 Queue parameters
 Basic queuing models
 M/M/1 and M/M/s
 G/G/1 and G/G/s
Extensions
 Systems with finite buffers
 Serial (tandem) queuing system
 Queuing network
 Multiple priority system
 Priority queuing network
Key points
Useful material in the textbook:
Hopp, W. & Spearman, M. (2000) Factory Physics, Chapter 8.6
35E00100 Service Operations and Strategy #4
2
Aalto/BIZ Logistics
10%
0%
0%
Service rate
Arrival rate
30%
100%
25%
100%
25%
90%
80%
20%
80%
15%
60%
10%
40%
60%
15%
50%
40%
10%
30%
90%
Probability
70%
20%
35E00100 Service Operations and Strategy #4
3
Yli
190
180
170
160
150
140
130
120
110
90
100
80
70
60
50
40
30
20
10
0
Yli
190
180
170
160
150
140
130
120
110
90
100
80
0%
70
0%
60
0%
50
0%
40
20%
30
5%
20
20%
10%
10
5%
0
Probability
“Customer arrives
every 10 minutes,
service process
takes 8 minutes”
195
20%
10%
180
20%
165
30%
150
40%
30%
135
50%
40%
120
50%
105
60%
90
70%
60%
75
70%
60
80%
45
90%
80%
30
90%
15
100%
0
Probability
100%
Aalto/BIZ Logistics
What is queuing theory about?
Average waiting time
in queue (CTq )
Service
Arrival rate (ra 
Average number of jobs
in queue (WIPq )
Service rate (re 
Average number of jobs in the system (WIP )
Average time in the system (CT )
35E00100 Service Operations and Strategy #4
4
Aalto/BIZ Logistics
Cost Trade-Off:
Capacity Utilization
Low utilization levels (u < 0.6 ) provide
Cost
Total costs
 Better service levels
 Lower waiting costs (e.g., lost business)
 Greater flexibility
Cost of
queuing
High utilization levels (u > 0.9 ) provide
 Better equipment and employee utilization
 Fewer idle periods
 Lower production/service costs
Cost of
operations
0%
35E00100 Service Operations and Strategy #4
Utilization
100 %
5
Aalto/BIZ Logistics
Cost Trade-Off:
Capacity Level
Cost
Total costs
Cost of
operations
Cost of
queuing
Capacity
35E00100 Service Operations and Strategy #4
Optimum
6
Aalto/BIZ Logistics
Kendall's Classification 1/2/3/4/5/6
2
1
Queue
Server
3
1 = the nature of arrival process
2 = the nature of service process
3 = the number of (parallel) machines
4 = queue discipline
5 = the maximum allowable number of jobs
6 = the size of population
35E00100 Service Operations and Strategy #4
7
Aalto/BIZ Logistics
System Characteristics
Inter-arrival and service times
 M = exponential (Markovian) distribution
 Memoryless property
 Common in service models
 G = completely general distribution (with mean and variance
specified)
 Memoryless property is lost  performance approximations
 Manufacturing environment
Typical queuing disciplines
 FCFS, SPT, EDD, LCFS, etc.
 Priority classes and within class FCFS
35E00100 Service Operations and Strategy #4
8
Aalto/BIZ Logistics
Inter-arrival and Service Times
Exponential Distribution
1.0
0.9
0.8
0.7
Exp(1)
0.6
Exp(3)
0.5
Exp(5)
0.4
0.3
0.2
0.1
0.0
0
2
4
6
8
10
12
14
16
18
20
22
24
26
28
30
Time (t)
35E00100 Service Operations and Strategy #4
9
Aalto/BIZ Logistics
Inter-arrival and Service Times
Poisson Distribution
0.40
0.35
If the times between arrivals are independent and
exponentially distributed, then the number of customer
that arrive within a given period of time is Poisson
distributed. These are often referred to as “Poisson
arrivals”.
0.30
0.25
For instance, if inter-arrival times are exponentially
distributed with mean (1 / ra) = 0.25 hrs, then the number
of customer arrivals in a one hour period has a Poisson
distribution with mean ra = 4.
0.20
0.15
Poisson(1)
0.10
Poisson(3)
Poisson(5)
0.05
0.00
0
2
4
6
8
10
12
14
16
18
20
Arrivals per hr
35E00100 Service Operations and Strategy #4
10
Aalto/BIZ Logistics
M/M/1 Queue - Relevant Equations
ra
re
Utilization rate u
Average waiting time CTq
Average queue length WIPq
Average time of jobs in system CT
Average number of jobs in system WIP
35E00100 Service Operations and Strategy #4
11
ra
u
te or r (r  r )
e e
a
1 u
u2
or ra CTq
1 u
te
or CTq  te
1 u
u
1 u
e.g. Krajewski & Ritzman
Aalto/BIZ Logistics
M/M/m Queue - Relevant Equations
Utilization rate u
ra
mre
Average queue length WIPq
ra m
p0 ( ) u
re
m !(1  u ) 2
Average waiting time CTq
Average time of jobs in system CT
Average number of jobs in system WIP
 m 1


 n  0
Probability for being idle p0
35E00100 Service Operations and Strategy #4
12
u 2( m 1) 1
te
m(1  u )
1
CTq  t e  CTq 
re
ra
WIPq 
re
(ra / re )
(ra re ) 


n!
m !(1  u ) 
n
m
1
e.g. Krajewski & Ritzman
Aalto/BIZ Logistics
General Inter-arrival & Process Times
G/G/1 queue
G/G/m queue
CT q  V  U  t
 ca2  ce2
 
 2
CTq  V  U  t
 ca2  ce2  u 2 ( m 1) 1 

 
te


 2  m(1  u ) 
 u 

 1  u t e

 Single machine workstations
 Multi-machine workstations
 Flow variability, process
(parallel machines)
 Fast and accurate
 Extremely general
variability, or both can
combine to inflate queue time
 Variability causes congestion
Note! This VUT equation is also called Kingman’s Equation.
(VUT = Variability x Utilization x Time)
35E00100 Service Operations and Strategy #4
14
Hopp and Spearman 2000, 270
Aalto/BIZ Logistics
Some points to be remembered
Arrival rate is rarely stationary
 Long term average versus ”worst case” estimate
A heuristic to decide how many servers to provide
 Specify service level by defining the probability for waiting in line
 Calculate the number of servers
ra
m   z1
re
ra
re
Little’s law
 Lower utilization, less waiting
 Change in throughput can be avoided by decreasing variability
Resource pooling
 Economies of scale achieved by joining multiple queues into a
single queue with multiple machines
 Problems in one machine do not delay all orders
50%
Queue
50%
?
Server
Queue
35E00100 Service Operations and Strategy #4
15
Server
Aalto/BIZ Logistics
Extensions to the Basic Models
35E00100 Service Operations and Strategy #4
16
Aalto/BIZ Logistics
Effects of Blocking
VUT equation versus real world systems?
Blocking models
 The principle is to estimate WIP and TH for given set of rates
and buffer sizes.
 Typically much more complex than non-blocking (open) models.
 Often simulation is needed to evaluate realistic systems.
Differences of blocking models compared to basic
queuing models:
 Arrival rate is only the rate of potential arrivals
 Utilization can equal or exceed 100 %
 Balking rate to be defined (rate at which arrivals are rejected)
35E00100 Service Operations and Strategy #4
17
Hopp and Spearman 2000, 273-279
Aalto/BIZ Logistics
M/M/1/b Queue
There is room for b=B+2 jobs in system, B
in the buffer and one at each station
B
Infinite raw
materials
1
2
Model of Station 2
Formulas valid for u1
b 1
(
b

1)
u
u
Goes to u/(1-u) as b  

Always less than WIP(M/M/1) WIP( M / M /1/ b ) 
1 u
1  u b 1
b
1

u
Goes to ra as b  
r
Always less than TH(M/M/1) TH ( M / M /1/ b ) 
b 1 a
1 u
WIP( M / M /1/ b )
te 2
Little’s law
CT( M / M /1/ b ) 
, where u 
TH ( M / M /1/ b )
te1
35E00100 Service Operations and Strategy #4
18
Hopp and Spearman 2000, 273-279
Aalto/BIZ Logistics
Example 1
Illustrating the Effect of Blocking
te1=21
te2=20
1
2
te 2 20

 0.9524
te1 21
u
WIP( M / M /1) 
 20 jobs
1 u
1
1
TH ( M / M /1)  ra 

 0.0476 job/min
te1 21
u
Conclusion:
M/M/1/b system has
less WIP and less TH
than M/M/1 system!
18 %
1  0.9524 4  1 
TH (M/M/ 1/b) 
r


0.039
job/min
less
TH
b 1 a
5  21 
1- u
1  0.9524  
(b  1)u b 1
5(0.95245 )
u
90 %
WIP( M / M /1/ b ) 


20


1.8954
job
less WIP
1 u
1  u b 1
1  0.95245
1 - ub
35E00100 Service Operations and Strategy #4
19
Hopp and Spearman 2000, 275-277
Aalto/BIZ Logistics
We need to be able to analyze
different types of processes…
Single Stage
Multi-Stage
ATM
Car wash
Single
Channe
l
Queue Server
Queue
Queue
Server
Bank teller’s windows
MultiChannel
Queue
Servers
35E00100 Service Operations and Strategy #4
Server
Hospital admissions
Queue
Queue
Servers
Servers
Aalto/BIZ Logistics
Serial and Network Queuing Systems
Serial (or tandem) queuing systems
 Servers arranged in series
 e.g. repetitive flow process
1
2
3
Queuing networks
 Some servers arranged in parallel and some in series
 E.g. cellular manufacturing, job shops
2a
1a
3a
2b
1b
3b
2c
35E00100 Service Operations and Strategy #4
21
Aalto/BIZ Logistics
Example 2
Serial Queuing System
1
2
3
Suppose a company produces a variety of similar but customized products
using a three stage batch flow process. Customer orders are received
randomly during the day according to a Poisson process at the rate of five
orders per day. Because of differences in order (batch) sizes, machine setup
times, and operating speeds, and because of machine breakdowns quality
problems, and worker fatigue, the time to process a customer order at each
production stage is exponentially distributed, with an average processing
time of 1/6 day.
The 1st stage of the system is then an M/M/1 queue, where orders are the
customers and the 1st stage is the server, ra =5 orders/day and re =6
orders/day.
It can be proved that in steady state, the pattern of served customers leaving
an M/M/1 queuing system will approximate a Poisson process with an
average rate of ra. So, the seriel queuing system can be treated as a series
of 3 identical M/M/1 queues.
35E00100 Service Operations and Strategy #4
22
Aalto/BIZ Logistics
Example 2
1
2
3
Serial Queuing System
Using the M/M/1 formulas for the 1st stage
u = ra / re = 5/6 = 0.83
WIPq = ra2/ [re(re-ra)] = 52 / 6(6-5) = 4.17 orders
CTs = 1/(re -ra) = 1/(6-5) = 1 day
In front of the 1st stage there will be an average of 4.17 customer orders
waiting in the queue to be processed. It will take an order an average of 1 day
to make its way through the 1st stage (from receipt of the order until
processing is completed at stage 1).
The other two stages are identical, so in front of each stage there will be an
average of 4.17 orders in queue, and it will take 1 day to get through each
stage. So, on average, there will be a total of 12.51 jobs in inventory in front of
the three processing stages. The average throughput time is 3 days, even
though the time spent processing an order is one-half of a day.
CT=1 day
CT=1 day
1
2
re=5/day
WIPq=4.17
35E00100 Service Operations and Strategy #4
ra=6/day
WIPq=4.17
ra=6/day
23
CT=1 day
3
WIPq=4.17
ra=6/day
Aalto/BIZ Logistics
Example 2
1
2
3
Serial Queuing System
Demand increases from 5.0 to 5.7 orders per day
u = ra / re = 5.7/6 = 0.95
WIPq = ra2/ [re(re-ra)] = 5.72 / 6(6-5.7) = 18.05 orders
CTs = 1/(re -ra) = 1/(6-5.7) = 3.3 days
In front of the 1st stage there will be an average of 18.05 customer orders
waiting in the queue to be processed. It will take an order an average of
3.33 days to make its way through the 1st stage.
On average, there will be a total of 54.15 jobs in inventory in front of the
three processing stages. The average throughput time is 10 days, even
though the time spent processing an order is one-half of a day.
re=5.7/da
y
WIPq=
18.05
1
ra=6/day
M/M/1
35E00100 Service Operations and Strategy #4
CT=3.33 d
CT=3.33 d
CT=3.33 d
WIPq=
18.05
2
ra=6/day
M/M/1
24
WIPq=
18.05
3
ra=6/day
M/M/1
Aalto/BIZ Logistics
Example 2
1
2
3
Serial Queuing System
No randomness in processing times
Using the M/D/1 formulas for the first stage
WIPq = u2 / [2(1-u)] = 0.952 / 2(1-0.95) = 9.025 orders
CTq = WIPq / ra = 9.025 / 5.7 = 1.583 days
CT = CTq +1/re = 1.583 + 1/6 = 1.75 days
re=5.7/da
y
WIPq=9.025
1
2
WIPq=0
ra=6/day
M/D/1
CT=0.167 d
CT=0.167 d
CT=1.75 d
ra=6/day
D/D/1
3
WIPq=0
ra=6/day
D/D/1
No queues develop in front of stages 2 and 3, and so the average time in
the stage is the processing time 0.167 days per job.
On average, there will be a total of 9.025 jobs in inventory in the system.
The average throughput time is 2.08 days.
Inventories are reduced by 83% and throughput time decreases by nearly 80%.
35E00100 Service Operations and Strategy #4
25
Aalto/BIZ Logistics
Example 3
Serial Queuing System
Process and Resources
Two single-server work stations
A
B
 Three types of tasks to perform
 2 job types (A and B)
 Inter-arrival times for A and B Uniform[0,40]
Stage 1
 Type A makes two passes
 Type B jobs make a single pass through the system
 Service times
Stage 2
 Stage 1: Uniform[0,12]
 Stage 2: Uniform[0,10]
 Individual service times not known
 No changeover cost
 Can change from one task type to another without penalty
 No preemption
 Processing of jobs cannot be interrupted
35E00100 Service Operations and Strategy #4
27
Aalto/BIZ Logistics
Example 3
Serial Queuing System
Questions
Stage 1
Stage 2
a) What is the long run utilization rate for server 1 and for
server 2?
b) What are key findings of the following simulation?
 The length of the simulation is 120,000 hrs.
 First 20,000 hrs are discarded.
 Summary statistics of the remaining 100,000 hrs are used.
 95% confidence interval for the mean throughput time
(MTPT) of each class = MTPT estimate +/- 10%
 FCFS discipline is applied.
c) Same as b) except type B jobs have non-preemptive
priority over type A jobs.
d) Same as b) except two identical servers at each station
and an inter-arrival time distribution of each customer type
that is uniformly distributed between 0 and 20 hrs.
e) Inter-arrival and service time distributions are exponential.
35E00100 Service Operations and Strategy #4
28
Aalto/BIZ Logistics
Example 3
Serial Queuing System
Summary Statistics of a Simulation
Stage 1
Stage 2
MTPT of A
MTPT of B
b)
64,85
32,86
c)
76,05
17,26
d)
44,7
22,13
e)
156,2
78,46
QL - station 1
QL - station 2
2,65
0,65
2,38
0,63
2,77
0,63
7,84
2,25
u - station 1
u - station 2
0,897
0,749
0,897
0,75
0,898
0,754
0,901
0,753
QL=queue length
35E00100 Service Operations and Strategy #4
29
Aalto/BIZ Logistics
Example 3
Serial Queuing System
Simulation Results (Questions b, c and d)
Throughput times for type A (b)
0,6
Throughput times for type B (b)
0,6
0,5
0,5
0,4
0,4
0,3
0,3
0,2
0,2
0,1
0,1
0
Stage 1
Stage 2
0
0-20
20-40
40-60
60-80 80-100
100120
120140
140160
160180
0-10
10-20 20-30 20-40 40-50 50-60 60-70 70-80 80-90
90100
Throughput times for type B (c)
Throughput times for type A (c)
0,6
0,6
0,5
0,5
0,4
0,4
0,3
0,3
0,2
0,2
0,1
0,1
0
0
0-20
20-40
40-60
60-80 80-100
100120
120140
140160
160180
0-10
Throughput times for type B (d)
Throughput times for type A (d)
0,6
10-20 20-30 20-40 40-50 50-60 60-70 70-80 80-90
90100
0,6
0,5
0,5
0,4
0,4
0,3
0,3
0,2
0,2
0,1
0,1
0
0
0-20
20-40
40-60
60-80 80-100
35E00100 Service Operations and Strategy #4
100120
120140
140160
160180
0-10
30
10-20 20-30 20-40 40-50 50-60 60-70 70-80 80-90
90100
Aalto/BIZ Logistics
Example 3
Serial Queuing System
Simulation Results (Question e)
Stage 1
Stage 2
Throughput times for type A (e)
0,35
0,3
0,25
0,2
0,15
0,1
0,05
0
0-50
50100
100150
150200
200250
250300
300350
350400
400450
450500
Throughput times for type B (e)
0,5
0,4
0,3
0-50
50-100
100-150
150-200
200-250
250-300
300-350
350-400
400-450
450-500
Type A
0,177
0,286
0,18
0,124
0,105
0,059
0,027
0,009
0,005
0,019
Type B
0,4356
0,3194
0,1643
0,0469
0,0104
0,0067
0,0051
0,0069
0,0047
0
0,2
0,1
0
0-50
50100
100150
150200
35E00100 Service Operations and Strategy #4
200250
250300
300350
350400
400450
31
450500
Aalto/BIZ Logistics
Example 4
Queuing Network
 Precedence constraints as illustrated
 n “servers” are identical
 Service times per stage j UNIFORM[aj,bj]
 Many statistically independent replications of the project to be
completed over time
 Inter-arrival times uniformly distributed between 0 and 7 days
Uniform[0,7]
Start
35E00100 Service Operations and Strategy #4
1
3
a1= 3
b1= 9
n1= 3
a3= 3
b3= 5
n3= 3
2
4
a2= 3
b2= 7
n2= 2
a4= 2
b4= 4
n4= 1
32
End
Aalto/BIZ Logistics
Example 4
Queuing Network
Simulation Setting and Questions
1
3
Start
End
2
4
Simulation for 60,000 days
 First 5,000 days are discarded
 Statistics of the remaining 55,000 days are used as the base case
 This data represents the “steady state” behaviour of the system.
Potential improvements
 One improvement at a time (effect evaluated in isolation)
 If improvement achieved, the whole task time distribution will be
shifted by one day.
Station
1
2
3
4
a'
2
2
2
1
b'
8
6
4
3
mean
5
4
3
2
 Which of the four improvements is the best for improving the
system performance? Why?
35E00100 Service Operations and Strategy #4
33
Aalto/BIZ Logistics
Example 4
Queuing Network
Summary Statistics
1
Start
End
2
Base case
Reduction at
Reduction at
Reduction at
Reduction at
station 1
station 2
station 3
station 4
35E00100 Service Operations and Strategy #4
MTPT
12.8
12.5
12.1
12.3
11.1
3
95% confid.
level
(12.4, 13.2)
(12.1, 12.9)
(11.7, 12.5)
(11.9, 12.7)
(11.0, 11.2)
34
4
Utilization of stations
(0.58, 0.72, 0.38, 0.86)
(0.48, 0.72, 0.38, 0.86)
(0.58, 0.58, 0.38, 0.86)
(0.58, 0.72, 0.29, 0.86)
(0.58, 0.72, 0.38, 0.58)
Aalto/BIZ Logistics
Example 4
Queuing Network
Simulation Results
TPT
0-6
6-8
8-10
10-12
12-14
14-16
16-18
18-20
20-22
22-24
24-100
Base case
0
0,0406
0,2153
0,3228
0,1995
0,0871
0,0504
0,0319
0,0197
0,0135
0,0192
Reduction
at st 1
0,0031
0,0648
0,2491
0,3143
0,1503
0,0839
0,05
0,0318
0,0202
0,0134
0,0191
Reduction
at st 2
0
0,0701
0,2802
0,2932
0,1852
0,0679
0,039
0,0244
0,0155
0,0097
0,0148
Reduction
at st 3
0,0037
0,086
0,2706
0,2773
0,1474
0,0814
0,0494
0,0318
0,0198
0,0134
0,0192
1
3
Start
Reduction
at st 4
0
0,0709
0,3105
0,3746
0,1797
0,043
0,0116
0,0058
0,0018
0,0014
0,0007
End
2
4
Base case
0,4
0,3
0,2
0,1
0
0-6
6-8 8-10 1012
1214
1416
1618
1820
2022
2224
24100
0,4
0,4
Reduction at station 1
0,3
Reduction at station 3
0,3
0,2
0,2
0,1
0,1
0
0
0-6
6-8
8-10
1012
1214
1416
1618
1820
2022
2224
24100
0-6
6-8 8-10 10-12 12-14 14-16 16-18 18-20 20-22 22-24 24100
0,4
Reduction at station 2
0,4
Reduction at station 4
0,3
0,3
0,2
0,2
0,1
0,1
0
0
0-6
6-8
8-10 10-12 12-14 14-16 16-18 18-20 20-22 22-24 24100
35E00100 Service Operations and Strategy #4
0-6
35
6-8
8-10 10-12 12-14 14-16 16-18 18-20 20-22 22-24 24100
Aalto/BIZ Logistics
Single Channel, Multiple Priority
Average waiting time
in queue (CTq )
Service
Arrival rate (ra 
Average number of jobs
in queue (WIPq )
New orders are assigned a
priority upon arrival
35E00100 Service Operations and Strategy #4
Service rate (re 
Decision on the
processing order
36
Aalto/BIZ Logistics
Performance Measures for Multiple
Priority Queuing Model
System utilization
ra 
r
u
ak
ra
mre
Average waiting time in line for units in kth priority class
CTqk
ra

where A 
and Bk  1 
A  Bk 1  Bk
(1  u )WIPq
1
k

c 1
rac
mre
Average waiting time in system for units in kth priority class
CTq  CTqk  te
Average number waiting in line for units in kth priority class
WIPq  rek  CTqk
35E00100 Service Operations and Strategy #4
37
Aalto/BIZ Logistics
Example 5
Multiple Priorities Model
4
4
3
3
3
2
1
1
1
Arriving jobs are assigned a priority and based on it placed into one of
several priority classes. Jobs are then processed by class, highest class
first. Within each class, on FCFS basis. Non-preemptive system assumed.
A machine shop handles tool repairs in a large company. As each job arrives
in the shop, it is assigned a priority based on urgency of the need for that
tool.
Requests for repair can be described by a Poisson distribution. Arrival rates
are: ra1 = 2 per hour, ra2 = 2 per hour , and ra3 = 1 per hour. The service rate
is one tool per hour for each server, and there are six servers in the shop.
Determine:
 System utilization
 The average time a tool in each of the priority classes will wait for service
 The average time spends in the system for each priority class
 The average number of tools waiting for repair in each class
35E00100 Service Operations and Strategy #4
38
Aalto/BIZ Logistics
Example 5
3
2
1
1
Multiple Priorities Model
ra =  rak = ra1 + ra2 + ra3 = 5 per hr
re = 1 job per hr
3
3
3
m = 6 servers
2
1
1
1
1
System utilization u = 5 / 6*1 = 0.833
Average waiting times per each priority class
 For ra  5 and m=6, WIPq=2.938 (given)
A
ra
5

 10.19
(1  u )WIPq (1  0.833) 2.938
rac
1
c 1 mr e
k
B0  1  
B1  1 
2
 0.667
6 *1
B2  1 
22
 0.333
6 *1
B3  1 
2  2 1
 0.167
6 *1
35E00100 Service Operations and Strategy #4
1
1

 0.147hr
A  B0  B1 10.19(1)(0.667)
1
1
CT2 

 0.442hr
A  B1  B2 10.19(0.667)(0.333)
1
1
CT3 

 1.765hrs
A  B2  B3 10.19(0.333)(0.167)
CT1 
Average time in system = CTq+ 1/re = CTqk+ 1
39
Aalto/BIZ Logistics
Example 5
3
2
1
Multiple Priorities Model
1
1
Average times in the system per each priority class
 Average time in system = CTqk+ 1/ re = CTqk+ 1
Class
1
2
3
CTqk
CT (hrs)
0.147
0.442
1.765
1.147
1.442
2.765
Average number of units waiting in each priority class
 WIPqk= rak * CTk
Class
1
2
3
35E00100 Service Operations and Strategy #4
rak*CTk
WIPqk (units)
2(0.147)
2(0.442)
1(1.765)
0.294
0.884
1.765
40
Aalto/BIZ Logistics
Example 6
Priority Queuing Network
Process and Resources
 Two processing resources
 Six kinds of tasks each with own processing time distribution
 All distributions exponential
Deterministic arrival
of type A jobs: one
every 4.5 hrs
Station 1
Station 2
MPT 2.0
MPT 1.9 MPT 0.1
MPT 0.1 MPT 1.9 MPT 2.0
Deterministic
arrival of type B
jobs: one every
5.0 hrs
35E00100 Service Operations and Strategy #4
41
Aalto/BIZ Logistics
Example 6
Priority Queuing Network
Simulation and Questions
Simulation for 120,000 hrs
MPT
2.0
MPT
1.9
MPT
0.1
MPT
0.1
MPT
1.9
MPT
2.0
 First 20,000 hours discarded
 The statistics of the remaining 100,000 hours = Base case
 The data represents the “steady state” behavior of the system
Disciplines tested
1: FCFS
2: Type B jobs are given priority at station 1, and type A jobs are
prioritized at station 2, otherwise FCFS applied
3: Type B jobs are given priority at station 1, and type A jobs are
prioritized at station 2, otherwise second priority at each station
given to jobs which are waiting for their final operation (otherwise
processed on FCFS basis)
Questions
 What is the long run utilization rate?
 Can any principles of network scheduling be deduced from the
summary statistics?
35E00100 Service Operations and Strategy #4
42
Aalto/BIZ Logistics
Example 6
Priority Queuing Network
Simulation Results
MPT
2.0
MPT
1.9
MPT
0.1
MPT
0.1
MPT
1.9
MPT
2.0
0,3
FCFS
0,25
0,2
A-FCFS
0,15
B-FCFS
0,1
0,05
0
0-3
3-6
6-9 9-12 1215
MTPT of A
FCFS
Priority 1
Priority 2
19.1
15.7
14.6
35E00100 Service Operations and Strategy #4
1518
1821
2124
2427
95% Conf
MTPT of B
Interv
(18.9, 19.2)
17.0
(14.0, 16.9)
11.2
(14.5, 14.7)
10.8
2730
3033
3336
95% Conf
Interv
(16.9, 17.1)
(11.1, 11.3)
(10.7, 10.9)
43
3639
3942
4245
45100
Utilization of
Stations
(0.887, 0.807)
(0.887, 0.807)
(0.887, 0.807)
Aalto/BIZ Logistics
Example 6
Priority Queuing Network
Simulation Results
MPT
2.0
MPT
1.9
MPT
0.1
MPT
0.1
MPT
1.9
MPT
2.0
0,3
Priority 1
0,25
0,2
A-Priority 1
0,15
B-Priority 1
0,1
0,05
0
0,3
0-3
3-6
6-9 9-12 1215
1518
0,25
1821
2124
2427
Priority 2
2730
3033
3336
3639
3942
0,2
A-Priority 2
0,15
B-Priority 2
4245
45100
0,1
0,05
0
0-3
3-6
6-9 9-12 12-
35E00100 Service Operations and Strategy #4
15-
18-
21-
24-
27- 3044
33-
36-
39-
42-
45Aalto/BIZ Logistics
Key Points
Cost trade-offs include the cost of waiting, lost sales, and
cost of capacity.
The VUT equation considers the impact of variability and
utilization on system performance.
 High variability lead to long queues and long waits.
 Reduction in throughput reduces waiting.
 Reducing variability improves performance.
 Pooling servers improves performance.
Different types of systems exists
 A variety of models is needed in practice.
 Simple ones easy to solve; simulation can be used to gain
insights in more complex ones.
35E00100 Service Operations and Strategy #4
45
Aalto/BIZ Logistics
Queuing Notation and Measures
ra
ta
re
u
te
m
WIP
WIPq
CT
CTq
p0
pn
b
ca 2
ce 2
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
arrival rate
mean inter-arrival time (=1/ ra)
mean service rate for a single server (=m/ te)
system utilization (=ra / mre)
mean process time (1/re)
the number of parallel machines in the system
average number of jobs in the system (incl. those being served; steady state)
average number of jobs in the queue (steady state)
average time spent in the system (including service; steady state)
average time spent in the queue (steady state)
the probability that there are no jobs in the system
the probability that there are n jobs in the system
buffer size e.g. between machines2

SCV of the inter-arrival time ca2  2a
2
t
SCV of the effective process time a ce2   e
te2
SCV = squared coefficient of variation
MPT = mean processing time
MTPT = mean throughput time
35E00100 Service Operations and Strategy #4
46
Hopp and Spearman 2000, 265
Aalto/BIZ Logistics