= 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 https://www.cmu.edu/cee/projects/PMbook/10_Fundamental_Scheduling_Procedures.html#10.2[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\geq0$, starting at $t_i\geq0$. The <optimization constraints> and project finish time are
$$
t_j\geq t_i+\tau_i\quad(i\to j),\qquad T=\max_i(t_i+\tau_i).
$$
The <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:
|| Activity
|| Duration
|| Immediate predecessors
| A
| 3
| None
| B
| 2
| A
| C
| 4
| A
| D
| 2
| B and C
| E
| 3
| None
| F
| 1
| D and E
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.
\Image[/critical-path-precedence-network.png]
{title=Six-activity <project scheduling> network: the critical <graph path> A-C-D-F takes 10 time units}
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
Back to article page
