Lecture Day 8
Project Scheduling
Stochastic PERT
Critical Path Method
Stochastic PERT
For most projects, activity times are random
variables. If these random times take on
values significantly different from those point
estimates used in the PERT analysis, the output
from PERT is rendered invalid.
To compensate for the lack of certainty in many
the time estimates, the project manager is often
asked to give three subjective time estimates
for each activity, to wit:
ai = most optimistic time required for activity i
mi = most likely time required for activity i
bi = most pessimistic time required for activity i
The three time estimates are used to define a
probability distribution of time for each activity.
of
The distribution used in analyzing stochastic
PERT is the beta distribution. Such pattern has
three properties that make it the logical choice:
1. It is a continuous probability distribution;
2. It is unimodal and not necessarily
symmetrical; and
3. It has a bounded range of values.
. . .
ai mi
bi
The mean of the distribution, the expected time for
an activity, is estimated using the following function:
ti = ai + 4mi + bi
6
where: ti = the expected time for activity i
The standard deviation of the beta distribution can be
approximated using:
si = bi ai
6
The reason for calculating the standard deviation is to
provide a means of computing the probability of
completing the project on or before the scheduled
completion date.
Example:
Activity
Immediate
Predecessor
ai
mi
bi
ti
si
A
B
C
D
E
F
A
A
B, C, F
E
1
1
3
3
2
2
3
4
5
7
3
6
5
5
7
12
4
9
3.00
3.67
5.00
7.17
3.00
5.83
0.67
0.67
0.67
1.50
0.33
1.17
Step 1: Estimate the expected time and
standard deviation for each activity
Example:
Activity
Immediate
Predecessor
ai
mi
bi
ti
si
A
B
C
D
E
F
A
A
B, C, F
E
1
1
3
3
2
2
3
4
5
7
3
6
5
5
7
12
4
9
3.00
3.67
5.00
7.17
3.00
5.83
0.67
0.67
0.67
1.50
0.33
1.17
Step 2: Find the critical path by the PERT algorithm
using the expected activity time (ti)
D = 7.17
D = 7.17
D = 7.17
Example:
Activity
Immediate
Predecessor
ai
mi
bi
ti
si
si2
A
B
C
D
E
F
A
A
B, C, F
E
1
1
3
3
2
2
3
4
5
7
3
6
5
5
7
12
4
9
3.00
3.67
5.00
7.17
3.00
5.83
0.67
0.67
0.67
1.50
0.33
1.17
0.44
0.44
0.44
2.25
0.11
1.36
Step 3: Determine the probability of completing the
expected critical path within a given length
of time by first calculating the variance (si2)
for each activitys time.
Example:
Activity
Immediate
Predecessor
ai
mi
bi
ti
si
si2
A
B
C
D
E
F
A
A
B, C, F
E
1
1
3
3
2
2
3
4
5
7
3
6
5
5
7
12
4
9
3.00
3.67
5.00
7.17
3.00
5.83
0.67
0.67
0.67
1.50
0.33
1.17
0.44
0.44
0.44
2.25
0.11
1.36
Step 4: Determine the variance of the critical path.
If we assume that the activities on a given path
are independent (that is, that the duration of
one task has no effect on the length of time
necessary to complete another task), then the
variance related to an entire paths length is
the sum of the variances of the individual
activities on that path.
Example:
Activity
Immediate
Predecessor
ai
mi
bi
ti
si
si2
A
B
C
D
E
F
A
A
B, C, F
E
1
1
3
3
2
2
3
4
5
7
3
6
5
5
7
12
4
9
3.00
3.67
5.00
7.17
3.00
5.83
0.67
0.67
0.67
1.50
0.33
1.17
0.44
0.44
0.44
2.25
0.11
1.36
Step 4: Determine the variance of the critical path.
EFD2 = 0.11 + 1.36 + 2.25 = 3.72
If there are many activities on a given path, the
distribution of the total time of the path is often
assumed to be normally distributed.
To estimate the probability of completing a path
within a certain length of time, the mean and
variance of a normally distributed random
variable (path length) are needed.
To compute for this probability, it is necessary
to transform the normal distribution into the
standard normal with a mean of 0 and a
standard deviation of 1. This is done by using
the following transformation:
Z = (x m)
s
where:
m = mean of the non-standard normal
s = std. deviation of the non-standard normal
x = non-standardized normal variate
Z = (x m)
s
ZEFD = 17
D = 7.17
Z = (x m)
s
ZEFD = 17 - 16
Example:
Activity
Immediate
Predecessor
ai
mi
bi
ti
si
si2
A
B
C
D
E
F
A
A
B, C, F
E
1
1
3
3
2
2
3
4
5
7
3
6
5
5
7
12
4
9
3.00
3.67
5.00
7.17
3.00
5.83
0.67
0.67
0.67
1.50
0.33
1.17
0.44
0.44
0.44
2.25
0.11
1.36
Step 4: Determine the variance of the critical path.
EFD2 = 0.11 + 1.36 + 2.25 = 3.72
Z = (x m)
s
ZEFD = 17 - 16
1.928730152
ZEFD = 0.5184758474
Pr (ZEFD < 0.52) =
EFD2 = 3.72
EFD = 1.928730152
Standard Normal Distribution Table
Z = (x m)
s
ZEFD = 17 - 16
1.928730152
EFD2 = 3.72
EFD = 1.928730152
ZEFD = 0.5184758474
Pr (ZEFD < 0.52) = 0.6985 = 69.85%
D = 7.17
Z = (x m)
s
ZEFD = 17 - 16
1.928730152
EFD2 = 3.72
EFD = 1.928730152
ZEFD = 0.5184758474
Pr (ZEFD < 0.52) = 0.6985 = 69.85%
ZABD = 17 -
D = 7.17
Z = (x m)
s
ZEFD = 17 - 16
1.928730152
EFD2 = 3.72
EFD = 1.928730152
ZEFD = 0.5184758474
Pr (ZEFD < 0.52) = 0.6985 = 69.85%
ZABD = 17 - 13.84
Activity
Immediate
Predecessor
ai
mi
bi
ti
si
si2
A
B
C
D
E
F
A
A
B, C, F
E
1
1
3
3
2
2
3
4
5
7
3
6
5
5
7
12
4
9
3.00
3.67
5.00
7.17
3.00
5.83
0.67
0.67
0.67
1.50
0.33
1.17
0.44
0.44
0.44
2.25
0.11
1.36
Z = (x m)
s
ZEFD = 17 - 16
1.928730152
EFD2 = 3.72
EFD = 1.928730152
ZEFD = 0.5184758474
Pr (ZEFD < 0.52) = 0.6985 = 69.85%
ZABD = 17 - 13.84
1.769180601
ZABD = 1.786137604
Pr (ZABD < 1.79) =
ABD2 = 3.13
ABD = 1.769180601
Standard Normal Distribution Table
Z = (x m)
s
ZEFD = 17 - 16
1.928730152
EFD2 = 3.72
EFD = 1.928730152
ZEFD = 0.5184758474
Pr (ZEFD < 0.52) = 0.6985 = 69.85%
ABD2 = 3.13
ZABD = 17 - 13.84
1.769180601
ABD = 1.769180601
ZABD = 1.786137604
Pr (ZABD < 1.79) = 0.9633 = 96.33%
ZACD = 17 -
D = 7.17
Z = (x m)
s
ZEFD = 17 - 16
1.928730152
EFD2 = 3.72
EFD = 1.928730152
ZEFD = 0.5184758474
Pr (ZEFD < 0.52) = 0.6985 = 69.85%
ABD2 = 3.13
ZABD = 17 - 13.84
1.769180601
ABD = 1.769180601
ZABD = 1.786137604
Pr (ZABD < 1.79) = 0.9633 = 96.33%
ZACD = 17 - 15.17
1.769180601
Activity
Immediate
Predecessor
ai
mi
bi
ti
si
si2
A
B
C
D
E
F
A
A
B, C, F
E
1
1
3
3
2
2
3
4
5
7
3
6
5
5
7
12
4
9
3.00
3.67
5.00
7.17
3.00
5.83
0.67
0.67
0.67
1.50
0.33
1.17
0.44
0.44
0.44
2.25
0.11
1.36
Z = (x m)
s
ZEFD = 17 - 16
1.928730152
EFD2 = 3.72
EFD = 1.928730152
ZEFD = 0.5184758474
Pr (ZEFD < 0.52) = 0.6985 = 69.85%
ABD2 = 3.13
ZABD = 17 - 13.84
1.769180601
ABD = 1.769180601
ZABD = 1.786137604
Pr (ZABD < 1.79) = 0.9633 = 96.33%
ZACD = 17 - 15.17
1.769180601
ZACD = 1.034377157
Pr (ZACD < 1.03) =
Standard Normal Distribution Table
Z = (x m)
s
ZEFD = 17 - 16
1.928730152
EFD2 = 3.72
EFD = 1.928730152
ZEFD = 0.5184758474
Pr (ZEFD < 0.52) = 0.6985 = 69.85%
ABD2 = 3.13
ZABD = 17 - 13.84
1.769180601
ABD = 1.769180601
ZABD = 1.786137604
Pr (ZABD < 1.79) = 0.9633 = 96.33%
ZACD = 17 - 15.17
1.769180601
ZACD = 1.034377157
Pr (ZACD < 1.03) = 0.8485
= 84.85%
If independence of paths can be assumed, the
probability of finishing a project at a particular
duration is the product of the probabilities of
each path in the PERT diagram.
If independence of paths cannot be assumed,
the probability of finishing a project at a
particular duration is the least among the
probabilities of each path in the PERT diagram.
D = 7.17
Z = (x m)
s
ZEFD = 17 - 16
1.928730152
EFD2 = 3.72
EFD = 1.928730152
ZEFD = 0.5184758474
Pr (ZEFD < 0.52) = 0.6985 = 69.85%
ABD2 = 3.13
ZABD = 17 - 13.84
1.769180601
ABD = 1.769180601
ZABD = 1.786137604
Pr (ZABD < 1.79) = 0.9633 = 96.33%
ZACD = 17 - 15.17
1.769180601
ZACD = 1.034377157
Pr (ZACD < 1.03) = 0.8485
= 84.85%
Critical Path Method
(CPM)
Evaluating Time-Cost Trade-Offs
CPM is a variation of PERT that introduces
cost as a companion factor to time for
project evaluation.
The combined PERT and CPM techniques
are used to make decisions concerning
how best to shorten a projects completion
time. A project manager often has the
prerogative of increasing resource
allocation to specific tasks so that the
project can be finished at an earlier date.
Example:
Activity
A
B
C
D
E
F
Immediate Normal Time Crash Time Incremental
Cost
Predecessor Estimate
Estimate of Crash Time
3
2
P150
A
4
3.5
100
A
5
4
200
B, C, F
7
5
300
3
3
E
6
5
75
Crash time refers to how much time
the normal time estimate can be
reduced.
Steps
Involved:
1. Determine the
projects critical
path, based on
the normal time
estimate, using
PERT.
Activity Immediate Normal Time Crash Time
Predecessor Estimate
Estimate
A
3
2
B
A
4
3.5
C
A
5
4
D
B, C, F
7
5
E
3
3
F
E
6
5
Incremental Cost
of Crash Time
D=7
P150
100
200
300
75
Steps
Involved:
D=7
2. Plot all possible
paths on a time
line.
ABD
A=3
ACD
A=3
EFD
E=3
B=4
C=5
F=6
D=7
D=7
D=7
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Steps
Involved:
3. Consider only
the activities on the
critical path when
crashing.
4. Shorten the critical
path until it
coincides with
another paths
duration.
5. Stop when the
critical path can
no longer be
shortened.
Activity Immediate Normal Time Crash Time
Predecessor Estimate
Estimate
A
3
2
B
A
4
3.5
C
A
5
4
D
B, C, F
7
5
E
3
3
F
E
6
5
ABD
A=3
ACD
A=3
EFD
E=3
B=4
Incremental Cost
of Crash Time
P150
100
200
300
75
D=7
C=5
D=7
F=6
D=7
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Activity
Crashed
By How
Much
Cost
1 day
P 75
Steps
Involved:
3. Consider only
the activities on the
critical path when
crashing.
4. Shorten the critical
path until it
coincides with
another paths
duration.
5. Stop when the
critical path can
no longer be
shortened.
Activity Immediate Normal Time Crash Time
Predecessor Estimate
Estimate
A
3
2
B
A
4
3.5
C
A
5
4
D
B, C, F
7
5
E
3
3
F
E
6
5
ABD
A=3
B=4
ACD
A=3
C=5
D=7
EFD
E=3
F=5
D=7
Incremental Cost
of Crash Time
P150
100
200
300
75
D=7
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Activity
Crashed
By How
Much
Cost
F
D
1 day
2 days
P 75
300
Steps
Involved:
3. Consider only
the activities on the
critical path when
crashing.
4. Shorten the critical
path until it
coincides with
another paths
duration.
5. Stop when the
critical path can
no longer be
shortened.
Activity Immediate Normal Time Crash Time
Predecessor Estimate
Estimate
A
3
2
B
A
4
3.5
C
A
5
4
D
B, C, F
7
5
E
3
3
F
E
6
5
ABD
A=3
B=4
ACD
A=3
C=5
D=5
EFD
E=3
F=5
D=5
Incremental Cost
of Crash Time
P150
100
200
300
75
D=5
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Activity
Crashed
By How
Much
Cost
F
D
1 day
2 days
P 75
300
3 days
P 375
Total
Steps
Involved:
3. Consider only
the activities on the
critical path when
crashing.
4. Shorten the critical
path until it
coincides with
another paths
duration.
5. Stop when the
critical path can
no longer be
shortened.
Activity Immediate Normal Time Crash Time
Predecessor Estimate
Estimate
A
3
2
B
A
4
3.5
C
A
5
4
D
B, C, F
5
5
E
3
3
F
E
5
5
G
F
6
4
ABD
A=3
B=4
ACD
A=3
C=5
EFG
E=3
F=5
Incremental Cost
of Crash Time
P150
100
200
300
D=5
D=5
G=6
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Activity
Crashed
By How
Much
Cost
1 day
P 150
Steps
Involved:
3. Consider only
the activities on the
critical path when
crashing.
4. Shorten the critical
path until it
coincides with
another paths
duration.
5. Stop when the
critical path can
no longer be
shortened.
Activity Immediate Normal Time Crash Time
Predecessor Estimate
Estimate
A
3
2
B
A
4
3.5
C
A
5
4
D
B, C, F
5
5
E
3
3
F
E
5
5
G
F
6
4
ABD
A=3
B=4
ACD
A=3
C=5
D=5
EFG
E=3
F=5
G=5
Incremental Cost
of Crash Time
P150
100
200
300
D=5
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Activity
Crashed
By How
Much
Cost
1 day
P 150
End of Lecture Day 8