Year 12 General Mathematics: Critical path analysis from a precedence table

A precedence table lists the activities in a project, how long each one takes, and which activities have to be finished before it can start. From that table alone you can draw the project as a network and work out two things a manager actually needs: the shortest time the whole project can take, and which activities have no room to slip.

The critical path is the longest path through the network. That sounds backwards, but every path has to be walked before the project is done, so the longest one sets the finish time. Activities on it have zero float — delay any of them by a day and the whole project finishes a day late.

float = LST - EST

The project

A council is building a skate park. Twelve activities, durations in days.

Precedence table
Activity	Description	Duration (days)	Immediate predecessors
A	Survey the site	6	—
B	Apply for the building permit	4	—
C	Order the steel ramp modules	10	—
D	Book the traffic-control crew	3	—
E	Clear and level the ground	5	A
F	Excavate the bowl	8	B
G	Fabricate the handrails	7	C
H	Close the access road	4	D
I	Lay the reinforcing steel	9	E, F
J	Pour and cure the concrete	6	C, H, I
K	Powder-coat the handrails	5	G
L	Install the ramps and open	4	J, K

Step 1: draw the activity network

In this style of network the activities are the arrows and the numbered circles are events — moments in time, not jobs. An activity can start once every arrow feeding into its circle has arrived.

Work down the predecessor column. A, B, C and D have no predecessors, so all four leave the start event. E follows A, F follows B, and so on. Where an activity has several predecessors, they all have to land on the same circle: I needs both E and F, so those two arrows meet at event 6.

Why there is a dashed arrow. Look at C. On its own it is the predecessor of G; together with H and I it is a predecessor of J. One arrow cannot end in two different circles. So C ends at its own event and a dummy activity — dashed, duration 0 — carries the fact that C is finished across to where J begins. A dummy takes no time and uses no resources. It only carries a dependency.

Activities on the arrows, events in the circles. The dashed arrow is the dummy.

Step 2: forward scan for the earliest starting times

Start at event 1 with 0 and move left to right. The earliest time an event can be reached is set by the slowest arrow arriving at it, because every one of them has to finish first.

Forward scan: take the largest of (EST at the tail of each arrow) + (duration of that arrow).

Event 6 has E arriving from event 2 and F arriving from event 3:

EST (6) = \max (6 + 5, 4 + 8) = 12

Event 7 is the busy one — I from event 6, H from event 5, and the dummy from event 4:

EST (7) = \max (12 + 9, 3 + 4, 10 + 0) = 21

Carrying on gives 27 at event 9 and 31 at event 10. That last number is the answer to “what is the minimum time to complete the project”: the earliest the final event can possibly happen is day 31.

Step 3: backward scan for the latest starting times

Now go the other way. Put 31 on the last event and work right to left, asking of each event: how late can this happen without pushing the finish past day 31? Here the tightest arrow leaving the event wins.

Backward scan: take the smallest of (LST at the head of each arrow) − (duration of that arrow).

Event 4 has two arrows leaving it, G to event 8 and the dummy to event 7:

LST (4) = \min (22 - 7, 21 - 0) = 15

Keep going and event 1 comes back to 0. It always should — if it does not, there is an arithmetic slip somewhere in the scan, and that check is worth doing every time.

Step 4: float, and the critical path

Each event now carries two numbers: the earliest it can happen and the latest it may happen. The gap is how much slack there is. Where the two numbers are equal there is no slack at all, and those events are on the critical path.

Each box holds EST on the left and LST on the right. The highlighted route is the critical path.

For an individual activity, its float is the room between the earliest it can start and the latest it may start:

float = LST at the head - EST at the tail - duration

For G, which runs from event 4 to event 8, that is 22 − 10 − 7 = 5 days of float. Doing this for every activity:

Critical path analysis
Activity	Duration	EST	LST	Float
A	6	0	1	1
B	4	0	0	0	critical
C	10	0	5	5
D	3	0	14	14
E	5	6	7	1
F	8	4	4	0	critical
G	7	10	15	5
H	4	3	17	14
I	9	12	12	0	critical
J	6	21	21	0	critical
K	5	17	22	5
L	4	27	27	0	critical

Five activities have zero float, and they join up into one continuous route from start to finish:

B \to F \to I \to J \to L

4 + 8 + 9 + 6 + 4 = 31 days

The critical path length matches the forward scan, which is the final check that the analysis hangs together. The minimum time to complete the project is 31 days.

What the float column is telling you

C is the longest single activity in the project at 10 days, and it is not critical — it has 5 days of float. How long one activity takes says nothing on its own about whether it matters. What matters is the path it sits on.
D and H have 14 days of float between them. The traffic-control crew could be booked a fortnight late and the park would still open on day 31.
Float is shared along a branch, not stockpiled per activity. D and H do not have 14 days each; the branch has 14 days in total, and using it on D leaves none for H.
To finish sooner than day 31 you must shorten something on the critical path. Speeding up C or G changes nothing at all.

Common mistakes

Taking the minimum on the forward scan and the maximum on the backward scan. It is the other way round: everything feeding an event must finish, so forward takes the largest; nothing leaving may be late, so backward takes the smallest.
Forgetting the dummy, and drawing C straight into J's circle. That would make G wait for H and I as well, which the table never said.
Giving the dummy a duration. It is always 0.
Calling the path with the most activities critical. Here the critical path has five activities and the route through C and G has four, but that is a coincidence — count days, not arrows.
Stopping at the forward scan. It gives the project length, but not which activities are critical; that needs the backward scan too.
Reporting a critical path that is not a connected route from the start event to the final event. If your zero-float activities do not join up, recheck the scans.

Next step: once you can identify the critical path and calculate float, learn how to shorten a project at the lowest possible cost in Project crashing and minimum-cost scheduling.