Activity networks and precedence tables
A project is split into activities. Each has a duration (time it takes). A precedence table lists, for each activity, the activities that must finish first (its immediate predecessors).
In an activity-on-node network, each activity is a box (node). An arrow from A to C means C cannot start until A ends. Many networks also add a Start node and an End node.
Another style puts activities on the arrows (activity-on-arc) and may need dummy activities (dotted arrows, duration 0) to show some links correctly. The analysis is the same.
Example precedence table
A(3) and B(4) have no predecessors. C(2) and D(4) need A. E(6) needs B and C. F(3) needs D. G(2) needs E and F.
Early and late times: forward and backward pass
Forward pass (left to right): Earliest start ES of a start activity = 0. Earliest finish EF = ES + duration. For any other activity, ES = the largest EF of its predecessors. Why the largest? It has to wait for the slowest one.
The largest EF of all activities is the minimum project completion time.
Backward pass (right to left): Latest finish LF of a final activity = project time. Latest start LS = LF โ duration. For other activities, LF = the smallest LS of the activities that follow it. Why the smallest? It must not hold up the most urgent follower.
In our example: ES of E = max(EF of B = 4, EF of C = 5) = 5. LF of A = min(LS of C = 3, LS of D = 4) = 3.
Critical path and float
Total float = LS โ ES (= LF โ EF). It is how long an activity can be delayed without delaying the whole project.
An activity with total float 0 is critical. A chain of critical activities from start to end is the critical path. It is the longest path through the network, so its length is the project time. There can be more than one critical path.
Some courses also use independent float (how much an activity can slip without affecting any other activity even in the worst case) and interfering float = total float โ independent float.
Effect of changes to the model
If a critical activity takes 2 days longer, the project takes 2 days longer. If a non-critical activity takes longer by less than or equal to its float, nothing changes; by more than its float, the critical path changes. Shortening a critical activity can help only until another path becomes critical. In the scene, D has float 1, so D can rise from 4 to 5 days with no effect; at 6 days the project grows to 14.
Gantt charts, resource histograms and resource levelling
A Gantt (cascade) chart draws each activity as a bar on a time line, starting at its ES. Its float is shown as a pale or dotted extension. Critical activities have no extension.
A resource histogram shows how many workers (or machines) are needed in each time period. Add the workers of every activity running in that period.
Resource levelling: slide non-critical activities within their float so the histogram is flatter, or so it never goes above the number of workers you have. If you only have a fixed number of workers, you may need to extend the project. A lower bound for the number of workers is (total worker-days) รท (project time), rounded up.
Try it at home
Plan making tea and toast for your family: list the jobs (boil water, toast bread, butter, pour tea...), their times and what must come first. Draw the network and find the critical path. Can two people do it faster?
Key formulas and definitions
- EF = ES + duration; ES of an activity = the MAXIMUM EF of its predecessors.
- LS = LF โ duration; LF of an activity = the MINIMUM LS of its successors.
- Total float = LS โ ES = LF โ EF. Critical activity โ total float = 0.
- Project time = length of the critical (longest) path.
- Lower bound for workers = โ total worker-days รท project time โ.
Worked examples
1. Activities: A(3), B(4) start; C(2) and D(4) need A; E(6) needs B and C; F(3) needs D; G(2) needs E and F. Find the earliest start of every activity and the project time.
A: ES 0, EF 3. B: ES 0, EF 4. C: ES 3, EF 5. D: ES 3, EF 7. E: ES = max(4, 5) = 5, EF 11. F: ES 7, EF 10. G: ES = max(11, 10) = 11, EF 13. Project time = 13 days.
2. For the same project, do the backward pass and find the latest start of each activity.
G: LF 13, LS 11. E: LF 11, LS 5. F: LF 11, LS 8. D: LF 8, LS 4. C: LF 5, LS 3. B: LF 5, LS 1. A: LF = min(3, 4) = 3, LS 0.
3. Find each activity's total float and the critical path.
Float = LS โ ES: A 0, B 1, C 0, D 1, E 0, F 1, G 0. Critical path: A โ C โ E โ G (3 + 2 + 6 + 2 = 13 days).
4. D is delayed by 3 days (takes 7 days). What is the new project time?
D's float is 1, so 2 extra days spill over. New path A โ D โ F โ G = 3 + 7 + 3 + 2 = 15 days. That is longer than A โ C โ E โ G (13), so the project now takes 15 days and the critical path is A โ D โ F โ G.
5. Workers: A 2, B 1, C 3, D 2, E 2, F 1, G 3. Using earliest starts, how many workers are needed on day 3 (the period 3 to 4)?
Running: B (0โ4), C (3โ5), D (3โ7). Workers = 1 + 3 + 2 = 6.
6. Find a lower bound for the number of workers needed to finish in 13 days.
Worker-days = 2ร3 + 1ร4 + 3ร2 + 2ร4 + 2ร6 + 1ร3 + 3ร2 = 6 + 4 + 6 + 8 + 12 + 3 + 6 = 45. 45 รท 13 โ 3.46, so at least 4 workers.
Common mistakes
- Taking the smallest EF in the forward pass. An activity must wait for ALL predecessors, so use the largest.
- Taking the largest LS in the backward pass. Use the smallest, or a follower will be held up.
- Thinking the critical path is the shortest path. It is the longest path; that is why it fixes the project time.
- Delaying a non-critical activity by more than its float and assuming the project time is unchanged.