AN8, AN9 - Critical path analysis | OCR A-Level Further Mathematics B (MEI)

Use activity-on-arc networks to turn precedence requirements into a project model. AN8 constructs the network; AN9 finds event times, critical activities and float, then tests whether a resource schedule can achieve the minimum completion time.

Build an activity-on-arc network

Two activities each appear to have spare time. Can you use all that spare time on both? Sometimes they share the same allowance. A precedence network shows where delays can be absorbed and where one delay consumes another activity's flexibility.

You already know

A digraph uses arrows to specify permitted directions. A path follows consecutive arcs. A model must retain the dependencies needed for the question; weights must have a stated meaning.

For a project, draw each activity on an arc, with its duration as the weight. A vertex is an event: it occurs only when every activity entering it has finished. Activities leaving it may then start. Use a single start and finish, and arrows that preserve all required precedences without introducing extra ones.

Activity-on-arc and dummy activity

An activity-on-arc network represents activities by directed arcs and events by vertices. A dummy is a zero-duration, zero-resource arc used to express a dependency or distinguish activities that would otherwise share the same start and finish events. Draw it dashed and include its direction.

A dummy is not optional merely because it takes no time. Removing it can allow an activity to begin before a required predecessor is complete. Give real activities different ordered pairs of endpoint events; add an event and dummy when identification requires it.

Activity	Duration / hours	Immediate predecessors
$A$	$3$	None
$B$	$2$	None
$C$	$4$	$A$
$D$	$2$	$A,B$
$E$	$3$	$C,D$

[DIAGRAM: asset_name: A dummy preserves the exact predecessors; asset_slug: cpa_dummy_precedence; caption: The dummy makes D wait for A and B, while C waits only for A; description: An activity-on-arc network has events 1 through 5, with A from 1 to 2 of duration 3, B from 1 to 3 of duration 2, a dashed zero-duration dummy from 2 to 3, C from 2 to 4 of duration 4, D from 3 to 4 of duration 2, and E from 4 to 5 of duration 3. A second panel removes only the dummy when D is changed to depend on B alone.]
The dummy makes D wait for A and B, while C waits only for A

Worked example 1: different predecessor sets

Question. Construct an activity-on-arc model for the table, using one dummy.

Plan. Give $A$ its own completion event so $C$ can start, then merge $A$ with $B$ before $D$ .

\begin{aligned} A&:1\to2,\qquad B:1\to3 &&\text{both may start immediately}\\ \text{dummy}&:2\to3 &&\text{event }3\text{ also waits for }A\\ C&:2\to4,\qquad D:3\to4 &&\text{different predecessor requirements}\\ E&:4\to5 &&\text{wait for both }C,D \end{aligned}

Why this step? Merging $A$ and $B$ before both $C$ and $D$ would wrongly make $C$ wait for $B$ .

Answer. The six arcs shown in the first diagram, with the stated durations and the $2\to3$ dummy of duration zero.

Check. $D$ waits for $A,B$ ; $C$ waits only for $A$ ; $E$ waits for $C,D$ . No real activities share both endpoint events.

Change only $D$ 's predecessor requirement: it now depends on $B$ alone.

Worked example 2: remove a dependency

Question. Adapt the network for this changed requirement, leaving all durations and other dependencies unchanged.

Plan. Remove the dummy that carries the no-longer-required dependency from $A$ to $D$ .

