Critical path analysis, dummy activities and crashing: VCE General Mathematics Unit 4 Networks and decision mathematics

Syllabus dot point

“Construct an activity network from a precedence table, including dummy activities where necessary, use forward and backward scanning to find earliest and latest start times, identify the critical path and float times, and use crashing to reduce the completion time of a project”

16 min readUpdated 23 Sep 2026

Quick answer

Draw each activity as an edge; add a dashed dummy (duration 0) when two activities share some but not all predecessors. Forward scan: EST $=$ the largest finish time of the immediate predecessors, and the project time is the largest finish time overall. Backward scan: LST $=$ the smallest LST of the immediate successors minus the duration. Float $=$ LST $-$ EST; activities with zero float form the critical path (the longest path). Crashing only helps on critical activities, and it only helps until another path becomes critical, so reduce every critical path at the lowest total cost.

Jump to a section

What this dot point is asking
The answer
Flow and allocation in brief
Exam-style questions
Practice questions

What this dot point is asking

This is the scheduling part of Networks and decision mathematics. The Study Design lists four skills:

build an activity network from a precedence table, "including the use of dummy activities where necessary";
use forward and backward scanning to find earliest start times (EST) and latest start times (LST);
use them to identify the critical path and the float of non-critical activities;
use crashing to reduce the completion time.

Every year has a scheduling question on each paper, usually the last question. In 2025 it was Examination 1 Question 40 (a float, $39\%$ correct) and Examination 2 Question 18 (4 marks, including a crashing cost that only $21\%$ found). In 2023 Examination 2 Question 14 (5 marks) finished with a crashing budget problem that only $9\%$ solved. The steps are routine; the marks are lost to bookkeeping, so the method below is set out so you can write it the same way every time.

(Flow and allocation problems have their own pages; a short summary of how they connect is at the end.)

The answer

Activity networks and precedence tables

A precedence table lists each activity, its duration and its immediate predecessors (the activities that must be finished just before it can start). In the activity network:

each activity is an edge (an arrow) labelled with its name and duration, such as "D, 6";
each node is an event: the moment the activities into it are finished and the activities out of it can start;
there is one start node and one finish node, and arrows point forward in time.

To build the network, draw the activities with no predecessors from the start, then add each activity from the node where all its immediate predecessors end.

Dummy activities

Sometimes two activities share some but not all of their predecessors. Then no single node can represent "the end of exactly these activities" for both, and you need a dummy activity: a dashed arrow of duration 0 that carries a dependency without being real work.

In the network below, F follows C only, but G follows C and E. F starts at the end of C. G starts at the end of E, and a dummy from the end of C to that node makes G wait for C as well. Without the dummy, either G would not wait for C, or F would wrongly wait for E.

Two real exam examples:

2023 Examination 1 Question 38 ( $60\%$ correct): G followed C and F, but H followed F only, so the correct network had a dummy from the end of F to the start of G.
2025 Examination 1 Question 40: G followed B, D and F, but E followed B only, so a dummy runs from the end of B to the start of G. Students who missed that link did not see that B has to finish before G.

A dummy is not an activity: never count it when asked "how many activities" or "how many activities have zero float" (a common error in 2023 Examination 2 Question 14c), and read it as a predecessor link ("I follows C and G" when a dummy runs from C to the start of I).

The forward scan: earliest start times

Work from the start to the finish.

\text{EST} = \text{the largest earliest finish time (EST} + \text{duration) of the immediate predecessors}.

Activities from the start node have EST $= 0$ . When an activity has several predecessors, it must wait for the last one to finish, so take the maximum. The minimum completion time of the project is the largest earliest finish time into the finish node.

The backward scan: latest start times

Work from the finish back to the start, beginning with the minimum completion time.

\text{LST} = \text{the smallest LST of the immediate successors} - \text{duration}.

An activity that leads into the finish node has latest finish time equal to the completion time. When an activity has several successors, it must finish in time for the earliest-needed one, so take the minimum. (The latest finish time of an activity is the smallest LST of its successors; the LST is that minus the duration.)

Float and the critical path

\text{float} = \text{LST} - \text{EST}.

The float is how long an activity can be delayed without delaying the project. Activities with zero float are critical, and together they form the critical path: the longest path from start to finish, whose length is the minimum completion time. A network can have more than one critical path (2025 Examination 2 Question 18 had two). Delaying any critical activity delays the whole project; delaying a non-critical activity by more than its float also does.

A useful check: the float of a non-critical activity on a single side-branch equals the difference between the critical path length and the longest path through that activity.

