= Critical path method
{wiki}
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,
$$
T\geq\max_{P:s\leadsto z}\sum_{i\in P\setminus\{z\}}\tau_i.
$$
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:
$$
E_s=0,\qquad E_j=\max_{i\to j}(E_i+\tau_i),\qquad T_*=E_z.
$$
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 https://ptwiddle.github.io/MAS341-Graph-Theory-2017/lecturenotes/lecturex2.html[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 give
$$
E_D=\max(3+2,3+4)=7,\qquad E_F=\max(7+2,0+3)=9.
$$
F 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_*=10$. The latest starts $L_i$ come from a backward pass in reverse <topological order>:
$$
L_z=T_*,\qquad L_i=\min_{i\to j}(L_j-\tau_i).
$$
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 https://ocw.mit.edu/courses/esd-36-system-project-management-fall-2012/50d2b3499047b71baaa511aa809f6712_MITESD_36F12_Lec02.pdf#page=22[Olivier de Weck, MIT ESD.36 Lecture 2, slides 22–29].
|| Activity
|| Earliest start $E_i$
|| Earliest finish $E_i+\tau_i$
|| Latest start $L_i$
|| Latest finish $L_i+\tau_i$
|| <Task float> $L_i-E_i$
| A
| 0
| 3
| 0
| 3
| 0
| B
| 3
| 5
| 5
| 7
| 2
| C
| 3
| 7
| 3
| 7
| 0
| D
| 7
| 9
| 7
| 9
| 0
| E
| 0
| 3
| 6
| 9
| 6
| F
| 9
| 10
| 9
| 10
| 0
\Image[/critical-path-earliest-latest-schedule.png]
{title=Earliest solid and latest hollow activity bars for the <critical path method>, with <task floats> of 2 for B and 6 for E}
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.
Back to article page
