5.8 关键路径★3◎4

5.8 关键路径★3◎4　　AOE-网（Activity On Edge）是指边表示活动的网，这是一个带权的有向无环图，其中，顶点表示事

作者

次阅读

2010-11-16

5.8 关键路径★3◎4

　　AOE-网（Activity On Edge）是指边表示活动的网，这是一个带权的有向无环图，其中，顶点表示事件，弧表示活动，权表示活动持续的时间。在一般情况下，AOE-网用来估计工程的完成时　间，图5-15定义了6个时间、8个活动的AOE-网。

　　在正确的情况下，AOE-网表示的工程只有一个开始点和一个完成点，即只有一个入度为0的顶点（源点）和一个出度为0的顶点（汇点）。
　　在AOE-网表示的工程中，部分活动可以并行进行，那么完成工程的最短时间是从开始点到完成点的最长路径的长度，即该条路径上所有弧的权值之和。路径长度最长的路径称为“关键路径”。
　　在AOE-网中，“事件最早发生时间”，是指从开始点到事件顶点之间的最长路径的长度，同时这个时间也是所有以此顶点为尾的弧所表示的活动的“活动最早发生时间”，用e(i)表示。
　　“活动最迟开始时间”是指在不推迟整个工程完成的前提下，活动最迟必须开始进行的时间，用l(i)表示。
　　最早发生时间和最迟开始时间之差“l(i)-e(i)”是完成活动的时间余量，如果某活动的e(i)=l(i)，则称此活动为“关键活动”，关键路径上的所有活动都是关键活动，提前完成非关键活动（不在关键路径的活动）并不能加快工程的进度。
　　定义事件j的最早发生时间为ve(j)和最迟发生时间为vl(j)，活动ai的最早开始时间为e(i)，最迟开始时间为l(i)，则求AOE-网的关键路径算法如下。
　　1．求事件的最早发生时间
　　从ve(0)=0开始向前递推，其中T是所有以第j个顶点为头的弧的集合，<i，j>是其中的弧（活动），dut(<i，j>)是此弧的权（活动所需的时间）：
　　ve[j]=max{ve[i]+dut(<i, j>)} <i, j>∈T, j=1,2,3,…,n
　　以图5-15为例，求事件的最早发生时间的算法如表5-9所示。

表5-9 求事件的最早发生时间

顶点	VE	分析
V0	0	定义ve[0]=0
V1	5	V1只有一个直接前驱，故ve[1]=ve[0]+dut(<0,1>)=0+5=5
V2	5	V2只有一个直接前驱，故ve[2]=ve[0]+dut(<0,2>)=0+5=5
V3	6	V3有2个直接前驱，分别为V1和V0；考察V0：有ve[0]+dut(<0,3>)=0+4=4；考察V1：有ve[1]+dut(<1,3>)＝5+1=6； ve[3]取大值6
V4	12	V4有2个直接前驱，分别为V2和V3；考察V2：有ve[2]+dut(<2,4>)=5+7=12；考察V3：有ve[3]+dut(<3,4>)＝6+2=8； ve[4]取大值12
V5	14	V5有2个直接前驱，分别为V3和V4；考察V3：有ve[3]+dut(<3,5>)=6+8=14；考察V4：有ve[4]+dut(<4,5>)＝12+1=13； ve[5]取大值14

　　2．求事件的最迟开始时间
　　从vl(n-1)=ve(n-1)起向后递推，其中S是所有以第i个顶点为尾的弧的集合。
　　vl[j]=min{vl[i]-dut(<i, j>)} <i, j>∈T,i=n-2,n-3,…,0
　　以图5-15为例，求事件的最迟开始时间的算法，如表5-10所示。

表5-10 求事件的最迟开始时间

顶点	VL	分析
V5	14	定义vl[5]=ve[5]=14
V4	13	V4只有一个直接后继，故vl[4]=vl[5]-dut(<4,5>)=14-1=13
V3	6	V3只有一个直接后继，故vl[3]=vl[5]-dut(<3,5>)=14-8=6
V2	6	V2只有一个直接后继，故vl[2]=vl[4]-dut(<2,3>)=13-7=6
V1	5	V1只有一个直接后继，故vl[1]=vl[3]-dut(<1,3>)=6-1=5
V0	0	V0有3个直接后继，分别为V1，V2和V3：考察V1：vl[1]-dut(<0,1>)=5-5=0 考察V2：vl[2]-dut(<0,2>)=5-5=0 考察V3：vl[3]-dut(<0,3>)=6-4=2 vl[0]取小值0

　　事件的最早发生时间和最迟开始时间的对比，如表5-11所示。

表5-11 事件最早发生时间与最迟开始时间对比表

	V0	V1	V2	V3	V4	V5
最早发生时间	0	5	5	6	12	14
最迟开始时间	0	5	6	6	13	14
关键路径	V0	V1		V3		V5

　　所以图5-15的关键路径为V0、V1、V3、V5。
　　3．求活动的最早发生时间和最迟发生时间
　　活动ai由弧<j,k>（即从顶点j到k）表示，其持续时间记为dut(<j,k>)，则：
　　e(i) = ve(j)
　　l(i) = vl(k)-dut(<j,k>)
　　以图5-15为例，求活动的最早发生时间和最迟开始时间的算法，如表5-12所示。

表5-12 求活动的最早发生时间和最迟开始时间

活动	弧	E	L	关键活动
a1	<0,1>	ve[0]=0	vl[1]-dut(<0,1>)=5-5=0	a1：<0,1>
a2	<0,3>	ve[0]=0	vl[3]-dut(<0,3>)=6-4=2
a3	<0,2>	ve[0]=0	vl[2]-dut(<0,2>)=6-5=1
a4	<1,3>	ve[1]=5	vl[3]-dut(<1,3>)=6-1=5	a4：<1,3>
a5	<2,4>	ve[2]=5	vl[4]-dut(<2,4>)=13-7=6
a6	<3,4>	ve[3]=6	vl[4]-dut(<3,4>)=13-2=11
a7	<3,5>	ve[3]=6	vl[5]-dut(<3,5>)=14-8=6	a7：<3,5>
a8	<4,5>	ve[4]=14	vl[5]-dut(<4,5>)=14-1=13

　　所以图5-15的关键活动有：a1<0,1>、a4<1,3>、a7<3,5>。