必威体育Betway必威体育官网
当前位置:首页 > IT技术

图——关键路径

时间:2019-08-09 14:13:25来源:IT技术作者:seo实验室小编阅读:89次「手机版」
 

关键路径

 

AOE网示例图:

AOE网:在一个表示工程的带权有向图中,用顶点表示事件(如V0),用有向边表示活动(如<v0,v1> = a1),边上的权值表示活动的持续时间,称这样的有向图为边表示的活动的网,简称AOE网(activity on edge network)

源点:

在AOE网中,没有入边的顶点称为源点;如顶点V0

终点:

在AOE网中,没有出边的顶点称为终点;如顶点V3

AOE网的性质:

【1】只有在进入某顶点的活动都已经结束,该顶点所代表的事件才发生;

 例如:a1和a2活动都结束了,顶点V2所代表的事件才会发生。

【2】只有在某顶点所代表的事件发生后,从该顶点出发的各活动才开始;

 例如:只有顶点V1所代表的事件结束之后,活动a2和a4才会开始。

 

在AOE网中,所有活动都完成才能到达终点,因此完成整个工程所必须花费的时间(即最短工期)应该为源点到终点的最大路径长度。具有最大路径长度的路径称为关键路径关键路径上的活动称为关键活动:

 

事件的最早发生时间:ve[k]

根据AOE网的性质,只有进入Vk的所有活动<Vj, Vk>都结束,Vk代表的事件才能发生,而活动<Vj, Vk>的最早结束时间为ve[j]+len<Vj, Vk>。所以,计算Vk的最早发生时间的方法为:

ve[0] = 0

ve[k] = max(ve[j] + len<Vj, Vk>)

事件的最迟发生时间:vl[k]

vl[k]是指在不推迟整个工期的前提下,事件Vk允许的最迟发生时间。根据AOE网的性质,只有顶点Vk代表的事件发生,从Vk出发的活动<Vk, Vj>才能开始,而活动<Vk, Vj>的最晚开始时间为vl[j] - len<Vk, Vj>。

活动的最早发生时间:ee[i]

ai由有向边<Vk, Vj>,根据AOE网的性质,只有顶点Vk代表的事件发生,活动ai才能开始,即活动ai的最早开始时间等于事件Vk的最早开始时间。

活动的最迟发生时间:el[i]

el[i]是指在不推迟真个工期的前提下,活动ai必须开始的最晚时间。若活动ai由有向边<Vk, Vj>表示,则ai的最晚开始时间要保证事件vj的最迟发生时间不拖后。

案例:

原始AOE网:

事件的最早发生时间:ve[k]

从源点向终点方向计算

ve[0] = 0

ve[1] = ve[0] + a0 = 0 + 4 = 4

ve[2] = max( ve[0] + a1, ve[1] + a2 ) = max(0 + 3, 4 + 2 = 6

ve[3] = max(ve[1] + a4, ve[2] + a3) = max(4 + 6, 3 + 4) = 10

事件的最迟发生时间:vl[k]

从终点向源点方向计算

vl[3] = ve[3] = 10

vl[2] = vl[3] - a3 = 10 - 4 = 6

vl[1] = min(vl[3] - a4, vl[2] - a2) = min(10-6, 6-2) = 4

vl[0] = min(vl[2] - a1, vl[1] - a0) = min(4-4, 4-2) = 0 

活动的最早发生时间:ee[i]

共有五个活动:

ee[0] = ve[0] = 0

ee[1] = ve[0] = 0

ee[2] = ve[1] = 4

ee[3] = ve[2] = 6

ee[4] = ve[1] = 4

活动的最迟发生时间:el[i]

el[0] = v[1] - a0 = 4 - 4 = 0

el[1] = vl[2] - a1 = 6 - 3 = 3

el[2] = vl[2] - a2 = 6 - 2 = 4

el[3] = vl[3] - a3 = 10 - 4 = 6

el[4] = vl[3] - a4 = 10 - 6 = 4

活动的最早开始时间和最晚开始时间相等,则说明该活动时属于关键路径上的活动,即关键活动。

经过比较,得出关键活动有:a0, a2, a3, a4,画出示意图如下:

该AOE网有两条关键路径。

所以,通过此案例也可以发现,一个AOE网的关键路径可能有多条。

相关阅读

如何使用「关键路径」法对需求进行高效管理?

产品的需求管理是产品经理所担当的责任之一,通过需求的管理能够良好的支持项目经理安排任务以及确保产品的交付进度。关键路径法在

如何使用「关键路径」法对需求进行高效管理?

产品的需求管理是产品经理所担当的责任之一,通过需求的管理能够良好的支持项目经理安排任务以及确保产品的交付进度。关键路径法在

分享到:

栏目导航

推荐阅读

热门阅读