\begin{aligned} \text{remove}&\quad2\to3 &&\text{drop only }A\text{'s dependency into }D\\ A&:1\to2,\quad C:2\to4 &&\text{unchanged branch}\\ B&:1\to3,\quad D:3\to4 &&\text{now independent of }A\\ E&:4\to5 &&\text{still waits for both branches} \end{aligned}

Why this step? Removing an activity arc would change the work; removing this dummy changes only the precedence.

Answer. The second diagram, containing the five real activity arcs and no dummy.

Check. $C$ and $D$ can now start independently once their own predecessors finish.

Activity-on-arc conventions and dummy construction are not printed in the formula booklet. Before doing arithmetic, check the predecessor list against every merge in your drawing.

Watch out

Wrong: delete the original $2\to3$ dummy because its duration is zero. That would let $D$ start after $B$ without waiting for $A$ . Correct: retain the dummy while $D$ requires both $A,B$ ; remove it only when that dependency changes.

Check the full predecessor list against the next drawing.

Make forward and backward passes

Return to the original project, including the dummy. An early event time is the earliest time that all incoming requirements can be complete. A late event time is the latest the event can occur without delaying the project's earliest possible finish, assuming resources are available.

Event-time passes

For an arc $i\to j$ of duration $d_{ij}$ ,

E_j=\max_{i\to j}(E_i+d_{ij}),\qquad L_i=\min_{i\to j}(L_j-d_{ij})

Start the forward pass with $E_{\mathrm{start}}=0$ . Set $L_{\mathrm{finish}}=E_{\mathrm{finish}}$ , then work backwards. Include dummy arcs with duration zero in both passes.

Not in the formula booklet: learn it.

Take a maximum going forward because an event must wait for every incoming branch. Take a minimum backwards because all outgoing requirements must remain achievable. A critical path is a longest-duration start-to-finish path; its activities have no total float. There may be more than one critical path.

Worked example 3: the original project

Question. Carry out both passes for the original project and identify its completion time and critical activities.

Plan. Compute earliest events in dependency order, then reverse the process from the earliest finish.

\begin{aligned} E_2&=0+3=3 &&\text{finish }A\\ E_3&=\max(0+2,3+0)=3 &&\text{wait for }B\text{ and dummy}\\ E_4&=\max(3+4,3+2)=7 &&\text{wait for }C,D\\ E_5&=7+3=10 &&\text{finish }E\\ L_4&=10-3=7 &&\text{back through }E\\ L_3&=7-2=5 &&\text{back through }D\\ L_2&=\min(7-4,5-0)=3 &&\text{both outgoing requirements}\\ L_1&=\min(3-3,5-2)=0 &&\text{back to start} \end{aligned}

Event	$1$	$2$	$3$	$4$	$5$
Early time $E_i$	$0$	$3$	$3$	$7$	$10$
Late time $L_i$	$0$	$3$	$5$	$7$	$10$

Why this step? Adding the durations of every activity would ignore work that can run in parallel.

Answer. Minimum completion time $10$ hours; critical path $ACE$ , with critical activities $A,C,E$ .

Check. $3+4+3=10$ along $ACE$ , while $D$ 's branch can finish earlier than event $4$ 's time $7$ .

Change only $D$ 's duration from $2$ to $5$ . The controlling branch may change, so redo both passes.

Worked example 4: a new critical branch

Question. Find the completion time, event times and critical activities after this change.

Plan. Keep earlier event times that are unaffected, then propagate the longer duration forwards and backwards.

\begin{aligned} E_2&=3,\quad E_3=3 &&\text{unchanged predecessors}\\ E_4&=\max(3+4,3+5)=8 &&\text{longer }D\text{ branch}\\ E_5&=8+3=11 &&\text{new finish}\\ L_4&=11-3=8,\quad L_3=8-5=3 &&\text{backward pass}\\ L_2&=\min(8-4,3-0)=3 &&\text{dummy controls this minimum}\\ L_1&=\min(3-3,3-2)=0 &&\text{start remains zero} \end{aligned}

Event	$1$	$2$	$3$	$4$	$5$
Early time	$0$	$3$	$3$	$8$	$11$
Late time	$0$	$3$	$3$	$8$	$11$

Why this step? Increasing a non-critical activity can consume its float and eventually change which branch determines completion.

Answer. Completion time $11$ hours; critical activities $A,D,E$ . Their critical path includes the zero-duration dummy from event $2$ to event $3$ .

Check. $3+0+5+3=11$ ; the old $ACE$ path still takes $10$ hours.

An activity is critical when $L_j-E_i-d_{ij}=0$ . Equal early and late times at its endpoints alone are not enough unless the activity duration also fills the gap between them.

Watch out

Wrong: $E_4=\min(3+4,3+5)$ after increasing $D$ to five hours. Event $4$ must wait for both incoming activities, not the first to finish. Correct: $E_4=\max(3+4,3+5)=8$ ; use minima for the backward pass instead.

Choose maxima forward and minima backward in the next pair of passes.

Continue this lesson.

You’re previewing NovaLearn without an account. Create a free account to read the rest.

Create free account

Last Accessed

Core Pure

Mechanics (Major and Minor)

Statistics (Major and Minor)

Modelling with Algorithms

Numerical Methods

Extra Pure

Further Pure with Technology

AN8, AN9 - Critical path analysis

Build an activity-on-arc network

Make forward and backward passes

Continue this lesson.

Learn faster with Nova