7.05a–7.05c - Activity networks and critical paths | OCR A-Level Further Mathematics A

Turn a list of jobs into an activity network, then find how quickly the whole project can finish. You will construct activity-on-arc networks in 7.05a, use forward and backward passes to find critical activities in 7.05b, and calculate total float in 7.05c.

Constructing activity networks

A gallery needs five jobs completed before an exhibition opens. Preparing the room takes $3$ hours, connecting the equipment takes $4$ , making signs takes $2$ , testing takes $5$ , and opening checks take $1$ . Must this project take all $15$ hours, and could making the signs take four extra hours without delaying the opening? The order of the jobs matters as much as their lengths.

You already know

A graph has vertices and arcs joining them. A path follows consecutive arcs without repeating vertices. The connections matter, rather than the position of the drawing on the page.

Here the arcs are directed: an arrow records the order in which events must occur, and a directed path follows those arrows. Some jobs can happen together. Others have to wait: the signs require the prepared room, testing requires both the room and the equipment, and opening checks require both signs and testing. The table records only immediate predecessors: jobs which must finish before that activity can start, with no intervening activity in that dependency.

Activity	Job	Immediate predecessors	Duration, hours
$A$	Prepare the room	none	$3$
$B$	Connect equipment	none	$4$
$C$	Make signs	$A$	$2$
$D$	Test	$A, B$	$5$
$E$	Opening checks	$C, D$	$1$

An activity network records these dependencies without assigning workers. For now, assume enough resources for every available activity to start immediately, with fixed durations and no interruption.

Activity-on-arc network

In an activity-on-arc network, each activity is a directed arc labelled with its name and duration. A vertex represents an event: completion of all activities entering it, allowing activities leaving it to start. An event takes no time. A burst has more than one outgoing arc; a merge has more than one incoming arc. For example, the project start is a burst when $A$ and $B$ can begin together. An activity written inside a vertex is activity-on-node, which is a different representation.

Use a single start and a single finish, with all arcs directed. Numbering events so that arrows go from smaller to larger numbers helps prevent accidental directed cycles. A project cannot require a job to precede itself.

Sometimes two dependencies need to be separated. In this project $D$ needs both $A$ and $B$ , but $C$ needs only $A$ . Merging $A$ and $B$ before both $C$ and $D$ would wrongly make $C$ wait for $B$ .

Dummy activity

A dummy activity is a directed arc of duration $0$ , drawn dashed. It records a dependency and represents no actual work. It can also distinguish activities that would otherwise have the same start and finish events. For example, a dummy from the end of $A$ to the end of $B$ can make $D$ wait for $A$ while leaving $C$ free to follow $A$ alone. A dashed dummy is still an arc whose direction must be respected.

Construct from the dependencies, then read the resulting network back as a check. Use a dummy only when it carries necessary information.

Worked example 1: separating two predecessor lists

Question. Construct an activity-on-arc network for the gallery project in the table above.

Plan. Give $A$ and $B$ separate finish events, join them for $D$ with one dummy, then merge $C$ and $D$ before $E$ .

\begin{aligned} A &: 1\longrightarrow 2\quad (3) && \text{room starts immediately} \\ B &: 1\longrightarrow 3\quad (4) && \text{equipment starts immediately} \\ \text{dummy} &: 2\longrightarrow 3\quad (0) && D\text{ must also wait for }A \\ C &: 2\longrightarrow 4\quad (2) && C\text{ needs only }A \\ D &: 3\longrightarrow 4\quad (5) && \text{both predecessors now complete} \\ E &: 4\longrightarrow 5\quad (1) && \text{merge }C\text{ and }D \end{aligned}

Why this step? Event $3$ can occur only after both $B$ and the dummy from $A$ have finished. Event $2$ can occur after $A$ alone, so $C$ has the correct, shorter predecessor list.

Answer. The left-hand network below has exactly the required precedences and one dummy activity.

Check. Reading backwards from $E$ gives $C, D$ ; from $D$ gives $A, B$ ; from $C$ gives $A$ alone. There is one start, one finish and no directed cycle.

Worked example 2 changes one feature: an extra job follows testing alone. A second dummy is now needed, because the new job must not wait for the signs.

Worked example 2: separating a second merge

Question. The gallery adds activity $F$ , which lasts $2$ hours and follows $D$ alone. The project is complete when both $E$ and $F$ finish. All five original activities and their dependencies are unchanged. Construct an activity network.

Plan. Keep the first dummy, separate the finish of $D$ from the merge of $C, D$ , and use a second dummy to carry $D$ 's dependency into that merge.

\begin{aligned} A &: 1\longrightarrow2\quad(3) && \text{room completion event} \\ B &: 1\longrightarrow3\quad(4) && \text{equipment completion event} \\ \text{dummy} &: 2\longrightarrow3\quad(0) && D\text{ still needs }A,B \\ D &: 3\longrightarrow4\quad(5) && \text{testing has its own finish} \\ C &: 2\longrightarrow5\quad(2) && \text{signs arrive at the later merge} \\ \text{dummy} &: 4\longrightarrow5\quad(0) && E\text{ still needs }C,D \\ E &: 5\longrightarrow6\quad(1) && \text{opening checks} \\ F &: 4\longrightarrow6\quad(2) && F\text{ needs }D\text{ alone} \end{aligned}

