The idea: the longest chain of tasks sets the end date

A project is a set of tasks. Each task takes some days, and some tasks must wait for others: you cannot test the code before it is written. Tasks that do not depend on each other can run at the same time. So the project does not take the sum of all the durations. It takes as long as the longest chain of tasks that wait for each other. That chain is the critical path. The critical path method (CPM) finds it with two passes over the task network, and also tells you how far every other task can slip without harm.

Left, the forward pass: Testing waits for Backend, which finishes on day 12, and Frontend, which finishes on day 9, so its earliest start is the larger one, 12. Right, the backward pass: Spec comes before UI design, Database and Docs, whose latest starts are 6, 3 and 13, so its latest finish is the smallest one, 3
Forward, a task takes the largest finish of the tasks before it; backward, it takes the smallest start of the tasks after it.

The task network

The page uses a small software project. Each box in the animation is a task, and an arrow from X to Y means Y waits for X. The network has no cycle (a task cannot wait for itself), so it is a DAG.

TaskDaysWaits for
A Spec3nothing
B UI design2A
C Database4A
D Backend5C
E Frontend4B
F Docs2A
G Testing3D and E
H Release1G and F

The durations add up to 24 days, but the project takes only 16. Times are counted from the project start: a task with start 3 and finish 7 runs during days 4, 5, 6 and 7.

Forward pass: earliest start and finish

Take the tasks in an order where each one comes after the tasks it waits for (a topological order). For each task:

ES = largest EF of the tasks it waits for   (0 if it waits for nothing)
EF = ES + days

ES is the earliest start and EF the earliest finish. Testing waits for Backend (EF 12) and Frontend (EF 9), so it cannot start before day 12, and it finishes on day 15. The largest EF of all, 16, is the length of the project (Demo: forward and backward pass).

Backward pass: latest start and finish

Now keep the end fixed at day 16 and walk the same order backward. For each task:

LF = smallest LS of the tasks that wait for it   (the project length if none does)
LS = LF − days

LF is the latest finish and LS the latest start that still let the project end on time. Spec comes before UI design (LS 6), Database (LS 3) and Docs (LS 13). The most urgent one decides, so Spec must finish by day 3.

Slack and the critical path

The slack of a task (also called total float) is LS − ES, which is the same as LF − EF. It is how many days the task can slip, or run long, before the end of the project moves.

A time axis from day 4 to day 13. Frontend takes 4 days and may run anywhere between its earliest start, day 5, and its latest finish, day 12. Placed as early as possible it runs from 5 to 9; placed as late as possible it runs from 8 to 12. The difference, 3 days, is its slack
Frontend has a 7-day window for 4 days of work, so 3 days of slack; a critical task has a window exactly as long as its work.
TaskESEFLSLFSlack
A Spec03030
B UI design35683
C Database37370
D Backend7127120
E Frontend598123
F Docs35131510
G Testing121512150
H Release151615160

Tasks with slack 0 are critical. Here they form one chain, A → C → D → G → H, with 3 + 4 + 5 + 3 + 1 = 16 days: the critical path, red in the animation. It is the longest path in the DAG, with the weights on the tasks.

Slack belongs to a path, not to one task. B and E both show 3, but it is the same 3 days: if UI design uses them, Frontend has none left.

A delay with slack, a delay without

Pick a task and a change, then press Change Duration. The page runs both passes again and marks every number that moved.

Two small Gantt charts. Top: Frontend takes 2 days longer, 5 to 11 instead of 5 to 9; Testing still starts on day 12 and the project still ends on day 16. Bottom: Backend takes 2 days longer, 7 to 14 instead of 7 to 12; Testing moves to 14 and the project ends on day 18
Two days late on a task with slack costs nothing; two days late on a critical task costs two days.
ChangeSlack beforeProjectWhy
Docs +51016 → 16the slack takes it; 5 left
Backend +2016 → 18critical: every day counts
Frontend +3316 → 16slack used up; two critical paths
Frontend +5316 → 183 days of slack, then 2 on the end

In general a delay of k days on a task with slack s moves the end by k − s days, or not at all when k ≤ s. After Frontend +5 the critical path is A → B → E → G → H, and Database and Backend have 2 days of slack (Demo: Frontend +5). The critical path is not fixed: it is whatever chain is longest now.

Making the project shorter

To finish sooner you must shorten a critical task, for example by adding people to it (this is called crashing). Shortening a task that has slack gains nothing: Docs in 1 day instead of 2 still gives 16 (Demo: cut Docs).

And a critical task only helps until another path catches up. Cut Backend from 5 days to 3 and the project drops to 14. Cut it to 1 and the project is 13, not 12: the path through Frontend, 3 + 2 + 4 + 3 + 1 = 13, is now the longest, and Backend has a day of slack (Demo: cut Backend by 4).

The Gantt strip

A Gantt chart draws each task as a bar on a time axis. On this page a bar runs from ES to EF, so every task is placed as early as possible. The grey tail after a bar reaches to LF: that is its slack. Critical bars are red and have no tail, and they line up end to start from day 0 to the red end line.

Cost

Each pass visits every task once and reads every arrow once: O(tasks + arrows), the same as the topological sort it relies on. See also timing analysis, where the same two passes over a circuit give the slack of each signal path.

See also a Scrum Sprint and its burndown chart, where the team plans by velocity and value instead of a task network.

See also earned value management, which measures a running project against its dated plan with PV, EV and AC and forecasts the final cost.

What the page leaves out

PERT, which uses three estimates per task (optimistic, likely, pessimistic) and gives a probability for the end date; free float, the slack a task has without touching the next task's earliest start; people and machines, since two tasks that need the same person cannot really overlap (resource levelling); dependencies other than finish-to-start, and lags between tasks; calendars with weekends and holidays; the cost side of crashing; and the older activity-on-arrow drawing, where tasks are the arrows.

On the mind map

This page on the Dynamic Programming mind map · 35 pages in 8 branches · open it to see the whole map and test yourself in recall mode.