Critical Path Analysis

Every large undertaking — building a house, staging a concert, launching a product — is a web of tasks, some of which must wait for others. Critical Path Analysis (CPA) turns that web into a network and answers three sharp questions: what is the shortest possible time to finish the whole project?, which tasks are so tight that any delay to them delays everything?, and how much slack does each non-critical task have? The mathematics is a pair of passes through a directed graph — a forward pass that propagates earliest times and a backward pass that propagates latest times — followed by a float calculation. It is one of the most directly applicable topics in the whole Discrete option.

---

1. Where this sits in AQA 7367

This is a core modelling topic of the Paper 3 Discrete option (7367/3D) (Paper 3: 2 h, 100 marks, 33⅓%; AO1 40% / AO2 25% / AO3 35%). Drawing the activity network and carrying out the forward/backward passes is AO1; identifying the critical path, interpreting float, and reasoning about resource scheduling (how few workers can finish on time) are AO2/AO3. AQA 7367 uses the activity-on-node (AoN) convention with each activity drawn as a box recording earliest and latest times — that is the form developed and examined here.

---

2. Core theory: activities, precedence and the activity-on-node box

A project is a set of activities, each with a duration, and a set of precedence (dependency) relations: activity $Y$Y cannot start until its immediate predecessors are complete. We record this in a precedence (dependence) table.

Activity	Duration (days)	Immediate predecessors
A	4	—
B	3	—
C	5	A
D	2	A, B
E	6	C
F	3	D
G	4	E, F

In the activity-on-node (AoN) representation each activity is a vertex, drawn as a box, and an arrow $X \to Y$X→Y means "$X$X immediately precedes $Y$Y". The box carries four numbers around the activity's name and duration:

Earliest start (ES)	Duration	Earliest finish (EF)
Latest start (LS)	Activity	Latest finish (LF)

with the defining relations, for every activity,

$\text{EF} = \text{ES} + \text{duration}, \qquad \text{LS} = \text{LF} - \text{duration}.$EF=ES+duration,LS=LF−duration.

The dependency graph for the table above:

graph LR
  START((Start)) --> A[A 4]
  START --> B[B 3]
  A --> C[C 5]
  A --> D[D 2]
  B --> D
  C --> E[E 6]
  D --> F[F 3]
  E --> G[G 4]
  F --> G
  G --> END((Finish))

(The older activity-on-arc convention puts activities on the edges and milestones on the vertices, and then needs dummy activities — duration-zero dashed arcs — to separate tasks that share endpoints or to carry partial dependencies. AoN avoids dummies entirely, which is why it is the cleaner modern choice.)

The four box numbers are not independent: knowing any two of ES, EF, LS, LF together with the duration determines the other two, via $\text{EF} = \text{ES} + d$EF=ES+d and $\text{LS} = \text{LF} - d$LS=LF−d. The forward pass fills the top of every box (ES, EF) left to right; the backward pass fills the bottom (LS, LF) right to left; the gap between top and bottom — the float — is what scheduling then exploits. A useful sanity check while drawing: at the source, ES $= \text{LS} = 0$=LS=0; at the sink, EF $= \text{LF} =$=LF= the project duration. If those endpoints do not match after both passes, an arithmetic slip has crept in. Holding the meaning of each number in mind — "earliest I can possibly begin", "latest I dare finish" — guards against the classic error of mechanically copying a neighbour's value without checking whether it is a merge (max) or a burst (min).

---

3. The forward pass: earliest times (with M1/A1 mark scheme)

The forward pass sweeps left to right, computing how early each activity can begin:

• An activity with no predecessors has $\text{ES} = 0$ES=0.
• Otherwise $\text{ES} = \max(\text{EF of all immediate predecessors})$ES=max(EF of all immediate predecessors) — you must wait for the last prerequisite.
• Then $\text{EF} = \text{ES} + \text{duration}$EF=ES+duration; the project duration is the largest EF.

