1.AOE网
“边活动(Activity On Edge,AOE )网”用加权边集合表示活动,用顶点表示事件的方向图,用crdwx表示活动完成所需的时间。
如下图所示,边a1 -a6表示需要学习的课程,即“活动”,crdwx表示课程学习所需的时间。 顶点V1-V6表示到目前为止上节课已经结束,下节课可以开始学习。 也就是说,是“事件”。 很明显,“事件”只代表中介状态。
AOE网络只有在)1)发生了以某个顶点为代表的事件之后,才能开始以从该顶点出发的有向边为代表的活动; )只有在进入某个顶点的有向边表示的活动全部结束时,才会发生该顶点表示的事件。
AOE网络只有一个入度为0的顶点,称为开始顶点(源点),表示整个项目的开始。 在网中,也只有一个被称为终点(汇点)的出度为0的顶点,这标志着整个工程的结束。
在AOE网络中,可以并行进行一些活动。 虽然从源到宿的有向路径可能有多个,并且这些路径的长度可能不同,完成路径上的活动所需的时间不同,但是只有所有路径上的活动都完成了,整个项目才算结束。 因此,在从源到宿的所有路径中,路径长度最大的路径称为关键路径。 关键路径上的活动称为关键活动。
完成整个项目所需的最短时间是关键路径的长度,也就是关键路径上一个活动所需的总费用。 这是因为关键活动会影响整个项目的时间。 这意味着,如果关键活动不能按时完成,整个项目的完成时间就会变长。 因此,只要找到关键活动,就能找到关键路径,也能得到最短的完成时间。
2.参量定义
以下是寻找重要活动时使用的一些参数定义。
(1)事件vk的最早发生时刻ve ) k ) ) ) ) ) )。
从开始顶点v到Vk的最长路径的长度。 事件发生的最早时间决定了从Vk开始的所有活动可以开始的最早时间。 可以用以下递归公式计算。
ve (源点)=0
ve(k )=max ) ve ) j ) weight(vj,vk ) },weight ) vj,vk )表示vj,vk上的权重
注意:计算ve(k )时,先对面再按顺序计算。
)2)事件vk的最迟发生时间VL(k ) ) ) ) ) ) ) )。
这意味着在不延迟整个项目的完成的情况下,即在确保指示的事件vi能够在ve(I )时刻发生的情况下,该事件必须最晚发生的时间。 可以用以下递归公式计算。
vl (信宿=ve )信宿) )。
VL(j )=min ) VL(k )-weight (vj,vk )、weight (VJ,vk )表示VJ,vk上的权重
注意:计算VL(j )时,从后面开始按顺序计算。
)3)活动ai的最早开始时间e ) I ) ) ) ) ) ) )。
这是指由事件起点表示的事件最早发生的时间。 在vk、vj表示活动ai的情况下,有e(I )=ve (k ) )。
(4)活动ai的最早开始时间l ) I ) ) ) ) )
这是事件终点表示的事件的最晚发生时间与事件所需的时间之间的差。 在边vk、vj表示活动ai的情况下,有l(I )=VL(j )-weight (vk,vj )。
)一个活动ai的最晚开始时间L(I )与其最晚时间e ) I )之差d ) I )=L ) I )-e ) I ) ) ) ) ) ) ) )。
这意味着活动完成的时间充裕,是活动ai可以延迟的时间,而不增加完成整个项目所需的总时间。 L(I(-E ) I )=0,即l (I )=E )的活动ai是一项重要的活动,因为如果一项活动的时间裕度为零,则表明该活动必须如期完成,否则将延缓整个工程的进度。
求关键路径的算法步骤为以下:
求出AOE网内所有事件的最早发生时间ve (。 求出AOE网内所有事件的最迟发生时间vl (。 求出AOE网络中所有活动的最早开始时间e (。 求出AOE网内所有活动的最迟开始时间l (。 求出AOE网内所有活动的差额d (),找到d )=0的活动构成关键路径。 下图显示了求解关键路径的过程。 从该图中可以看到,此AOE网的关键路径为[v1、v3、v4、v6]。
关于关键路径,必须注意以下事项:
)关键路径上的所有活动都是重要的活动,它是决定整个工程的重要因素,因此加快重要活动可以缩短整个工程的工期。 但是,重要的活动不能任意缩短。 因为缩短到一定程度后,其重要活动就有可能成为非重要活动。
)2)网络关键路径不唯一。 此外,在具有多个关键路径的网络中,仅仅加快关键路径上的关键活动速度并不能缩短整个项目的工期。 要达到缩短工期的目的,必须加快所有关键路径中的关键活动。