Transcript BA 560 Management of Information System

PERT
Program Evaluation and Review Technique
Estimation of Task Times
In CPM, we assume that the task durations
are known with certainty.
This may not be realistic in many project
settings.
 How long does it take to design a switch?
 PERT tries to account for the uncertainty in
task durations.
Key question: What is the probability of
completing project by given deadline?
PERT
SEEM 3530
2
CPM vs. PERT
CPM (critical path method)
PERT (program evaluation and review
technique)
Both approaches work on a project network,
which graphically portrays the activities of the
project and their relationships.
 CPM assumes that activity times are
deterministic, while PERT views the time to
complete a task as a random variable.
PERT
SEEM 3530
3
Estimation of the duration of project
activities
(1) The deterministic approach (CPM), which
ignores uncertainty thus results in a point
estimate (e.g. The duration of task 1 = 23
hours, etc.)
(2) The stochastic approach (PERT), which
considers the uncertain nature of project
activities by estimating the expected duration
of each activity and its corresponding variance.
To analyse the past data to construct the
probabilistic distribution of a task.
PERT
SEEM 3530
4
Estimation of the activity duration
Example: An activity was performed 40 times
in the past, requiring a time between 10 to 70
hours. The figure below shows the frequency
distribution.
PERT
SEEM 3530
5
Estimation of the activity duration
The probability distribution of the
activity is approximated by a probability
frequency distribution.
PERT
SEEM 3530
6
Estimation of the activity duration
In project scheduling, we usually use a
beta distribution to represent the time
needed for each activity.
PERT
SEEM 3530
7
Estimation of the activity duration
 Three key values we use in the time estimate
for each activity:
a = optimistic time, which means that there is little
chance that the activity can be completed before
this time;
m = most likely time, which will be required if the
execution is normal;
b = pessimistic time, which means that there is little
chance that the activity will take longer.
PERT
SEEM 3530
8
Estimation of Mean and SD
 The expected or mean time is given by:
D= (a+4m+b)/6
The variance is:
V = (b-a) 2/36
 The standard deviation is (b - a)/6
 For our example (Figure 7-3), we have a=10, b=70,
