Project Scheduling and

Control
 Critical Path Method (CPM)

• A project planning and scheduling technique

• CPM is part of group of techniques called Network Models

• CPM is broken into:

• Creating Work Breakdown Structure (WBS)

• Creating a Network Diagram of the Project

• Computing Activity Times and Activity Total Float

• Computing the Project Duration and Critical Path

• Creating an Activity Schedule Table

• Creating a GANTT Chart Schedule
Typical Layout of Work Breakdown
Structure (WBS)
Example of Work Breakdown Structure
(WBS)
Network Diagram

Types of Network Diagram

Activity on Arrow (AOA) Activity on Node (AON)

Precedence
Critical Path
Diagram
Method
Method (PDM)

PERT

PERT: Program evaluation and review technique

Activity on Arrow (AOA)

• Normally, the first event is the “Start”

event.

• The last event is the “End” event.

• First event has no predecessors.

Event

Activity X • Last event has no successors.

Node Node
Y weeks • All networks have a first and last event.
 B
A
C A must finish before either B or C can start.

A
C
B Both A and B must finish before C can start.
Situations in
AOA A C
Both A and B must finish before either of C
or D can start.
B D

A B
A must finish before B can start.
Dummy Both A and C must finish before D can start.
C B is dependent upon A; D is dependent upon
A and C.
D
 a b c Activities must be completed in sequence:
first a, then b, and then c.

a
c Both a and b must be completed before c
b can start.

b
a Activity a must be completed before b or c
can start.
Situations in c

AOA a c Both a and b must be completed before c

or d can start.
b d

Use a dummy activity to clarify

a c relationships:
b 1. To separate two activities that have the
Dummy
activity same starting and end nodes.

a c
2. When activities share some, but not all,
b d precedence activities.
 ONLY for AOA diagram !!!

Concurrent
Activities
QUESTION?

9 6
B E
6 6
1 2 3 8 9
A 8 4 F
C D
Dummy Activities

• Required due to AOA rule that each task is represented by one “Arc”, which connects two
events

• Parallel tasks have a different duration

• If terminated on one event (instant in time), implication is that they both have the same
duration
• Not generally the case
• Cannot change the schedule if one event slips without revising the diagram

• Add Dummy Activity wherever necessary

• Remove non-essential dummies

• Overriding Rule
• Do not remove dummy activity when the result creates two or more activities between a
start/finish node pair
Dummy Activities
What are the correct representations below? Hint: Additional nodes/events may be required.

A C
5 15 20
B D
25
10
C depends on A and B
D depends on B only

5 A
15

B
Dummy Activities
What are the correct representations below? Hint: Additional nodes/events may be required.

A C A C
5 15 20 5 20 25
B D Dummy
25 B D
10 10 15 30
C depends on A and B
D depends on B only

A
A 5 15
5 15
B
Dummy
B
10
Dummy Activities

Construct an activity network from the precedence table.

Activity Immediate predecessor

A -
B -
C -
D A, B
E B, C
Dummy Activities

Construct an activity network from the precedence table.

Activity Immediate predecessor

A - A
D
B - B dummy
Start Finish
C -
dummy
D A, B
E
C
E B, C
Dummy Activities

Construct an activity network from the precedence table.

Activity Immediate
predecessor
A -
B -
C A
D B
E C, D
F C
G E, F
Dummy Activities

Construct an activity network from the precedence table.

Activity Immediate
predecessor C
A
A - F
G
B - Start dummy
Finish
C A
B E
D B
D
E C, D
F C
G E, F
 Activity on Arrow (AOA)

The critical path (or paths) is the longest path (in time) from Start to Finish.
Indicate the critical path (or paths) below.

2 5
B(6) E(13)

A(3) C(7) H(6)

START 1 3 7 9 FINISH

D(9) G(11)

4 6 F(8) 8
Activity on Arrow (AOA)

The critical path is shown below.

2 5
B(6) E(13)

A(3) C(7) H(6)

START 1 3 7 9 FINISH

D(9) G(11)

