Skip to content

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:

  1. Define the basic terms of project networks and draw an AON diagram.
  2. Perform the forward pass (ES, EF) and the backward pass (LS, LF).
  3. Compute total float and free float, and identify the critical path.
  4. Interpret float for resource and risk management.
  5. 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
\[ \boxed{\ \textbf{This course uses AON — it is simpler and needs no dummies.}\ } \]

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

\[ \boxed{\ \text{ES}_j \ =\ \max_{i \in \text{predecessors}(j)} \ \text{EF}_i, \qquad \text{EF}_j \ =\ \text{ES}_j + d_j\ } \]

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.

\[ \boxed{\ \textbf{Project duration } T \ =\ \max_j \text{EF}_j\ } \]

19.4 The Backward Pass — Latest Times

\[ \boxed{\ \text{LF}_i \ =\ \min_{j\in\text{successors}(i)}\ \text{LS}_j, \qquad \text{LS}_i \ =\ \text{LF}_i - d_i\ } \]

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

\[ \boxed{\ \text{TF}_i \ =\ \text{LS}_i - \text{ES}_i \ =\ \text{LF}_i - \text{EF}_i\ } \]

How long activity \(i\) can be delayed without delaying the PROJECT.

\[ \boxed{\ \textbf{Critical activity} \iff \text{TF} = 0\ } \]

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

\[ \boxed{\ \text{FF}_i \ =\ \min_{j\in\text{successors}(i)}\text{ES}_j \ -\ \text{EF}_i\ } \]

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
\[ \boxed{\ \textbf{Free float is "safe" float. Total float is shared and must be managed centrally.}\ } \]

Independent float

\[ \text{IF}_i = \max\Big(0,\ \min_j \text{ES}_j - \max_k\text{LF}_k - d_i\Big) \]

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
\[ \boxed{\ \textbf{Project duration } T = 20 \ \text{weeks}\ } \]

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 ✓
\[ \boxed{\ \textbf{Critical path: } A \to D \to F \to G, \qquad \text{length } 4+5+7+4 = 20\ \checkmark\ } \]

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).

\[ \boxed{\ \textbf{Manage total float centrally; free float can be devolved to activity owners.}\ } \]

19.7 Crashing — the Cost–Time Trade-Off

Definition. Crashing shortens an activity by adding resources, at extra cost.

\[ \boxed{\ \text{Crash cost slope} \ =\ \frac{\text{crash cost} - \text{normal cost}} {\text{normal time} - \text{crash time}} \qquad (\text{₹ per unit time saved})\ } \]

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

\[ \text{Total cost} = \underbrace{\text{direct costs}}_{\text{rise when crashing}} + \underbrace{\text{indirect costs}}_{\text{fall with duration}} \]

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
\[ T = \mathbf{13\ \text{days}} \]

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 ✓
\[ \boxed{\ \textbf{Critical path: } B \to D \to F, \qquad 4+5+4 = 13\ \checkmark\ } \]

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.

\[ \boxed{\ \textbf{This project is FRAGILE: a 1-day slip on A, C or E makes a second path 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.

\[ \text{FF}_B = \text{ES}_E - \text{EF}_B = 7 - 6 = \mathbf{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).

\[ \textbf{The project is NOT delayed} \ \checkmark \]

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.

\[ \boxed{\ \textbf{B's total float was SHARED with C and E. Using it took float away from them.}\ } \]

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.

\[ \textbf{Project duration becomes 21 — DELAYED by 1 day.} \]

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
\[ \boxed{\ \textbf{Publishing total float to activity owners invites double-spending. Publish FREE float; hold TF centrally.}\ } \]

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\).

\[ \text{Path } A{-}D{-}F{-}G = 4+4+7+4 = \mathbf{19} \]
\[ \text{Path } A{-}C{-}E{-}G = 4+3+2+4 = 13, \qquad \text{Path } B{-}E{-}G = 6+2+4 = 12 \]

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.

\[ \boxed{\ \textbf{Crash D by 2 weeks and F by 1 week. Project duration 17 weeks.}\ } \]

Total crashing cost.

\[ 2\times₹5 + 1\times₹6 = 10 + 6 = \mathbf{₹16} \]

Total project cost.

\[ \text{Normal direct} = 20+30+15+25+10+40+20 = ₹160 \]
\[ \text{Crashed direct} = 160 + 16 = \mathbf{₹176} \]

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.)

\[ \boxed{\ \textbf{The minimum-total-cost duration is 15 weeks at ₹308 — SHORTER than the 17-week deadline.}\ } \]

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.

\[ \boxed{\ \textbf{The absolute minimum duration is 14 weeks.}\ } \]

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:

\[ P_1: A\to D\to F\to G \qquad\text{and}\qquad P_2: A\to C\to E\to G \]

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.

\[ \boxed{\ \textbf{Crashing A costs ₹6; crashing D and C costs ₹12. Choose the common activity.}\ } \]

The general principle.

\[ \boxed{\ \textbf{Activities on MULTIPLE critical paths are the most valuable to crash — one payment, several savings.}\ } \]

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
\[ \boxed{\ \textbf{Project duration} = 22\ \text{weeks}\ } \]

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 ✓
\[ \boxed{\ \textbf{Critical path: } A\to B\to E\to F\to G\to I, \quad 3+4+6+3+4+2 = 22\ \checkmark\ } \]

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.

\[ \boxed{\ \textbf{Redeploy documentation staff to the critical path during weeks 7–13, then write documentation in weeks 13–18.}\ } \]

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

\[ \sigma_{\text{path}} = \sqrt{6\times0.5^2} = \sqrt{1.5} = 1.22 \ \text{weeks} \]

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

  1. 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\)]
  2. If ES = 5, EF = 9, LS = 7, LF = 11, what is TF? [Ans: 2]
  3. An activity has TF = 5 and FF = 0. Interpret.
  4. Compute the crash slope: normal (8 days, ₹40), crash (5 days, ₹58). [Ans: ₹6/day]
  5. Why must the critical path be recomputed after each crash?
  6. Which is safer to devolve to activity owners, TF or FF? Why?
  7. 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.