Project Scheduling: CPM and PERT

A building, a spacecraft, a software release — every big project is a web of tasks, some of which cannot start until others finish. Pour the foundation before the walls; write the code before you test it. Given all these dependencies and each task's duration, two questions rule the project manager's life: how soon can the whole thing possibly finish, and which tasks must I never let slip? CPM (the Critical Path Method) and PERT (Program Evaluation and Review Technique) answer both, and they did it first for real: PERT was built in the 1950s to manage the Polaris missile programme, CPM by DuPont for plant maintenance.

The project as a network

Draw each activity as a node, and an arrow from activity X to Y whenever Y cannot start until X is done. This is an activity-on-node network — a directed acyclic graph of the whole plan. Consider a five-task project:

Activity	Description	Duration (days)	Must follow
A	Design	3	—
B	Build frame	5	A
C	Prepare parts	2	A
D	Assemble	4	B, C
E	Ship	2	D

There are two routes from start to finish: A\!\to\!B\!\to\!D\!\to\!E and A\!\to\!C\!\to\!D\!\to\!E. The highlighted one is the bottleneck.

The critical path is the longest path

Here is the beautiful paradox at the centre of the subject. The project can only finish once every path through it is complete, so the earliest possible finish is set by the longest path — the critical path. Add up the durations:

A\to B\to D\to E:\; 3+5+4+2 = 14 \text{ days}, \qquad A\to C\to D\to E:\; 3+2+4+2 = 11 \text{ days}.

The critical path is A\!\to\!B\!\to\!D\!\to\!E at 14 days — the shortest time in which the project can possibly be done. "Longest path = shortest possible duration" is not a contradiction: the longest chain of dependencies is exactly what you cannot compress by working in parallel.

Earliest, latest, and slack

A forward pass through the network computes each activity's earliest start (EST) and earliest finish (EFT); a backward pass from the deadline gives the latest start (LST) and latest finish (LFT) that still keep the whole project on time. The gap between them is the activity's slack (or float):

\text{slack} = \text{LST} - \text{EST} = \text{LFT} - \text{EFT}.

An activity with zero slack is critical: delaying it by one day delays the whole project by one day.
The critical path is precisely the chain of zero-slack activities.
Activity C here has slack 14 - 11 = 3 days: its route is 3 days shorter, so C could start up to 3 days late without harm.

This is what makes the method actionable: it tells a manager exactly where a delay is fatal (the critical path) and where there is breathing room (everything with slack).

PERT: when durations are uncertain

CPM assumes each duration is a known number. Real tasks are uncertain, so PERT asks for three estimates per activity — optimistic o, most likely m, and pessimistic p — and models the duration with a Beta distribution whose mean and variance are approximated by

t_e = \frac{o + 4m + p}{6}, \qquad \sigma^2 = \left(\frac{p - o}{6}\right)^{\!2}.

Run CPM on the expected times t_e to find the critical path. Because the total project time is a sum of many independent activity times, the central limit theorem makes that total roughly normal, with mean = sum of the critical t_e and variance = sum of the critical \sigma^2. The chance of finishing by a deadline D is then a simple z-score:

Z = \frac{D - \sum t_e}{\sqrt{\sum \sigma^2}}, \qquad P(\text{done by }D) = \Phi(Z).

The formula t_e = (o + 4m + p)/6 is a tidy approximation to the mean of a Beta distribution — a flexible curve that lives on a finite range [o, p] and can lean either way, unlike a symmetric bell. Weighting the most-likely value four times reflects that reality clusters near m, while the extremes still nudge the average. Dividing the range by 6 for the standard deviation comes from the rough idea that o and p sit about three standard deviations either side of the mean — six of them across the whole span. They are engineering approximations, not sacred truths, but they have scheduled everything from submarines to Olympic Games.

PERT computes the finish-time distribution from the critical path alone — but that is only the critical path of the expected durations. A second path that is nearly as long, yet far more variable, can easily overrun and become the true bottleneck on the day. Ignoring these near-critical paths makes PERT optimistic: it systematically underestimates the expected project length because it forgets that whichever path happens to be longest is what actually governs. When several paths have similar length, watch them all — and treat PERT's probability as a hopeful upper bound, not a promise.