4 6 F(8) 8
Activity on Arrow (AOA)

Which are nodes, events, durations, arrows, activities and dummy?

 AOA Diagram based on Activities
and Predecessors
Activity Immediate Predecessors Duration (Day)
A --- 6
B A 9
C A 8
D B, C 4
E C 4
F D, E 6
D/4 F/6
B/9
A/6 Dummy
Dummy
1 2
E/4
C/8
 Activity Precedence Duration
A - 5
B - 4

Critical Path C A 8
D B 8
Method E B 8

(CPM) F B 5
G C, D 8
H E, I 22
I F 2
J F 12
Critical Path Method

C
8
A
5 G
D
8
8
B
4 E H

8 22

F I 2 J
5 12
 Critical Path Method

What is/are the critical path(s)?

C Paths
A 8 A – C – G = 5 + 8 +8 = 21
5 G
D
8 8 B – D – G = 4 + 8 + 8 = 20
B
4 E H
8 22 B – E – H = 4 + 8 + 22 = 34
F I 2 J
5 12 B – F – J = 4 + 5+ 12 = 21

B – F – I – H = 4 + 5+ 2 +22 = 33
 Activity Duration

1-2 2

1-3 4

2-4 7

2-5 11
Exercise 1: 3-6 8
Draw AOA
4-7 8
Diagram
5-6 2

5-7 9

6-8 8

7-9 7

8-9 8
 Exercise 1: Draw AOA Diagram

4
7 8

2 9
2 5 7
11 7

1
2 9

4
8
3 6 8
8 8
 Exercise 1: Draw AOA Diagram
9
4
7 8
2
13 22
2 9 c
2 5 7
0 11 7
31
1 c
2 9

4 4 15 23
8
3 6 8
8 8

ES + Duration =EF
 Exercise 1: Draw AOA Diagram
4
7 8
16
2 9
2 5 7
2 11 7
13
24
1
2 9
0
4 31
8
3 6 8
8 8
7 15 23
LF - Duration = LS
 Exercise 1: Draw AOA Diagram
9
4
7 16 8
2
13 22
2 9
2 5 7
0 2 11 7
13
24 31
1
2 9
0
4 4 15 23 31
8
3 6 8
8 8
7 15 23
Activity on Node (AON)

• Use boxes or circles to denote

schedule activities.

• Show which activities must be

completed in order for other activities
to commence.

• There is no dummy activity.

Node

Activity A Activity B
4 weeks 6 weeks
 a b c
Activities must be completed in sequence:
first a, then b, and then c.
a
c
Both a and b must be completed before c
Situations in b
can start.

Network a
b
Activity a must be completed before b or c
Diagram can start.
c

a c
Both a and b must be completed before c
or d can start.
b d
Activity on Node (AON)

Lay foundations Build house

2 4
2 3 Finish work
7
1 1
3
Design house and 5 6
3
Obtain financing 1 1
1
Order and receive Select paint Select carpet
materials
Activity on Node (AON)

Activity Immediate Predecessors

A ---
B A
C A
D B, C
E B, C

B, 9 D, 9

Start A, 6 Finish

C, 9 E, 9
Activity on Node (AON)

Activities Predecessors Activities Predecessors

1 - Design house and obtain financing --- 5 - Select paint 2, 3

2 - Lay foundations 1 6 - Select carpet 5

3 - Order and receive materials 1 7 - Finish work 4, 6

4 - Build house 2, 3
 Activity Earliest Start Time (EST)

Activity Earliest Finish Time (EFT)

Activity Times Activity Latest Start Time (LST)

Activity Latest Finish Time (LFT)

 Earliest Start Time (EST)
This is the earliest possible time that an activity can begin. All
immediate predecessors must be finished before an activity can
start.

Earliest Finish Time (EFT)

This is the earliest possible time that an activity can be finished (=
earliest start time + activity completion time).

Latest Start Time (LST)

Activity Times This is the latest time that an activity can begin and not delay the
completion time of the overall project. If the earliest start and latest
start times are the same then the activity is critical.

