Project scheduling

Project scheduling asks how quickly a collection of dependent activities can finish. Adding their durations usually overestimates the answer, because independent activities can run together; taking only the longest single activity usually underestimates it, because some activities must wait. The critical path method identifies the chain of dependencies that determines the finish time. Its simplest model assumes known, fixed durations, unlimited parallel processing, and precedence requirements saying that each predecessor must finish before its successor starts. These are the assumptions of the basic model in Hendrickson, Project Management for Construction, §10.2.

Represent each activity by a vertex of a finite Directed acyclic graph; an edge $i\to j$ means that activity $j$ waits for activity $i$. Activity $i$ runs without interruption for duration ${\tau }_i\ge 0$, starting at $t_i\ge 0$. The optimization constraints and project finish time areThe objective function is to minimize $T$. All durations and start times use the same time unit, and the project starts at time zero. The Directed acyclic graph assumption allows a topological order in which every predecessor is processed first.

Consider this small, abstract project:

Activities A and E may start together. After A finishes, B and C may run together, but D must wait for both. F must similarly wait for both D and E: a merge means all incoming requirements must hold. This activity-as-vertex convention keeps durations on the activities and uses arrows only to express precedence.

Unlimited parallel processing is essential to the equality between the longest graph path duration and the optimal finish time. For example, two independent chains, each containing two activities of duration 3, have longest graph path duration 6. Two processors can finish both chains in 6, but one processor needs 12 because all four activities must run sequentially. Thus with limited resources the longest graph path still gives a lower bound, but it need not be achievable. Such resource requirements belong to the broader subject of scheduling.

// Target: mathematical-optimization.bigb