D1.4 Critical path analysis
⤓ Presentation⤓ PowerPointPresentation: opens offline in any browser, simulations live. PowerPoint: editable.
Decision Mathematics 1 (AS), specification sections 4.1–4.5: activity networks, event times, critical paths, float, cascade charts and scheduling workers.
What this page covers
7 points
- Precedence tables and activity-on-arc networks, with a single start event and a single finish event
- Dummy activities: keeping the precedences correct and keeping every activity uniquely labelled by its events
- The forward pass (early event times) and the backward pass (late event times)
- Critical activities, the critical path and the length of the project
- Total float, and what a delay does to the finishing time
- Cascade (Gantt) charts, and which activities must, or could, be happening at a given time
- A lower bound for the number of workers, scheduling with a given number of workers, and the minimum completion time
In one minute
5 points
- Critical path analysis turns a precedence table into an activity network, finds the earliest and latest time of each event, and so identifies the critical activities that fix the length of the project.
- A dummy (dashed, duration 0) is added only to keep a precedence correct, or so that no two activities share both their start and end events.
- Forward pass: early event time = the largest of (early time at the start of an incoming arc + its duration). Backward pass: late event time = the smallest of (late time at the end of an outgoing arc − its duration).
- Total float = late time at the end − duration − early time at the start. Critical activities have zero float; together they form the critical path, whose length is the project duration.
- Workers: lower bound = total of all durations ÷ critical path length, rounded up. When a worker is free, give them the available activity with the smallest latest finish time.
Contents
13 sections
- How do you turn a precedence table into an activity network?
- Why and where do you need dummy activities?
- How do you find the early and late event times?
- Which activities are critical, and what is total float?
- How do you draw and read a cascade (Gantt) chart?
- How many workers are needed, and how do you schedule them?
- How do you tackle a full critical path question?
- Exam tips for D1.4
- Common misconceptions
- How this topic connects
- Key formulae
- Check your understanding
- Specification checklist
How do you turn a precedence table into an activity network?
Any real project is made of smaller jobs: some can run side by side, others must wait for certain jobs to finish. The project is first broken into activities, each with a duration. The information about order is given in a precedence table (also called a dependence table), which lists for each activity the activities that must be finished immediately before it can start.
Conventions:
- There is one source (the start, event 0) and one sink (the finish). Activities with no predecessors leave the source; activities that nothing depends on end at the sink.
- Number the events so that every arc goes from a lower number to a higher number. Arrows go left to right.
- The precedence table lists immediate predecessors only. If R depends on P and T depends on R, then T depends on P automatically; the table does not repeat it, and neither should your network.
The figure shows the idea on a five-activity project. T leaves event 3, so T cannot start until both R and S have finished. R can finish at 4 + 3 = 7 and S at 6 + 2 = 8, so event 3 happens at time 8: an event waits for everything that enters it.
To draw a network, let activities with no predecessors leave the source, look for predecessor lists that overlap but are not identical (that is where dummies go), and join every activity with no successors into the sink.
A small project has the precedence table below. Draw an activity network for the project, using activity on arc and exactly one dummy.
| Activity | Immediately preceded by | Duration (days) |
|---|---|---|
| P | — | 4 |
| Q | — | 3 |
| R | P | 5 |
| S | P, Q | 2 |
| T | R, S | 3 |
Step 1. Activities with no predecessors leave the source: P and Q both start at event 0.
Step 2. R needs only P; S needs P and Q, so they cannot start at the same event.
Step 3. Let R leave the end of P. Let S leave the end of Q, and draw a dummy from the end of P to the end of Q. S now waits for Q directly and for P through the dummy, while R still waits for P only.
Step 4. R and S both end at event 3, so T(3) starts there and ends at the sink, event 4.
Check. Tracing backwards from the start of T reaches R, S, P and Q, and nothing else; tracing back from the start of R reaches only P. The network below, with one dummy from event 1 to event 2.
Why and where do you need dummy activities?
There are exactly two reasons to use a dummy.
- To show the precedences correctly. When one activity depends on a set of activities and another on only part of that set, a dummy lets one event “inherit” the completion of another, as in worked example 1.
- To keep activities unique. Each activity must be identified by its start and end events. If G and H have the same predecessors and the same successors, end one of them at an extra event and join that event to the other with a dummy.
Use as few dummies as possible; “exactly two dummies” in a question is a hint to look for two places where predecessor lists overlap.
Drawing the dummy the wrong way round. In worked example 1, a dummy from the end of Q to the end of P would make R wait for Q, which the table does not say. Before you draw a dummy, say to yourself “everything after the arrowhead must wait for everything before the tail”.
The activity network in the figure above shows nine activities A to I and three dummies. (a) Write down the immediate predecessors of each activity. (b) Explain why each of the three dummies is needed.
(a) For each activity, look at the arcs entering its start event, following dummies backwards.
| Activity | A | B | C | D | E | F | G | H | I |
|---|---|---|---|---|---|---|---|---|---|
| Immediately preceded by | — | — | A | A, B | B | C, D | E | E | G, H |
(b) Dummies 1 → 3 and 2 → 3: D needs A and B, but C needs only A and E only B, so D needs its own event fed by both (precedence dummies).
Dummy 6 → 7: G and H both follow E and precede I; without it they would both run from event 5 to event 7. Two precedence dummies and one uniqueness dummy.
How do you find the early and late event times?
From here on the page uses one main project of ten activities, with durations in days:
| Activity | Immediately preceded by | Duration (days) |
|---|---|---|
| A | — | 5 |
| B | — | 3 |
| C | — | 4 |
| D | A | 5 |
| E | A, B | 2 |
| F | C | 7 |
| G | C, E | 4 |
| H | D | 3 |
| I | D, G | 5 |
| J | F | 4 |
Each event gets a box (here, “early | late” beside the node). Set \(e = 0\) at the source and work forwards in event order; then set \(l\) at the sink equal to its early time and work backwards. A dummy is an arc of duration 0 and is included in both passes.
Forward and backward pass
\[e_j = \max\left(e_i + d_{ij}\right) \qquad\qquad l_i = \min\left(l_j - d_{ij}\right)\]Forward: over every arc \(ij\) entering event \(j\). Backward: over every arc \(ij\) leaving event \(i\). These are not in the formulae list and must be known.
Forwards, the slowest route in decides the event; backwards, the tightest route out decides it. The project duration is the early time of the sink, and the late time of the source always comes back to 0, which is a useful check.
The main project is shown as a network in the figure below. Carry out a forward pass and a backward pass to find the early and late event times, and state the minimum project duration.
Forward pass, taking the largest value at each event:
\(e_1 = 5,\; e_3 = 4,\; e_2 = \max(0+3,\ 5+0) = 5\)
\(e_4 = \max(5+2,\ 4+0) = 7,\; e_5 = 5+5 = 10,\; e_7 = 4+7 = 11\)
\(e_6 = \max(7+4,\ 10+0) = 11,\; e_8 = \max(10+3,\ 11+5,\ 11+4) = 16\)
Backward pass, taking the smallest value at each event:
\(l_8 = 16,\; l_7 = 16-4 = 12,\; l_6 = 16-5 = 11,\; l_5 = \min(16-3,\ 11-0) = 11\)
\(l_4 = 11-4 = 7,\; l_3 = \min(12-7,\ 7-0) = 5,\; l_2 = 7-2 = 5\)
\(l_1 = \min(11-5,\ 5-0) = 5,\; l_0 = \min(5-5,\ 5-3,\ 5-4) = 0\) ✓
The dummies count: \(e_2\) is 5, not 3, because the dummy from event 1 brings the finish time of A across. Minimum project duration = 16 days.
Taking the smallest value on the forward pass (or the largest on the backward pass). An event cannot happen until every activity entering it has finished, so the forward pass needs the maximum; the backward pass needs the minimum so that no activity leaving the event makes the project late.
Which activities are critical, and what is total float?
Equal times at both ends are not enough: the activity must also fill the whole gap. A critical path is a path from source to sink made entirely of critical activities (and possibly dummies). Its length is the project duration. A network may have more than one critical path.
The total float of an activity is the time it can be delayed, or extended, without delaying the project. The activity sits in a window from its earliest start \(e_i\) to its latest finish \(l_j\); it needs \(d\) of that window and the rest is float.
Total float
\[\text{total float} = l_j - d - e_i\]\(l_j\) = late event time at the end of the activity (its latest finish); \(d\) = duration; \(e_i\) = early event time at its start (its earliest start). Not in the formulae list: it must be known.
Critical activities have total float 0. Float is shared along a chain: using the float of one activity can reduce the float of those after it.
Using the event times of the main project, (a) find the total float of each activity, (b) state the critical path, (c) find the effect on the project of a delay of 3 days to F, and of a delay of 2 days to H.
(a) Total float = latest finish − duration − earliest start.
| Activity | Duration | Earliest start | Latest finish | Total float |
|---|---|---|---|---|
| A | 5 | 0 | 5 | 5 − 5 − 0 = 0 |
| B | 3 | 0 | 5 | 5 − 3 − 0 = 2 |
| C | 4 | 0 | 5 | 5 − 4 − 0 = 1 |
| D | 5 | 5 | 11 | 11 − 5 − 5 = 1 |
| E | 2 | 5 | 7 | 7 − 2 − 5 = 0 |
| F | 7 | 4 | 12 | 12 − 7 − 4 = 1 |
| G | 4 | 7 | 11 | 11 − 4 − 7 = 0 |
| H | 3 | 10 | 16 | 16 − 3 − 10 = 3 |
| I | 5 | 11 | 16 | 16 − 5 − 11 = 0 |
| J | 4 | 11 | 16 | 16 − 4 − 11 = 1 |
(b) The zero-float activities, joined by the dummy from event 1 to event 2, give critical path A – E – G – I, length 5 + 2 + 4 + 5 = 16 days.
(c) Compare each delay with the float. F has float 1, so a 3-day delay makes the project 3 − 1 = 2 days late: 18 days, and the critical path becomes C – F – J (4 + 10 + 4 = 18). H has float 3, so a 2-day delay to H has no effect on the 16-day duration.
When you list a critical path, give the activities in order from start to finish, and check that their durations add up to the early time at the sink. If they do not, either an event time is wrong or you have joined two separate pieces of path.
How do you draw and read a cascade (Gantt) chart?
A cascade chart (Gantt chart) shows every activity against a time axis, drawn to scale.
- The critical activities go in a single row along the top, end to end, from 0 to the project duration.
- Every other activity has its own row: a solid bar from its earliest start for its duration, followed by a dashed box showing its total float. The end of the dashed box is the latest finish.
The chart answers two kinds of question. An activity must be happening at time \(t\) if, even when started as late as possible, it has begun and, even when started as early as possible, it has not yet finished:
\[\text{latest start} \le t \lt \text{earliest finish}.\]An activity could be happening at time \(t\) if \(t\) lies anywhere between its earliest start and its latest finish. Here latest start = latest finish − \(d\) and earliest finish = earliest start + \(d\). On the chart, slide each bar across its dashed box: if it covers \(t\) in every position, the activity must be happening.
Use the cascade chart of the main project. (a) State which activities must be happening at time 9.5 days. (b) State which activities must be happening, and which could be happening, at time 12.5 days.
(a) G is critical and runs from 7 to 11. D: latest start 11 − 5 = 6, earliest finish 10, and \(6 \le 9.5 \lt 10\). F: latest start 12 − 7 = 5, earliest finish 11, and \(5 \le 9.5 \lt 11\). Must be happening: D, F, G.
(b) I is critical (11 to 16). J has latest start 12 and earliest finish 15, so it must be happening. H could start at 10 and run to 13, or start as late as 13, so it could be happening but need not be. Must: I, J. Could: H.
How many workers are needed, and how do you schedule them?
Assume each activity needs one worker, and an activity once started is finished by the same worker without a break.
To finish in the minimum time, all the work (the total of the durations) has to fit into the critical path length. So a lower bound for the number of workers is the total of the durations divided by the critical path length, rounded up. It is a bound, not a promise: the precedences may leave workers idle and force more.
Lower bound for the number of workers
\[\text{workers} \ge \left\lceil \frac{\text{sum of all activity durations}}{\text{critical path length}} \right\rceil\]\(\lceil\ \rceil\) means round up to the next whole number. Not in the formulae list: it must be known. It is the same idea as the lower bound for the number of bins in bin packing: total size ÷ capacity, rounded up.
Scheduling rule. Whenever a worker becomes free, give them the available activity (all its predecessors finished) with the smallest latest finish time. If nothing is available, the worker waits.
With fewer workers, total of durations ÷ number of workers, rounded up, is a lower bound for the completion time.
(a) Find a lower bound for the number of workers needed to complete the main project in 16 days. (b) Schedule the project using this number of workers, so that it finishes in 16 days.
(a) Total of the durations: 5 + 3 + 4 + 5 + 2 + 7 + 4 + 3 + 5 + 4 = 42 days of work. \(42 \div 16 = 2.625\), so lower bound = 3 workers.
(b) Time 0: A, B and C are available, one each: worker 1 takes A, worker 2 takes B, worker 3 takes C.
Time 3: B ends, but nothing is available until C ends at 4. Time 4: F (latest finish 12) goes to worker 2; worker 3 waits.
Time 5: A ends; D (latest finish 11) and E (latest finish 7) are available. E goes to worker 1 (smaller latest finish) and D to worker 3.
Continue the same way: 7: G to worker 1. 10: H to worker 3. 11: I to worker 1, J to worker 2. Everything is finished at 16. Three workers complete the project in 16 days (schedule below).
Check: every activity stays inside its window on the cascade chart.
How do you tackle a full critical path question?
Long questions follow the order of this page, and each part uses the one before, so check each before moving on. Draw the network large and do the passes in the boxes on the diagram. When a question gives fewer workers than the lower bound, schedule them with the latest-finish rule and compare the finish time with \(\lceil \text{total} \div \text{workers} \rceil\): if they are equal, the schedule is as short as possible.
The refit of a small shop is broken into the nine activities in the table. Each activity needs one worker.
| Activity | Immediately preceded by | Duration (days) |
|---|---|---|
| A | — | 2 |
| B | — | 6 |
| C | A | 7 |
| D | A | 3 |
| E | B, C | 5 |
| F | D | 8 |
| G | B, C, F | 3 |
| H | E | 2 |
| I | E, G | 3 |
(a) Draw an activity network using activity on arc and exactly two dummies. (b) Find the early and late event times. (c) State the critical path and its length. (d) Find the total float of each non-critical activity. (e) Find a lower bound for the number of workers needed to finish in the minimum time. (f) Only two workers are available. Schedule the project and show that your schedule finishes in the least possible time.
(a) E needs B, C; G needs B, C and F. So B and C end at event 2, with a dummy from event 2 to the start of G. I needs E and G; H needs E only, so a dummy runs from the end of E to the start of I.
(b) Forward: \(e_1 = 2,\ e_2 = \max(0+6,\ 2+7) = 9,\ e_3 = 5,\ e_4 = \max(5+8,\ 9+0) = 13,\ e_5 = 14,\ e_6 = \max(13+3,\ 14+0) = 16,\ e_7 = \max(14+2,\ 16+3) = 19\).
Backward: \(l_7 = 19,\ l_6 = 16,\ l_5 = \min(19-2,\ 16-0) = 16,\ l_4 = 13,\ l_3 = 5,\ l_2 = \min(13-0,\ 16-5) = 11,\ l_1 = \min(11-7,\ 5-3) = 2,\ l_0 = 0\).
(c) Critical path A – D – F – G – I, length 2 + 3 + 8 + 3 + 3 = 19 days.
(d)
| Activity | Duration | Earliest start | Latest finish | Total float |
|---|---|---|---|---|
| B | 6 | 0 | 11 | 11 − 6 − 0 = 5 |
| C | 7 | 2 | 11 | 11 − 7 − 2 = 2 |
| E | 5 | 9 | 16 | 16 − 5 − 9 = 2 |
| H | 2 | 14 | 19 | 19 − 2 − 14 = 3 |
B: 5, C: 2, E: 2, H: 3 (A, D, F, G and I have float 0).
(e) Total = 39 days; \(39 \div 19 = 2.05\ldots\), so lower bound = 3 workers.
(f) Two workers, smallest latest finish first. 0: A (latest finish 2) and B. 2: D (latest finish 5) before C (11). 5: C (11) before F (13). 6: F. 12: E. 14: G. 17: H and I, finishing at 20.
Two workers can do at most 2 days of work per day: \(39 \div 2 = 19.5\), so at least 20 days are needed. The schedule finishes in 20 days, which is the minimum. F is critical but waits a day for a free worker, so 19 days is impossible with two workers.
Exam tips for D1.4
For each activity, trace backwards from its start event (through any dummies): you must reach its predecessors and nothing that should not be there.
Write both times in every event box. The late time at the source must come back as 0; if not, there is a slip on the backward pass.
When asked for floats, write latest finish − duration − earliest start with numbers, for example 16 − 3 − 10 = 3.
2.625 workers means at least 3, because 2 workers could do at most 2 × 16 = 32 days of work in 16 days, less than the 42 needed.
Equal time intervals, one row per worker, every activity labelled, and no activity starting before all its predecessors have finished.
Common misconceptions
| Misconception | Why it is wrong | Correct idea |
|---|---|---|
| A dummy takes some time, or represents a real task. | A dummy carries a dependence, not work. | Every dummy has duration 0, and it is still included in both passes. |
| If both ends of an activity have equal early and late times, the activity is critical. | B in the main project runs from event 0 (0, 0) to event 2 (5, 5) but takes only 3 days. | The activity must also fill the gap: late end − duration − early start = 0. |
| The forward pass uses the smallest total at each event. | An event needs all incoming activities finished. | Forward pass: maximum. Backward pass: minimum. |
| A delay to a non-critical activity never matters. | Only a delay up to its total float is absorbed. | A delay longer than the float delays the project by the excess, and the critical path may change. |
| The lower bound always gives enough workers. | The precedences may leave workers idle, so the bound may not be achievable. | Treat it as a minimum; a schedule is needed to show that it works. |
| The total float belongs to one activity only. | Activities in a chain share it: if D uses its 1 day, H has only 2 left. | Total float assumes the activities before start early and those after can finish late. |
How this topic connects
D1 Graphs and networks
An activity network is a directed network without cycles; the vocabulary of arcs, vertices and paths comes from the D1 graphs page.
D1 Algorithms
The worker bound mirrors the lower bound for bin packing.
D1 Dijkstra's algorithm and D1.5 Linear programming
The forward pass is the longest-path cousin of Dijkstra's shortest-path working: keep the largest value, not the smallest.
Key formulae
| Formula | Use | In the formulae list? |
|---|---|---|
| \(e_j = \max(e_i + d_{ij})\) | Forward pass: early event times, starting from 0 at the source | No — learn it |
| \(l_i = \min(l_j - d_{ij})\) | Backward pass: late event times, starting from the duration at the sink | No — learn it |
| total float \(= l_j - d - e_i\) | Spare time of the activity from event \(i\) to event \(j\) | No — learn it |
| \(e_i = l_i,\ e_j = l_j,\ l_j - e_i = d\) | Conditions for a critical activity (zero float) | No — learn it |
| latest start = latest finish − \(d\); earliest finish = earliest start + \(d\) | Cascade charts; “must be happening” questions | No — derive it |
| workers \(\ge \lceil \sum \text{durations} \div \text{critical path length} \rceil\) | Lower bound for the number of workers | No — learn it |
| time \(\ge \lceil \sum \text{durations} \div \text{number of workers} \rceil\) | Lower bound for the completion time with a fixed number of workers | No — derive it |
Check your understanding
1. What are the two reasons for using a dummy activity?
To show the precedences correctly when two activities share some but not all of their predecessors, and to make sure no two activities have the same start event and the same end event.
2. An activity of duration 6 runs from an event with early time 9 to an event with late time 23. Find its total float.
Total float = 23 − 6 − 9 = 8.
3. A project has activities totalling 50 hours and a critical path of 18 hours. Find a lower bound for the number of workers.
\(50 \div 18 = 2.77\ldots\), so at least 3 workers.
4. The main project on this page is given only two workers. Without scheduling, what is the shortest time it could possibly take?
42 days of work ÷ 2 workers = 21 days, so at least 21 days. A schedule is needed to see whether 21 days is actually achieved.
5. In the main project, activity D is delayed by 2 days. Find the new project duration and the new critical path.
D has total float 1, so the project is delayed by 2 − 1 = 1 day: 17 days. With D taking 7 days, \(e_5 = 12\), \(e_6 = \max(11, 12) = 12\) and \(e_8 = \max(15, 17, 15) = 17\). The new critical path is A – D – I (through the dummy from event 5 to event 6): 5 + 7 + 5 = 17.
6. Why must the late event time at the source come out as 0?
The backward pass starts from the project duration and subtracts the durations along the longest path back to the start, so it returns exactly to 0. Any other value means an arithmetic error.
Specification checklist
- (D1 4.1) Draw an activity-on-arc network from a precedence table, with one start and one finish event, events numbered in order.
- (D1 4.1) Write down the immediate predecessors of each activity from a network.
- (D1 4.2) Explain the two uses of a dummy; place as few dummies as possible, the right way round.
- (D1 4.3) Carry out the forward pass (early event times) and backward pass (late event times), including dummies.
- (D1 4.3) Identify critical activities and state a critical path and its length.
- (D1 4.4) Calculate total float and describe the effect of a delay on the project.
- (D1 4.4) Draw a cascade (Gantt) chart to scale and say which activities must or could be happening at a given time.
- (D1 4.5) Find a lower bound for the number of workers, schedule with a given number of workers and find the minimum completion time.