Project Longest Path Model¶

Definition¶

The course's project longest path model uses a directed acyclic activity network with start $S$ and finish $T$. Each edge has an activity duration; an outgoing activity may start only after all activities entering its starting vertex finish. Under these precedence rules and without additional resource restrictions, project duration is the length of a longest $S$-to-$T$ path.

Interpretation¶

The project cannot finish before its longest chain of dependent activities has finished. Activities on different chains can run side by side, but along one chain each activity must wait for the previous one, so the project duration is the length of the longest $S$-to-$T$ path. The model finds it with binary edge-selection variables.

Each node carries its earliest start time: the largest total duration over the paths from $S$ to that node. Node 3 can start only when both $C$ and $D$ are done, at $\max\{3+4,\,2+5\}=7$$7$, and $T$ is reached at $\max\{7+2,\,2+6\}=9$$9$. The red path $S\to2\to3\to T$ has length $2+5+2=9$$9$, but so does $S\to1\to3\to T$ with $3+4+2=9$$9$: a longest path need not be unique. The path through $F$ has length $8$, so activity $F$ could finish one time unit later without delaying the project.

The formulation reuses the shortest path binary formulation: one unit of flow leaves $S$, enters $T$ and is balanced at every other node, but the objective is maximized instead of minimized. This is safe because a precedence network is acyclic, since a cycle would mean that an activity waits for itself; with cycles, maximizing could select an extra cycle that satisfies the balance equations without lying on the $S$-to-$T$ path.

A common slip is to add up all activity durations. Activities on parallel chains overlap in time, so only the durations along one chain count.

Key Results¶

• Maximize the sum of selected activity durations.
• Use one unit of source-to-sink binary flow with balance at intermediate vertices.
• Acyclicity matters: in a general cyclic network, flow balance alone could allow unrelated selected cycles.

Examples¶

In the figure, both critical paths, $S-2-3-T$ with $2+5+2=9$ and $S-1-3-T$ with $3+4+2=9$$9$, have duration 9, compared with 8 for $S-2-T$$T$. Negating the activity lengths turns this acyclic longest-path calculation into a shortest-path calculation; the lack of cycles permits the negative lengths.

• In the exercise, $S-A-D-F-T$ has duration $5+2+6+4=17$$17$.
• $S-B-D-F-T$ has duration $3+3+6+4=16$$16$.

Prerequisites¶

• Directed Network
• Shortest Path Binary Formulation

Related Concepts¶

• Path in a Network
• Assignment Problem

Sources¶

• OR Modelling · Week 5

Keywords: critical path method, CPM, critical path

Last updated: 20 October 2026 03:02