Project networks: CPM and floats

Why it matters

Plant installations, machine overhauls, new-product launches and shutdown maintenance are projects of many interdependent activities. The Critical Path Method (CPM) gives the shortest possible project duration, tells you which activities cannot slip (the critical path) and how much the others can slip (floats). That is what decides where supervisors, overtime and money go.

Key ideas

Network representation.

• Activity-on-arrow (AOA): arrows are activities, nodes are events (instants). Needs dummy activities (zero duration, dashed) to show some dependencies correctly and to keep two activities from sharing the same start and end events.
• Activity-on-node (AON): nodes are activities, arrows show precedence; no dummies needed. CPM assumes deterministic (known, fixed) durations — the probabilistic version is PERT.

Forward pass (earliest times). Start at time 0. ES of an activity = largest EF among its predecessors (a merge takes the maximum). EF = ES + duration. The largest EF is the project duration T.

Backward pass (latest times). Set LF of the final activities = T. LF of an activity = smallest LS among its successors (a burst takes the minimum). LS = LF − duration.

Floats (slack).

• Total float TF = LS − ES = LF − EF: how long an activity can be delayed without delaying the project. Using it may consume float of following activities.
• Free float FF = (earliest ES of successors) − EF: delay possible without delaying the early start of any successor.
• Independent float IF (AOA): delay possible even if predecessors finish as late as possible and successors start as early as possible; negative values are taken as zero.
• Interference float = TF − FF (the part of total float shared with successors). Always 0 ≤ IF ≤ FF ≤ TF.

Critical path. The chain of activities with TF = 0 (the minimum float, if a deadline is imposed), and the longest path from start to finish. There may be more than one. Delaying a critical activity by Δ delays the project by Δ; shortening it helps only until another path becomes critical.

Event slack (AOA). For event i, slack = Lᵢ − Eᵢ. Critical events have zero slack, but an activity joining two critical events is critical only if its own TF is zero.

Formulas

• EF = ES + t
• ES(j) = max{ EF(i) } over predecessors i
• LS = LF − t
• LF(i) = min{ LS(j) } over successors j
• Total float: TF = LS − ES = LF − EF
• Free float: FF = min ES(successors) − EF
• AOA forms for activity i→j: TF = Lⱼ − Eᵢ − t, FF = Eⱼ − Eᵢ − t, IF = Eⱼ − Lᵢ − t (≥ 0)
• Interference float: TF − FF = Lⱼ − Eⱼ

Symbols: t = activity duration (days); ES, EF = earliest start and finish (days); LS, LF = latest start and finish (days); Eᵢ, Lᵢ = earliest and latest occurrence times of event i (days).

Worked examples

Example 1 (AON, standard). Activities (days, predecessors): A 3 (–), B 4 (–), C 2 (A), D 6 (A), E 3 (B, C), F 4 (D, E), G 2 (E).

1. Forward pass: A 0–3, B 0–4, C 3–5, D 3–9, E starts at max(4, 5) = 5 → 5–8, F starts at max(9, 8) = 9 → 9–13, G 8–10. T = max(13, 10) = 13 days.
2. Backward pass: F LF 13, LS 9; G LF 13, LS 11; E LF = min(9, 11) = 9, LS 6; D LF 9, LS 3; C LF 6, LS 4; B LF 6, LS 2; A LF = min(LS C, LS D) = min(4, 3) = 3, LS 0.
3. Total floats: A 0, B 2, C 1, D 0, E 1, F 0, G 3.
4. Free floats: B = ES(E) − EF(B) = 5 − 4 = 1; C = 5 − 5 = 0; E = min(9, 8) − 8 = 0; G = 13 − 10 = 3.
5. Critical path A–D–F, 13 days. C and E share one day of float: if C uses it, E has none left (C's TF 1, FF 0).

Example 2 (GATE-type, AOA event times and floats). Activities (i–j, days): 1–2: 4, 1–3: 6, 2–4: 5, 3–4: 2, 3–5: 7, 4–6: 6, 5–6: 3.

1. Earliest event times: E₁ = 0, E₂ = 4, E₃ = 6, E₄ = max(4 + 5, 6 + 2) = 9, E₅ = 6 + 7 = 13, E₆ = max(9 + 6, 13 + 3) = 16.
2. Latest event times: L₆ = 16, L₅ = 16 − 3 = 13, L₄ = 16 − 6 = 10, L₃ = min(10 − 2, 13 − 7) = 6, L₂ = 10 − 5 = 5, L₁ = min(5 − 4, 6 − 6) = 0.
3. Activity 3–4: TF = L₄ − E₃ − t = 10 − 6 − 2 = 2; FF = E₄ − E₃ − t = 9 − 6 − 2 = 1; IF = E₄ − L₃ − t = 9 − 6 − 2 = 1.
4. Activity 4–6: TF = 16 − 9 − 6 = 1; FF = 16 − 9 − 6 = 1; IF = 16 − 10 − 6 = 0.
5. Activities 1–2 and 2–4 each have TF = 1 and FF = 0.
6. Critical path 1–3–5–6 = 6 + 7 + 3 = 16 days; for activity 3–4, TF = 2, FF = 1, IF = 1 day.

Common mistakes

• Taking the minimum at a merge in the forward pass or the maximum at a burst in the backward pass — it is the reverse.
• Calling the path with the most activities, rather than the longest duration, critical.
• Computing free float from the successor's late start instead of its early start.
• Assuming an activity between two zero-slack events is critical without checking its own float.
• Adding up the total floats of activities on one path as if each could be used independently.
• Leaving out dummies in AOA, so two activities share both end events or a false dependency is created.

For GATE PI

• Project duration and critical path from an activity table (AON or AOA) — NAT.
• Total, free and independent float of a named activity from event times.
• Effect of delaying a given activity by a few days on the project duration.
• Practise both passes in a small table; check that every critical activity has TF = 0 and that the path lengths add to T.

Quick check

1. An activity has ES 4, LS 9, t 3. What is its total float?
2. A merge node receives activities finishing at days 7, 11 and 9. What is the ES of the following activity?
3. An activity with TF = 4 is delayed by 6 days. By how much is the project delayed?
4. Which is larger, free float or total float?

Answers: 1. 5 days. 2. Day 11. 3. 2 days. 4. Total float (TF ≥ FF).