Critical Path Method (CPM)

389. Critical Path Method (CPM)

What’s the shortest possible time to finish the whole project, and which tasks are “tight” (any delay on them delays the whole project)

Let $𝐺 = (𝑉, 𝐸)$ be a DAG with a duration of $𝑑 (𝑣) \geq 0$ on each node. And edge $(𝑢, 𝑣)$ means $𝑢$ must finish before $𝑣$ starts. $pred (𝑣)$ and $succ (𝑣)$ for in- and out-neighbors.

Forward Pass (one recurrence)

EF (𝑣) = 𝑑 (𝑣) + max_{𝑢 \in pred (𝑣)} EF (𝑢), ES (𝑣) = EF (𝑣) - 𝑑 (𝑣)

with $max ⦰ = 0$ (sources get $ES = 0$ ).

The makespan is $𝑇 = {max}_{𝑣} EF (𝑣)$ .

Backward Pass (dual recurrence)

LF (𝑣) = min_{𝑤 \in succ (𝑣)} LS (𝑤), LS (𝑣) = LF (𝑣) - 𝑑 (𝑣)

with $min ⦰ = 𝑇$ (sinks get pinned to project end)

Clack & Critical Pass

slack (𝑣) = LS (𝑣) - ES (𝑣) = LF (𝑣) - EF (𝑣)

$Critical path = {𝑣 : slack (𝑣) = 0}$

Example

Let’s compute. We start the project at time 0.

A has no predecessors, so ES = 0, and EF = 0 + 3 = 3.
B depends only on A, so ES = EF(A) = 3, and EF = 3 + 4 = 7.
C also depends only on A, so ES = EF(A) = 3, and EF = 3 + 2 = 5.
D depends only on B, so ES = EF(B) = 7, and EF = 7 + 5 = 12.
E depends only on C, so ES = EF(C) = 5, and EF = 5 + 1 = 6.