Critical Path Analysis

Critical path analysis plans a project made of activities, some of which must wait for others. It was worth 5 marks in NESA's sample HSC paper, often as one longer question that takes you from a table all the way to the critical path. The method is the same every time, so practise it until it is automatic.

• Draw a network from a precedence table (up to 10 activities), including dummy activities where needed.
• Use forward scanning and backward scanning to find the earliest start time (EST) and latest start time (LST) of each activity.
• Calculate float time, and identify critical and non-critical activities.
• Find the critical path(s) and the minimum completion time.
• Draw a Gantt chart from a network.
• Examine what happens when an activity takes longer or shorter, and use a spreadsheet to model a project.

A precedence table lists each activity, its duration and its immediate prerequisites: the activities that must be finished before it can start.

In the network, each activity is an edge (an arrow) labelled with its letter and duration. The vertices are events: moments when activities finish and others can begin. There is one start vertex and one finish vertex.

Worked example: the project

A school is building a garden. Times are in days.

Draw it like this (vertices numbered 1 to 6):

• A goes from 1 to 2, and B goes from 1 to 3.
• C goes from 2 to 4, and D goes from 2 to 3. E needs B and D, so both end at vertex 3.
• E goes from 3 to 5. F and H both need only C, so they start at vertex 4: F goes from 4 to 5, H from 4 to 6.
• G needs E and F, so it starts at vertex 5 and goes to the finish, 6. H also ends at 6.

Check against the table: every activity starts at a vertex where all its prerequisites, and only those, have finished.

Dummy activities

Sometimes one activity needs both X and Y, while another needs only Y. You can't make both happen at one vertex. A dummy activity is a dashed arrow with duration 0 that carries the "Y is finished" information from one vertex to another without adding time. It shows a dependency, not real work.

Example. P (3 days) and Q (4 days) have no prerequisites; R (2 days) needs P and Q; S (5 days) needs only Q. Draw P from 1 to 2 and Q from 1 to 3. S starts at vertex 3 (only Q finished). R must wait for Q too, so draw a dummy (dashed, 0 days) from 3 to 2, and start R at vertex 2. Forward scan: vertex 2 has EST max(0 + 3, 4 + 0) = 4.

Forward scan: earliest start times

Start at vertex 1 with EST 0. Move forwards. At each vertex, the EST is the largest value of (EST of the previous vertex + duration) over all the arrows coming in, because every prerequisite must be done.

The EST at the finish is the minimum completion time: 16 days.

Backward scan: latest start times

Start at the finish with 16. Move backwards. At each vertex, take the smallest value of (later vertex − duration) over all the arrows going out, so no later activity is delayed.

For each activity:

Float time is how long an activity can be delayed without delaying the whole project. An activity with zero float is critical.

For example, B can start at day 0 but needn't start until day 3: it has 3 days of float. H can start at day 9 but must finish by day 16, so its LST is $16-5=11$ and its float is 2 days.

The critical path is a path from start to finish made only of critical activities. Its length is the minimum completion time. This project has two critical paths:

Checking that each critical path adds up to the minimum completion time is a quick way to catch errors.

A Gantt chart shows the project against a time scale. Each activity is a horizontal bar starting at its EST and as long as its duration; float is often shown as a dashed or lighter extension after the bar. Critical activities have no float and are usually shaded or labelled. In the garden project, the bar for H runs from day 9 to day 14, followed by 2 days of float to day 16. A Gantt chart makes it easy to see which activities happen at the same time, which helps when planning workers.

The bars for the garden project (times in days):

• If a critical activity takes longer, the whole project takes longer by the same amount (on that path).
• If a non-critical activity takes longer by no more than its float, the finish time doesn't change. If it is delayed by more than its float, the project is delayed by the extra amount, and the critical path changes.
• Shortening a critical activity only helps if it is on every critical path. Here, shortening C by 1 day does nothing, because A–D–E–G still takes 16 days.

Example. B is delayed by 4 days, so it takes 7 days. Its float is 3, so the project is delayed by $4-3=1$ day, to 17 days. Check: vertex 3 now has EST max(0 + 7, 4 + 2) = 7, vertex 5 has max(7 + 6, 9 + 3) = 13, and the finish is $13+4=17$.

A spreadsheet can hold the precedence table with formulas for EST, LST and float, so you can change a duration and see the effect instantly.

• Using the smallest value in the forward scan or the largest in the backward scan. Forward: largest. Backward: smallest.
• Drawing an activity from a vertex where some, but not all, of its prerequisites have finished.
• Treating "prerequisites" as all earlier activities rather than the ones listed.
• Finding only one critical path when there are two.
• Saying a delay to a non-critical activity always delays the project. Compare the delay with its float.
• Adding the durations of every activity to get the completion time. Activities run at the same time.

• Write the EST and latest time in boxes at each vertex, so the marker can follow your scans.
• State the critical path as a list of activities (A–C–F–G) and give the minimum completion time with units.
• Explain questions about delays need a number (the float, or the new completion time) and a sentence in context.
• If you're asked for the float of one activity, show $\text{LST}-\text{EST}$ with numbers.

• Networks, paths and trees (Year 11): vertices, directed edges and finding the longest or shortest path.
• Network flow: another directed network, where the weights are capacities instead of times.