Critical paths and floatEdexcel International A Level Maths: Revision notes

The earliest event time $e(i)$ is the earliest time at which event $i$ can occur, and so the earliest time any activity leaving it can start. To find it, work forwards from the start:

• set $e(1)=0$;
• for each later event $j$, find $e(i)+d$ for every activity or dummy arriving at it, and take the largest, since every arriving activity must be complete;
• the value at the finish event is the minimum project duration. Example: A (1 to 2, 3 days), B (1 to 3, 5), C (2 to 4, 6), D (3 to 4, 2). Then $e(2)=3$, $e(3)=5$, and $e(4)=\max(3+6,\,5+2)=9$. A dummy has duration 0, so $e(j)\ge e(i)$ along it.

The latest event time $l(j)$ is the latest time event $j$ can occur without delaying the project. Work backwards:

• set $l(n)=e(n)$ at the finish event;
• for each earlier event $i$, find $l(j)-d$ for every activity or dummy leaving it, and take the smallest, since every leaving activity must still finish on time. Example (the network above, with E from 3 to 5 for 4 days, F from 4 to 6 for 3, G from 5 to 6 for 5, and $e(6)=14$): $l(6)=14$, $l(5)=14-5=9$, $l(4)=14-3=11$, $l(3)=\min(11-2,\,9-4)=5$, $l(2)=11-6=5$, $l(1)=\min(5-3,\,5-5)=0$. A good check is $l(1)=0$; if it is not, there is an arithmetic error.

For an activity from event $i$ to event $j$ with duration $d$:

• earliest start time $=e(i)$;
• earliest finish time $=e(i)+d$;
• latest finish time $=l(j)$;
• latest start time $=l(j)-d$. Example: C (2 to 4, 6 days) with $e(2)=3$ and $l(4)=11$: earliest start 3, earliest finish 9, latest finish 11, latest start 5. The difference between the latest and earliest start (or finish) times is the activity's slack.

The total float of an activity is the amount by which it can be delayed (or extended) without delaying the project, assuming all other activities start as early as possible: $F(i,j)=l(j)-e(i)-d(i,j).$ It is the time available between the earliest start and the latest finish, minus the time the activity needs. In the example, $F(\text{D})=l(4)-e(3)-2=11-5-2=4$ days, so D can start up to 4 days late. $F(\text{A})=5-0-3=2$ and $F(\text{C})=11-3-6=2$. Total float is never negative on a valid network.

An activity is critical if its total float is 0. It has no freedom: any delay in it delays the whole project. The critical path is a path from the start to the finish consisting of critical activities, and its length equals the minimum project duration. To find it: carry out both passes, then find the activities with $F=0$ (equivalently with $e(i)=l(i)$, $e(j)=l(j)$ and $l(j)-e(i)=d$). In the first example, B, E and G are critical: $5+4+5=14$. Warning: an activity can join two events with equal earliest and latest times and still not be critical, if its duration is less than $l(j)-e(i)$. There can be more than one critical path (for example, two routes of equal length). Dummies on a critical path are included in the path.