Latest Finish Time (LFT)

This is the latest time that an activity can be finished and not delay
the completion time of the overall project (= latest start time +
activity completion time). As with start times, the activity is critical if
the earliest finish and latest finish times are the same.
Activity on Node (AON)

EFT
8 11
Activity
EST Analyse
requirements (3) Name
0 8 13 16

Conduct
interviews (8)

0 8 8 16 16 21

Investigate
Start packages (8)
Produce report (5) Finish

0 4 8 16 16 21

Investigate other
systems (4)
Activity
4 8 8 13
Duration
Investigate

LST hardware (5)

LFT 11 16
Network Diagram Rules

• The calculation of Start time is on the left, finish time is on the right

• Always use a single start event

• No predecessors

• Always use a single completion event

• No successors
Early Expected/Start Time of an
Event
• Designated as TE

• Calculation of Early Expected Time is part of schedule analysis

• Events which are not on the critical path can be started early
• By definition, events on the critical path cannot be started early
• Can have more than one critical path, on that path events cannot be started early

• Calculated by taking the sum of all task durations on the longest path leading to the
event
• Traverse network from left to right
Latest Allowable Time of an Event

• Designated as TL

• Latest time to which an event can be slipped without affecting succeeding events

• Calculated by taking the sum of all task durations on the longest backward path from
the finish date to the event of interest
• Traverse network from right to left
Total Slack / Float

• Slack (i.e. float) is the range of allowable time between when a task can be started, and when
it must be started
• Once slack is used up, the finish date of the project is affected
• The task of interest is now on the critical path

• Total slack of an activity is the amount of slack available to all activities on a given subpath of a
network

• Total slack of activities on the critical path is zero

• Total Slack of an activity (task) is calculated as follows:

Total Slack = LS - ES
Free Slack

Activities not on the critical path can be delayed without affecting the start time of succeeding
tasks

Free slack of an activity is the amount of time that the activity can slip without affecting its
successors
Assumes that the TE of all preceding tasks has been met

Free Slack of an activity is calculated as follows:

Free Slack = ES (earliest successor) – EF If there are more than one pair of free
slacks, take the smaller one.
or

Free Slacki = ES of “j” – ES of “ i ” – Duration of Activityi

Critical Path Determination
 Example

Activity Predecessor Duration (D)

A - 3
B A 4
C A 2
D B 5
E C 1
F C 2
G D, E 4
H F, G 3

TF
ES Act EF
LS Dur LF
FF
 Example

Activity Predecessor Duration (D)

0
A - 3
7 D 12
B A 4 7 5 12 0
0 12 G 16
C A 2 0 0
3 B 7 12 4 16
D B 5 3 4 7 6 16 H 19
0 0
E C 1 0 5 E 6 16 3 19
0 A 3
11 1 12
F C 2 0 3 3 6 0
3 C 5
6
G D, E 4 0
9 2 11 9
H F, G 3 5 F 7
0
14 2 16
TF
ES Act EF 9
LS Dur LF
FF
 Exercise 1: Draw AON Diagram

Activity Predecessor Duration

A - 6
B - 7
C A 3
D A 2
E B 4
F B 6
G C,D 10
H E,F 7
 Exercise 1: Draw AON Diagram
C

A G

START END

B H

F
 C
3

A G
6 10
D
2

START END

E
4
B H
7 7

F
6
 6 C 9
3

0 A 6 9 G 19
6 10
6 D 8
2

ES + Duration =EF
START END

20 Days
7 E 11
4
0 B 7 13 H 20
7 7

7 F 13
6
 6 C 9
7 3 10
0 A 6 9 G 19
1 6 7 10 10 20
6 D 8
8 2 10

START Critical Path END

20 Days
7 E 11
9 4 13
0 B 7 13 H 20
0 7 7 13 7 20

7 F 13
7 6 13
 Activity Description Immediate Predecessor Duration
(Weeks)
H Basic design - 10
I Hardware design for “A” H 8
J Hardware design for “B” H 6
K Drawings for B J 4
L Software specifications J 2
M Parts purchase for B J 4
N Parts purchase for A I 4
Exercise 2: O Drawings for A I 5