Formula

Earliest finish $=$ EST $+$ duration. EST $= \max$ (earliest finish of immediate predecessors). LST $= \min$ (LST of immediate successors) $-$ duration. Float $=$ LST $-$ EST. Critical activities have float $0$ ; the critical path is the longest path, and its length is the minimum completion time.

Crashing

Crashing reduces the duration of some activities, usually at an extra cost, to finish sooner. Three rules decide every crashing question:

Only critical activities matter. Shortening an activity with float does not change the completion time.
The gain is limited by the next-longest path. If the critical path is 20 days and the next path is 19 days, crashing the critical path alone saves at most 1 day; after that both paths are critical and both must be shortened.
Every critical path must be reduced. With two or more critical paths, look for an activity common to all of them, and compare its cost with shortening each path separately.

A clean way to work: list every path and its length, write the target time, then for each path over the target write how much it must lose and which crashable activities lie on it. Choose the cheapest combination that brings every path down to the target, then check that no path is still too long.

Worked examples: scanning, float and crashing

Scanning the network in the figure

Precedence table (days): A 4 and B 3 (none); C 5 and D 6 (A); E 4 (B); F 3 (C); G 5 (C, E); H 7 (D); I 2 (F, G); J 3 (H, I).

Step 1: forward scan: EST(A) $=$ EST(B) $= 0$ . C and D follow A: EST $= 4$ . E follows B: EST $= 3$ . F follows C: EST $= 9$ . G follows C (finishes 9) and E (finishes 7): EST $= \max(9, 7) = 9$ . H follows D: EST $= 10$ . I follows F (finishes 12) and G (finishes 14): EST $= 14$ . J follows H (finishes 17) and I (finishes 16): EST $= 17$ . The project finishes at $17 + 3 = 20$ days.
Step 2: backward scan: J: LST $= 20 - 3 = 17$ . H and I must finish by 17: LST(H) $= 10$ , LST(I) $= 15$ . D: $10 - 6 = 4$ . F and G must finish by 15: LST(F) $= 12$ , LST(G) $= 10$ . C is followed by F (LST 12) and G (LST 10), so it must finish by 10: LST(C) $= 5$ . E: $10 - 4 = 6$ . B: $6 - 3 = 3$ . A is followed by C (LST 5) and D (LST 4): LST(A) $= 4 - 4 = 0$ .
Step 3: float table

Activity	B	C	D	E	F	G	H	I	J
EST	0	4	4	3	9	9	10	14	17
LST	3	5	4	6	12	10	10	15	17
Float	3	1	0	3	3	1	0	1	0

Answer. Minimum completion time 20 days; critical path A-D-H-J. Check with path lengths: A-D-H-J $= 20$ , A-C-G-I-J $= 19$ , A-C-F-I-J $= 17$ , B-E-G-I-J $= 17$ . C, G and I have float 1 because the longest path through them is 1 day shorter than 20.

Crashing at minimum cost

For the same project, H can be reduced by up to 3 days at $200 per day, D by up to 2 days at $350 per day, G by up to 2 days at $150 per day and A by 1 day at $500. Find the minimum cost to finish in 18 days.

Step 1: list the paths against the target: A-D-H-J 20 (must lose 2); A-C-G-I-J 19 (must lose 1); A-C-F-I-J 17 and B-E-G-I-J 17 (already fine).
Step 2: the tempting wrong answer: Reducing H by 2 days ($400) makes A-D-H-J 18 days, but A-C-G-I-J is still 19, so the project takes 19 days, not 18.
Step 3: compare the ways to fix both paths

H 2 days and G 1 day: $2(200) + 150 = 550$ .
A 1 day (on both paths) and H 1 day: $500 + 200 = 700$ .
D 2 days and G 1 day: $2(350) + 150 = 850$ .

Answer. Reduce H by 2 days and G by 1 day for a minimum extra cost of $550. Check: A-D-H-J $= 18$ , A-C-G-I-J $= 18$ , the others are 17 and 16. Going further, 17 days costs $900 (H 3, G 2), and 16 days needs A as well ($1400).

Reading a latest start time straight from a network

In 2025 Examination 2 Question 18b the finish time was 25 days and E was followed by H (7 days) and I (4 days), with J (1), K (4) and L (5) after them.

Step 1: work back from the finish: L starts by $25 - 5 = 20$ , so J starts by $20 - 1 = 19$ and K by $20 - 4 = 16$ .
Step 2: the successors of E: H must finish by 19, so it starts by 12; I must finish by 16, so it starts by 12.
Step 3: take the minimum: E must finish by $\min(12, 12) = 12$ , so LST(E) $= 12 - 3 = 9$ days.

