Transcript Document

5. MONTE CARLO BASED CPM
Objective:
To understand how to apply the Monte Carlo based
CPM method to planning construction projects that
are subject to uncertainty:
Summary:
Part I: General Principles
5.1 Introduction
5.2 Monte Carlo Sampling
5.3 Application to a Construction Problem
1
Part II: P3 Monte Carlo Related Issues
5.4 The Use of Lead and Lag Times
5.5 Total Float Calculations
5.6 Probabilistic & Conditional Activity
Branches
5.7 Duration Distribution Types
5.8 Correlated Activity Durations
2
Part I: General Principles
5.1 INTRODUCTION
• Monte Carlo is a statistical method that allows a
sample of possible project outcomes to be made.
• The probability of sampling an outcome is equal to
the probability of it occurring in the actual project.
• Some characteristics:
– its accuracy increases with the number of samples made;
– it is computationally expensive, but well within the
capabilities of today’s desktop computers;
– the method is very flexible, allowing many real-world
factors to be included in the analysis.
3
• It is used in similar situations to PERT:
– when there is a lot of uncertainty about activity
durations;
– when there is a lot to be lost by finishing late (or by
missing out on large bonuses for early completion).
• Its advantages over PERT are:
– much more accurate;
– much more flexible:
• measures variance on floats (as well as project duration);
• measures probability of alternative paths becoming critical;
• can be extended to take account of correlation between the
durations of different activities;
• can be extended to allow for exclusive activity branching.
4
5.2 MONTE CARLO SAMPLING
• For each cycle through a Monte Carlo analysis, we
need to randomly select a duration for every activity.
• The probability of selecting a duration should match
the likelihood of its occurrence on site:
Observed Frequency
on Site
most likely
duration T = 27 days
7
6
5
4
3
2
1
0
Observations from similar
past activities can be plotted
on a frequency chart
20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 Activity duration
Fig. 5-1: Observed Frequency Distribution
5
• The frequency distribution can be converted
(automatically by the computer) into a probability
density function (to give a continuous distribution):
– not necessary, but can give more accurate results for
larger numbers of observations.
Frequency
Distribution
7
6
5
4
3
2
1
0
Probability Density
Function (pdf)
For example, if the distribution
approximates a Normal distribution,
then can calculate:
sample mean: X   d
n
sample standard
2
deviation:

X d