Worked Example 3.1 — forward pass

Carry out the forward pass for the table in §2.

$$\begin{aligned} \text{A: } & \text{ES}=0,\ \text{EF}=4, & \text{B: } & \text{ES}=0,\ \text{EF}=3, \\ \text{C: } & \text{ES}=\text{EF(A)}=4,\ \text{EF}=9, & \text{D: } & \text{ES}=\max(4,3)=4,\ \text{EF}=6, \\ \text{E: } & \text{ES}=\text{EF(C)}=9,\ \text{EF}=15, & \text{F: } & \text{ES}=\text{EF(D)}=6,\ \text{EF}=9, \\ \text{G: } & \text{ES}=\max(\text{EF(E)},\text{EF(F)})=\max(15,9)=15,\ \text{EF}=19. && \end{aligned}$$A: C: E: G: ​ES=0, EF=4,ES=EF(A)=4, EF=9,ES=EF(C)=9, EF=15,ES=max(EF(E),EF(F))=max(15,9)=15, EF=19.​B: D: F: ​ES=0, EF=3,ES=max(4,3)=4, EF=6,ES=EF(D)=6, EF=9,​

(M1 for taking the maximum of predecessor finishes at a merge — at D and at G; A1 for all earliest times correct.) The largest earliest finish is $19$19, so the minimum project duration is $19$19 days. (A1.)

Exam tip. At a merge node take the maximum — a frequent slip is to add or to take the minimum. The single number you must underline is the project duration, here $19$19.

---

4. The backward pass and float (with M1/A1 mark scheme)

The backward pass sweeps right to left, computing how late each activity may finish without lengthening the project:

• An activity with no successors has $\text{LF} = \text{project duration}$LF=project duration.
• Otherwise $\text{LF} = \min(\text{LS of all immediate successors})$LF=min(LS of all immediate successors) — you must finish before the earliest thing that needs you must start.
• Then $\text{LS} = \text{LF} - \text{duration}$LS=LF−duration.

Worked Example 4.1 — backward pass

Continue with the project (duration $19$19).

$$\begin{aligned} \text{G: } & \text{LF}=19,\ \text{LS}=15, & \text{E: } & \text{LF}=\text{LS(G)}=15,\ \text{LS}=9, \\ \text{F: } & \text{LF}=\text{LS(G)}=15,\ \text{LS}=12, & \text{C: } & \text{LF}=\text{LS(E)}=9,\ \text{LS}=4, \\ \text{D: } & \text{LF}=\text{LS(F)}=12,\ \text{LS}=10, & \text{B: } & \text{LF}=\text{LS(D)}=10,\ \text{LS}=7, \\ \text{A: } & \text{LF}=\min(\text{LS(C)},\text{LS(D)})=\min(4,10)=4,\ \text{LS}=0. && \end{aligned}$$G: F: D: A: ​LF=19, LS=15,LF=LS(G)=15, LS=12,LF=LS(F)=12, LS=10,LF=min(LS(C),LS(D))=min(4,10)=4, LS=0.​E: C: B: ​LF=LS(G)=15, LS=9,LF=LS(E)=9, LS=4,LF=LS(D)=10, LS=7,​

(M1 for the minimum of successor latest-starts at a burst node — at A; A1 for all latest times correct.)

Total float

The total float of an activity is how long it can be delayed without delaying the project:

$\text{total float} = \text{LF} - \text{ES} - \text{duration} \;=\; \text{LS} - \text{ES}.$total float=LF−ES−duration=LS−ES.

Activity	ES	EF	LS	LF	Total float	Critical?
A	0	4	0	4	$0$0	✔
B	0	3	7	10	$7$7
C	4	9	4	9	$0$0	✔
D	4	6	10	12	$6$6
E	9	15	9	15	$0$0	✔
F	6	9	12	15	$6$6
G	15	19	15	19	$0$0	✔

