教你轻松计算AOE网关键路径(转)

原文链接:http://blog.csdn.net/wang379275614/article/details/13990163

本次结合系统分析师—运筹方法—网络规划技术—关键路径章节,对原文链接描述不准确的地方做了修正。

认识AOE网

有向图中,用顶点表示活动,用有向边表示活动之间开始的先后顺序,则称这种有向图为AOV(Activity On Vertex)网络;AOV网络可以反应任务完成的先后顺序(拓扑排序)。

  在AOV网的边上加上权值表示完成该活动所需的时间,则称这样的AOV网为AOE(Activity On Edge)网,如下图: 

  图中,顶点表示事件(能被触发,两特征属性:最早发生时间Ve(j);最晚发生时间Vl(j)),边表示活动(能被开始,两特征属性:最早开始时间e(i);最晚开始时间l(i)),权表示活动持续时间,通常用AOE网来估算工程完成的时间

两条原则:

  Ø  只有某顶点所代表的事件发生后,从该顶点出发的各活动才能开始

  Ø  只有进入某顶点的各活动都结束,该顶点所代表的事件才能发生

计算关键路径

  首先,在AOE网中,从始点到终点具有最大路径长度(该路径上的各个活动所持续的时间之和)的路径为关键路径。

计算关键路径,只需求出上面的四个特征属性,然后取e(i)=l(i)的边即为关键路径上的边(关键路径可能不止一条)。

  先来看看四个特征属性的含义:

  Ø Ve(j):是指从始点开始到顶点Vj的最大路径长度

   计算技巧:

   (1)从前向后,取大值:直接前驱结点的Ve(j)+到达边(指向顶点的边)的权值,有多个值的取较大者

   (2)首结点Ve(j)已知,为0

  如上图各顶点(事件)的Ve(j): (从V1开始)

  Ø  Vl(j):在不推迟整个工期的前提下,事件vj允许的最晚发生时间

   计算技巧:

   (1)从后向前,取小值:直接后继结点的Vl(j) –发出边(从顶点发出的边)的权值,有多个值的取较小者;

   (2)终结点Vl(j)已知,等于它的Ve(j))

  如上图各顶点(事件)的Vl(j): (从V7开始,它的最早、最晚发生时间相同,都为10):

  Ø  e(i): 若活动ai由弧<vk,vj>表示,则活动ai的最早开始时间应该等于事件vk的最早发生时间。因而,有:e(i)=ve(k);(即:边(活动)的最早开始时间等于,它的发出顶点的最早发生时间)

如上图各边(活动)的e(i):

  Ø  l(i): 若活动ai由弧<vk,vj>表示,则ai的最晚开始时间要保证事件vj的最迟发生时间不拖后。 因而有:l(i)=vl(j)-len<vk,vj>(为边(活动)的到达顶点的最晚发生时间减去边的权值

如上图各边(活动)的l(i):

  至此已介绍完了四个特征属性的求法,也求出了上图中边的e(i)和l(i),取出e(i)=l(i)的边为a1、a2、a4、a8、a9,即为关键路径上的边,所以关键路径有两条:a1 a4 a9和 a2 a8 a9

总结

  求关键路径,只需理解顶点(事件)和边(活动)各自的两个特征属性以及求法即可:

   Ø  先根据首结点的Ve(j)=0由前向后计算各顶点的最早发生时间

   Ø  再根据终结点的Vl(j)等于它的Ve(j)由后向前依次求解各顶点的最晚发生时间

   Ø  根据边的e(i)等于它的发出顶点的Ve(j)计算各边的最早开始时间(最早开始,对应最早发生)

   Ø  根据边的l(i)等于它的到达顶点的Vl(j)减去边的权值计算各边的最晚开始时间(最晚开始,对应最晚发生)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏PPV课数据科学社区

【完整案例】如何用R实现空间数据可视化

image.png 流行病学的数据讲究“三间分布”,即人群分布、时间分布和空间分布。其中的“空间分布”最好是在地图上展示,才比较清楚。R软件集统计分析与高级...

1.1K7
来自专栏CDA数据分析师

为什么说 Python 是数据科学的发动机(二)工具篇(附视频中字)

毋庸置疑,Python是用于数据分析的最佳编程语言,因为它的库在存储、操作和获取数据方面有出众的能力。 在PyData Seattle 2017中,Jake V...

22510
来自专栏程序人生

谈谈调度 - Linux O(1)

约莫十五年前,当我刚刚开始参加工作时,赶上 Linux 发布划时代的 2.6 内核。在这个大家都翘首期盼的内核版本中,最令人兴奋的便是 O(1) schedul...

2958
来自专栏熊彪的专栏

精准测分:基于函数调用关系链的用例消振算法 ( 上帝视角 )

地球文明不是孤岛,函数呢?从静态的视角观察函数,她只是一个一个在文件中孤立存在的代码片段。但从动态的视角观察,函数与函数之间就天然的发生了关联。这个关联是怎么产...

2260
来自专栏企鹅号快讯

程序员的花样编程,你到底行不行?

【导读】:说到 C/C++ 代码技巧,也许会有童鞋说 ,这是属于 C/C++ 程序员离职前恶搞之类的抖机灵。即便想,也不能干。别忘了有这样一句编程名言:「在编写...

2295
来自专栏Vamei实验室

一天能学会的计算机技术

作者:Vamei 出处:http://www.cnblogs.com/vamei 欢迎转载,也请保留这段声明。谢谢!

1582
来自专栏大数据挖掘DT机器学习

python数据挖掘:能不能找出吃货最佳住宿点?

这次我爬出了哈尔滨市TOP285家好吃的店,包括烧烤的TOP,饺子的TOP,酱骨的TOP等等等等,在地图上显示,规划热点,再用聚类算法计算下能不能找出吃货最佳的...

3755
来自专栏小樱的经验随笔

【经验分享】Trachtenberg system(特拉亨伯格速算系统)

二战期间,俄国的数学家Jakow Trachtenberg(1888-1953)被关进纳粹集中营,在狱中,他开发出了一套心算算法,这套算法后来被命名为Trach...

5468
来自专栏Crossin的编程教室

【每周一坑】图像的指纹:数字水印 + 【解答】鸡兔同笼

曾经有过这样的新闻:某公司的员工将内网论坛上的言论截屏发布到互联网上,引发了热议。于是公司通过截图定位到了员工的身份,将其开除。

1612
来自专栏伪君子的梦呓

用 Python 分析微信好友性别比例

0 前言 上一次是用 python 实现聊天机器人,其中提及到 itchat 这个包,使用了一下,发现挺好玩的,找了相关的代码看了一下,发现可以用来分析微信好...

4567

扫码关注云+社区

领取腾讯云代金券