S
n or n  1
20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 Activity duration
Fig. 5-2: Converting a Frequency Distribution to a PDF
6
A good method of sampling from a frequency
distribution, or a probability density function, is the
inverse transform method (ITM) (automatic by computer).
STEP 1: convert the frequency distribution to its cumulative frequency
distribution:
Frequency
Distribution
9
8
7
6
5
4
3
2
1
0
Cumulative Frequency
Distribution
CFD   FD
23 24 25 26 27 28 29
Activity duration
9
8
7
6
5
4
3
2
1
0
Total = 8 observations
23 24 25 26 27 28 29
Activity duration
Fig. 5-3: Converting to the Cumulative Distribution
(a) frequency to cumulative frequency distribution
7
If dealing with a probability density function then convert it to its
cumulative probability function:
Probability
Density Function
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0.0
Probability of
completing within
26 days = shaded
area = 0.65
Cumulative Probability
Function
CPF   PDF
1.0
0.5
Probability of
completing within
26 days = height
= 0.65
0
23 24 25 26 27 28 29
Activity duration
23 24 25 26 27 28 29
Activity duration
Fig. 5-3: Converting to the Cumulative Distribution
(b) probability density to cumulative probability function
8
STEP 2:
• generate a uniformly distributed random number between 0.0 and 1.0;
• multiply it by the number of observations;
• go to the multiplied number on the vertical axis;
• read across until you hit a cumulative distribution bar and select the
corresponding duration
PDF
Cumulative Frequency
Distribution
* 1.0
0.0
Uniform Distribution
r = 0.81
R = 0.81 * 8 = 6.48
Selected Activity
Duration = 27 days
9
8
7
6
5
4
3
2
1
0
23 24 25 26 27 28 29
Activity duration
Fig. 5-4: Selecting a Duration from the Cumulative Distribution9
It can be seen that the probability of selecting a duration in this way is
proportional to the length of the left-side exposed face of its bar. Eg:
– the bar for a duration of 25 days has 2 blocks exposed;
– the bar for a duration of 26 days has 3 blocks exposed;
– the bar for 28 days has 0 blocks exposed;
and the number of exposed blocks corresponds to the number of site
observations made at that duration (see the left side of Fig 5-3 (a)).
Cumulative Frequency
Distribution
0 exposed blocks
for 28 days
3 exposed blocks
for 26 days
2 exposed blocks
for 25 days
9
8
7
6
5
4
3
2
1
0
23 24 25 26 27 28 29
Activity duration
Fig. 5-5: Probability of Selecting an Activity Duration
10
5.3 APPLICATION TO A
CONSTRUCTION PROBLEM
The following will perform 6 Monte Carlo cycles on a very
simple project:
11
Cycle 1:
cf
2
1
0
0
0
d
5 8
0
act ‘A’
8
8
0
8
8
0
8
8
1
9
act ‘A’
cycle
n
d
1
8
2
3
4
5
6
5
5
8
5
8
0
act ‘B’
11
1
act ‘C’
10
Activity ‘A’
19
0
19
18
1
19
cf
cf
4
3
2
1
19
dummy
19
4
3
2
1
d
9 11 13
5 10 15
act ‘B’
d
act ‘C’
Activity ‘B’
Activity ‘C’
ES EF LS LF TF FF IF
0 8 0 8
0 0 0
d ES EF LS LF TF FF IF
11 8 19 8 19 0 0 0
d ES EF LS LF TF FF IF
10 8 18 9 19 1 1 1
0
0
0
0
0
13
11
9
11
11
15
5
15
5
5
5
5
8
5
8
Mean TF = 0
Mean IF = 0
0
0
0
0
0
5
5
8
5
8
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
5
5
8
5
8
18
16
17
16
19
7 20 2
5 16 0
14 23 6
5 16 0
8 19 0
2
0
6
0
0
2
0
6
0
0
5
5
8
5
8
20
10
23
10
13
5
11
8
11
14
20 0
16 6
23 0
16 6
19 6
0
6
0
6
6
0
6
0
6
6
Mean FF = 0
Mean TF = 1.33 Mean FF = 1.33
Mean TF = 3.17 Mean FF = 3.17
Critical Index = 1.0 Mean IF = 1.33 Critical Index = 0.67 Mean IF = 3.17 Critical Index = 0.33
Fig. 5-6: Example of Monte Carlo CPM Process
12
Sampled Frequency
Distribution
Need More Samples
(cycles)
2
1
0
16 17 18 19 20 21 22 23
Project duration
Mean Project Duration = X  n = 18.8 days
d
 X  d 