(A1 for the float column.) The activities with zero float form the critical path A → C → E → G, of length $4 + 5 + 6 + 4 = 19$4+5+6+4=19 — equal, as it must be, to the project duration.

---

5. A second walkthrough: a full project from a table

A project has the dependence table below. Find the project duration and the critical path.

Activity	Duration	Predecessors
P	5	—
Q	4	—
R	6	P
S	3	P, Q
T	2	R, S
U	4	S

Forward pass. P: ES $0$0, EF $5$5. Q: ES $0$0, EF $4$4. R: ES $5$5, EF $11$11. S: ES $\max(5,4)=5$max(5,4)=5, EF $8$8. T: ES $\max(11,8)=11$max(11,8)=11, EF $13$13. U: ES $8$8, EF $12$12. Project duration $= \max(13,12) = 13$=max(13,12)=13.

Backward pass (end $=13$=13). T: LF $13$13, LS $11$11. U: LF $13$13, LS $9$9. R: LF $\text{LS(T)}=11$LS(T)=11, LS $5$5. S: LF $\min(\text{LS(T)},\text{LS(U)})=\min(11,9)=9$min(LS(T),LS(U))=min(11,9)=9, LS $6$6. P: LF $\min(\text{LS(R)},\text{LS(S)})=\min(5,6)=5$min(LS(R),LS(S))=min(5,6)=5, LS $0$0. Q: LF $\text{LS(S)}=6$LS(S)=6, LS $2$2.

Floats (LS − ES): P $0$0, Q $2$2, R $0$0, S $1$1, T $0$0, U $1$1. The critical path is P → R → T, length $5 + 6 + 2 = 13$5+6+2=13. The non-critical activities Q, S, U have a little slack, which §6 will let us exploit when scheduling workers.

---

6. Scheduling, free float and resource levelling

Total float is shared along chains of activities, so using one activity's slack can rob a later activity of its own. The finer free float measures the delay possible without disturbing any successor's earliest start:

$\text{free float} = \text{ES(successor)} - \text{EF(activity)} \quad(\le \text{total float}).$free float=ES(successor)−EF(activity)(≤total float).

For the §3–§4 project: activity B has total float $7$7 but free float $\text{ES(D)} - \text{EF(B)} = 4 - 3 = 1$ES(D)−EF(B)=4−3=1 — delaying B beyond one day eats into D's slack; activity F has total float $6$6 and free float $\text{ES(G)} - \text{EF(F)} = 15 - 9 = 6$ES(G)−EF(F)=15−9=6 (all of it free, since G is critical and cannot move). A Gantt (cascade) chart plots each activity against time with its float shown as a bar, and resource levelling slides non-critical activities within their float to flatten the peak demand for workers — for instance, scheduling B at its latest start can avoid clashing with A's labour requirement. The critical activities, having zero float, are fixed; only the floated ones can be moved.

A worked resource question makes the idea concrete. Suppose in the §3–§4 project each activity needs one worker for its whole duration, and we ask: can the project finish in $19$19 days using only two workers at any time? The critical chain A, C, E, G is fixed at days $0\!-\!4$0−4, $4\!-\!9$4−9, $9\!-\!15$9−15, $15\!-\!19$15−19 and uses one worker throughout. The floated activities B ($3$3 days, total float $7$7), D ($2$2 days, float $6$6) and F ($3$3 days, float $6$6) must each be slotted somewhere in their windows. If we schedule B at its earliest start (days $0\!-\!3$0−3) it overlaps A, needing two workers early; pushing B to its latest start (days $7\!-\!10$7−10) spreads the load. Because each floated activity has ample slack, a feasible two-worker schedule exists — but the minimum peak demand is itself an optimisation question, and that is precisely the bridge to linear and integer programming in the next two lessons. The exam-relevant message is that float is the resource that scheduling spends: every day of total float you hand to one activity is a day you may have taken from another downstream.

Reading a precedence table correctly