第 69 题
下表给出了某工程各工序之间的优先关系和各工序所需的时间(其中“一”表示无先 驱工序),请完成以下各题： 1)画出相应的AOE网 。 2)列出各事件的最早发生时间和最迟发生时间。 3)求出关键路径并指明完成该工程所需的最短时间。 工序代号 A B C D E F G H 所需时间 3 2 2 3 4 3 2 1
先驱工序 一 一 A A B A C、E D
[tag_link]
参考答案
可把工序表转换为下面的 AOE 边集；顶点编号只是为了表达依赖关系，虚活动可按等价方式设置。
| 活动 | 边 | 持续时间 |
|---|---|---|
| A | 1→2 | 3 |
| B | 1→3 | 2 |
| C | 2→4 | 2 |
| D | 2→5 | 3 |
| E | 3→4 | 4 |
| F | 2→8 | 3 |
| G | 4→8 | 2 |
| H | 5→8 | 1 |
按拓扑序正向计算事件最早发生时间，按逆拓扑序反向计算最迟发生时间：
| 事件 | 1 | 2 | 3 | 4 | 5 | 8 |
|---|---|---|---|---|---|---|
ve | 0 | 3 | 2 | 6 | 6 | 8 |
vl | 0 | 4 | 2 | 6 | 7 | 8 |
对活动 i→j，最早开始 e=ve(i)，最迟开始 l=vl(j)-duration，时差为 l-e：
| 活动 | A | B | C | D | E | F | G | H |
|---|---|---|---|---|---|---|---|---|
e | 0 | 0 | 3 | 3 | 2 | 3 | 6 | 6 |
l | 1 | 0 | 4 | 4 | 2 | 5 | 6 | 7 |
| 时差 | 1 | 0 | 1 | 1 | 0 | 2 | 0 | 1 |
因此关键活动为 B、E、G，关键路径是 1→3→4→8，最短工期为 8 个时间单位。
易错点
活动 F 虽然直接通向汇点，但路径 1→2→8 只有 6，不决定总工期；关键活动必须满足时差为 0，不能只看是否连接汇点。