2
Standard Deviation on Duration =
S
n  1
= 2.64 days
Variance on Duration = 6.98 days
Fig. 5-7: Analysis of Results from Monte Carlo CPM
Questions:
1. What is the deterministic project duration?
A: 6.50 (act A) + 11.25 (act C) = 17.75 days (note, this is less than the mean project
duration according to the Monte Carlo analysis)
2.
What is the probability of completing within the deterministic duration
(17.75 days)? A: z  17.75  18.8  0.4 p = 34.5 % (much less than 50%)
6.98
3.
What is the probability of activity ‘B’ having <=5 days float?
13
(use the observed frequencies as not a Normal distribution) A: p = 5/6 = 83.3%
Part II: P3 Monte Carlo Related Issues
5.4 THE USE OF LEAD AND LAG TIMES
• P3 Monte Carlo interprets negative delays on links
(negative lags in P3 terminology) as zero lag:
– so how can we represent situations requiring negative delays?
– first of all, we will review what we mean by negative delays,
then we will explore possible solutions.
14
PRECEDENCE DIAGRAM
BAR CHART
Earliest B can start is
5 days after end of A
Example:
delay is for
cure concrete.
dA
act A
act A
+5 days
dA
5 days
act B
act B
dB
dB
(a) simple delay
Example:
Until the last 5 days of
A, both activities
need same space.
act A
dA
-5 days
Note:
negative delay
Earliest B can start is
5 days before end of A
dA
act A
-5 days
act B
act B
dB
dB
(b) negative delay
Fig. 5-8: Dealing with Delays
15
• Can we get around the problem by:
– reversing the direction of the activity link, and then
using a positive delay?
16
PRECEDENCE DIAGRAM
BAR CHART
dA
Earliest B can start is
5 days before end of A
act A
act A
dA
-5 days
- 5 days
act B
dB
act B
dB
Are these
equivalent ?
act A
NO !
dA
dA
+ 5 days
act B
dB
act A
Example:
A is dry walling and B
is inspection of
to be hidden columns.
Latest B can start is
5 days before end of A
-5 days
act B
dB
Fig. 5-9: Reversing the Direction of the Activity Link
17
• Can we get around the problem by:
– using a positive delay from the start of the
activity?
18
PRECEDENCE DIAGRAM
BAR CHART
dA
Earliest B can start is
5 days before end of A
act A
act A
dA
-5 days
- 5 days
act B
dB
act B
dB
Are these
equivalent ?
act A
Only if
dA is fixed !
dA
dA
Earliest B can start is
5 days before end of A
act A
(dA-5) days
act B
dB
Using
Monte Carlo
dA changes !
(dA-5)
days
act B
dB
Fig. 5-10: Measuring the Delay from the Start of the Activity Link
19
• For example, if dA is expected to last
14 days:
act A
dA
(dA-5) days
act B
dB
– then the delay from start of activity A
to start of B = 14 - 5 = 9 days;
– this must be specified before all the
Monte Carlo cycles start (it cannot
change from cycle to cycle).
• but in Monte Carlo, the duration is
variable from cycle to cycle:
– thus, if in one Monte Carlo analysis,
activity A was 12 days, then the 9 day
delay would allow B to start just 3
days before the end of A !!!
20
PRECEDENCE DIAGRAM
BAR CHART
dA
Earliest B can start is
5 days before end of A
act A
act A
dA
-5 days
- 5 days
act B
dB
act B
dB
Are these
equivalent ?
dA
Earliest B can start is
5 days before end of A
act A
act A
dA
Yes! as long as
dummy cannot be
delayed
dummy
dummy:
5
act B
5
dB
act B
dB
Fig. 5-11: Introducing a Dummy Activity with F-F and S-S Links
21
5.5 TOTAL FLOAT CALCULATIONS
• P3 Monte Carlo provides several choices for
calculating Total Float:
–
–
–
–
Finish Total Float;
Start Total Float;
Critical Total Float; and
Interruptible Total Float.
• For most activities, these different types of Total
Float will have the same value.
• Differences occur when there are links from the
start of an activity, or to the finish of an activity.
• What do the different types of Total Float
represent, and when should we use each one?22
PRECEDENCE DIAGRAM
0
BAR CHART
Standard TF =
22 - 0 - 5 = 17
10
act ‘A’
act ‘A’
0
10
P3: Start TF = 0
0
22
Standard TF includes
necessary interruptions to
the activity (and Finish TF) = 17
P3: Finish TF =
22 - 10 = 12
0
10
act ‘B’
act ‘B’
0
0
5
P3: Finish TF = 12
8
22
P3: Start TF =
0-0=0
20
30
act ‘C’
20
20
10
30
Note, activity B must
be interrupted 5 days.
It cannot start after 0, and
cannot finish before 10,
yet it only has 5 days of work
act ‘C’
Fig. 5-12: Graphical Interpretation of Different Types of Total Float
23
• Critical Total Float is defined as:
smallest of Start Total Float and Finish Total Float
– use Start TF when concerned about allowable delays to the
start of the activity;
– use Finish TF when concerned about allowable delays to
the finish of the activity;
– use Critical TF when concerned about the worst case for
the activity;
• Interruptible Total Float is defined as:
Finish Total Float with:
late start time = early start time + Total Float.
• The Standard Total Float is not available in P3
MC, but it tells us:
– the sum of all allowable delays on the activity,
including those resulting from forced interruptions
24
(necessary to ensure the logic of the network).
5.6 PROBABILISTIC AND CONDITIONAL
ACTIVITY BRANCHES
• P3 Monte Carlo provides decision branches:
– points in a network where alternative sequences of
activities can be performed;
– two types:
• probabilistic - where the choice of branch is random;
• conditional - where the choice of branch is dependent on
whether a task has started (or finished).
25
fail: p = 5%
inspect HVAC
equipment
make-good
installation
fail
or pass
?
next task…
pass: p = 95%
(a) probabilistic (random)
no
position steel
in found exc.
activity ‘X’
(uses crane)
use concrete
pumps
act ‘X’
finished
?
yes
use crane
to convey
conc to found
(b) conditional
Fig. 5-13: Decision Branches in a Network
26
outcome ‘a’
act ‘A’
decision
node
act ‘A’
decision
node
x
outcome ‘b’
act ‘B’
outcome ‘a’
act ‘B’
not allowed
(a) decision node must be only predecessor
outcome ‘b’
act ‘B’
x
A specified actual
start time.
not allowed
(b) no actual start times for branch activities
outcome ‘a’
act ‘A’
decision
node
Fig. 5-14: Decision Branch Rules
outcome ‘b’
not allowed
act ‘B’
x
(b) no SS and SF links from branch activities
27
pass: p = 80%
inspect HVAC
equipment
pass
/fail
?
fail: p = 20%
act ‘B’
minor problems: p = 75%
act ‘B’
major
/minor
?
major problems: p = 25%
act ‘B’
combined probability
of major installation
problems is:
20% x 25% = 5%
Fig. 5-15: Multiple Decisions (Trees)
28
5.7 DISTRIBUTION TYPES
• P3 Monte Carlo provides 4 basic types of
activity duration distribution:
–
–
–
–
Triangular;
Modified Triangular;
Poisson;
Custom.
29
probability
probability
most likely
Anything sampled within
the end X & Y percentiles are
read as the limit (thus
most likely
creating a spike at each end).
pessimistic
pessimistic
X%
Y%
act duration
optimistic
act duration
optimistic
(a) Triangular Distribution
A discrete
distribution
probability
(b) Modified Triangular Distribution
probability
Define the durations that
can occur and their
respective probabilities
S=?
P=?
act duration
(c) Poisson Distribution
act duration
(d) Custom
Fig. 5-16: Activity Distribution Types in P3 MC
30
5.8 CORRELATED ACTIVITY
DURATIONS
• P3 Monte Carlo allows activity durations to be
either completely correlated or completely
uncorrelated:
– Uncorrelated:
• the duration of activity ’A’ has no relationship to the duration of
activity ‘B’;
– Correlated:
• the duration of activity ’A’ is either dependent on the duration of
activity ‘B’ or is dependent on something else that ‘B’ is also
dependent on.
31
duration B
duration B
duration of
A is a linear
function of
duration of B
y
x
y
x
duration A
(a) Linear Perfect Correlation
duration of
A is a nonlinear
function of
duration of B
duration A
(b) Non-Linear Perfect Correlation
duration B
duration B
as duration of
A increases,
duration of B
decreases
y
x
duration A
(c) Linear Perfect Negative Correlation
duration of
A is partially
correlated to
duration of B
range
of possible
values of y
for a given x
x
duration A
(d) Partially Correlated
Fig. 5-17: Types of Correlation Between Two Activity Durations 32
cumulative pdf
cumulative pdf
• P3 Monte Carlo correlates two activity durations
by using the same random number to generate
their durations:
Same random
number for
both activities
Fig. 5-18: Types of Correlation Between Two Activity Durations33
act A
prob
act B
prob
10 20
duration A
20 30
duration B
act A
act B
prob
prob
10 20
duration A
20 30
duration B
UnCorrelated
Correlated
10+30=40
prob 10+20=30
20+30=50
p=0.5
prob 10+20=30
20+30=50
20+20=40
p=0.5
30
50
project duration
(a) sequential, correlated activities
40
30
50
project duration
(b) sequential, uncorrelated activities
Fig. 5-19: Impact of Correlated Activity Durations on Project Duration
34