求解AOE网关键路径例题详解

☆求解AOE 网关键路径例题

【例7-1】下表给出了某工程各工序之间的优先关系和各工序所需的时问（其中“一”表示无先驱工序），请完成以下各题：

(1) 画出相应的AOE 网。

(2) 列出各事件的最早发生时间和最迟发生时间。

(3) 求出关键路径并指明完成该工程所需的最短时间。

【例题分析】

· 试题考核AOE 网和关键路径问题。要求熟悉AOE 网的概念和如何求关键路径的方法及步骤。

【例题解答】

(1) 根据表的数据，可得AOE 网，如图所示。

(2) 所有事件的最早发生时间ve ，如下所示：

ve （v1）＝ 0 ve （v2）＝ 3 ve （v3）＝ 2

ve （v4）＝ Max{ ve（v2）+2，ve （v3）+4}＝ 6

ve （v5）＝ ve （v2）＋3 ＝ 6

ve （v6）＝ Max{ ve（v3）+3，ve （v4）+2，ve （v5）+1}＝ 8

所有事件的最迟发生时间vl ，如下所示：

vl （v6）＝ 8 vl （v5）＝vl （v6）－1＝ 7 vl （v4）＝vl （v6）－2 ＝ 6

vl （v3）＝ Min{ vl（v4）－4，vl （v6）－3}＝ 2

vl （v2）＝ Min{ vl（v4）－2，vl （v5）－3}＝ 4

vl （v1）＝ Min{ vl（v2）－3，vl （v3）－2}＝ 0

(3) 求所有活动的最早发生时间e 、最迟发生时间l 和时间余量l-e 。 e （A ）＝ve （v1）＝ 0 l （A ）＝vl （v2）－3＝ 1 l （A ）－e （A ）＝ 1 e （B ）＝ve （v1）＝ 0 l （B ）＝vl （v3）－2＝ 0 l （B ）－e （B ）＝ 0 e （C ）＝ve （v2）＝ 3 l （C ）＝vl （v4）－2＝ 4 l （C ）－e （C ）＝ 1 e （D ）＝ve （v2）＝ 3 l （D ）＝vl （v5）－3＝ 4 l （D ）－e （D ）＝ 1 e （E ）＝ve （v3）＝ 2 l （E ）＝vl （v4）－4＝ 2 l （E ）－e （E ）＝ 0 e （F ）＝ve （v3）＝ 2 l （F ）＝vl （v6）－3＝ 5 l （F ）－e （F ）＝ 3 e （G ）＝ve （v4）＝ 6 l （G ）＝vl （v6）－2＝ 6 l （G ）－e （G ）＝ 0 e （H ）＝ve （v5）＝ 6 l （H ）＝vl （v6）－1＝ 7 l （H ）－e （H ）＝ 1

所以，关键路径为：B 、E 、G 。

完成该工程最少需要8天时间。