摘要:对于前面的两个概念很多人不能理解:从源点开始到汇点递推以后,我们已经得到了关键路径的长度,按理把这些点记录下来,就得到了关键路径,为什么在此时,还要从汇点到源点进行递推,来求关键路径,这样岂不多此一举?其实不是这样的,一个AOE网络中可能有多条关键路径,若我们只正推过去,只能求得一条关键路径,而不能找出所有的关键路径。 要求一个AOE的关键路径,一般需要根据以上变量列出一张表格,逐个检查。
对于前面的两个概念很多人不能理解:从源点开始到汇点递推以后,我们已经得到了关键路径的长度,按理把这些点记录下来,就得到了关键路径,为什么在此时,还要从汇点到源点进行递推,来求关键路径,这样岂不多此一举?其实不是这样的,一个AOE网络中可能有多条关键路径,若我们只正推过去,只能求得一条关键路径,而不能找出所有的关键路径。
要求一个AOE的关键路径,一般需要根据以上变量列出一张表格,逐个检查。例如,求图1所示的求AOE关键路径的过程如表1所示。
因此,图1的关键活动为a1,a2,a4,a8和a9,其对应的关键路径有两条,分别为(V1,V2,V5,V7)和(V1,V4,V5,V7),长度都是10。
其实从学员的疑问可以看出,最关键的问题就在于此表如何填写。首先值得我们注意的一点是,对于顶点的V1,V2等事件,有最早,最迟发生时间;对于边a1,a2,a3,等活动,有最早,最迟开始时间。Ve(j)表示的是顶点j的最早发生时间,Vl(j)表示的是顶点j的最迟发生时间,e(i)表示的是活动i的最早开始时间,l(i)表示的是活动i的最迟开始时间。总的来说填这个表有以下四个步骤。
—由源点开始递推计算出表1-1中的Ve(j)列;
—由Ve(7)=10,回算Vl(j)列;
—Vl(j)列算出后用公式l(i)=Vl(j)-(ai所需要的时间);
—由l(i)=e(i)找出关键活动,求出关键路径。
下面来填写表格,首先我们来填最早发生时间和最早开始时间。
因为由源点V1到顶点V2的最长路径长度是3(到V2只有一条路径,长度为3,这个很好判断),所以V2的最早发生时间是3,从V2出发的活动有a4,a5,所以a4,a5的最早开始时间也是3。又比如,到顶点V4的最长路径长度是6,所以V4的最早发生时间是6,从V4出发的活动有a8,a8的最早开始时间也是6,其余的依次类推。
最迟发生时间和最迟开始时间要先求出关键路径的长度后,再进行逆推。通过上面求最早发生时间,我们可以求得关键路径长度为10。
现在可以开始逆推了。
首先由于关键路径长度为10,所以V7的最迟发生时间是10,再看V6,V6到V7有a10,长度为4,所以V6的最迟发生时间是10-4=6,同样V5到V7有a9,长度为3,所以V5的最迟发生时间是10-3=7,依次类推,此项值对应表1中的Vl(j)。
接下来求最迟开始时间。
V7的最迟开始时间为10,a9,a10都指向V7,a9=3,a10=4,所以a9的最迟开始时间为10-3=7,a10的最迟开始时间为10-4=6。V6的最迟开始时间为6,a7指向V6,a7=3,所以a7的最迟开始时间为6-3=3。此项值对应表1中的l(i)。
相关推荐:
软考备考资料免费领取
去领取