Maths › Decision Mathematics 1 › Critical path analysis
Critical path analysis
Critical path analysis finds how long a project must take when some activities cannot start until others finish. A forward pass gives the earliest event times, a backward pass gives the latest, and the activities where the two agree form the critical path. The same two passes fill in the boxes when the project is drawn the other way round, with the activities on the nodes.
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, and name the merges and bursts they turn on.
- Identify the critical activities and the project duration.
- Draw and complete an activity-on-node network, filling in the six numbers each box carries.
- Translate a project between the two conventions and check that the answers agree.
COMMON MISCONCEPTION
The critical path is the route through the network with the most activities on it.
An activity is critical when its earliest and latest start agree, so any delay to it delays the whole project. The critical activities form one or more continuous paths from start to finish whose durations total the project duration. Length in days decides it and the number of activities decides nothing, and a network can carry two critical paths of equal length.
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 carries the dependency you want without implying the one you do not. A dummy is also needed when two activities would otherwise share both their start and their end events, since the notation cannot tell such a pair apart.
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, taking the largest of the earliest finishes of the activities leading into it. The backward pass starts at the end and gives each event its latest time, taking the smallest of the latest starts of the activities leading out.
Those two rules exist because of the two shapes an event can take, and the specification names both. A merge is an event with several activities arriving at it, and nothing leaving can start until the slowest of them is done, which is why the forward pass takes the largest. A burst is an event with several activities leaving it, and the event has to be reached in time for the most urgent of them, which is why the backward pass takes the smallest. An event with one arc in and one out is neither, and the rules then have a single number to choose from.
An activity is critical when its earliest and latest start agree, so any delay to it delays the whole project. The critical activities form one or more continuous paths from start to finish, each with durations summing to the project duration; a network can hold two critical paths of equal length. Length in days decides it; the number of activities on a path decides nothing.
GUIDED PRACTICE
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.
The two maxima are taken at the two merges, where B and C both arrive and where E and F do. The event at the end of A is a burst, since C and D both leave it, and so is the start event, where A and B leave.
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.
At the burst after A the backward pass has two candidates, 7 − 4 = 3 from C and 10 − 2 = 8 from D, and takes the smaller, so that event's latest time is 3.
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.
Activity on node
The other convention in common use draws each activity as a box and each dependency as a plain arrow from box to box, and is called activity on node. Nothing stands for an event, so the times attach to activities rather than to moments. Dummy activities are not used in activity-on-node networks: an arrow between two boxes says only that one activity precedes another, which is the job a dummy does in the arc convention. Since the arrows carry a direction, the drawing is a digraph either way.
A box holds six numbers around the activity's name. Across the top go the earliest start, the duration and the earliest finish; across the bottom the latest start, the float and the latest finish. Filling them in is the same pair of passes as before, moved indoors.
The forward pass runs left to right. An activity's earliest start is the largest of the earliest finishes of the activities immediately before it, and zero when there are none; its earliest finish is that plus its duration. The backward pass runs right to left. An activity's latest finish is the smallest of the latest starts of the activities immediately after it, and the project duration when there are none; its latest start is that minus its duration. The float is the latest start minus the earliest start, and an activity of zero float is critical.
WORKED EXAMPLE
The same project, activity on node
Redraw the seven-activity project above as boxes and complete both passes.
Each activity becomes a box and the arrows run A to C, A to D, B to E, C to E, D to F, E to G and F to G. No dummy appears.
| Activity | Duration | Earliest start | Earliest finish | Latest start | Latest finish | Float |
|---|---|---|---|---|---|---|
| A | 3 | 0 | 3 | 0 | 3 | 0 |
| B | 5 | 0 | 5 | 2 | 7 | 2 |
| C | 4 | 3 | 7 | 3 | 7 | 0 |
| D | 2 | 3 | 5 | 8 | 10 | 5 |
| E | 6 | 7 | 13 | 7 | 13 | 0 |
| F | 3 | 5 | 8 | 10 | 13 | 5 |
| G | 2 | 13 | 15 | 13 | 15 | 0 |
The float column holds zeros against A, C, E and G, so those are the critical activities, and 3 + 4 + 6 + 2 = 15 days again.
B, D and F carry floats of 2, 5 and 5, read straight off their boxes. On the arc network those had to be worked out from the event times at either end.
Translating between the conventions is a question of where the numbers live. An activity arrow becomes a box; a dummy becomes an ordinary arrow, or disappears where the dependency it carried is drawn already; the earliest and latest times of an event spread out into the times on the boxes around it. The project duration, the critical activities and the float of each activity come out the same either way, which is worth confirming whenever a question supplies one convention and your memory works in the other.
ASSESSMENT FOCUS
- 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. The choice only arises at a merge going forward and at a burst coming back.
- Check that the critical activities form at least one unbroken path and that each such path's durations total the project time.
- Use a dummy whenever two activities share some but not all predecessors, and say why.
- A project can have more than one critical path. Do not stop looking once you have found one.
- Read which convention the question is in before drawing. Boxes with arrows between them need no dummies at all.
- On a node box, fill the top row left to right on the way forward and the bottom row right to left on the way back, then subtract for the float.
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
The latest start is 13 − 4 = 9, which is later than the earliest start of 6, so the activity has 3 days of float and is not critical.
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; critical activities form one or more continuous paths from start to finish, each with total duration equal to the project duration.
Activity on node draws each activity as a box of six numbers and each dependency as an arrow; dummy activities are not used in activity-on-node networks.
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.
Or read them with their worked answers on the critical path analysis questions page.
USED LATER IN
CHECK YOUR PROGRESS
Rate how confident you feel with each objective for this lesson. Ratings are saved in this browser, on this device, unless you sign in.
- Draw an activity network from a precedence table, using dummies where needed.
- Carry out the forward and backward passes to find event times, and name the merges and bursts they turn on.
- Identify the critical activities and the project duration.
- Draw and complete an activity-on-node network, filling in the six numbers each box carries.
- Translate a project between the two conventions and check that the answers agree.
Open the full revision checklist to see every objective in the course in one place.