D1.4 - Critical path analysis

An activity network models which project activities must finish before others can start. In the activity-on-arc convention, each labelled arrow is an activity and its duration; each vertex is an event marking the completion of all activities that enter it. Arrow direction therefore records precedence, not physical movement.

Begin with every activity that has no predecessor at a start event. Add each remaining activity only when all of its immediate predecessors have reached its start event. Merge arrows when several activities must all finish before the next one starts, and continue until all final activities reach one finish event. Number events so every arrow points from a lower to a higher event number.

A dummy is a zero-duration arrow that preserves a dependency without adding work or resources. Use one when the real arrows alone would make an activity depend on too many predecessors, or would give two activities the same start and finish events. It is part of the network logic but not a project activity.

One valid construction is $A:1 o2$, $B:1 o3$, a dummy $2 o3$, $C:2 o4$, $D:3 o4$ and $E:4 o5$. The dummy makes $D$ wait for both $A$ and $B$, while $C$ still depends on $A$ only; the common event 4 makes $E$ wait for both $C$ and $D$.

A precedence table reverses the modelling step: for each real activity in an activity-on-arc network, it lists only the activities that must finish immediately before that activity can start.

Take one activity at a time and inspect its tail event. Record the real activities whose arrows feed that event. If an incoming arrow is a dummy, do not list the dummy; trace backwards through it to the real activity or activities whose completion it carries. Activities leaving the initial event have no predecessors.

Although $A$ and $B$ must occur before $E$, they are not immediate predecessors of $E$: once $C$ and $D$ are complete, their earlier requirements are already satisfied. Listing only $C,D$ keeps the table equivalent to the network without redundant transitive dependencies.

The critical path is a start-to-finish path whose activities determine the minimum project duration. A delay to any activity on that path delays the project unless the plan changes. Find it by a forward pass for earliest event times and a backward pass for latest event times.

Set the start event's earliest time to 0. Moving with the arrows, an event can occur only after every incoming activity finishes, so take the maximum incoming finish time. At the finish event, set the latest time equal to its earliest time. Moving against the arrows, take the minimum latest permitted start supplied by the outgoing activities.

Let $A:1 o2$ take 4, $B:1 o3$ take 3, $C:2 o4$ take 5 and $D:3 o4$ take 2. The forward pass gives $e_1=0$, $e_2=4$, $e_3=3$ and $e_4=\max(4+5,3+2)=9$. The backward pass gives $l_4=9$, $l_2=4$, $l_3=7$ and $l_1=0$. Thus $A,C$ form the critical path and the minimum completion time is 9.

An activity $(i,j)$ is critical when it uses all available time: $e_i+d_{ij}=l_j$. Join critical activities continuously from the start event to the finish event; more than one critical path can exist.

Total float is the amount by which an activity can be delayed without delaying the project's minimum completion time. For activity $(i,j)$, compare its earliest possible start with the latest start allowed by its finish event.

If $e_i=6$, $l_j=15$ and the duration is 4 hours, then $F=15-6-4=5$ hours. A critical activity has total float 0; a non-critical activity may be moved within its float only while all precedence constraints remain satisfied.

Place critical activities first because they cannot move. Then fit non-critical activities into their allowed float, shifting them only when predecessors have finished and the assigned worker is free. A cascade chart displays flexibility; a finished scheduling diagram displays the chosen start times and worker allocation, not the unused float. When every activity requires one worker, total activity duration is the total worker-time used in the lower bound.

For example, 68 worker-hours in a 24-hour project gives the lower bound $\lceil68/24 ceil=3$ workers. This average-work bound may be unattainable: precedence can force several activities to overlap. To prove that at least $k$ workers are needed, identify a time strictly inside an interval when $k$ named activities must all be running; then construct a valid $k$-worker schedule if the exact minimum is required.