Construct an activity network, use forward and backward scanning to find earliest and latest start times, floats and the critical path, determine the maximum flow through a network using the minimum cut, and solve an allocation problem with the Hungarian algorithm

What this dot point is asking

VCAA wants you to use networks to make decisions: schedule a project with critical path analysis, find the maximum flow through a capacitated network, and solve an allocation problem with the Hungarian algorithm. These three techniques make up the decision-mathematics half of the module and are reliable Exam 2 questions where the analysis is methodical and the marks reward correct procedure.

Critical path analysis

Each activity is scheduled by two scans through the network.

• Forward scan gives the earliest start time (EST) of each activity: it cannot start until all its predecessors finish, so the EST is the largest finishing time among them.
• Backward scan gives the latest start time (LST): the latest an activity can begin without delaying the project.

The float (slack) of an activity is

Activities with zero float lie on the critical path and cannot be delayed at all. Delaying any critical activity delays the whole project.

Maximum flow and minimum cut

A flow network has a source, a sink, and directed edges each with a capacity. The maximum flow is the greatest amount that can pass from source to sink. A cut separates the source from the sink; its capacity is the sum of the capacities of the edges crossing it from the source side to the sink side. The maximum-flow minimum-cut principle states:

Allocation and the Hungarian algorithm

An allocation problem assigns $n$ workers to $n$ tasks (a bipartite matching) to minimise total cost or time. The Hungarian algorithm works on the cost matrix:

1. Subtract the smallest entry in each row from that row.
2. Subtract the smallest entry in each column from that column.
3. Cover all zeros with the fewest possible horizontal or vertical lines. If the number of lines equals $n$, an optimal assignment of zeros exists.
4. If fewer than $n$ lines are needed, subtract the smallest uncovered entry from all uncovered entries, add it to entries covered twice, and repeat from step 3.

The optimal allocation reads off the positions of an independent set of zeros, one in each row and column.

Why this matters for the exams

Decision mathematics rewards careful bookkeeping, so set out forward and backward scans, cuts, and Hungarian tables clearly. Exam 2 typically presents a project network and asks for the minimum completion time, the critical path and a float, or a maximum flow value. Method marks are available even when the final number is wrong, so always show each scan and each cut.