A schedule is a system of inequalities
A project contains activities that cannot all begin at once. An arrow from to means that must finish before starts. Durations and dependencies together determine a lower bound on completion time; a scheduling calculation should also produce a feasible schedule that attains the bound.
We assume a finite nonempty directed acyclic graph, one activity per vertex, deterministic durations , unlimited resources, no release dates, and project time starting at zero. No activity may be split or accelerated; resource conflicts and uncertainty are outside this model.
Definition 8.2.1
(Feasible schedule and completion time)
A schedule assigns each activity a start time . It is feasible if for every arrow . Its completion time is . The length of a directed path is the sum of the durations of its activities.
Forward and backward passes
Definition 8.2.2
(Earliest start, latest start and total slack)
In a topological order, set for a source and otherwise ; put . In reverse topological order, set for a sink and otherwise . The total slack of activity is . An activity with zero total slack is critical.
Theorem 8.2.3
(The forward pass gives the minimum completion time)
Every feasible schedule satisfies for all , and the schedule is feasible. Hence is the minimum completion time. It equals the greatest length of a directed path.
Proof
(Induction along a topological order)
By induction in topological order, every feasible schedule has : it holds at sources, where , and if it holds at every predecessor of , then for each , so . The schedule is feasible, because for every arrow by the maximum in its definition. Therefore every feasible completion time is at least , and attains it.
The same induction shows that is the greatest length of a directed path ending just before : the recurrence appends to a longest path ending before and maximizes over predecessors. Hence is the greatest length of a path ending at , and is the greatest length of any directed path.
Concept lensAlgebraic
The critical path as a dual certificate
The minimum completion time is a linear program: minimize subject to on every arrow , for every , and . For a directed path , add , the arrow constraints along the path and ; the start times telescope away and leave . These unit weights form a feasible dual solution with value the path length. The forward pass is a primal optimum, a longest path is a dual optimum, and their common value is strong duality for this problem.
To find how late an individual activity can start while preserving , the backward pass runs the same argument in reverse.
Proposition 8.2.4
(Latest starts are attained)
Every feasible schedule completing by satisfies for all . The vector is itself a feasible schedule completing by , and , so every total slack is nonnegative.
Proof
(Backward induction from the sinks)
Take a feasible schedule completing by . A sink must finish by , so . If holds for every successor of , then for each such , so .
Next, by backward induction: at a sink, ; otherwise for each successor , and taking the minimum gives . Thus . The definition gives for every arrow , so is feasible, and every chain of successors ends at a sink with , so completes by . Each is therefore an attained latest start, not merely a bound.
Proposition 8.2.5
(Critical activities are exactly those on longest paths)
An activity has zero total slack if and only if it lies on a directed path of length .
Proof
(Joining a longest prefix to a longest continuation)
By the two passes, is the greatest length of a path ending at , and is the greatest length of a path starting at , both counting . A path from a source to followed by one from to a sink, with counted once, has length at most , and the two longest pieces attain this; in a DAG they share only , so together they form a path. If , this is a path of length through . Conversely, if lies on a path of length , its part up to and including has length at most and its part from onward has length at most ; these overlap only in , so , which forces .
Proof X-ray
A zero slack activity and its path
The proof rests on reading each pass as a longest-path value: the forward pass measures the longest prefix ending at , the backward pass the longest continuation starting at . The one move is to add them with counted once, which shows that total slack is exactly the shortfall minus the longest path through . Acyclicity is what makes the two pieces combine into a genuine path, since a prefix and a continuation through the same vertex cannot share another vertex in a DAG. Both directions then close at once: zero shortfall means a longest path through , and a longest path through means zero shortfall. Nothing forces the longest path to be unique.
Worked examples
Worked example 8.2.6
(Five activities with one critical path)
Take activities with durations and arrows , , , , . The forward pass gives starts , , , , and completion . Backward from , obtain , , , and . Their slacks in activity order are .
The path has length , certifying the lower bound. Starting every activity at its earliest time attains it. can start at time one in the all-latest schedule without delaying completion. The all-latest schedule is feasible, but independently choosing delays within individual slack bounds need not produce a feasible schedule.
The explorer below lets you change the durations, read E, L, slack and the longest paths, and then test your own start times against every precedence constraint, including delays that each stay within slack.
Counterexample mode
Slack is not a free independent delay budget
Consider alongside an independent activity , with durations . The project takes four time units. Earliest starts of are ; their latest starts are , so both have slack two. Delaying both from their earliest starts by two gives starts , which is feasible. But delaying only by two while leaving at its earliest start one violates . Individual slack bounds do not remove precedence constraints.
The next two examples show boundary cases: ties between longest paths, and an activity of zero duration.
Worked example 8.2.7
(Two longest paths sharing an activity)
In the five-activity network, change 's duration to three. Then , , and . Backward, , , , and . The slacks are , and both and have length . The critical activities form two longest paths, not one.
Common mistake
(Shortening one critical path and expecting the project to shrink)
With two longest paths, reducing the duration of an activity on only one of them does not shorten the project. In the tied network, cutting from three to two gives , and completion stays because is still a path of length ten. Only a change that shortens every longest path can lower .
Worked example 8.2.8
(A zero-duration milestone)
Let and have durations and , let a milestone have duration , and let have duration , with arrows , , . Forward, , , and . Backward, , , and . The slacks are for . The longest path has length . The milestone is critical even though it consumes no time: it records the synchronization that must wait for.
Limits
A cycle makes the topological algorithm inapplicable; for positive durations along a cycle the inequalities are inconsistent. A zero-duration cycle can satisfy the inequalities, but is excluded by our DAG assumption. Limited workers, shared machines, stochastic durations, and deadlines other than the minimum completion time require additional models. A critical path is a certificate for this deterministic precedence-only problem, not a promise about real-world project completion.
Exercises
Quick check
(Verify every precedence inequality in the first worked example's all-latest schedule.)
Solution · Answer
The latest starts are . The predecessor finishes are on the five listed arrows, each no later than its successor's start.
Quick check
(In the first worked example, increase 's duration from two to four, leaving the graph otherwise unchanged. Find the new earliest completion time and a longest path.)
Solution · Answer
Now starts at four, at four and at eight. Completion is eleven; has length .
Quick check
(In the and example, give the all-latest starts and check their feasibility.)
Solution · Answer
, , and . finishes at three when starts; and finish at four.
Quick check
(Explain why a directed cycle of two activities with strictly positive durations cannot satisfy the precedence inequalities.)
Solution · Answer
If and , the inequalities imply and . Adding them gives , a contradiction.