一个项目由图 3 所示的活动网络模拟。活动由弧表示。每条弧上的括号内的数字表示完成相应活动所需的时间（单位：天）。每项活动恰好需要一名工人。项目应在最短时间内完成。

(a) 在答案本中完成图 1，显示最早事件时间和最迟事件时间。

(b) 计算在最短时间内完成项目所需的工人数量的下界。必须展示计算过程。

(c) 在答案本的网格 1 上使用最少数量的工人安排活动，使项目在最短时间内完成。

额外资源变得可用，可以将活动 D、G 或 P 中的一个的持续时间缩短一天。

(d) 确定应缩短这三个活动中的哪一个以允许项目在最短时间内完成。必须给出理由。

先按箭头方向做 forward pass，在每个汇合事件取所有进入路线完成时间的最大值，得到最早完成时间 33。再从终点 33 反向做 backward pass，在每个分支事件取允许时间的最小值。虚活动工期为 0，但其优先关系仍须计入。

The completed event times are:

Thus the minimum project completion time is

The completed network is:

每项活动需要一名工人，所以先把所有活动的持续时间相加得到总工作量，再除以必须完成项目的 33 天。工人数必须为整数，因此结果向上取整。

The total amount of work is

Therefore the lower bound is

and hence at least

are required.

先把关键活动安排在不延误项目的时间上，再将其余活动分配给三名工人。每项活动的开始时间必须不早于所有紧前活动的完成时间，同一名工人的活动不能重叠。下面的排程恰好使用 3 名工人并在第 33 天完成，因此达到 (b) 的下界。

One valid schedule is:

All $15$ activities appear exactly once. Every activity starts after all of its immediate predecessors have finished, and no worker is assigned overlapping activities.

The project therefore finishes at time $33$ using the minimum of three workers. The corresponding schedule is:

先判断三个候选活动的关键性。$G$ 有 8 天总浮时，缩短它不会改变工期。$D$ 与 $P$ 都是关键活动，但项目有两条长度 33 的关键路径；$D$ 同时位于两条路径上，而 $P$ 只位于其中一条，因此只有缩短 $D$ 才能同时缩短所有关键路径。

Activity $G$ is not critical. Its total float is

so reducing its duration does not reduce the project completion time.

Activities $D$ and $P$ are critical. However, one critical path is

with length

while the other critical path is $A-D-P$, also of length $33$. Reducing $P$ would leave the path $A-D-J-N$ unchanged at $33$ days.

Activity $D$ lies on both critical paths, so it is the activity that should be shortened: