路径"/>
AOE网与关键路径
AOE网(Activity On Edge Network)
是一个有向图:
- 顶点:事件;
- 弧:活动;
- 权:完成该活动所需的时间;
- 源点:工程的开始,入度为0的事件,AOE网只能有一个源点
- 汇点:工程的结束,出度为0的事件,AOE网只能有一个汇点
- 每一事件v表示:以它为弧头的所有活动已经完成
- 每一事件v表示:以它为弧尾的所有活动可以开始
例子:
上图为一个AOE网
有4个事件: v 1 , v 2 , v 3 , v 4 v_1, v_2, v_3, v_4 v1,v2,v3,v4 ( v 1 v_1 v1为源点, v 4 v_4 v4为汇点)
有4个活动: a 1 , a 2 , a 3 , a 4 a_1, a_2, a_3, a_4 a1,a2,a3,a4
其中:事件 v 3 v_3 v3表示: a 2 a_2 a2已完成, a 4 a_4 a4可以开始
AOE网可解决如下问题:
- 估算最短工期:从源点到汇点至少需要多少时间
- 找出哪些活动是影响整个工程进展的关键
关键路径 Critical Path
- 路径长度:路径上各活动持续时间的总和
即:路径上所有弧的权值之和 - 关键路径:从源点到汇点之间路径长度最长的路径
注意:关键路径不一定唯一 - w ( j , k ) w(j,k) w(j,k) 表示活动 < j , k > <j,k> <j,k>的持续时间
例子:
- 事件( v j v_j vj)的最早发生时间: E v ( j ) E_v(j) Ev(j)
从源点到 v j v_j vj 的最长路径长度 - 活动( a i a_i ai)的最早开始时间: E a ( i ) E_a(i) Ea(i)
等于该活动的弧尾事件( v j v_j vj)的最早发生时间
例子:
若以符号 < j , k > <j, k> <j,k>表示活动 a i a_i ai,则有: E a ( i ) = E v ( j ) E_a(i) = E_v(j) Ea(i)=Ev(j) - 事件( v k v_k vk)的最迟发生时间: L v ( k ) L_v(k) Lv(k)
在不推迟整个工期的前提下,该事件最迟必须发生的时间 - 活动( a i a_i ai)的最迟开始时间: L a ( i ) L_a(i) La(i)
该活动的弧头事件最迟发生时间与该活动的持续时间之差
即: L a ( i ) L_a(i) La(i) = L v ( k ) L_v(k) Lv(k) - ( a i a_i ai 的持续时间) - 关键活动: L a ( i ) L_a(i) La(i) = E a ( i ) E_a(i) Ea(i) 的活动
- 由此:在AOE网中找关键活动问题可转化为
求满足如下条件的活动: L a ( i ) L_a(i) La(i) = E a ( i ) E_a(i) Ea(i)
其中: E a ( i ) E_a(i) Ea(i) = E v ( j ) E_v(j) Ev(j), L a ( i ) L_a(i) La(i) = L v ( k ) L_v(k) Lv(k) - ( a i a_i ai 的持续时间)
因此需首先求出事件的最早、最迟发生时间
关键路径算法设计
- 从 E v ( 1 ) = 0 E_v(1)=0 Ev(1)=0 开始,递推计算出各事件的最早发生时间
事件( v i v_i vi)的最早发生时间:从源点到 v i v_i vi 的最长路径长度 - 从 L v ( n ) = E v ( n ) L_v(n) = E_v(n) Lv(n)=Ev(n)开始,计算出各事件的最迟发生时间
L v ( i ) L_v(i) Lv(i):事件( v i v_i vi)最迟必须发生的时间
E v ( i ) E_v(i) Ev(i):事件( v i v_i vi)的最早发生时间 - 计算出AOE网络中各活动的最早、最迟开始时间
- 找出 E a ( i ) = L a ( i ) E_a(i) = L_a(i) Ea(i)=La(i) 的活动,即为关键活动
- 由关键活动组成的从源点到汇点的路径即为关键路径
例子:
结论
在有多条关键路径时,缩短那些存在于所有关键路径上的关键活动,才能缩短整个工期
更多推荐
AOE网与关键路径
发布评论