Why this step? Starting $F$ at the same merge as $E$ would wrongly make it depend on $C$ . The dummy $4\to5$ lets $E$ wait for testing without making $F$ wait for the signs.

Answer. The right-hand network below uses exactly two directed dummy activities and has one finish at event $6$ .

Check. Reading immediate predecessors gives $C:A$ , $D:A,B$ , $E:C,D$ , and $F:D$ . Neither $E$ nor $F$ depends on the other, and the project waits for both.

Compare the diagrams at the second merge, where the new job needs a different predecessor list.

[DIAGRAM: asset_name: Dummies preserve different predecessor lists; asset_slug: h245_7_05_activity_construction; caption: One dummy separates the dependencies of C and D. Adding F after D alone requires a second dummy before the merge for E; description: Left panel has the original five-event gallery network with dummy 2 to 3. Right panel adds F of duration 2 and uses six events: A 1 to 2, B 1 to 3, dummy 2 to 3, D 3 to 4, C 2 to 5, dummy 4 to 5, E 5 to 6 and F 4 to 6. Both diagrams have all arcs directed, labelled real activities, dashed zero-duration dummies, a single start and a single finish]
One dummy separates the dependencies of C and D. Adding F after D alone requires a second dummy before the merge for E

A correct diagram is judged by its dependencies, not by its shape on the page.

Watch out

Wrong: merge $A$ and $B$ and then start both $C$ and $D$ . That makes $C$ depend on $B$ . Right: keep separate completion events and use a directed dummy to pass only the required dependency to $D$ .

Now separate both merges in a project with different activities.

Earliest times and the forward pass

At a merge, an event must wait for every incoming activity, so its earliest possible time is the latest of their finishing times.

Return to the original gallery project, with the dummy and $C$ lasting $2$ hours. Write $E_i$ for the earliest event time at vertex $i$ , taking the project start as time $0$ . The outgoing activities can start at $E_i$ , so this is also their earliest start time. For example, $C$ can start at time $3$ , immediately after $A$ .

Forward pass

For an activity $i\to j$ of duration $d_{ij}$ , its earliest completion is $E_i+d_{ij}$ . Starting with $E_1=0$ , calculate

E_j=\max_{i\to j}(E_i+d_{ij})

over all arcs entering event $j$ , including dummies of duration $0$ . The earliest time at the single finish event is the minimum project completion time, assuming sufficient resources.

Not in the formula booklet: learn it.

The maximum is essential: arriving by one short route does not complete the work on the other routes.

Worked example 3: a merge waits for the later branch

Question. Carry out a forward pass for the original gallery network and determine the minimum project completion time.

Plan. Work from the start towards the finish, adding each arc's duration and taking the maximum at each merge.

\begin{aligned} E_1&=0 && \text{start} \\ E_2&=0+3=3 && \text{complete }A \\ E_3&=\max(0+4,3+0)=4 && B\text{ and the dummy must finish} \\ E_4&=\max(3+2,4+5)=9 && C\text{ and }D\text{ must finish} \\ E_5&=9+1=10 && \text{complete }E \end{aligned}

Why this step? Although the signs finish at time $5$ , testing finishes at time $9$ . Opening checks cannot begin until both are complete.

Answer. The earliest event times are $0,3,4,9,10$ . The minimum project completion time is $10$ hours.

Check. Activities $B,D,E$ must occur consecutively and take $4+5+1=10$ hours, so no shorter completion time is possible.

Worked example 4 changes one duration: the signs now take $7$ hours. The maximum at the merge may therefore come from a different branch.

Worked example 4: a different branch becomes the bottleneck

Question. Activity $C$ now takes $7$ hours; all other gallery data are unchanged. Determine the new minimum project completion time by a forward pass.

Plan. Keep the early event times before $C$ , then recalculate from its finishing event onwards.

\begin{aligned} E_1=0,\quad E_2&=3,\quad E_3=4 && \text{earlier activities unchanged} \\ E_4&=\max(3+7,4+5)=10 && \text{compare the new finishes} \\ E_5&=10+1=11 && \text{opening checks follow} \end{aligned}

Why this step? The dependency structure has not changed, but the controlling branch has: $C$ now finishes after $D$ .

Answer. The project now takes at least $11$ hours.

Check. The path $A,C,E$ has length $3+7+1=11$ , agreeing with the finish event time.

The numbers at events belong to events, not to individual routes. Carry each number to every outgoing arc at a burst.

Continue this lesson.

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

Create free account

Last Accessed

Pure Core

Statistics

Mechanics

Discrete Mathematics

Additional Pure Mathematics

7.05a–7.05c - Activity networks and critical paths

Constructing activity networks

Earliest times and the forward pass

Continue this lesson.

Learn faster with Nova