题目
[The sum of the durations of all the activities is 59 days.]
The network in Figure 1 shows the activities that need to be undertaken to complete a project. Each activity is represented by an arc and the duration, in days, of the corresponding activity is shown in brackets. Each activity requires one worker. The project is to be completed in the shortest possible time.
(a) (i) Complete Diagram 1 in the answer book to show the early event times and the late event times.
(ii) State the minimum completion time of the project.
(b) Calculate a lower bound for the number of workers needed to complete the project in the minimum time. You must show your working.
(c) Schedule the activities using the minimum number of workers so that the project is completed in the minimum time.
题目中文翻译
[所有活动的持续时间之和为 59 天。]
图 1 所示的网络表示完成一个项目所需进行的各项活动。每项活动用一条弧表示，括号内标出相应活动的持续时间（单位：天）。每项活动需要一名工人。项目须在最短时间内完成。
(a) (i) 在答题册的图 1 中填写各事件的最早事件时间和最晚事件时间。
(ii) 写出项目的最短完成时间。
(b) 计算在最短时间内完成项目所需工人数的下界。必须写出计算过程。
(c) 使用最少数量的工人安排各项活动，使项目在最短时间内完成。
解答
(a)
解法一
思路
展开
先从起点向右作 forward pass：每个事件的最早时间等于所有进入该事件的路线所给完成时间的最大值。再从终点向左作 backward pass：每个事件的最晚时间等于所有离开该事件的路线所允许开始时间的最小值。
答题过程
展开
(i) The completed event times are:
| Event position | Early event time | Late event time |
|---|---|---|
| Start | 0 | 0 |
| After A | 5 | 5 |
| After D | 9 | 9 |
| After C | 7 | 11 |
| Merge before I | 12 | 12 |
| After G | 11 | 17 |
| After K | 14 | 18 |
| Merge before M | 18 | 18 |
| Finish | 20 | 20 |
(ii) The early event time at the finish event is 20. Therefore the minimum completion time is
(b)
解法一
思路
展开
总工作量为 59 worker-days，项目最短工期为 20 天。用总工作量除以工期得到平均所需人数，再向上取整。
答题过程
展开
The lower bound is
Since the number of workers must be an integer, at least
are required.
(c)
解法一
思路
展开
上一问说明少于三名工人不可能。接着构造一个只用三名工人、满足全部先后约束且在第 20 天完成的排程；这同时证明三名工人确实是最少数量。
答题过程
展开
One valid schedule is:
| Worker | Activities and time intervals |
|---|---|
| 1 | A: 0-5; D: 5-9; F: 9-12; I: 12-18; M: 18-20 |
| 2 | C: 0-7; J: 7-14; H: 14-18; N: 18-20 |
| 3 | B: 0-4; idle: 4-5; E: 5-8; K: 8-15; G: 15-17; L: 17-20 |
All precedence constraints are satisfied, and all 14 activities are completed by time 20 using three workers.
Therefore the minimum number of workers is