m=35.
Therefore D=36.6, and V2 =100.
PERT
SEEM 3530
9
Estimation of Mean and SD
Beta-distribution
a
m
b
a  4m  b
t
Expected task time:
6
2
ba
ba
2
)
 (
Standard deviation:  
6
PERT
SEEM 3530
6
10
The PERT Approach
The PERT (Program evaluation and
review technique) approach
addresses situations where
uncertainties must be considered.
PERT
SEEM 3530
11
The PERT Approach (cont’d)
 Now assume that the activity times are
independent random variables.
 Further, assume that there are n activities in
the project, k of which are critical. Denote
the activity times of the critical activities by
the random variables di with mean E(di) and
variances V(di), for i=1,2, …, k.
 Then, the total project time (the total length
of the critical path) is the random variable:

X= d1 + d2 +,…, +dk
PERT
SEEM 3530
12
The PERT Approach (cont’d)
 The mean project length, E(X), and its variance,
V(X):
E(X)= E(d1)+E(d2)+,…, +E(dk)
V(X)= V(d1)+V(d2)+,…, +V(dk)
 Assumption:
 Activity times are independent random variables.
 The project duration (=sum of times of activity on a
critical path) is normally distributed.
 Based on the Central Limit Theorem, which states
that the distribution of the sum of independent
random variables is approximately normal when the
number of terms in the sum if sufficiently large.
PERT
SEEM 3530
13
The PERT Approach (cont’d)
 Using a normal distribution, the probability of completing
the project in not more than some given time T:
X-E(X)
T -E(X)
T -E(X)
P(X  T) = P( ------------  ------------- ) = P(Z  ----------)
V(X)1/2
V(X)1/2
V(X)1/2
where Z is the standard normal deviate with mean 0 and
variance 1.
• The probability for P(Z < ), given any , can be found
using normal distribution tables.
PERT
SEEM 3530
14
PERT
SEEM 3530
15
Example: Shopping Mall Renovation
Activity
A: Prepare initial design
B: Identify new potential clients
C: Develop prospectus for tenants
D: Prepare final design
E: Obtain planning permission
F: Obtain finance from bank
G: Select contractor
H: Construction
I: Finalize tenant contracts
J: Tenants move in
PERT
IP
a
1
4
A
2
A
1
D
1
E
1
D
2
G, F
10
B, C, E 6
I, H
1
SEEM 3530
m
3
5
3
8
2
3
4
17
13
2
b
5
12
10
9
3
5
6
18
14
3
16
Example: Issues to Address
1. Schedule the project.
2. What is the probability of completing
the project in 36 weeks?
PERT
SEEM 3530
17
Expected Activity Time and SD
Act
A
B
C
D
E
F
G
H
I
J
PERT
a
1
4
2
1
1
1
2
10
6
1
m
3
5
3
8
2
3
4
17
13
2
b
5
12
10
9
3
5
6
18
14
3
t
3
6
4
7
2
3
4
16
12
2
SEEM 3530
1 4 3  5
2
t
3
6
0.44
1.78
1.78   (124 ) 1.78
6
1.78
0.11
0.44
0.44
1.78
1.78
0.11
2
2
18
CPM with Expected Activity Times
I,12
B,6
1
C,4
J,2
E,2
End
F,3
A,3
PERT
D,7
G,4
SEEM 3530
H,16
19
Critical Path and Expected Time
1. Critical path: A-D-E-F-H-J.
2. Expected Completion time: 33 weeks
3. What is the probability to complete the
project within 36 weeks?
-- Use the critical path to assess the
probability
PERT
SEEM 3530
20
Probability Assessment
Expected project completion time:
Sum of the expected activity times
along the critical path.
Used to obtain
probability of project
 = 3+7+2+3+16+2 = 33
completion
Variance of project-completion time
Sum of the variances along
the critical path.
2 = 0.44+1.78+0.11+0.44+1.78+0.11= 4.66
 = 2.15
PERT
SEEM 3530
21
Assessment by Normal Distribution
P(X  36) = ?
Assume X ~ N(33, 2.152)
Normal
Distribution
 = 2.15
-  36 - 33
T
=
= 1.4
z =
.

2.15
Standardized Normal Distribution
 = 33 36
PERT
P(Z  1.4) = ?
 =1
z
X
SEEM 3530
 = 0 1.4
z
Z
22
Obtain the Probability
Standardized Normal Probability Table (Portion)
Z
.00
.01
.02
P(Z<1.4) = 0.9192
z=1
0.0.5000.5040.5080
:
:
:
:
.9192
1.4.9192.9207.9222
1.5.9332.9345.9357
PERT
z=0
1.4
z
P( 0 < Z < z )
SEEM 3530
23
The PERT Approach: A Summary
1.
2.
3.
4.
5.
For each activity i, assess its probability distribution or
assume a beta distribution and obtain estimates ai, bi, and
mi. These values could by supplied by the project manager
or experts working in the field.
Compute the mean and variance for each activity.
Apply CPM to determine the critical path, using the
activity means as the activity times for CPM computation.
Once the critical activities are identified, sum their
means and variances to find the mean and the variance of
the project length.
Use the formula to compute P(X  T) (see above) to
compute the probability that the project finishes within
some desired time/due date.
PERT
SEEM 3530
24
Completion Time with a Given Prob.


Using PERT, it is also possible to estimate the
completion time for a desired completion
probability.
For example, for a 95% probability the
corresponding Z value is Z0.95 = 1.64. Solving
for the time T for which the probability to
complete the project is 95%, we get
Z0.95 = (T – 33)/2.15 = 1.64
T = 33 + (2.15)(1.64) = 36.5
PERT
SEEM 3530
25
A Shortcoming of Standard PERT
The standard PERT method ignores all activities not on
the critical path.
What is the probability to complete the project within 17
weeks?
PERT
SEEM 3530
26
A Modification
Identify each sequence of activities leading from the start
to the end, and then calculate separately the probability
for each path to complete by a given date.
 The above can be done by assuming that the central limit
theorem holds for each sequence and then applying normal
distribution theory to calculate the individual sequence
(path) probabilities.
 Assume, if necessary, that the paths are statistically
independent (i.e. the time to traverse each path in the
network is independent of what happens on the other
paths).
 Although this additional assumption is rarely true in
practice, empirical evidence suggests that good results can
be obtained.
PERT
SEEM 3530
27

Modified Probability of Completion


PERT
Once the calculations on all paths (at least
those that we are concerned with) are
performed, the probability of completing the
whole project can be calculated.
Assume there are n paths, with completion
times X1, X2, …, Xn. Then, the probability of
completing the project is
P(X  T) = P(X1  T) P(X2  T) … P(Xn  T)
SEEM 3530
28
Example: Modified Calculations


PERT
If no uncertainty exists, then the critical
path is (A-B) and exactly 17 weeks are
required to finish the project.
If the durations of the four activities are
normally distributed (the means and
variances are as shown in the figure above),
then the durations of the two paths are
normally distributed as follows:
length (A-B) = X1 ~ N(17, 3.61)
length (C-D) = X2 ~ N(16, 3.35)
SEEM 3530
29
The Probability Density Functions
PERT
SEEM 3530
30
Project Completion Probabilities

The project can be completed in 17 weeks only if both (A-B) and
(C-D) are completed within that time. The probabilities for the
two paths to be completed in that time are given below:
17-17
P(X1  17) = P(Z  ----------- ) = P(Z  0)=0.5
3.61
17-16
P(X2  17) = P(Z  ----------- ) = P(Z  0.299)=0.62
3.35

Thus, the probability of completing the project within 17 weeks is
P(X  17) = P(X1  17) P(X2  17) = (0.5)(0.62)=0.31 = 31 %.
PERT
SEEM 3530
31
PERT - Summary
 PERT accounts for uncertainty in activity times.
 Assumptions:
Project completion time is sum of activity times on critical
path.
Activities are probabilistically independent.
By CLT, project completion time is normally distributed.
 PERT provides:
Expected project completion time
Probability of completion by deadline
 Concerns:
Activities not necessarily independent
“Slack” activities with large variances
More than one critical path
PERT
SEEM 3530
32