Network models: PERT and CPM

Why it matters

Commissioning a production line, overhauling a plant or launching a product involves dozens of activities that depend on one another. PERT and CPM show which activities control the finish date, how much other activities can slip, and how likely you are to meet a deadline — the information a project engineer reports every week.

Key ideas

• Project network. Activities, their durations and precedence relations form a network.
  • Activity-on-arrow (AOA): activities are arrows, events (nodes) are their start and end points. A dummy activity (zero time, dashed arrow) is added only to show a dependency correctly or to keep two activities from sharing the same start and end events.
  • Activity-on-node (AON): activities are nodes; no dummies are needed.
  • Rules: one start and one end event, no loops, no dangling activities.
• Forward pass. Earliest start ES of an activity = largest earliest finish EF of all its predecessors (0 for start activities); EF = ES + t. Project duration T = largest EF.
• Backward pass. Latest finish LF = smallest latest start LS of all its successors (T for end activities); LS = LF − t.
• Floats.
  • Total float TF = LS − ES = LF − EF: how long the activity can slip without delaying the project.
  • Free float FF = (earliest ES of the successors) − EF: how long it can slip without delaying any successor's earliest start.
  • Independent float — the slack left even if predecessors finish late and successors must start early (can be negative, then taken as zero).
  • FF ≤ TF always. A negative total float means the target date is already impossible.
• Critical path. The longest path from start to end; all its activities have zero total float (when the target date equals T). Delaying any critical activity delays the project. There may be more than one critical path.
• CPM (Critical Path Method). Deterministic durations; used where time is well known (construction, maintenance). Adds time–cost trade-off: crashing shortens critical activities by spending more on resources. Crash the critical activity with the lowest cost slope first, one step at a time, and re-check the critical path because new paths can become critical. Total cost = direct (rises when crashing) + indirect (falls with shorter duration); the optimum duration minimises the sum.
• PERT (Program Evaluation and Review Technique). Probabilistic durations for new or R&D work. Each activity has an optimistic time a, most likely time m and pessimistic time b, modelled by a beta distribution. Expected time and variance follow from them.
• Project completion probability. The project time along the critical path is the sum of many independent activity times, so by the central limit theorem it is approximately normal with mean T_E = Σ tₑ and variance Σ σ² of critical activities. Z = (T_s − T_E)/σ_p gives the probability of finishing by the scheduled time T_s from the normal table. If two paths are nearly equal, the path with the larger variance can matter; standard PERT uses only the critical path, a known limitation.
• Resource smoothing and levelling. Using floats to shift non-critical activities so the daily demand for crews or machines is steadier.

Formulas

• Forward pass: ES_j = max(EF_i) over all predecessors i; EF_j = ES_j + t_j
• Backward pass: LF_i = min(LS_j) over all successors j; LS_i = LF_i − t_i
• Total float: TF = LS − ES = LF − EF
• Free float: FF = min(ES of successors) − EF
• PERT expected time: tₑ = (a + 4m + b) / 6
• PERT activity variance: σ² = ((b − a) / 6)²
  • a, m, b = optimistic, most likely, pessimistic times (days or weeks, all in the same unit).
• Project mean and variance (critical path): T_E = Σ tₑ, σ_p² = Σ σ² (add variances, never standard deviations)
• Standard normal variate: Z = (T_s − T_E) / σ_p; probability of completion P(T ≤ T_s) = Φ(Z) from the normal table (Φ(0) = 0.5, Φ(1) = 0.8413, Φ(1.645) = 0.95, Φ(2) = 0.9772).
• Crashing cost slope: slope = (crash cost − normal cost) / (normal time − crash time) in ₹ per day.

Worked examples

Example 1 (standard): CPM forward and backward pass Activities (predecessor, duration in days): A (–, 4), B (–, 6), C (A, 5), D (A, 3), E (B and D, 4), F (C and E, 2).

1. Forward pass:
   • A: ES 0, EF 4. B: ES 0, EF 6.
   • C: ES = EF(A) = 4, EF 9. D: ES 4, EF 7.
   • E: ES = max(EF B, EF D) = max(6, 7) = 7, EF 11.
   • F: ES = max(EF C, EF E) = max(9, 11) = 11, EF 13. Project duration T = 13 days.
2. Backward pass (LF of F = 13):
   • F: LS 11. E: LF 11, LS 7. C: LF 11, LS 6.
   • D: LF = LS(E) = 7, LS 4. B: LF 7, LS 1.
   • A: LF = min(LS C, LS D) = min(6, 4) = 4, LS 0.
3. Total floats: A 0, B 1, C 2, D 0, E 0, F 0. Free floats: B = ES(E) − EF(B) = 7 − 6 = 1; C = ES(F) − EF(C) = 11 − 9 = 2. Answer: Critical path A–D–E–F, duration 13 days; B can slip 1 day and C 2 days.

Example 2 (GATE level): PERT probability Critical path has three activities with (a, m, b) in days: P (2, 5, 14), Q (3, 6, 9), R (4, 7, 16).

1. Expected times: tₑ(P) = (2 + 20 + 14)/6 = 6; tₑ(Q) = (3 + 24 + 9)/6 = 6; tₑ(R) = (4 + 28 + 16)/6 = 8 days.
2. Variances: σ²(P) = (12/6)² = 4; σ²(Q) = (6/6)² = 1; σ²(R) = (12/6)² = 4 days².
3. T_E = 6 + 6 + 8 = 20 days; σ_p² = 4 + 1 + 4 = 9 days², σ_p = 3 days.
4. Probability of finishing in 23 days: Z = (23 − 20)/3 = 1.0 → P = Φ(1.0) = 0.8413.
5. Duration for 95% confidence: T_s = T_E + 1.645·σ_p = 20 + 4.94 = 24.9 days. Answer: T_E = 20 days, P(finish ≤ 23 days) ≈ 84.1%, and about 25 days are needed for 95% confidence.

Common mistakes

• Taking the minimum instead of the maximum EF of predecessors in the forward pass (or the maximum LS in the backward pass).
• Adding standard deviations of activities instead of variances.
• Using all activities' variances rather than only those on the critical path.
• Writing σ² = (b − a)/6 — that is σ, not the variance.
• Confusing total float with free float; only total float decides criticality.
• Crashing a non-critical activity, or crashing past the point where another path becomes critical without re-checking.
• Using dummy activities in AON networks, or omitting a needed dummy in AOA.

For GATE ME

Questions give an activity table or network and ask for project duration, the critical path, total or free float of a named activity, or the expected time and variance of a PERT activity. Probability questions need T_E, σ_p and a Z value (the normal-table value is usually given). Crashing questions ask for the minimum cost to cut the duration by a few days. Practise forward/backward passes quickly in a table.

Quick check

1. An activity has ES = 5, EF = 9, LS = 8, LF = 12. What is its total float?
2. a = 4, m = 6, b = 14 days. Find tₑ and σ².
3. If T_s equals T_E, what is the probability of completing on time?
4. Why is a dummy activity used in an AOA network?
5. Which activity should be crashed first?

Answers: 1. 3 days. 2. tₑ = (4 + 24 + 14)/6 = 7 days; σ² = (10/6)² ≈ 2.78 days². 3. 50%. 4. To show a dependency correctly or to give two parallel activities distinct end events; it takes no time or resources. 5. The critical activity with the lowest cost slope.