Network models: PERT and CPM

Why it matters

Launching a new vehicle model, commissioning a press line or doing a plant shutdown overhaul involves hundreds of activities that depend on one another. CPM finds the chain of activities that fixes the completion date and shows where there is slack; PERT adds the uncertainty of each estimate and gives the probability of finishing on time; crashing shows the cheapest way to shorten the project. Network calculations (forward and backward pass, floats, PERT probability, crashing) are among the most reliable scoring areas in GATE industrial engineering.

Key ideas

Network representation.

• Activity on node (AON): each activity is a node; arrows show precedence. No dummies needed. Used by most software.
• Activity on arrow (AOA): each activity is an arrow between two events (nodes). Dummy activities (zero duration, dashed) are needed to show some dependencies correctly and to keep two activities from sharing the same start and end events.
• Rules: one start and one end node, no loops, no dangling activities.

Forward and backward pass.

• Forward pass gives the earliest start (ES) and earliest finish (EF = ES + t); an activity's ES is the largest EF of its predecessors. The largest EF of the end activities is the project duration.
• Backward pass, starting from the project duration, gives the latest finish (LF) and latest start (LS = LF − t); an activity's LF is the smallest LS of its successors.

Floats.

• Total float (TF) = LS − ES = LF − EF: how long an activity can slip without delaying the project.
• Free float (FF) = (smallest ES of successors) − EF: how long it can slip without delaying any successor's earliest start.
• Independent float = (smallest ES of successors) − (largest LF of predecessors) − t (if negative, take 0): slack available even if predecessors finish late and successors must start early.
• In AOA terms, with event times E (earliest) and L (latest): TF = L_j − E_i − t, FF = E_j − E_i − t, IF = E_j − L_i − t.
• The critical path is the longest path through the network; its activities have zero total float (when the target equals the computed duration). There can be more than one critical path.

PERT. Each activity has three estimates: optimistic a, most likely m, pessimistic b, assumed to follow a beta distribution. The expected time and variance are computed for each activity. The project duration is taken as the sum of expected times along the critical path, and — by the central limit theorem — approximately normal, with variance equal to the sum of the variances of critical activities (activities are assumed independent). Probability of meeting a due date comes from the standard normal table. Limitation: a near-critical path with high variance can make the true probability lower than PERT predicts.

CPM and time–cost trade-off. CPM uses a single deterministic time per activity and, in its full form, a normal and a crash time and cost. Direct cost rises as the project is shortened; indirect cost (overheads, penalties, lost sales) falls. Crashing: repeatedly shorten the critical activity with the lowest cost slope; when several paths become critical, shorten all of them together, choosing the cheapest combination; stop when the extra direct cost per day exceeds the indirect saving per day, or when no critical activity can be crashed further. The minimum of total cost gives the optimum duration.

PERT versus CPM. PERT is event-oriented and probabilistic, suited to R&D and first-of-a-kind work. CPM is activity-oriented and deterministic, suited to repetitive construction and maintenance with known times, and it includes cost.

Formulas

t_e = (a + 4m + b) / 6

• Expected activity time (days); a, m, b = optimistic, most likely, pessimistic times (days).

σ² = ((b − a) / 6)²

• Activity variance (days²); σ = (b − a)/6 is the standard deviation (days).

T_E = Σ t_e (critical path), σ_T² = Σ σ² (critical path)

• Expected project duration (days) and its variance (days²).

Z = (T_S − T_E) / σ_T

• Standard normal variable; T_S = scheduled (target) completion time (days). P(T ≤ T_S) = Φ(Z) from the normal table.

EF = ES + t, LS = LF − t, TF = LS − ES, FF = min ES(successors) − EF

Cost slope = (C_c − C_n) / (t_n − t_c)

• ₹/day; C_c, C_n = crash and normal cost (₹); t_n, t_c = normal and crash time (days).

Worked examples

