Critical paths and scheduling
Introducido| English | Significado |
|---|---|
| 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/ | flotante |
| 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.
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
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.
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
$\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.
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
$\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.
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
$13 - 4 - 6 = 3$.
In the worked example, which activity can be delayed by 2 days without delaying the project?
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
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.
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
$\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.