Maths › Decision Mathematics 1 › Critical path analysis
Critical path analysis
Some jobs can wait and some cannot. A forward pass finds the earliest anything can happen, a backward pass finds the latest it may, and the jobs where those agree decide how long the whole project takes.
Builds on Shortest paths: Dijkstra and Floyd and Algorithms, sorting and bin packing.
IN THIS TOPIC
- Draw an activity network from a precedence table, using dummies where needed.
- Carry out the forward and backward passes to find event times.
- Identify the critical activities and the project duration.
WHAT YOU PROBABLY THINK
The critical path is the route through the network with the most activities on it.
From table to network
This paper uses activity on arc: each activity is an arrow, and the circles between them are events. A precedence table lists, for each activity, only its immediate predecessors, and the network must reproduce exactly those dependencies and no others.
Where two activities share some but not all of their predecessors, a dummy arrow of zero duration is needed to carry the dependency without implying the wrong one. A dummy is also used when two activities would otherwise share both their start and end events, which the notation cannot distinguish.
WORKED EXAMPLE
Reading the dependencies
A project has activities A (3 days), B (5), C (4, after A), D (2, after A), E (6, after B and C), F (3, after D) and G (2, after E and F).
A and B have no predecessors, so both start at time zero.
C and D both wait for A, and E waits for both B and C, which is where a dummy may be needed depending on the drawing.
G waits for E and F, so it cannot start until both branches have finished.
Forward and backward
The forward pass gives each event its earliest time: the largest of the earliest finishes of the activities leading into it. The backward pass works from the end, giving each event its latest time: the smallest of the latest starts of the activities leading out.
An activity is critical when its earliest and latest start agree, so any delay to it delays the whole project. The critical activities form a continuous path from start to finish whose durations sum to the project duration. Length in days is what matters, not the number of activities, which is where the opening claim goes wrong.
YOUR TURN
The passes in full
For the project above, carry out both passes and state the critical path and the project duration.
Show the working
Forward: A finishes at 3, B at 5, C at 7, D at 5, E at max(5, 7) + 6 = 13, F at 8, G at max(13, 8) + 2 = 15.
Backward from 15: G starts at 13, so E must finish by 13 and start at 7; F may start as late as 10; C must finish by 7.
Critical activities, where early and late starts agree: A, C, E, G.
3 + 4 + 6 + 2 = 15 days, matching the forward pass, which is the check to make.
THE EXAM BIT
- Copy the durations onto the arcs before starting the forward pass.
- Take the largest value on the way forward and the smallest on the way back.
- Check that the critical activities form one unbroken path and that their durations total the project time.
- Use a dummy whenever two activities share some but not all predecessors, and say why.
CHECK YOURSELF
An activity has earliest start 6, duration 4, and latest finish 13. Is it critical?
Show a hint
Compare the latest start with the earliest start.
Show the answer
T
h
e
l
a
t
e
s
t
s
t
a
r
t
i
s
1
3
−
4
=
9
,
w
h
i
c
h
i
s
l
a
t
e
r
t
h
a
n
t
h
e
e
a
r
l
i
e
s
t
s
t
a
r
t
o
f
6
,
s
o
t
h
e
a
c
t
i
v
i
t
y
h
a
s
3
d
a
y
s
o
f
f
l
o
a
t
a
n
d
i
s
n
o
t
c
r
i
t
i
c
a
l
.
The forward pass takes the largest incoming finish and the backward pass the smallest outgoing start.
An activity is critical when its earliest and latest starts agree; the critical activities form one path whose durations total the project duration.
WORKBOOK
Printable practice for this topic: original exam-style questions with room to work, and a fully worked answer book. Free to use; please do not redistribute or sell.
CHECK YOUR PROGRESS
Rate how confident you feel with each objective for this lesson. Ratings are saved in this browser, on this device only.
- Draw an activity network from a precedence table, using dummies where needed.
- Carry out the forward and backward passes to find event times.
- Identify the critical activities and the project duration.
Open the full revision checklist to see every objective in the course in one place.
No animated video for this topic yet; these notes stand alone.