Example 1 (standard) — CPM. Activities (days, predecessors): A 4 (–), B 6 (–), C 3 (A), D 5 (A), E 4 (B, C), F 3 (D, E).

1. Forward pass: A 0–4; B 0–6; C 4–7; D 4–9; E starts at max(6, 7) = 7, ends 11; F starts at max(9, 11) = 11, ends 14. Duration = 14 days.
2. Backward pass: F LF 14, LS 11; E LF 11, LS 7; D LF 11, LS 6; C LF 7, LS 4; B LF 7, LS 1; A LF = min(4, 6) = 4, LS 0.
3. Total floats: A 0, B 1, C 0, D 2, E 0, F 0. Free floats: B = 7 − 6 = 1; D = 11 − 9 = 2; others 0.

Answer: critical path A–C–E–F, 14 days; B has 1 day and D 2 days of float.

Example 2 (GATE level) — PERT probability. For the same network the critical activities have (a, m, b) = A (2, 4, 6), C (1, 3, 5), E (2, 4, 6), F (1, 3, 5) days. Find the probability of finishing within 16 days.

1. t_e: A = (2 + 16 + 6)/6 = 4; C = (1 + 12 + 5)/6 = 3; E = 4; F = 3 → T_E = 14 days.
2. Each σ² = (4/6)² = 0.444 → σ_T² = 4 × 0.444 = 1.778 → σ_T = 1.333 days.
3. Z = (16 − 14) / 1.333 = 1.5 → Φ(1.5) = 0.9332.

Answer: about 93.3 % chance of finishing within 16 days.

Example 3 (GATE level) — crashing. Same network; indirect cost ₹5,000/day. Cost slopes (₹/day, maximum crash): A 3,000 (1), B 1,000 (1), C 2,000 (1), D 2,500 (1), E 4,000 (2), F 6,000 (1). Paths: A–C–E–F 14, B–E–F 13, A–D–F 12.

1. Crash C by 1 day (₹2,000 < ₹5,000): duration 13; now A–C–E–F = B–E–F = 13. Saving ₹3,000.
2. Both 13-day paths share E: crash E by 1 (₹4,000 < ₹5,000): duration 12; all three paths are 12. Saving ₹1,000.
3. To go to 11 days all three paths must shorten. Cheapest: F alone (₹6,000), or E + D (₹6,500), or E + A (₹7,000). All exceed ₹5,000 — stop.

Answer: optimum duration 12 days; total cost ₹4,000 lower than at 14 days.

Common mistakes

• Taking the minimum EF of predecessors in the forward pass (it is the maximum) or the maximum LS of successors in the backward pass (it is the minimum).
• Adding standard deviations along the critical path; variances add, then take the square root.
• Using (b − a)/6 as the variance; that is the standard deviation.
• Including variances of non-critical activities in the project variance.
• Crashing a non-critical activity, or crashing beyond the point where a new path becomes critical without shortening that path too.
• Confusing free float with total float: free float can never exceed total float.

For GATE ME

Expect forward/backward passes on 6–10 activity networks, total and free float, PERT expected time, variance and probability of completion, and crashing to find the minimum-cost duration. Conceptual questions test dummy activities, the beta distribution assumption and the difference between PERT and CPM. Practise writing ES/EF/LS/LF in a table — it is faster and less error-prone than marking the diagram.

Quick check

1. a = 2, m = 5, b = 14 days. Find t_e and σ².
2. An activity has ES = 8, LS = 11, t = 4. What is its total float?
3. Critical-path variances are 1, 4 and 4 days². What is σ_T?
4. T_E = 30 days. What is the probability of finishing in 30 days?
5. Normal 10 days ₹20,000; crash 7 days ₹29,000. Cost slope?

Answers: 1. t_e = 36/6 = 6 days; σ² = (12/6)² = 4 days². 2. 3 days. 3. 3 days. 4. 50 %. 5. ₹3,000 per day.