8.4 Project scheduling: CPM
A project consists of activities with durations and precedence relations: an activity can start only when its predecessors have finished. In an activity-on-node network each activity is a node and each precedence an arc. The project cannot finish before the longest chain of activities does, and the critical path method (CPM; Kelley and Walker, 1959) computes:
- in a forward pass, the earliest start \(ES_k = \max \{EF_p : p \text { a predecessor of } k\}\) (\(0\) if none) and earliest finish \(EF_k = ES_k + t_k\); the project duration is \(T = \max _kEF_k\);
- in a backward pass, the latest finish \(LF_k = \min \{LS_q : q \text { a successor of } k\}\) (\(T\) if none) and latest start \(LS_k = LF_k - t_k\);
- the total float \(LS_k - ES_k\), the delay activity \(k\) can suffer without delaying the project.
Activities with zero float are critical; they form a longest path, the critical path. Since the network has no cycles, the forward pass is the longest-path version of Bellman’s equations, solved in one sweep in topological order.
Proposition 8.4.1. The minimum project duration \(T\) equals the length of a longest path of activities through the network, and an activity has zero total float if and only if it lies on such a path.
Proof. By induction in topological order, \(EF_k\) is the length of a longest chain ending with \(k\), and so \(T\) is the longest path length. A schedule must start each activity no earlier than \(ES_k\), so no schedule is shorter. Symmetrically \(T - LS_k\) is the length of a longest chain starting with \(k\), so \(LS_k - ES_k = T - (\text {longest chain through } k)\), which is zero exactly when \(k\) lies on a longest path. □
Questions on this section
Stuck on something here? Ask below and it stays attached to this topic.