Activity Networks

A project takes as long as its longest chain of dependent work.

A small pump house takes six activities. Their durations add up to 23 days, yet the job finishes in 16, because some crews work at the same time. Then the owner pays extra to get the pump installed in 1 day instead of 3, and the finish date doesn't move at all. By the end of this Lesson, you'll be able to see both of those coming from a diagram.

What waits for what

A schedule starts with three facts about each activity: what the work is, how long it takes (its duration), and what has to be finished before it can start. You can't pour a foundation into a hole nobody has dug. Questions lay these facts out in a precedence table. Here's the pump house:

Precedence table for the pump house
ActivityWorkDaysImmediate predecessors
AExcavate3None
BPour foundation5A
CLay buried pipe4A
DErect walls and roof6B
EInstall pump3B, C
FConnect and test2D, E

The word immediate matters. A has to be done before F can start, but the table doesn't list A for F, because F waits for D and E, and the chains behind them already take care of A. An earlier activity that holds this one up only by way of another isn't an immediate predecessor.

Two ways to draw the same logic

A table holds all the logic, but you can't see the shape of the job in it, so we draw it as a network. The Handbook's Construction section says questions may use either the activity-on-node method or the activity-on-arrow method, so you need to read both. They differ only in where they put the work.

Activity-on-node

In activity-on-node, each activity is a box (a node), and each arrow is a dependency: the activity at the tail must finish before the one at the head can start. All the time sits in the boxes, and the arrows take none. The Handbook's node annotation also has slots for dates and float, which later Lessons fill in.

A 3 B 5 C 4 D 6 E 3 F 2
The pump house as an activity-on-node network
Each box holds an activity's letter and its duration in days.

Drawing this from the table takes one box per row and one arrow per listed predecessor, no more. E lists B and C, so two arrows end at E. Reading goes the other way: an activity's immediate predecessors are the boxes at the tails of the arrows ending at it. To check a diagram against a table, go row by row and ask whether the arrows ending at each box are exactly the ones listed.

Activity-on-arrow

In activity-on-arrow, each activity is an arrow, and the numbered circles are events: moments in time that take no time and no crew. Event 5 is the moment when D and E are both done, and F, which leaves event 5, can't start before it. The circles aren't activities, and their numbers aren't durations. The Handbook's annotation for this style shows one arrow from circle ii to circle jj, with the activity above the line and its duration below, so an activity can also go by its two events: B is activity (2, 3).

1 2 3 4 5 6 A 3 B 5 C 4 D 6 E 3 F 2 dummy
The same job as an activity-on-arrow network
Letters above the arrows name the activities, and numbers below give their durations in days.

The dashed arrow is a dummy, and it's there to solve a small logic problem. E waits for B and C, but D waits only for B. Try drawing that with real arrows alone. If B and C both end at one event, then D, leaving that event, waits for C too, which is false. So B gets its own event 3, D leaves from there, and the dummy runs from event 3 to event 4 to say that E waits for B as well. A dummy represents no work and has a duration of 0. It carries logic and nothing else, and its direction matters: pointed the other way, it would say D waits for C. The Handbook doesn't mention dummies, so this one is yours to remember.

To read immediate predecessors here, go to the event where the activity's arrow starts and take every arrow ending there. If one is a dummy, walk back through it and take the arrows ending at its tail too. E starts at event 4. C ends there, and so does the dummy from event 3, where B ends. That gives B and C, just as the table says. Run that on every row, and you've checked an on-arrow diagram against a table.

Checkpoint
1 of 4

Which line correctly describes both diagram styles?

A.
In both styles: nodes are activities, and arrows are dependencies.
B.
Activity-on-node: nodes are activities, and arrows are dependencies. Activity-on-arrow: nodes are events, and arrows are activities.
C.
Activity-on-node: nodes are events, and arrows are activities. Activity-on-arrow: nodes are activities, and arrows are dependencies.
D.
Activity-on-node: nodes are activities, and arrows take time. Activity-on-arrow: nodes are events, and arrows take no time.

The longest path sets the finish

A path is a route through the network that follows the arrows from start to finish. The pump house has three: A-B-D-F, A-B-E-F, and A-C-E-F. Now run the thought experiment. Along any one path, each activity waits for the one before it, so that path can't finish faster than its durations added together. The project isn't done until every path is done. So the project can't beat its longest path, and if every crew starts the moment it's allowed to, it doesn't take any longer than that either.

A-B-D-F A B D F 16 A-B-E-F A B E F 13 A-C-E-F A C E F 12 Finish: day 16 0 2 4 6 8 10 12 14 16 Days
The pump house's three paths, drawn to scale
Each bar adds the durations along one path. The job finishes when the longest bar does, on day 16.

That longest path is the critical path, and its activities are the critical activities. Here, A, B, D, and F set the finish date, while C and E have room to spare. The 23 days from the start of this Lesson was every duration added up, which pretends no two crews ever work at the same time. The Handbook prints the rule in the Critical Path Method (CPM) section of its Industrial and Systems Engineering chapter, not in the Construction section:

T=∑(i, j)∈CPdijT = \sum_{(i,\,j) \in CP} d_{ij}

Here, TT is the project duration, dijd_{ij} is the duration of activity (i,j)(i, j), and CPCP is the critical path, which the Handbook glosses as "longest path." The equation is only addition. Finding the path is left to you, so here's the habit: start at the beginning, and at each fork, follow one branch to the end, then come back for the others. If several activities have no predecessor, start from each. When you're done, every arrow should be on at least one path. Longest means the most days, however many activities that takes.

Listing paths is the quick way on a small network and a good check on a larger one. The Forward Pass gets the duration without listing anything.

Worked Example Finding the critical activities
1 of 2

For this network, with durations in days, find the project duration and the critical activities.

A 2 B 3 C 9 D 2 E 4 F 3 G 4
An activity-on-node network with seven activities

Reading paths on an activity-on-arrow network

The idea doesn't change when the activities move onto the arrows. Trace the arrows from the first event to the last, and add the durations written on them. The numbers in the circles are only labels, which makes them handy for naming a path, and questions often do.

The pump house's paths, named both ways
ActivitiesEventsDays
A-B-D-F1-2-3-5-63 + 5 + 6 + 2 = 16
A-B-dummy-E-F1-2-3-4-5-63 + 5 + 0 + 3 + 2 = 13
A-C-E-F1-2-4-5-63 + 4 + 3 + 2 = 12

These are the same three paths with the same three totals, as they should be, since it's the same job. The dummy adds 0 days, but the middle path exists only because of it. So treat a dummy as a real link with no time on it: skip it and you lose a path, and give it a duration and you stretch one.

Checkpoint
1 of 2
1 2 3 4 5 6 A 8 B 3 C 5 D 9 E 2 F 3
An activity-on-arrow network, with durations in days

What is the project duration?

days

When two paths tie

Nothing says the longest path has to be unique. Suppose the pump takes 6 days to install instead of 3. Then A-B-E-F grows to 16 days and ties A-B-D-F, while A-C-E-F reaches 15. Both 16-day paths are critical, so every activity on either one is critical: A, B, D, E, and F. Only C has room to spare. A question asking for the critical activities wants that whole list, and stopping at the first long path you find will miss some.

Checkpoint
A 6 B 4 C 5 D 7 E 1 F 2 G 3
An activity-on-node network, with durations in days

Which activities are critical?

A.
A
B.
B
C.
C
D.
D
E.
E
F.
F
G.
G

What shortening an activity buys

Now the owner's surprise makes sense. A cut changes only the paths the activity is on. Back on the original pump house, the pump installation, E, isn't on the 16-day path, so when it drops from 3 days to 1, the two paths through it shrink, and the 16-day path stays exactly where it was. Shortening a noncritical activity never shortens the project.

Cutting a critical activity can help, though maybe not as much as you paid for. Cut D from 6 days to 1, and its path falls from 16 days to 11. But A-B-E-F is still 13 days, so the job now finishes on day 13: a 5-day cut buys 3 days. Partway through that cut, the critical path moved to A-B-E-F, and D isn't on it. So you can judge a cut without redrawing anything: take what's left of the paths it touches, and compare that with the longest path it doesn't touch.

As planned A-B-D-F A B D F 16 A-B-E-F A B E F 13 A-C-E-F A C E F 12 Finish: day 16 E cut from 3 days to 1 A-B-D-F A B D F 16 A-B-E-F A B E F 11 A-C-E-F A C E F 10 Finish: day 16 D cut from 6 days to 1 A-B-D-F A B D F 11 A-B-E-F A B E F 13 A-C-E-F A C E F 12 Finish: day 13 0 2 4 6 8 10 12 14 16 Days
The pump house's paths before and after each cut
All three panels share one scale. The dashed line marks the finish, which is set by the longest bar.
Checkpoint
1 of 3

Which statements about critical paths are always true?

A.
A critical path has the longest total duration.
B.
A critical path has the most activities.
C.
A network can have more than one critical path.
D.
Shortening an activity on a critical path by 4 days shortens the project by 4 days.
E.
Shortening an activity that's on no critical path doesn't shorten the project.

Recap

  • A precedence table lists each activity's duration and immediate predecessors: the activities it waits on directly, not the ones behind them.
  • In activity-on-node, nodes are activities and arrows are dependencies. In activity-on-arrow, nodes are events and arrows are activities, and a dashed dummy carries logic with a duration of 0.
  • A project takes as long as its longest path, in days: T=∑(i, j)∈CPdijT = \sum_{(i,\,j) \in CP} d_{ij}. Its activities are the critical ones.
  • When paths tie for longest, every activity on each tied path is critical.
  • Shortening a noncritical activity doesn't shorten the project, and shortening a critical one helps only until a path that skips it becomes the longest.