From Precedence Constraints to a Schedule
A project may contain tasks that can happen in parallel and tasks that must wait for earlier tasks to finish. A graph records these dependencies: its vertices represent tasks, and a directed edge \(uv\) means that task \(v\) cannot start until task \(u\) is complete. The graph helps distinguish work that can proceed simultaneously from work that lies along a sequence of dependencies.
A directed acyclic graph, or DAG, has no directed cycle. Thus its precedence requirements do not demand that a task finish before itself. A task with no incoming arcs has no required predecessor; a task with no outgoing arcs has no required successor. Neither kind of task has to be unique. Durations may be zero, and unrelated tasks may run at the same time.
A directed path is a sequence of distinct vertices in which each consecutive pair is joined by an arc in the direction of the sequence. Its duration is the sum of the durations of its task vertices. When a project is nonempty, add a dummy source \(s\), a dummy sink \(t\), arcs from \(s\) to every task with no predecessors, and arcs from every task with no successors to \(t\). Give the dummy vertices duration zero. The resulting source-to-sink paths represent sequences of dependent tasks, and their durations are sums over the actual tasks on those paths.
Earliest and Latest Times
The earliest start time \(ES(v)\) is the earliest time task \(v\) can start while respecting all predecessor constraints. Its earliest finish time is \(EF(v)=ES(v)+p(v)\). In a forward calculation, process tasks in an order in which every predecessor comes before its successors. Such an order exists for every finite DAG.
For the backward calculation, regard \(T\) as a fixed project deadline. The latest start time \(LS(v)\) is the latest start of \(v\) that still permits the project to finish by \(T\). If \(v\) has no successors, it must finish by \(T\), so \(LS(v)=T-p(v)\). Otherwise it must finish by the earliest latest-start requirement among its successors:
The slack of \(v\) is \(LS(v)-ES(v)\). It measures how much the task's start can be delayed from its earliest start without delaying completion under this deadline. A task with zero slack is called critical. A critical path is a source-to-sink path whose duration is \(T\).
Proof. In any nonempty finite DAG there is a vertex with no incoming arc. Otherwise, starting at any vertex and repeatedly following an incoming arc would eventually revisit a vertex, since there are only finitely many vertices. The portion between two visits would be a directed cycle, contrary to the assumption. Remove a vertex with no incoming arc and apply the same argument to the remaining DAG, which is still finite and acyclic. Listing the removed vertices in removal order gives an ordering in which each arc goes from an earlier vertex to a later one: when a vertex is removed, none of the vertices still present has an arc into it. The empty graph has the empty ordering, so the claim also holds in that case. \(\square\)
Why the Longest Path Determines the Completion Time
Proof. First consider any feasible schedule \(x\), and any directed path of tasks \(v_1,\dots,v_k\). Feasibility gives \(x(v_{i+1})\ge x(v_i)+p(v_i)\) for every \(i\) from \(1\) to \(k-1\). Also \(x(v_1)\ge0\). Repeatedly applying these inequalities gives \(x(v_k)+p(v_k)\ge \sum_{i=1}^k p(v_i)\). The schedule's completion time is at least \(x(v_k)+p(v_k)\). Therefore it is at least the duration of every task path, and hence at least the maximum source-to-sink path duration.
Now compute \(ES\) in a vertex order supplied by the lemma. For each task with no predecessors, \(ES=0\), which is the maximum duration of a path ending at that task with no earlier tasks. For a task \(v\) with predecessors, every path ending at \(v\) consists of a path ending at some predecessor \(u\), followed by \(v\). Its duration is the duration up to \(u\), plus \(p(v)\). Taking the maximum over all predecessors gives exactly \(ES(v)=\max_{u:uv\in E}(ES(u)+p(u))\). This proves, successively through the ordering, that \(ES(v)\) is the maximum duration of any task path ending at \(v\).
The earliest-start assignment is feasible because its definition gives \(ES(v)\ge ES(u)+p(u)\) for every arc \(uv\); it is also nonnegative. Its completion time \(T\) is the maximum duration of any task path, by the result just proved. Together with the lower bound for every feasible schedule, this shows that \(T\) is the minimum possible completion time. Adding the dummy source and sink only attaches zero-duration vertices to paths, so this maximum is the maximum source-to-sink path duration. \(\square\)
The theorem concerns a nonempty task set, so the dummy source and sink are joined by at least one source-to-sink path. For an empty project, there are no tasks and the completion time is naturally zero; the dummy construction has no source-to-sink path in that case. One may handle the empty project separately, or add a zero-duration arc \(st\) and define its path duration to be zero.
Worked Schedule: A Forward and Backward Pass
Worked Example: Finding the Critical Path and Slack
Let the tasks be \(A,B,C,D,E,F,G\), with durations \(p(A)=3\), \(p(B)=2\), \(p(C)=4\), \(p(D)=2\), \(p(E)=3\), \(p(F)=2\), and \(p(G)=1\). The precedence graph has vertex set \(V=\{A,B,C,D,E,F,G\}\) and arc set \(E=\{AC,AD,BD,CE,DE,BF,EG,FG\}\). Thus \(C\) follows \(A\); \(D\) follows \(A\) and \(B\); \(E\) follows \(C\) and \(D\); \(F\) follows \(B\); and \(G\) follows \(E\) and \(F\). This graph is a DAG, for example in the order \(A,B,C,D,E,F,G\).
In the forward pass, tasks \(A\) and \(B\) have no predecessors, so \(ES(A)=ES(B)=0\). Then \(ES(C)=ES(A)+p(A)=0+3=3\), and \(ES(D)=\max(ES(A)+p(A),ES(B)+p(B))=\max(3,2)=3\). Next, \(ES(E)=\max(ES(C)+p(C),ES(D)+p(D))=\max(3+4,3+2)=\max(7,5)=7\); \(ES(F)=ES(B)+p(B)=0+2=2\); and \(ES(G)=\max(ES(E)+p(E),ES(F)+p(F))=\max(7+3,2+2)=\max(10,4)=10\). The finish times of \(A,B,C,D,E,F,G\) are respectively \(3,2,7,5,10,4,11\), so \(T=11\).
For the backward pass, \(G\) is the only task with no successors, so \(LS(G)=11-1=10\). Then \(LS(E)=LS(G)-p(E)=10-3=7\), and \(LS(F)=LS(G)-p(F)=10-2=8\). Since \(C\) leads to \(E\), \(LS(C)=7-4=3\). Since \(D\) also leads to \(E\), \(LS(D)=7-2=5\). For \(A\), the latest-start requirements from \(C\) and \(D\) give \(LS(A)=\min(3,5)-3=0\). For \(B\), the requirements from \(D\) and \(F\) give \(LS(B)=\min(5,8)-2=3\).
| Task | Duration | Earliest start | Latest start | Slack |
|---|---|---|---|---|
| A | 3 | 0 | 0 | 0 |
| B | 2 | 0 | 3 | 3 |
| C | 4 | 3 | 3 | 0 |
| D | 2 | 3 | 5 | 2 |
| E | 3 | 7 | 7 | 0 |
| F | 2 | 2 | 8 | 6 |
| G | 1 | 10 | 10 | 0 |
Check: The path \(A,C,E,G\) has duration \(3+4+3+1=11\). The other source-to-sink path durations are \(A,D,E,G: 3+2+3+1=9\), \(B,D,E,G: 2+2+3+1=8\), and \(B,F,G: 2+2+1=5\). Thus the longest path has duration \(11\), agreeing with the forward-pass completion time. The slack entries are also the latest starts minus earliest starts; for example, \(LS(B)-ES(B)=3-0=3\) and \(LS(F)-ES(F)=8-2=6\).
Critical Tasks and Tied Longest Paths
Proof. For a task \(v\), let \(P(v)\) be the maximum duration of a task path ending at \(v\), including \(v\), and let \(R(v)\) be the maximum duration of a task path starting at a successor of \(v\) and continuing to a task with no successors. If \(v\) has no successors, set \(R(v)=0\). The forward-pass argument shows \(ES(v)=P(v)-p(v)\). The backward recurrence, applied from tasks with no successors in reverse vertex order, gives \(LS(v)=T-p(v)-R(v)\). Hence \(LS(v)-ES(v)=T-(P(v)+R(v))\). A longest prefix ending at \(v\) and a longest continuation after \(v\) join to make a valid path: their vertices cannot overlap beyond \(v\), since such an overlap would give a directed cycle. Thus \(P(v)+R(v)\le T\), and equality holds exactly when the joined path through \(v\) has duration \(T\). The displayed slack is zero exactly in that case. \(\square\)
Worked Example: Two Critical Paths
Let \(V=\{P,Q,R\}\), with durations \(p(P)=2\), \(p(Q)=2\), \(p(R)=1\), and arc set \(E=\{PR,QR\}\). Tasks \(P\) and \(Q\) can start immediately; \(R\) must wait for both. The forward pass gives \(ES(P)=ES(Q)=0\) and \(ES(R)=\max(0+2,0+2)=2\). The finish times are \(2,2,3\), so \(T=3\).
In reverse order, \(LS(R)=3-1=2\). Then \(LS(P)=2-2=0\) and \(LS(Q)=2-2=0\). The slacks are \(0-0=0\) for \(P\), \(0-0=0\) for \(Q\), and \(2-2=0\) for \(R\). Both paths \(P,R\) and \(Q,R\) have duration \(2+1=3\), so both are critical.
Check: Any feasible schedule must start \(R\) no earlier than time \(2\), because both length-two tasks must finish first. It therefore cannot finish before time \(2+1=3\), and the computed schedule does finish at time \(3\).
A Small Example with Parallel Tasks
Worked Example: An Independent Task Does Not Extend the Project
Let \(V=\{X,Y,Z\}\), with durations \(p(X)=4\), \(p(Y)=1\), and \(p(Z)=2\), and arc set \(E=\{XZ\}\). Task \(Y\) has no precedence relation with either other task. The forward pass gives \(ES(X)=ES(Y)=0\) and \(ES(Z)=ES(X)+p(X)=4\). The finish times are \(4\), \(1\), and \(6\), so \(T=6\).
Backward from the deadline, \(Z\) has no successors, so \(LS(Z)=6-2=4\). Task \(X\) has successor \(Z\), giving \(LS(X)=4-4=0\). Task \(Y\) has no successors, giving \(LS(Y)=6-1=5\). Their slacks are \(0\), \(5\), and \(0\), respectively.
Check: The only task path containing a precedence arc is \(X,Z\), with duration \(4+2=6\). The separate path containing \(Y\) has duration \(1\). Thus the longest path duration is \(6\), and \(Y\) can be delayed by \(5\) time units before it affects the deadline.
Common Pitfalls and Practical Interpretation
Do not add durations of parallel tasks as though they were sequential. In the last example, a mistaken calculation might add \(4+1+2=7\), claiming that all three tasks must be completed one after another. But the graph has only the arc \(XZ\): \(Y\) can run at the same time as \(X\) and \(Z\). The actual earliest completion is \(\max(4+2,1)=\max(6,1)=6\), not \(7\).
Do not confuse latest start with earliest start. A positive slack does not mean a task must be delayed; it means there is room to delay its start while still meeting the chosen deadline \(T\). In the main example, \(B\) can start at time \(0\), but it can also start as late as time \(3\) without extending the project. Its slack is \(3-0=3\).
Check every successor and predecessor. The forward pass uses the maximum over all predecessors, since a task must wait for the last predecessor to finish. The backward pass uses the minimum over all successors, since a task must finish soon enough for every successor. Replacing either maximum or minimum with a sum or an arbitrary choice can give an incorrect schedule.
The longest-path calculation is useful because it identifies the chains of dependent tasks that set the project duration. If a critical task is delayed, the completion time may increase unless another scheduling change compensates for it. Tasks with positive slack provide some flexibility, but their available delay depends on the full network of later constraints, not only on their immediate neighbors.
Check Your Understanding
For each question, use the stated precedence constraints and show the relevant calculation.
- For tasks \(A,B,C\) with durations \(3,2,4\) and arcs \(AC,BC\), find the earliest start times and project completion time.
- In the main worked example, why does the forward-pass rule use a maximum when calculating \(ES(E)\)? What incorrect requirement would a sum impose?
- For the graph with tasks \(X,Y,Z\), explain why \(Y\) has slack \(5\) even though its duration is \(1\).
- Construct a nonempty project network with two distinct longest paths, and verify their durations.
- What is the completion time of an empty project, and why must the longest-path theorem as stated above treat that case separately?