Draw AON P Installation drawings I, J 5

Q Software purchases L 5
Diagram
R Delivery of parts for A M 5
S Delivery of parts for B N 3
T Software delivery Q 3
U Assembly of A O, S 1
V Assembly of B K, R 5
W Test A U 2
X Test B V 3
Y Final installation P, W, X 8
Z Final system test Y 6
AON Diagram

N, 4 S, 3

I, 8
O, 5 U, 1 W, 2

H, P, 5 Y, 8 Z, 6 Finish
Start 10

K, 4 V, 5 X, 3
J, 6

M, 4 R, 5

L, 2 Q, 5 T, 3
 18 N 22 22 S 25
23 4 27 27 3 30
10 I 18
15 8 23

18 O 23 25 U 26 26 W 28
25 5 30 30 1 31 31 2 33

0 H 10 18 P 23 33 Y 41 41 Z 47
0 10 10 28 5 33 33 8 41 41 6 47

16 K 20
21 4 25 25 V 30 30 X 33
10 6 16 25 5 30 30 3 33
16 M 20 20 R 25
10 J 16 16 4 20 20 5 25

16 L 18 18 Q 23 23 T 26
31 2 33 33 5 38 38 3 41
 18 N 22 22 S 25
23 4 27 27 3 30
10 I 18
15 8 23

18 O 23 25 U 26 26 W 28
25 5 30 30 1 31 31 2 33

0 H 10 18 P 23 33 Y 41 41 X 47
0 10 10 28 5 33 33 8 41 41 6 47

16 K 20
21 4 25 25 V 30 30 X 33
10 J 16 25 5 30 30 3 33
16 M 20 20 5 25
10 6 16 16 4 20 20 R 25

16 L 18 18 Q 23 23 T 26
31 2 33 33 5 38 38 3 41
 18 N 22 22 S 25
23 4 27 27 3 30
10 I 18
15 8 23

18 O 23 25 U 26 26 W 28
25 5 30 30 1 31 31 2 33

0 H 10 18 P 23 33 Y 41 41 Z 47
0 10 10 28 5 33 33 8 41 41 6 47

16 K 20
21 4 25 25 V 30 30 X 33
10 J 16 25 5 30 30 3 33
16 M 20 20 R 25
10 6 16 16 4 20 20 5 25

16 L 18 18 Q 23 23 T 26
31 2 33 33 5 38 38 3 41
 Resource Management

• The availability of resources and the smoothness of the demand for labour for a particular project
should be considered

• The float time can be used to optimize the resources allocation of a project
6 D 17 17 G 24
15 11 26 26 7 33

0 A 3 3 B 5 5 C 6 6 E 10 10 I 14 33 K 38
0 3 3 3 2 5 5 1 6 21 4 25 29 4 33 33 5 38

6 F 15 15 H 25 25 J 33
6 9 15 15 10 25 25 8 33
Resource Management

• Suppose that the costs of completing the activities are estimated as given in Table below.
Activity Time (weeks) Cost per week Total cost ($)
A 3 1,000 3,000
B 2 1,500 3,000
C 1 1,600 1,600
D 11 800 8,800
E 4 700 2,800
F 9 1,200 10,800
G 7 500 3,500
H 10 900 9,000
I 4 1,300 5,200
J 8 1,400 11,200
K 5 600 3000
 Resource Management

• The cost of each critical activity = The

area of each rectangle

• The positions of the rectangles

2000 representing costs of critical activities
in any way are fixed and cannot be
altered.

• The non-critical activities can be more

1000 flexible in this respect.

A B C F H J K

0 5 10 15 20 25 30 35 40
Resource Management

The following histogram shows when all the non-critical activities start at their respective earliest
start times.

I Float
4
19
E Float
4
15
G Float
7
9
D Float
11
9

A B C F H J K
3 2 1 9 10 8 5

0 5 10 15 20 25 30 35 40
 Resource Management
3,300

