Critical paths and scheduling
引入| English | 释义 | 拼音 |
|---|---|---|
| critical path method | 关键路径法 | guān jiàn lù jìng fǎ |
| activity network | 活动网络 | huó dòng wǎng luò |
| precedence table | 先后关系表 | xiān hòu guān xì biǎo |
| dummy/ˈdʌmi/ | 虚活动 | xū huó dòng |
| critical/ˈkrɪtɪkl/ | 关键的 | guān jiàn de |
| float/fləʊt/ | 浮动时间 | fú dòng shí jiān |
| total float/ˈtəʊtl fləʊt/ | 总时差 | zǒng shí chà |
| Gantt chart/ɡænt tʃɑːt/ | 甘特图 | gān tè tú |
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.
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
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.
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
$\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.
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
$\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.
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
$13 - 4 - 6 = 3$.
In the worked example, which activity can be delayed by 2 days without delaying the project?
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
Only B has float (2); the others are critical.
Workers and scheduling
- 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 甘特图 draws each activity as a bar at its early time, with its float shown after it; a schedule uses it to give each worker a list of activities.
Activities total 47 hours and the project time is 15 hours. Find the lower bound for the number of workers.
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
$\tfrac{47}{15} = 3.13$, rounded up to 4.
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.
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.