Critical path method

The critical path method calculates an earliest schedule, a latest schedule for a chosen finish time, and each activity's task float. A critical path is a start-to-finish graph path whose total duration is greatest. There can be several such graph paths, and every one constrains completion. In the six-activity project scheduling example, the critical graph path is A-C-D-F, of duration $3+4+2+1=10$.

Add a zero-duration source $s$ before every initial activity and a zero-duration sink $z$ after every terminal activity. Give each edge $i\to j$ weight ${\tau }_i$, including zero weight on edges leaving $s$. This produces a weighted graph in which a graph path's weight counts every activity on it exactly once. The possible source-to-sink graph paths in our example, omitting the dummy endpoints, are A-B-D-F with weight 8, A-C-D-F with weight 10, and E-F with weight 4.

Every feasible schedule must accommodate each of these sequential chains. Consequently,This bound applies to all source-to-sink graph paths, not just the one we happen to inspect. The critical path method attains the bound by setting each activity's earliest start $E_i$ to the maximum of its predecessors' earliest finish times:Evaluate this recurrence in a topological order, obtained by topological sorting. Each $E_j$ satisfies every incoming optimization constraint, so these times form a feasible solution. The same recurrence calculates the greatest weight of a graph path from $s$ to $j$; hence the feasible finish $E_z$ matches the lower bound. This is dynamic programming on a Directed acyclic graph, rather than an enumeration of all graph paths. See Paul Johnson, Scheduling and longest paths, longest-path algorithm. The linear programming formulation and its certificate are developed in project scheduling duality and unit-flow certificate for project duration.

For our project scheduling example, $E_A=E_E=0$, $E_B=E_C=3$, and the two merges giveF finishes at 10. All six activities are completed, even though E is absent from the critical graph path. Recording which predecessor attains each maximum lets us trace a critical graph path backward from the sink; retaining tied choices exposes multiple critical graph paths.

Now fix the project start at zero and the finish at $T_{\ast }=10$. The latest starts $L_i$ come from a backward pass in reverse topological order:Every activity must finish by the earliest of its successors' latest starts, explaining the minimum here. This gives $L_F=9$, $L_D=7$, $L_E=6$, $L_B=5$, $L_C=3$, and $L_A=\min (5-3,3-3)=0$. These latest times themselves form a feasible solution finishing at 10. The backward calculation depends on the chosen finish time; a later deadline would give different latest times and task floats. The forward and backward passes are described in Olivier de Weck, MIT ESD.36 Lecture 2, slides 22–29.

Changing a duration can change which graph paths are critical. If B's duration becomes 4, A-B-D-F and A-C-D-F both take 10: there are two critical graph paths. Shortening C alone then cannot reduce the finish time, because the chain through B still takes 10. If B's duration instead becomes 5, the earliest starts of D and F become 8 and 10, and the finish becomes 11. A-B-D-F is now the unique critical graph path; C has task float 1 relative to that new optimal finish. These calculations show why the critical path method is useful for understanding where a duration change matters, even in a project containing many parallel activities.