AOE网的运用与关键路径的计算

时间:2024-03-23 18:48:14

什么是AOE网

AOE网是边表示活动,点表示事件的有向无环图。在AOE网中,具有最大长度的路径称为关键路径,关键路径表示完成工程的最短工期
AOE网描述了活动之间的优先关系,可以认为是一个定向的研发,但是有时还需要定量的研究工程的进度,如整个工程完成的事件,子工程完成的事件,各个子工程影响整个工程的的程度。在AOE网表示一个工程计划时,用顶点来表示各个事件,弧表示子工程的活动,权值表示子工程的活动需要的时间在顶点表示事件发生后,从该顶点出发的有向弧所表示的活动才能开始。在进入某个顶点的有向弧所表示的活动完成之后,该顶点表示的事件才能发生

如何根据表画出AOE图

之所以提出这个问题,是因为我当时在查看资料的时候并没有看到有具体给出步骤的,而我自己有些疑问,并做出了如下解答:

  1. 当活动C是建立在活动B,A上的,这条线究竟是由两条线这样引出来呢还是在其中一个事件上印出来?下面我们来举出两个例子来分别说明:
    AOE网的运用与关键路径的计算
    图中活动C是建立在活动A,B上的,但是呢我们可以看到C是从A那条线引出来的,而且还在事件3和事件2上加了一条虚线(绿色线表示)
    AOE网的运用与关键路径的计算
    上图中活动G是建立在活动C,E上来的,但这个的表示又不太一样了。
    那么究竟是什么原因呢?通过上图我们可以观察到图一中活动A,B的准备事件是没有的,也就是说这两个活动最终导出的事件是不可以合并的,所以我们在图中添加了一条从事件3到事件2的虚线,这条虚线的含义就是虽然事件2和事件3之间没有依靠关系,但在顺序上是事件3先于事件2完成。所以活动C就应该是建立在后完成的事件2上了。图二呢我们发现活动C和活动E都是由前序工序的,这两个活动完成后的那个工序(事件)是可以合并为一个工序的(事件),而活动G是建立在活动C,E上的,故直接从事件4引出活动G即可。

  2. 在画图的时候我发现有的形成三角形的边上的权重并不能满足两边之和大于第三边,这又是为什么呢?后来发现是我自己的概念搞错了,两边之和大于第三边确实满足无向图中的三角形,但在有向图中呢,它就该满足矢量三角形,何为矢量三角形?????
    AOE网的运用与关键路径的计算
    好了,现在我们知道了矢量三角形是可以构成一个环的,但AOE图本质就是个有向无环图,故在画AOE图是,我们完全不用担心这方面的问题了。

  3. 画图是时刻记住这是一个“封闭”的图,即一个起始点,一个终点,不能有其他分叉。对一个工程来说,只有一个开始状态和一个结束状态。因此在AOE网中,只有一个入度为零的点表示工程的开始,称为源点;只有一个出度为零的点表示工程的结束,称为汇点。

如何计算关键路径呢

步骤1:找出每个事件的最早时间和最迟时间

这里有个比较好的方法:最早时间就是从源点开始到该顶点所代表的事件的最长路径,其中源点事件的最早时间为0.
最迟时间就是从汇点开始反向计算,min{(该事件的后序事件1的最早时间-活动时间),(该事件的后序事件2的最早时间-活动时间)。。。}

步骤2:事件的最早时间=最迟时间,则该事件入选进关键路径中的事件

步骤3:活动的最早时间和最迟时间

活动的最早时间:该有向线的起始点事件的最早时间
活动的最迟时间:该有向线的终止点事件的最迟事件-该有向线的权值

步骤4:活动的最早时间=活动的最迟时间,则该活动入选进关键路径中

步骤5:将上述的活动和事件整理起来画出相应的路径即是关键路径。

具体操作可以参考:https://wenku.baidu.com/view/a3d3bf224431b90d6c85c7f9.html