5.8 关键路径★3◎4
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>。
5.8 关键路径★3◎4未经允许不得转载:5.8 关键路径★3◎4