Marker's note: the report's one-line working was $20 - 4 - 4 - 3 = 9$ (back along L's start, K, I and E). Only $46\%$ scored the mark.

Common traps

Taking the minimum in the forward scan or the maximum in the backward scan: Forward: an activity waits for its last predecessor (maximum). Backward: an activity must be ready for its earliest successor (minimum).
Missing a dummy link: A dummy from the end of C to the start of I means C is an immediate predecessor of I. In 2025 Examination 1 Question 40 the link from B to G decided the answer.
Counting the dummy as an activity: It has duration 0 and is not an activity.

Giving the new time instead of the reduction (or the reverse). Read whether the question asks "by how much" or "what is the new completion time" (2023 Examination 2 Question 14d).

Crashing only one critical path: Once another path is as long, the completion time will not fall until every critical path is shortened.
Crashing beyond the next-longest path: Shortening a critical activity by more than the gap to the next path wastes money: the other path now sets the finish time.
Calling the critical path the shortest path: It is the longest path, because every activity on it must be completed in sequence.

Exam technique

For any question with a network, first write the list of start-to-finish paths and their lengths: it gives you the completion time, the critical path(s) and the floats on side branches in one line each, and it is the fastest check on your scans. In crashing questions, write the target time and each path's required reduction before choosing activities. When a table asks for EST and LST, show the max or min you took for any activity with more than one predecessor or successor.

Flow and allocation in brief

The other decision problems in this area of study use different networks and have their own pages.

Maximum flow. In a directed network with edge capacities, the maximum flow from source to sink equals the capacity of the minimum cut. Count only edges that cross the cut from the source side to the sink side. A branch of pipes in series carries only its smallest capacity: pipes of 6 then 4 carry 4, pipes of 5 then 7 carry 5, and the two branches in parallel carry $4 + 5 = 9$ .
Allocation. To assign $n$ people to $n$ tasks at minimum total cost, the Hungarian algorithm subtracts row minima, then column minima, covers the zeros with the fewest lines, adjusts if fewer than $n$ lines are needed, and reads off an assignment of zeros, one in each row and column.

Note

A big job is made of smaller tasks, and some tasks cannot start until others are done. Draw each task as an arrow and join them in order. Working forwards tells you the earliest each task can start and how long the whole job must take. Working backwards tells you the latest each task can start without making the job late. Tasks with no spare time form the critical path: slow any of them down and the whole job is late. To finish sooner, you speed up tasks on the critical path, cheapest first, but only until another chain of tasks becomes just as long.

Exam-style questions

Questions in the style of VCAA exam questions on this dot point, each with a worked answer. They are written by ExamExplained unless tagged "Past paper"; the year shows the paper a question is modelled on.

2025 VCAA-style1 mark

A project has 12 activities with durations in days and immediate predecessors: A 4 (none); B 6 (A); C 8 (A); D 3 (A); E 9 (B); F 6 (C); G 7 (B, D, F); H 12 (C); I 6 (G, H); J 4 (E, I); K 3 (G, H); L 9 (J). The project is to be completed in minimum time. The float time, in days, of Activity B is A. 4 B. 6 C. 8 D. 12

Show worked answer →

Forward scan (EST $=$ largest finish time of the immediate predecessors): A 0; B, C, D 4; E 10; F 12; H 12; G $= \max(10, 7, 18) = 18$ ; I $= \max(25, 24) = 25$ ; J $= \max(19, 31) = 31$ ; K 25; L 35. The project finishes at $35 + 9 = 44$ days.

Backward scan (LST $=$ smallest LST of the immediate successors, minus the duration): L 35, J 31, I 25, K 41, G $25 - 7 = 18$ , E $31 - 9 = 22$ . B is followed by E and G, so B must finish by $\min(22, 18) = 18$ and its LST is $18 - 6 = 12$ .

Float of B $=$ LST $-$ EST $= 12 - 4 = 8$ days: option C. The critical path is A, C, F, G, I, J, L.

Only $39\%$ answered correctly; $24\%$ chose A. The trap is forgetting that B leads to G as well as E. In the network this needs a dummy from the end of B to the start of G, because E follows B alone while G follows B, D and F.

Source: VCAA 2025 General Mathematics Examination 1, Question 40, and the 2025 examination report.

2025 VCAA-style4 marks

A home gym needs 12 activities, A to L (durations in days). The activity network in the paper is equivalent to these immediate predecessors: A 5 and B 4 (none); C 7 and D 7 (A); E 3 and F 6 (B); G 6 (C); H 7 and I 4 (D, E); J 1 (G, H); K 4 (F, I); L 5 (J, K). (a) The network has two critical paths. State the activities common to both. (b) Find the latest start time for E. (c) Which activity has the longest float? (d) A can be reduced by up to 2 days at $500 per day, F by 4 at $150, G by 4 at $150, H by 2 at $300 and K by 1 at $100. What is the minimum additional cost to finish 3 days earlier?

Show worked answer →

Path lengths: A-D-H-J-L $= 25$ , A-D-I-K-L $= 25$ , A-C-G-J-L $= 24$ , B-E-H-J-L $= 20$ , B-E-I-K-L $= 20$ , B-F-K-L $= 19$ .

(a) Both critical paths (25 days) share A, D and L. (1 mark; $44\%$ .)

(b) Backward scan: L starts at 20, J at 19, K at 16. H must finish by 19 so starts by 12; I must finish by 16 so starts by 12. E must finish by $\min(12, 12) = 12$ : LST of E $= 12 - 3 = 9$ days. (1 mark; $46\%$ .)

(c) Floats of the non-critical activities: B 5, C 1, E 5, F 6, G 1. Activity F. (1 mark; $47\%$ . Extra information written in the answer had to be correct.)

(d) The target is 22 days. A-D-I-K-L can only be shortened by A (2 days) and K (1 day), so both are forced: $1000 $+$ $100. A-D-H-J-L is then 23 days, so reduce H by 1 day ($300). A-C-G-J-L is now $24 - 2 = 22$ . Minimum cost $= 1000 + 100 + 300 =$ $1400. (1 mark; only $21\%$ .)

Source: VCAA 2025 General Mathematics Examination 2, Question 18, and the 2025 examination report.

2023 VCAA-style5 marks

A renovation has 12 activities (days): A 6 and B 4 (none); C 7 (A); D 5 and E 10 (B); F 4 (C); G 3 and H 7 (D); I 6; J 6 (E, H); K 4 (F, I); L 1 (J, K). In the network, I starts where G ends, and a dummy runs from the end of C to that node. (a) Write down the immediate predecessor(s) of I. (b) Find the EST of J. (c) How many activities have zero float? (d) If A and B are each reduced by 2 days, what is the maximum reduction in completion time? (e) A, B, F, H, I and K can each be reduced by up to 2 days, at $1500, $2000, $2500, $1000, $1500 and $3000 per day. With a budget of $15 000, give the reductions that achieve the earliest completion time.

Show worked answer →

(a) C and G (C through the dummy). (1 mark; $73\%$ .)

(b) $\text{EST}(J) = \max(\text{EFT}(E), \text{EFT}(H)) = \max(4 + 10, 9 + 7) = 16$ . (1 mark; $59\%$ .)

(c) Forward scan: finish time 24 days. Critical path A-C-I-K-L ( $6 + 7 + 6 + 4 + 1 = 24$ ), so 5 activities have zero float. (1 mark; $35\%$ . Some students counted the dummy, which is not an activity.)

(d) Paths: A-C-I-K-L 24, B-D-G-I-K-L 23, B-D-H-J-L 23, A-C-F-K-L 22, B-E-J-L 21. With A and B each 2 days shorter, the longest path is 22 days, a reduction of 2 days. (1 mark; $33\%$ . Writing the new time, 22, was a common error.)

(e) Reduce A 2, B 2, F 0, H 2, I 2, K 1. Cost $= 2(1500) + 2(2000) + 2(1000) + 2(1500) + 1(3000) = 15\,000$ . Check every path: A-C-I-K-L $24 - 2 - 2 - 1 = 19$ ; B-D-G-I-K-L $23 - 2 - 2 - 1 = 18$ ; B-D-H-J-L $23 - 2 - 2 = 19$ ; A-C-F-K-L $22 - 2 - 1 = 19$ ; B-E-J-L $21 - 2 = 19$ . B-D-H-J-L can lose at most 4 days (B and H), so 19 days is the earliest possible time. (1 mark; only $9\%$ .)

Source: VCAA 2023 General Mathematics Examination 2, Question 14, and the 2023 examination report.

Practice questions

Original practice questions graded from foundation to exam level, each with a full worked solution. Try them before revealing the solution.

foundation3 marks

A project has activities P 3 (none), Q 5 (none), R 4 (P), S 2 (P, Q), T 6 (R), U 3 (S) and V 2 (T, U), durations in days. (a) Find the earliest start time of each activity. (b) Find the minimum completion time. (c) State the critical path.

Show worked solution →

(a) EST $=$ largest finish time of the immediate predecessors:

Activity	P	Q	R	S	T	U	V
EST	0	0	3	$\max(3, 5) = 5$	7	7	$\max(13, 10) = 13$

(1 mark)

(b) V finishes at $13 + 2 = 15$ days. (1 mark)

(c) P-R-T-V ( $3 + 4 + 6 + 2 = 15$ ). The other paths are Q-S-U-V (12) and P-S-U-V (10). (1 mark)

foundation2 marks

In a precedence table, activity M follows K only, and activity N follows both K and L. (a) Explain why the network needs a dummy activity. (b) Describe where the dummy goes and state its duration.

Show worked solution →

(a) M must start from the node where K ends, and N must start from a node where both K and L have ended. One node cannot do both jobs: if L ended at K's node, M would wrongly have to wait for L; if it did not, N would not wait for L. M and N share some but not all predecessors, which is exactly when a dummy is needed. (1 mark)

(b) Draw a dashed dummy from the end of K to the start of N, where N also starts after L. The dummy has duration 0 and is not counted as an activity. (1 mark)

core3 marks

For the project in the first practice question (P 3, Q 5, R 4, S 2 after P and Q, T 6 after R, U 3 after S, V 2 after T and U), use a backward scan to find the latest start time and float of Q, S and U.

Show worked solution →

Start from the finish time of 15. V must start by $15 - 2 = 13$ .

U: must finish by 13, so LST $= 13 - 3 = 10$ ; EST 7, float $= 3$ .
S: must finish by 10 (the LST of U), so LST $= 10 - 2 = 8$ ; EST 5, float $= 3$ .
Q: must finish by 8 (the LST of S), so LST $= 8 - 5 = 3$ ; EST 0, float $= 3$ .

(1 mark each.) All three share the same 3 days of slack because they lie on the same non-critical path Q-S-U, which is 3 days shorter than the critical path.

core2 marks

An activity has an earliest start time of 11 days, a duration of 4 days and a float of 6 days. (a) Find its latest start time. (b) Find its latest finish time.

Show worked solution →

(a) Float $=$ LST $-$ EST, so LST $= 11 + 6 = 17$ days. (1 mark)

(b) Latest finish $=$ LST $+$ duration $= 17 + 4 = 21$ days. (1 mark)

exam4 marks

A project has activities (days): A 2 and B 5 (none); C 4 (A); D 3 (A, B); E 6 (C); F 4 (D); G 2 (D); H 5 (E, F); I 3 (G); J 2 (H, I). (a) Explain why a dummy activity is needed and where it goes. (b) Find the minimum completion time and all critical paths. (c) E can be reduced by up to 2 days at $250 per day, F by 1 day at $300, H by 2 days at $600 and B by 2 days at $400. Find the minimum cost of finishing 1 day earlier.

Show worked solution →

(a) C follows A only, but D follows A and B. A dummy runs from the end of A to the start of D (the node where B ends). (1 mark)

(b) Paths: A-C-E-H-J $= 2 + 4 + 6 + 5 + 2 = 19$ ; B-D-F-H-J $= 5 + 3 + 4 + 5 + 2 = 19$ ; A-D-F-H-J $= 16$ ; B-D-G-I-J $= 15$ ; A-D-G-I-J $= 12$ . Minimum completion time 19 days, with two critical paths: A-C-E-H-J and B-D-F-H-J. (1 mark)

(c) Both critical paths must lose a day. Options:

H by 1 day (on both): $600.
E by 1 and F by 1 (one on each): $250 + 300 = 550$ .
E by 1 and B by 1: $250 + 400 = 650$ .

Minimum cost $550 (reduce E and F by 1 day each). (2 marks: 1 for recognising both paths must be shortened, 1 for the answer.) Reducing only E would leave B-D-F-H-J at 19 days and save nothing.

Practise this

Sources & how we know this

VCE General Mathematics Examination 1 (2023) and examination report — VCAA (2023)
VCE General Mathematics Examination 2 (2023) and examination report — VCAA (2023)
VCE General Mathematics Examination 1 (2025) and examination report — VCAA (2025)
VCE General Mathematics Examination 2 (2025) and examination report — VCAA (2025)
VCE Mathematics Study Design: General Mathematics (from 2023) — VCAA
VCE General Mathematics: examination specifications, past examinations and reports — VCAA