Lesson 19: Network Scheduling: The Critical Path Method (CPM)¶
19.1 Learning Outcomes¶
By the end of this hour a student will be able to:
- Define the basic terms of project networks and draw an AON diagram.
- Perform the forward pass (ES, EF) and the backward pass (LS, LF).
- Compute total float and free float, and identify the critical path.
- Interpret float for resource and risk management.
- Perform crashing to shorten a project at minimum cost.
19.2 Project Networks¶
Definition. A project is a set of interrelated activities, each with a duration and precedence requirements, that together achieve a defined objective.
Basic terminology¶
| Term | Meaning |
|---|---|
| Activity | a task consuming time and resources |
| Event / node | a point in time marking a start or finish |
| Predecessor | an activity that must finish before another can start |
| Successor | an activity that cannot start until another finishes |
| Dummy activity | zero-duration arrow showing a precedence relation only (AOA networks) |
| Path | any chain of activities from project start to finish |
| Critical path | the longest path — it determines the project duration |
| Float / slack | how much an activity can be delayed without harming the project |
Two network conventions¶
| AON (Activity on Node) | AOA (Activity on Arrow) | |
|---|---|---|
| Activities are | nodes | arrows |
| Arrows show | precedence | activities |
| Dummy activities | never needed | often needed |
| Modern usage | standard (MS Project, Primavera) | older textbooks |
CPM versus PERT¶
| CPM | PERT (L20) | |
|---|---|---|
| Durations | deterministic (single estimate) | probabilistic (three estimates) |
| Origin | DuPont, 1957 (plant maintenance) | US Navy Polaris, 1958 |
| Emphasis | cost–time trade-off (crashing) | uncertainty and risk |
| Best for | repetitive projects with known times | novel projects (R&D, construction) |
In practice the two have merged; most software offers both.
19.3 The Forward Pass — Earliest Times¶
Start with \(\text{ES} = 0\) for activities with no predecessors, and work left to right.
The \(\max\) is essential: an activity cannot start until every predecessor has finished, so the latest of them governs.
19.4 The Backward Pass — Latest Times¶
Start with \(\text{LF} = T\) for activities with no successors, and work right to left.
The \(\min\) is essential: an activity must finish before the earliest of its successors must start.
19.5 Float¶
Total float¶
How long activity \(i\) can be delayed without delaying the PROJECT.
The critical path is the chain of zero-float activities from start to finish. Every project has at least one, and it is the longest path through the network.
Free float¶
How long activity \(i\) can be delayed without delaying ANY SUCCESSOR's earliest start.
Always \(0 \le \text{FF} \le \text{TF}\).
| Total float | Free float | |
|---|---|---|
| Delaying by this much affects | nothing (project safe) | nothing at all |
| Delaying beyond it | delays the project | delays a successor, but perhaps not the project |
| Shared between activities? | yes — using it consumes other activities' float | no — belongs to that activity alone |
Independent float¶
Float available even if all predecessors finish as late as possible and all successors start as early as possible. Rarely used in practice.
19.6 Worked Example¶
Project data.
| Activity | Duration (weeks) | Predecessors |
|---|---|---|
| A | 4 | — |
| B | 6 | — |
| C | 3 | A |
| D | 5 | A |
| E | 2 | B, C |
| F | 7 | D |
| G | 4 | E, F |
The network (AON).
(4) (3)
+--- A --------- C ----+
| | | (2)
START | +----- E ----+
| | (5) (7) | (4)
| +--- D ------ F ------+ +---- G ---> END
| | |
| (6) +-------+
+------- B ----------------------->+
Forward pass¶
| Activity | Predecessors | ES \(= \max(\text{EF of preds})\) | EF \(=\) ES \(+ d\) |
|---|---|---|---|
| A | — | 0 | 4 |
| B | — | 0 | 6 |
| C | A | \(\max(4) = 4\) | 7 |
| D | A | \(\max(4) = 4\) | 9 |
| E | B, C | \(\max(6,\ 7) = \mathbf{7}\) | 9 |
| F | D | \(\max(9) = 9\) | 16 |
| G | E, F | \(\max(9,\ 16) = \mathbf{16}\) | 20 |
Note how the \(\max\) operates: E waits for C (finishing at 7), not B (finishing at 6); G waits for F (16), not E (9).
Backward pass¶
Start with \(\text{LF}_G = T = 20\).
| Activity | Successors | LF \(=\min(\text{LS of succs})\) | LS \(=\) LF \(- d\) |
|---|---|---|---|
| G | — | 20 | 16 |
| F | G | \(\min(16) = 16\) | 9 |
| E | G | \(\min(16) = 16\) | 14 |
| D | F | \(\min(9) = 9\) | 4 |
| C | E | \(\min(14) = 14\) | 11 |
| B | E | \(\min(14) = 14\) | 8 |
| A | C, D | \(\min(11,\ 4) = \mathbf{4}\) | 0 |
Note the \(\min\) for A: it must finish by 4 to let D start on time, even though C could wait until 11.
Float and the critical path¶
| Activity | \(d\) | ES | EF | LS | LF | TF | FF | Critical? |
|---|---|---|---|---|---|---|---|---|
| A | 4 | 0 | 4 | 0 | 4 | 0 | 0 | ✓ |
| B | 6 | 0 | 6 | 8 | 14 | 8 | 1 | |
| C | 3 | 4 | 7 | 11 | 14 | 7 | 0 | |
| D | 5 | 4 | 9 | 4 | 9 | 0 | 0 | ✓ |
| E | 2 | 7 | 9 | 14 | 16 | 7 | 7 | |
| F | 7 | 9 | 16 | 9 | 16 | 0 | 0 | ✓ |
| G | 4 | 16 | 20 | 16 | 20 | 0 | 0 | ✓ |
Verify by checking all paths.
| Path | Length |
|---|---|
| \(A\to C\to E\to G\) | \(4+3+2+4 = 13\) |
| \(A\to D\to F\to G\) | \(4+5+7+4 = \mathbf{20}\) ← longest |
| \(B\to E\to G\) | \(6+2+4 = 12\) |
The critical path is the longest path ✓ — and its length equals the project duration.
Reading the float¶
Activity B: TF = 8 but FF = 1.
- B can be delayed up to 8 weeks without delaying the project.
- But delaying B by more than 1 week pushes E's earliest start (from 7 to beyond 7).
- The remaining 7 weeks of B's total float are shared with C and E — if C uses its float, B's shrinks.
Activity E: TF = FF = 7. E's float is entirely its own — delaying E by up to 7 weeks affects nothing at all, because G cannot start before 16 anyway (waiting for F).
19.7 Crashing — the Cost–Time Trade-Off¶
Definition. Crashing shortens an activity by adding resources, at extra cost.
The procedure¶
1. Compute the critical path at NORMAL times
2. Among CRITICAL activities that can still be crashed,
choose the one with the LOWEST cost slope
3. Crash it by 1 unit (or until it hits its crash limit, or another path becomes critical)
4. RECOMPUTE the critical path -- it may have CHANGED
5. If multiple paths are now critical, crash an activity COMMON to all of them,
or one on EACH, whichever is cheaper
6. Repeat until the target duration is met, or no further crashing is possible
Step 4 is the one most often forgotten. Crashing one path can make another path critical, and crashing further on the original path then achieves nothing.
The total-cost trade-off¶
Indirect costs (supervision, site overheads, equipment hire, penalty clauses) accrue per unit time. The optimum duration minimises the sum, and it is generally shorter than the normal duration but longer than the fully crashed one.
19.8 Solved Problems¶
Problem 1 — Full CPM analysis¶
Analyse the project below.
| Activity | Duration (days) | Predecessors |
|---|---|---|
| A | 3 | — |
| B | 4 | — |
| C | 2 | A |
| D | 5 | A, B |
| E | 3 | C |
| F | 4 | D, E |
Solution.
Forward pass.
| Act | ES | EF |
|---|---|---|
| A | 0 | 3 |
| B | 0 | 4 |
| C | \(\max(3) = 3\) | 5 |
| D | \(\max(3, 4) = \mathbf{4}\) | 9 |
| E | \(\max(5) = 5\) | 8 |
| F | \(\max(9, 8) = \mathbf{9}\) | 13 |
Backward pass (\(\text{LF}_F = 13\)).
| Act | Successors | LF | LS |
|---|---|---|---|
| F | — | 13 | 9 |
| E | F | 9 | 6 |
| D | F | 9 | 4 |
| C | E | 6 | 4 |
| B | D | 4 | 0 |
| A | C, D | \(\min(4, 4) = 4\) | 1 |
Float table.
| Act | \(d\) | ES | EF | LS | LF | TF | FF | Critical? |
|---|---|---|---|---|---|---|---|---|
| A | 3 | 0 | 3 | 1 | 4 | 1 | 0 | |
| B | 4 | 0 | 4 | 0 | 4 | 0 | 0 | ✓ |
| C | 2 | 3 | 5 | 4 | 6 | 1 | 0 | |
| D | 5 | 4 | 9 | 4 | 9 | 0 | 0 | ✓ |
| E | 3 | 5 | 8 | 6 | 9 | 1 | 1 | |
| F | 4 | 9 | 13 | 9 | 13 | 0 | 0 | ✓ |
All paths.
| Path | Length |
|---|---|
| \(A\to C\to E\to F\) | \(3+2+3+4 = 12\) |
| \(A\to D\to F\) | \(3+5+4 = 12\) |
| \(B\to D\to F\) | \(4+5+4 = \mathbf{13}\) ✓ |
Note the near-critical paths. Two paths have length 12, only 1 day shorter than critical.
Management implication. Do not focus attention solely on B, D and F. Activities A, C and E have only 1 day of float and must be monitored almost as closely. A project with many near-critical paths carries far more schedule risk than its single critical path suggests.
Problem 2 — Total float versus free float¶
In the §5 example, activity B has TF = 8 and FF = 1. Explain the difference concretely and state the management consequence.
Solution.
The scenario. B has ES = 0, EF = 6, LS = 8, LF = 14. Its only successor is E, with ES = 7.
Free float = 1.
If B is delayed by 1 day, it finishes at 7 — exactly when E is scheduled to start. Nothing else moves.
Delaying B by 5 days (still within TF = 8): B finishes at 11. E cannot start until 11, so E runs 11 → 13, and G still starts at 16 (waiting for F).
But E's earliest start has been pushed from 7 to 11, so E's free float has been consumed: E's remaining float is now \(16 - 13 = 3\), down from 7.
Delaying B by 9 days (beyond TF = 8): B finishes at 15, E runs 15 → 17, and G cannot start until 17 instead of 16.
The management consequence.
| Float type | Who may spend it | Governance |
|---|---|---|
| Free float (1 day for B) | B's owner, unilaterally | devolve — no coordination needed |
| Total float (8 days for B) | only with project-level approval | centralise — it is shared |
A common project-management failure. Each activity owner sees "8 days of float" on the Gantt chart and each uses it, believing they are safe. Collectively they overspend the shared buffer and the project slips — a phenomenon Goldratt called "student syndrome" and addressed with critical chain buffering.
Problem 3 — Crashing to a deadline¶
The §5 project (duration 20 weeks) must finish in 17 weeks. Crash data:
| Activity | Normal time | Crash time | Normal cost | Crash cost |
|---|---|---|---|---|
| A | 4 | 3 | 20 | 26 |
| B | 6 | 4 | 30 | 40 |
| C | 3 | 2 | 15 | 22 |
| D | 5 | 3 | 25 | 35 |
| E | 2 | 2 | 10 | 10 |
| F | 7 | 5 | 40 | 52 |
| G | 4 | 3 | 20 | 28 |
Solution.
Step 1 — cost slopes.
| Activity | Max crash | Cost increase | Slope (₹/week) | Critical? |
|---|---|---|---|---|
| A | 1 | 6 | 6 | ✓ |
| B | 2 | 10 | 5 | ✗ |
| C | 1 | 7 | 7 | ✗ |
| D | 2 | 10 | 5 | ✓ |
| E | 0 | — | — | ✗ |
| F | 2 | 12 | 6 | ✓ |
| G | 1 | 8 | 8 | ✓ |
Step 2 — crash 1 (target 19). Critical path is \(A\to D\to F\to G\). Cheapest critical slope is D at ₹5/week.
Crash D by 1 (5 → 4 weeks). New durations: \(A=4, D=4, F=7, G=4\).
Still the only critical path. Cost so far: ₹5.
Step 3 — crash 2 (target 18). D can be crashed one more week (limit 3).
Crash D by 1 more (4 → 3). \(A{-}D{-}F{-}G = 4+3+7+4 = \mathbf{18}\).
Other paths: 13 and 12. Still critical alone. Cost so far: ₹10.
Step 4 — crash 3 (target 17). D is now at its crash limit. Remaining critical candidates: A (₹6), F (₹6), G (₹8).
Choose A or F, both at ₹6. Take F (it has 2 weeks of crash room, giving future flexibility).
Crash F by 1 (7 → 6). \(A{-}D{-}F{-}G = 4+3+6+4 = \mathbf{17}\) ✓
Other paths: 13, 12. Target met.
Total crashing cost.
Total project cost.
Step 5 — is crashing worthwhile? Suppose indirect costs are ₹8 per week.
| Duration | Direct | Indirect | Total |
|---|---|---|---|
| 20 | 160 | \(20\times8 = 160\) | 320 |
| 19 | 165 | 152 | 317 |
| 18 | 170 | 144 | 314 |
| 17 | 176 | 136 | 312 ← |
| 16 | \(176+6 = 182\) | 128 | 310 ← lower still! |
| 15 | \(182+6 = 188\) | 120 | 308 ← |
| 14 | \(188+8 = 196\) | 112 | 308 |
(Beyond 17: crash A by 1 (₹6) → 16; crash F by 1 more (₹6) → 15; then only G (₹8) remains → 14.)
Advice. "Meeting the 17-week deadline costs ₹16 in crashing but saves ₹32 in indirect costs — a net gain of ₹16. Moreover, crashing further to 15 weeks saves another ₹4. Recommend targeting 15 weeks."
A caveat. Crashing compresses the schedule and removes float, increasing risk. At 15 weeks the near-critical paths may also become critical, making the project fragile. Recommend 16 weeks as a balance — near the cost optimum with slightly more buffer.
Problem 4 — When crashing stops helping¶
Continuing Problem 3, suppose we crash aggressively and reach a duration where a second path becomes critical. Explain what changes and compute the correct next step.
Solution.
When does path \(A\to C\to E\to G\) (length 13) become critical? Only when the main path is crashed down to 13 — which would require crashing \(A{-}D{-}F{-}G\) from 20 to 13, i.e. by 7 weeks. Maximum available crashing on that path is \(1(A)+2(D)+2(F)+1(G) = 6\) weeks, reaching 14.
But note that A and G are on BOTH paths. Crashing A shortens \(A{-}D{-}F{-}G\) and \(A{-}C{-}E{-}G\) simultaneously.
The general rule when multiple paths are critical.
IF an activity lies on ALL critical paths:
crash it -- one crash shortens every path (cheap per week of project time)
ELSE:
must crash one activity on EACH critical path simultaneously
-> cost per week = SUM of those slopes
Worked illustration. Suppose after crashing we reach a state where two paths are critical:
Option 1 — crash A (₹6). A is on both, so both paths shorten by 1 ⟹ project shortens by 1 week for ₹6.
Option 2 — crash D (₹5) and C (₹7). D shortens \(P_1\); C shortens \(P_2\). Project shortens by 1 week for ₹5 + ₹7 = ₹12.
The general principle.
Why this must be checked every iteration. If you continue crashing D after \(P_2\) has become critical, the project duration does not change at all — you pay ₹5 and gain nothing, because \(P_2\) still takes the same time. Recomputing the critical path after every crash is not optional.
Problem 5 — A complete project-management study¶
A software firm must deliver a system. Analyse, identify risks and advise.
| Activity | Description | Duration (weeks) | Predecessors |
|---|---|---|---|
| A | Requirements | 3 | — |
| B | System design | 4 | A |
| C | Database design | 3 | A |
| D | UI development | 5 | B |
| E | Backend development | 6 | B, C |
| F | Integration | 3 | D, E |
| G | Testing | 4 | F |
| H | Documentation | 5 | B |
| I | Deployment | 2 | G, H |
Solution.
Forward pass.
| Act | ES | EF |
|---|---|---|
| A | 0 | 3 |
| B | 3 | 7 |
| C | 3 | 6 |
| D | 7 | 12 |
| E | \(\max(7,6) = 7\) | 13 |
| H | 7 | 12 |
| F | \(\max(12,13) = \mathbf{13}\) | 16 |
| G | 16 | 20 |
| I | \(\max(20, 12) = \mathbf{20}\) | 22 |
Backward pass (\(\text{LF}_I = 22\)).
| Act | LF | LS |
|---|---|---|
| I | 22 | 20 |
| G | 20 | 16 |
| H | 20 | 15 |
| F | 16 | 13 |
| D | 13 | 8 |
| E | 13 | 7 |
| C | \(\min(\text{LS}_E) = 7\) | 4 |
| B | \(\min(8, 7, 15) = \mathbf{7}\) | 3 |
| A | \(\min(3, 4) = 3\) | 0 |
Float table.
| Act | \(d\) | ES | EF | LS | LF | TF | FF | Critical |
|---|---|---|---|---|---|---|---|---|
| A | 3 | 0 | 3 | 0 | 3 | 0 | 0 | ✓ |
| B | 4 | 3 | 7 | 3 | 7 | 0 | 0 | ✓ |
| C | 3 | 3 | 6 | 4 | 7 | 1 | 1 | |
| D | 5 | 7 | 12 | 8 | 13 | 1 | 1 | |
| E | 6 | 7 | 13 | 7 | 13 | 0 | 0 | ✓ |
| F | 3 | 13 | 16 | 13 | 16 | 0 | 0 | ✓ |
| G | 4 | 16 | 20 | 16 | 20 | 0 | 0 | ✓ |
| H | 5 | 7 | 12 | 15 | 20 | 8 | 8 | |
| I | 2 | 20 | 22 | 20 | 22 | 0 | 0 | ✓ |
Advice to the firm.
1. Focus management attention on the critical path. A, B, E, F, G, I have zero float. Any slip on any of them delays delivery day for day. Assign the strongest staff and the tightest monitoring to E (backend, 6 weeks) — the longest critical activity and therefore the largest single risk.
2. Documentation (H) has 8 weeks of float — and it is FREE float. H's owner can start any time between weeks 7 and 15 without coordinating with anyone.
This is the single most actionable finding: 8 person-weeks of effort can be moved to where it matters, at no schedule cost.
3. Near-critical activities need watching. C and D have only 1 week of float. A 2-week slip on either creates a second critical path.
| Path | Length | Slack |
|---|---|---|
| \(A\to B\to E\to F\to G\to I\) | 22 | 0 |
| \(A\to C\to E\to F\to G\to I\) | 21 | 1 |
| \(A\to B\to D\to F\to G\to I\) | 21 | 1 |
| \(A\to B\to H\to I\) | 14 | 8 |
Three of four paths are within 1 week of critical ⟹ the schedule is tight and fragile.
4. Quantify the risk. With 6 activities on the critical path, even modest per-activity variability compounds. If each critical activity has a standard deviation of 0.5 weeks, the path standard deviation is
so a 22-week commitment has roughly a 50 % chance of being met, and a 95 % confident promise would be \(22 + 1.645(1.22) \approx \mathbf{24\ \text{weeks}}\). This is exactly what PERT (L20) formalises.
5. The recommendation.
"Commit to 24 weeks externally while managing to 22 internally. Move documentation staff onto the backend during weeks 7–13. Monitor C and D weekly — they have only 1 week of float. If the deadline is firm at 22 weeks, crash the backend (E) first, as it is the longest critical activity."
6. What CPM does NOT tell you. It assumes durations are known. They are not, especially in software. Use PERT (L20) for the probabilistic view, and re-run the network weekly as actuals come in — a schedule computed once and filed is worthless.
19.9 Practice Problems¶
- Activities: A(2,—), B(3,A), C(4,A), D(2,B,C). Find \(T\) and the critical path. [Ans: \(T=8\), \(A\to C\to D\)]
- If ES = 5, EF = 9, LS = 7, LF = 11, what is TF? [Ans: 2]
- An activity has TF = 5 and FF = 0. Interpret.
- Compute the crash slope: normal (8 days, ₹40), crash (5 days, ₹58). [Ans: ₹6/day]
- Why must the critical path be recomputed after each crash?
- Which is safer to devolve to activity owners, TF or FF? Why?
- A project has 5 paths of lengths 20, 19, 19, 12, 10. Comment on its risk.
19.10 Summary¶
- CPM uses deterministic durations; AON networks need no dummy activities.
- Forward pass: \(\text{ES}_j = \max_i \text{EF}_i\), \(\text{EF}_j = \text{ES}_j + d_j\); project duration \(T = \max \text{EF}\).
- Backward pass: \(\text{LF}_i = \min_j \text{LS}_j\), \(\text{LS}_i = \text{LF}_i - d_i\), starting from \(\text{LF} = T\).
- Total float \(= \text{LS}-\text{ES}\) — delay tolerable without delaying the project; free float \(= \min\text{ES}_{\text{succ}} - \text{EF}\) — delay tolerable without affecting any successor.
- Critical path = the chain of zero-float activities = the longest path, and its length is the project duration.
- Total float is SHARED; free float is not. Publish free float to activity owners and hold total float centrally, or it will be double-spent.
- Crashing: rank critical activities by cost slope \(\frac{\Delta\text{cost}}{\Delta\text{time}}\), crash the cheapest, and recompute the critical path every iteration. Activities on several critical paths are the most valuable to crash.
- The minimum-total-cost duration balances rising direct costs against falling indirect costs, and is often shorter than the deadline.
- Many near-critical paths mean high schedule risk — a fact the single critical path conceals.
Next lesson: L20 — PERT and probabilistic project scheduling.
Practise now: unit2-games-networks-lab.html → CPM/PERT Lab: enter activities, see the network
drawn automatically, with the critical path highlighted and a float table computed live.