Critical paths and scheduling
Introduced| English | Meaning |
|---|---|
| critical path method | A method that finds the activities that control how long a project takes. |
| activity network | A diagram that shows a project's activities and the order in which they must be done. |
| precedence table | A table listing each activity of a project and the activities that must be finished before it. |
| dummy/ˈdʌmi/ | A zero-duration activity arc used to represent a dependency in an activity-on-arc network. |
| critical/ˈkrɪtɪkl/ | Describes an activity whose delay would delay the whole project; its float is zero. |
| float/fləʊt/ | The time an activity can be delayed without delaying completion under the network model. |
| total float/ˈtəʊtl fləʊt/ | The delay available to an activity without delaying project completion: latest finish minus earliest start minus duration. |
| Gantt chart/ɡænt tʃɑːt/ | A bar chart showing scheduled activities and their timing along a time axis. |
Planning a chemical-plant shutdown, 1957
- In 1957, James Kelley of Remington Rand and Morgan Walker of the chemical company DuPont built the critical path method 关键路径法 to plan the maintenance shutdowns of DuPont's plants. Knowing which jobs could not be delayed cut the shutdown time, and the cost, sharply.
- D1 draws a project as an activity network 活动网络, finds the shortest possible project time and the jobs that control it.
Precedence and the network
- A precedence table 先后关系表 lists each activity, its duration and the activities that must finish first.
- In an activity-on-arc network, each activity is an arc between events. A dummy 虚活动 (dashed, duration 0) shows a dependence that the arcs alone cannot.
A dummy activity has a duration of zero.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
It shows only that one activity depends on another.
Early and late times
- Forward pass: the early time of an event is the largest of (early time + duration) over the activities into it.
- Backward pass: the late time of an event is the smallest of (late time − duration) over the activities out of it, starting from the project time at the end.
Critical paths and scheduling
For an activity network, calculate earliest event times forward and latest event times backward
Compare the model with the worked case and explain one change.
Activities into an event: P with early start 2 and duration 6, Q with early start 4 and duration 3. Find the early time of the event.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
$\max(2 + 6, 4 + 3) = 8$.
Activities out of an event: R with late finish 15 and duration 4, S with late finish 14 and duration 5. Find the late time of the event.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
$\min(15 - 4, 14 - 5) = 9$.
Worked example: a six-activity project
A (3) and B (5) start at once; C (4) and E (6) follow A; D (2) follows B and C; F (3) follows D and E. Find the project time, the critical activities and the float on B.
- Forward: A ends at 3; C ends at 7; E ends at 9; D starts at $\max(5, 7) = 7$ and ends at 9; F starts at $\max(9, 9) = 9$ and ends at 12. Project time 12.
- Backward: F must start by 9; D and E must end by 9, so D starts by 7 and E by 3; C must end by 7, so start by 3; B must end by 7.
- Critical and float: A, C, D, E, F have no slack — two critical paths, A–C–D–F and A–E–F. B's total float 总时差 is $7 - 0 - 5 = 2$.

Critical activities
- An activity is critical 关键的 when delaying it delays the whole project; its total float is 0.
- Total float $=$ late finish $-$ early start $-$ duration. Non-critical activities can move within their float without changing the end date.
An activity has early start 4, late finish 13 and duration 6. Find its total float.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
$13 - 4 - 6 = 3$.
In the worked example, which activity can be delayed by 2 days without delaying the project?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Only B has float (2); the others are critical.
Workers and the Gantt chart
- A lower bound for the number of workers is $\dfrac{\text{sum of all durations}}{\text{project time}}$, rounded up: here $\tfrac{23}{12} = 1.92$, so at least 2 workers.
- A Gantt chart 甘特图 (cascade chart) draws each activity as a bar starting at its early time, with its float shown after it. Critical activities have no float, so their bars cannot move.

Activities total 47 hours and the project time is 15 hours. Find the lower bound for the number of workers.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
$\tfrac{47}{15} = 3.13$, rounded up to 4.
Worked example: is the lower bound enough?
Can two workers finish the project in 12 days?
- Fixed bars: C (3 to 7) and E (3 to 9) are critical, so both must be running from time 3 to time 7.
- B: it lasts 5 days and must finish by 7, so it must start by 2 and is still running at time 3, 4 or later — whatever start we choose between 0 and 2.
- Look at a time line: at time 4 (see the chart), B, C and E are all in progress. That needs 3 workers.
- Conclusion: the lower bound 2 cannot be reached here; 3 workers are needed to finish in 12 days. The lower bound is only a minimum, so always check it against the chart.
In the Gantt chart, how many activities are in progress at time 8?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
At time 8, E (3 to 9) and D (7 to 9) are running; C has finished and F has not started.
Activities total 40 days and the project time is 15 days. What does the lower bound tell you?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
40 ÷ 15 = 2.67, rounded up to 3. It is a minimum, not a guarantee.
Exam-style question
Using the worked example, state the critical activities and the total float on B, and draw a Gantt chart. (5 marks)
- Critical activities A, C, D, E, F (B1), with project time 12 (B1).
- Float on B: late finish 7 − early start 0 − duration 5 $= 2$ (M1 for the formula, A1).
- Gantt chart: every critical bar at its early time, B from 0 to 5 with float to 7 shown (B1).
Where marks are lost: giving only one critical path (there are two, A–C–D–F and A–E–F); or drawing B's float as part of its duration.
Which list gives every critical path in the worked example?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Both paths have length 12; B has float 2, so B–D–F is not critical.
Taking the smallest value on the forward pass. D cannot start until both B and C have finished, so its early time is $\max(5, 7) = 7$, not 5. On the forward pass you take the largest value; on the backward pass the smallest.
Draw the network from the precedence table, using dummies where needed. The forward pass (largest) gives early times and the project time; the backward pass (smallest) gives late times. Critical activities have zero total float, which is late finish − early start − duration. A lower bound for workers is total time ÷ project time, rounded up, but check it on a Gantt chart: a time line that crosses more bars needs more workers.
In the worked example, B's duration rises from 5 to 8. Find the new project time and the new critical activities.
Re-run both passes.