Project Scheduling: PERT/CPM
Chapter 13
Project Scheduling: PERT/CPM
Learning Objectives
1. Understand the role and application of PERT/CPM for project scheduling.
2. Learn how to define a project in terms of activities such that a network can be used to describe the
project.
6. Understand the concept and need for crashing.
7. Be able to formulate the crashing problem as a linear programming model.
8. Learn how to schedule and control project costs with PERT/Cost.
9. Understand the following terms:
network beta distribution
PERT/CPM path
Chapter 13
Solutions:
B
E
2.
A
B
C
FinishStart D
E
F
G
H
I
J
3.
A
D
G
13 –
3
4. a.
Critical Path: A-D-G
b. The critical path activities require 15 months to complete. Thus the project should be completed in
1-1/2 years.
5.
UPDATED ACTIVITY SCHEDULE FOR THE WESTERN HILLS SHOPPING CENTER PROJECT
Earliest Latest Earliest Latest
Start Start Finish Finish Slack Critical
Activity (ES) (LS) (EF) (LF) (LS – ES) Path?
A 0 0 5 5 0 Yes
B 7 11 8 12 4
C 7 8 11 12 1
Chapter 13
13 –
4
6.
a. Critical path: A-D-F-H
b. 22 weeks
c. No, it is a critical activity
d. Yes, 2 weeks
7. a.
b. A-D-E-H
c. Activity F: 4 weeks
d. Yes, project completion time is 16 weeks
Start
B
C
D
E
H
A
F
G
Activity
Earliest
Start
Latest
Start
Earliest
Finish
Latest
Finish
Slack
Critical
Activity
A
0
0
3
3
0
Yes
B
0
2
1
3
2
D
3
3
7
7
0
Yes
E
7
7
0
Yes
F
3
7
6
4
G
7
3
H
0
Yes
8. a.
b. B-C-E-F-H
c.
Activity
Earliest
Start
Latest
Start
Earliest
Finish
Latest
Finish
Slack
Critical
Activity
A
0
2
6
8
2
B
0
0
8
8
0
Yes
C
8
8
20
20
0
Yes
D
20
22
24
26
2
E
20
20
26
26
0
Yes
26
26
41
41
0
Yes
G
26
29
38
41
3
H
41
41
49
49
0
Yes
d. Yes. Project Completion Time 49 weeks.
9. a.
Start
B
D
F
Finish
A
C
E
G
Chapter 13
5
6
7
6.00
0.11
b.
Activity
Expected Time
Variance
A
10.5
1.36
B
8
0.11
C
6.5
0.69
D
3
0
5
1.78
7
1
G
7.5
1.36
Activity
ES
LS
EF
LF
Slack
Critical
Activity
A
0
0
10.5
10.5
0
Yes
B
0
9
8
17
9
C
10.5
10.5
17
17
0
Yes
D
8
19.5
11
22.5
22
22
0
Yes
22.5
18
29.5
G
29.5
29.5
0
Yes
c. The critical path A – C – E – G:
d. Expected duration = 10.5 + 6.5 + 5 + 7.5 = 29.5
Variance = 1.36 + 0.69 + 1.78 + 1.36 = 5.19
10. a.
Activity
Optimistic
Most
Probable
Pessimistic
Expected
Times
Variance
A
4
5
6
5.00
0.11
B
8
9
10
9.00
0.11
C
7
7.5
11
8.00
0.44
D
6
9
10
8.83
0.25
E
6
7
9
7.17
0.25
13 –
7
11.
12. a.
Activity
Expected Time
Variance
A
4.83
0.25
B
4.00
0.44
C
6.00
0.11
D
8.83
0.25
4.00
0.44
2.00
0.11
G
7.83
0.69
H
8.00
0.44
4.00
0.11
Activity
Earliest
Start
Latest
Start
Earliest
Finish
Latest
Finish
Slack
Critical
Activity
A
0.00
0.00
4.83
4.83
0.00
Yes
B
0.00
0.83
4.00
4.83
0.83
C
4.83
5.67
10.83
11.67
0.83
D
4.83
4.83
0.00
Yes
E
4.00
17.67
8.00
21.67
13.67
10.83
11.67
12.83
13.67
0.83
G
13.67
13.83
21.50
21.67
0.17
H
0.00
Yes
0.00
Yes
Critical Path: A-D-H-I
b. E(T) = tA + tD + tH + tI
= 4.83 + 8.83 + 8 + 4 = 25.66 days
c.
2 = A
2 + D
2 + H
2 + I
2
= 0.25 + 0.25 + 0.44 + 0.11 = 1.05
Chapter 13
13 –
8
Probability of 25 days or less is 0.2578.
13.
Activity
Expected Time
Variance
A
5
0.11
B
3
0.03
C
7
0.11
D
6
0.44
E
7
0.44
3
0.11
G
0.44
H
8
1.78
From problem 6, A-D-F-H is the critical path.
E (T) = 5 + 6 + 3 + 8 = 22
2 = 0.11 + 0.44 + 0.11 + 1.78 = 2.44
z = T ime – E (T)
= T ime – 22
2.44
a. Time = 21 z = -0.64
Cumulative Probability = 0.2611
P(21 weeks) = 0.2611
14. a.
Activity
Expected Time
Variance
A
8
1.78
B
7
0.11
C
12
4.00
D
5
0.44
10
4.00
9
4.00
G
15
2.78
H
7
1.78
Activity
Earliest
Start
Latest
Start
Earliest
Finish
Latest
Finish
Slack
Critical
Activity
A
0
0
8
8
0
Yes
B
8
14
15
21
6
C
8
8
20
20
0
Yes
D
8
15
13
20
7
E
20
20
30
30
0
Yes
20
21
29
30
1
G
30
30
45
45
0
Yes
H
45
45
52
52
0
Yes
Critical Path: A-C-E-G-H
b. E(T) = tA + tC + tE + tG + tH
= 8 + 12 + 10 + 15 + 7 = 52 weeks (1 year)
c.
2 2 2 2 2 2
A C E G H
= + + + +
= 1.78 + 4.00 + 4.00 + 2.78 + 1.78 = 14.34
Using the normal distribution,
44 ( ) 44 52 2.11
14.34
ET
z
−−
= = = −
From the table for standard normal distribution, the cumulative probability for z = -2.11 is 0.0174.
14.34
From the table for standard normal distribution, the cumulative probability for z = 1.32 is 0.9066.
Probability of more than 57 weeks = 1.0000 – 0.9066 = 0.0934
15. a.
AB
F
E
Chapter 13
13 –
10
b.
Activity
Expected Time
Variance
A
2
0.03
B
3
0.44
C
2
0.11
D
2
0.03
1
0.03
2
0.11
G
4
0.44
H
4
0.11
2
0.03
Activity
Earliest
Start
Latest
Start
Earliest
Finish
Latest
Finish
Slack
Critical
Activity
A
0
0
2
2
0
Yes
B
2
2
5
5
0
Yes
C
0
1
2
3
1
D
2
3
4
5
1
E
5
10
6
11
5
6
11
8
13
5
G
5
5
9
9
0
Yes
H
9
9
0
Yes
0
Yes
c. Critical Path: A-B-G-H-I
E(T) = 2 + 3 + 4 + 4 + 2 = 15 weeks
d. Variance on critical path
2 = 0.03 + 0.44 + 0.44 + 0.11 + 0.03 = 1.05
13 –
11
16. a.
b.
B-C
Expected Time = 7.5 + 1 = 8.5 weeks
1.36 + 0 = 1.36
Cumulative probability = 0.90
d. The probability estimate from (c) based on both paths is more accurate. Both paths must be
completed for the entire project to be completed. These two paths only share one activity (C), which
has no variability, and thus are effectively independent.
Activity
Expected Time
Variance
A
6.67
2.78
B
7.5
1.36
C
1
0
Chapter 13
13 –
12
17. a.
A
B
FinishStart
D
b. Critical Path A-B-D
Expected Time = 4.5 + 8.0 + 6.0 = 18.5 weeks
c. Material Cost = $3000 + $5000 = $8000
Best Cost (Optimistic Times) 3 + 5 + 2 + 4 = 14 days
Total Cost = $8000 + 14($400) = $12,800
e.
3.47 1.86
==
Bid = $16,800 = $8,000 + Days ($400)
400 Days = 16,800 – 8000 = 8,800
Days = 22
The project must be completed in 22 days or less.
Probability of 22 weeks or less is 0.9699
The probability of a loss is 1.0000 – 0.9699 = 0.0301
18. a.
13 –
13
b.
Activity
Expected Time
Variance
A
1.17
0.03
B
6.00
0.44
C
4.00
0.44
D
2.00
0.11
E
3.00
0.11
2.00
0.11
G
2.00
0.11
H
2.00
0.11
1.00
0.00
Activity
Earliest
Start
Latest
Start
Earliest
Finish
Latest
Finish
Slack
Critical
Activity
A
0.00
0.00
1.17
1.17
0.00
Yes
B
1.17
1.17
7.17
7.17
0.00
Yes
C
1.17
3.17
5.17
7.17
2.00
D
7.17
7.17
9.17
9.17
0.00
Yes
E
7.17
10.17
10.17
13.17
3.00
1.17
11.17
3.17
13.17
10.00
G
9.17
9.17
11.17
11.17
0.00
Yes
H
11.17
11.17
13.17
13.17
0.00
Yes
13.17
13.17
14.17
14.17
0.00
Yes
c. Critical Path: A-B-D-G-H-I
Expected Project Completion Time = 1.17 + 6 + 2 + 2 + 2 + 1 = 14.17 weeks
d. Compute the probability of project completion in 13 weeks or less.
2 = A
2 + B
2 + D
2 + G
2+ H
2 + I
2
= 0.03 + 0.4 4 + 0.11 + 0.11 + 0.11 + 0.00 = 0.80
Chapter 13
13 –
14
19. a.
Activity
Expected Time
Variance
A
4
0.11
B
4
0.44
C
5
0.11
D
3
0.11
E
10
1.78
9
0.69
G
6
0.25
H
7
1.78
3
0.44
5
0.11
A
4
4
20
0
16
C
9
4
I
3
23
26
20
23
D
3
12
23
9
20
Activity
Earliest
Start
Latest
Start
Earliest
Finish
Latest
Finish
Slack
Critical
Activity
A
0
16
4
20
16
B
0
0
4
4
0
Yes
C
4
15
9
20
11
D
9
20
12
23
11
E
4
4
14
14
0
Yes
F
4
12
13
21
8
G
14
17
20
23
3
H
14
14
21
21
0
Yes
20
23
23
26
3
21
21
26
26
0
Yes
13 –
15
b. E(T) = tB + tE + tH + tJ
= 4 + 10 + 7 + 5 = 26
2 2 2 2 2
B E H J
= + + +
= 0.44 + 1.78 + 1.78 + 0.11 = 4.11
20. a.
Activity
Maximum
Crash
Crash
Cost/Week
A
2
400
B
3
667
C
1
500
D
2
300
1
350
2
450
G
5
360
H
1
Min
400YA
+
667YB
+
500YC
+
300YD
+
350YE
+
450YF
+
360YG
+
1000YH
s.t.
xA + yA 3
xE + yE – xD 4
xH + yH – xG
3
xB + yB 6
xF + yF – xE 3
xH
16
xC + yC – xA 2
xG + yG – xC 9
xD + yD – xC 5
xG + yG – xB 9
xD + yD – xB 5
xH + yH – xF 3
Maximum Crashing:
yA 2
yB 3
yC 1
yD 2
Chapter 13
13 –
16
b. Linear Programming Solution
Activity
Crash Time
New Time
Crash Cost
A
0
3
—
B
1
5
667
C
0
2
—
D
2
3
600
E
1
3
350
1
2
450
G
1
8
360
H
0
3
c.
Activity
Earliest
Start
Latest
Start
Earliest
Finish
Latest
Finish
Slack
Critical
Activity
A
0
0
3
3
0
Yes
B
0
0
5
5
0
Yes
C
3
3
5
5
0
Yes
D
5
5
8
8
0
Yes
E
8
8
0
Yes
0
Yes
G
5
5
0
Yes
H
0
Yes
All activities are critical.
21. a.
Activity
Earliest
Start
Latest
Start
Earliest
Finish
Latest
Finish
Slack
Critical
Activity
A
0
0
3
3
0
Yes
B
0
1
2
3
1
C
3
3
8
8
0
Yes
D
2
3
7
8
1
E
8
8
0
Yes
8
2
G
2
Critical Path: A-C-E
Project Completion Time = tA + tC + tE = 3 + 5 + 6 = 14 days
b. Total Cost = $8,400
13 –
17
22. a.
Activity
Max Crash Days
Crash
Cost/Day
A
1
600
B
1
700
C
2
400
2
400
E
2
500
1
400
1
500
xA + yA 3
xB + yB 2
xC + yC – xA 5
xD + yD – xB 5
xE + yE – xC 6
xG + yG – xF 2
xFIN – xE 0
xFIN – xG 0
xFIN 12
yA 1
yB 1
yC 2
b.
Activity
Crash
Crashing Cost
C
1 day
$400
E
1 day
500
Total
$900
Chapter 13
13 –
18
23. a. This problem involves the formulation of a linear programming model that will determine the length
of the critical path in the network. Since xI, the completion time of activity I, is the project
completion time, the objective function is:
Min xI
Activity
A
xA A
B
xB B
C
xC – xA C
D
xD – xA D
E
xE – xA E
G
xG – xD G
xG – xF G
H
xH – xB H
xH – xC H
24. a.
b.
Activity
Earliest
Start
Latest
Start
Earliest
Finish
Latest
Finish
Slack
A
0
0
10
10
0
B
10
10
18
18
0
C
18
18
28
28
0
D
10
11
17
18
1
17
18
27
28
1
28
28
31
31
0
13 –
19
d.
Crash Activities
Number of Weeks
Cost
A
2
$ 40
B
2
30
C
1
D
1
1
e.
Activity
Earliest
Start
Latest
Start
Earliest
Finish
Latest
Finish
Slack
A
0
0
8
8
0
B
8
8
14
14
0
C
14
14
23
23
0
D
8
8
14
14
0
14
14
23
23
0
23
23
26
26
0
25. a.
Let
Ki
=
Cost to crash activity i one week
Mi
=
Maximum crash time in weeks for activity i
Yi
=
Number of weeks activity i is crashed
Xi
=
Completion time for activity i
Ti
=
Normal completion time for activity i
Min
KAyA
+
KByB
+
KCyC
+
KDyD
+
KEyE
+
KFyF
+
KGyG
+
KHyH
+
KIyI
+
KJyJ
s.t.
xA + yA A
xB + yB B
xC + yC – xB C
xD + yD – xA D
xD + yD – xC D
xE + yE – xB E
Chapter 13
13 –
20
xFIN T
J values can be computed from data given in problem 19. (See solution to problem 19.)
yA MA
yF MF
yB MB
yG MG
yC MC
yH MH
yE ME
b. Information needed:
1. Maximum crash time for each activity (Mi)