E I
2,000 -

D G

1,000 -

A B C F H J K

0 5 10 15 20 25 30 35 40
Resource Management

• From the histogram above, for the first few weeks and the last few weeks, the resources utilized
(in terms of money) is not more than $1,000.

• During Week 11 to Week 14, it suddenly jumps to $3,300 per week. Certainly, such a situation is
not desirable.

• It is better to have a more evenly distributed resource utilization throughout the project.
Resource Management

By adjusting the start times of the non-critical activities within their allowable float times, the
histogram can be smoothened.

E I
4 4

D G
11 7

A B C F H J K
3 2 1 9 10 8 5

0 5 10 15 20 25 30 35 40
 Resource Management

The maximum total resource required is only $2,200 per week.

2,200
2,000 -
G

D
E I

1,000 -

A B C F H J K

0 5 10 15 20 25 30 35 40
 Tutorial 3
8
4 8

9 2

7 12 13
2 5 9 11
2

1 6 15 5 6
4

19
3 6 10

6 17
c
7 16 31
 Tutorial 3
11 19
8
4 8

9 2
2 10 24 37
7 12 13
2 5 9 11
2
0
1 6 15 5 6
4
4 9 29
5 19
3 6 10

6 17
10
c
7 16 31
 Tutorial 3
11 19
8
4 8

9 22
14 2
2 10 37
7 12 24 13
2 5 9 11
2 24
5 12 37
0
1 6 15 5 6
4
0 4 9 29
5 19
3 6 10

4 9
6 17 31
10
7

14
 Tutorial 3
Activity Duration ES EF LS LF TF FF
1–2 2 0 2 3 5 3
1–3 4 0 4 0 4 0
2–4 9 2 11 5 14 3
2–5 7 2 9 5 12 3 1
3–5 6 4 10 6 12 2
3–6 5 4 9 4 9 0
3–7 6 4 10 8 14 4
4–8 8 11 19 14 22 3
5–9 12 10 22 12 24 2 2
6–9 15 9 24 9 24 0
6 – 10 19 9 28 12 31 3 1
7 – 10 17 10 27 14 31 4 2
8–9 2 19 21 22 24 3 3
9 – 10 5 24 29 26 31 2
9 – 11 13 24 37 24 37 0
10 – 11 6 29 35 31 37 2 2
 Duration (weeks)
Activity
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

1–2 2 2

1–3 3 3 3 3
5 5 5 5 5 5 5 5 5
Before
2–4
2–5 6 6 6 6 6 6 6

3–5 4 4 4 4 4 4

3–6 1 1 1 1 1

3–7 3 3 3 3 3 3

4–8 3 3 3 3 3 3 3 3

5–9 5 5 5 5 5 5 5 5 5 5 5 5

6–9 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

6 – 10 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6

7 – 10 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7

8–9 10 10

9 – 10 8 8 8 8 8

9 – 11 4 4 4 4 4 4 4 4 4 4 4 4 4

10 – 11 7 7 7 7 7 7

5 5 14 14 19 19 19 19 19 20 25 23 23 23 23 23 23 23 23 30 30 20 15 15 25 25 25 18 12 11 11 11 11 11 11 4 4
 Duration (weeks)
Activity
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

1–2 2 2

1–3 3 3 3 3
5 5 5 5 5 5 5 5 5
After
2–4
2–5 6 6 6 6 6 6 6

3–5 4 4 4 4 4 4

3–6 1 1 1 1 1

3–7 3 3 3 3 3 3

4–8 3 3 3 3 3 3 3 3

5–9 5 5 5 5 5 5 5 5 5 5 5 5

6–9 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

6 – 10 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6

7 – 10 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7

8–9 10 10

9 – 10 8 8 8 8 8

9 – 11 4 4 4 4 4 4 4 4 4 4 4 4 4

10 – 11 7 7 7 7 7 7

5 5 14 14 19 19 19 19 19 20 25 23 23 23 23 23 23 23 23 20 20 20 25 25 25 25 25 18 12 11 11 11 11 11 11 4 4