我国唯一的项目管理信息化门户网站,国内项目管理软件资讯服务提供商

登录 注册
当前位置:首页 > IT信息化 > 正文

大规模软件项目管理系统中PERT网络图的优化问题研究

2018-12-14 来源:《西南民族大学学报(自然科学版)》 作者:崔梦天 张荣虎 程国忠 点击:
      摘要:针对大规模软件项目管理中使用手工方法生成PERT网络图不方便等问题,对PERT网路图的优化问题进行了研究,分析了节点间的布局优化问题,给出了基于蚁群算法(ACO)和遗传算法(GAs)来实现对PERT中的节点进行优化的新方法.利用GAs很强的自适应性和种群优化技术,通过引入ACO算法实现节点布局全局范围的调整.计算和仿真结果表明,该方法能使用计算机自动生成的PERT网络图节点达到最小,布局能更有效合理有效,从而有效地解决了大规模软件项目中工程评审评估问题.
      关键词:计划评价技术;软件项目管理;蚁群算法;遗传算法;
      1概述
      PERT网络图是工程评价技术的一个重要的工具,可以直观的反映出任务间的前后调度关系.由于工程评估评审技术主要用于大规模的项目开发和项目管理,因此通常使用计算机辅助完成PERT图的绘制和生成.由于大规模的项目,任务节点比较多,任务间的关系也比较复杂,因此,对于计算机自动生成的PERT图质量是工程评估的关键要素.本文针对PERT网络图的优化问题进行了研究,分析了节点间的布局优化问题,给出了基于蚁群算法(ACO)和遗传算法(GAs)来实现对PERT中的节点进行优化的新方法.利用GAs很强的自适应性和种群优化技术,通过引入ACO算法实现节点布局全局范围的调整.计算和仿真结果表明,该方法能使用计算机自动生成的PERT网络图节点达到最小,布局能更有效合理有效,从而有效地解决了大规模软件项目中工程评审评估问题.
      2PERT网络图的组成结构
      PERT网络是一种类似流程图的箭线图.它描绘出项目包含的各种活动的先后次序,标明每项活动的时间或相关的成本[1-2].图1为一个简单的PERT网络图,其中A、B、C、D分别表示活动的权重.
      对于PERT网络图,项目管理者必须考虑要做哪些工作,确定时间之间的依赖关系,辨认出潜在的可能出问题的环节.借助PERT网络图还可以方便地比较不同行动方案在进度和成本方面的效果.构造PERT图,需要明确三个概念:事件、活动和关键路线.其中,事件表示主要活动结束的那一点;活动表示从一个事件到另一个事件之间的过程;关键路线是PERT网络中花费时间最长的事件和活动的序列.它采用加权平均得到期望值
E=(O+4M+P)/6.(1)
其中,O是最小估算值:乐观(Optimistic),P是最大估算值:悲观(Pessimistic),M是最大可能估算(MostLikely).该算法把非肯定型问题转化为肯定型问题来计算,用概率论的观点分析,其偏差仍不可避免,但趋向总是有明显的参考价值,当然,这并不排斥每个估计都尽可能做到可能精确的程度.
      计划评审技术中的活动期望时间(ET)公式和活动时间方差公式都是在活动时间被假设为服从参数为p=4,q=4的β分布时得到的,而该假设是基于以下两个前提,一是最可能时间的可能性4倍于乐观时间和悲观时间的可能性,二是最可能时间恰好是乐观时间和悲观时间的平均值.实际在项目管理实践中,这两个前提都不一定成立,因而活动时间服从参数为p=4,q=4的β分布也是站不住脚的.那么,怎么才能使参数也趋于合理呢?本文针对PERT网络图的优化问题进行了研究,分析了节点间的布局优化问题,给出了基于蚁群算法(ACO)和遗传算法(GAs)来实现对PERT中的节点进行优化的新方法.
      3基于蚁群算法和遗传算法结合的PERT网络图的生成方法
      3.1蚁群算法及遗传算法描述
      蚁群算法[2-4]的基本思想是蚁群总是寻找食物源与蚁巢间的最短路径.该算法具有正反馈性、协同性、并行性和鲁棒性、易于与其它方法结合等优点,但是,该算法一般需要较长的搜索时间,而且容易出现早熟和停滞的现象,而得不到全局最优解.为了提高蚁群算法的全局搜索能力和搜索速度,这里利用遗传算法的基于种群数量最优化技术,防止种群收敛并停滞在任何局部的最优点.
      遗传算法有选择,交换,变异[5-9]3个基本操作数.选择操作是从当前一代生成一组新的种群,它决定哪些个体是参与生成下一代的个体,即产生下一代交配池的过程.个体基因链按照它们的适应性函数值被复制在交配池中;交换处理分为:(1)来自交配池的成员随机交配.(2)每对基因链按照下列方式交换:位置l沿着基因链在区间[1,l−1]随机被选择(l是链的长度).两个链通过在位置k和l之间交换产生;变异是基因链位置的值随机交替的过程.它能防止整个种群在任何局部的任一位收敛到一个值,更重要的是它能防止种群收敛并停滞在任何局部的最优点.因此,由交换操作中得到的好染色体不会丢失.
      3.2PERT网络图自动生成的步骤
      PERT网络图自动生成的步骤如下:
      (1)任务节点的逻辑定位.这个是指暂时不考虑节点的实际物理位置,只确定节点所在行列的相对位置;(2)任务节点逻辑位置的优化分布.按边集交点最少的要求对统一列中的节点顺序进行调整,使节点的布局合理;(3)任务节点的物理位置.节点的逻辑位置确定后,按边的分布紧凑和拐角最少的原则确定节点及边的实际物理位置.
      3.3基于蚁群算法和遗传算法结合的PERT网络图的生成方法
      算法主要包括选择策略、信息量的局部更新和求局部最优解遍历算法3部分.具体实现原理如下:(1)为了减少计算时间,在最初的迭代中,取较大的转移概率.(2)为了防止陷入局部最优解,漏掉全局最优解,可在搜索进行到一定时间后,通过遗传算法的一些交叉、变异对信息素进行调整,缩小最好和最差路径上信息量的差距,适当加大随机选择的概率,从而使搜索空间更完全,扩大搜索范围.(3)在信息素的更新上,通过改变更新策略,更好地把全局特点考虑进去.基于蚁群算法和遗传算法结合的PERT网络图的生成算法实现过程如图2所示.
      4结束语
      大规模的软件项目中,PERT网络图是计划评审技术的关键,这样,对于自动化生成PERT网络图的算法的设计提出了更高的要求.为解决PERT中的节点的优化问题,本文对此提出了基于交叉、变异的蚁群算法来实现对PERT中的节点进行优化的新方法.利用GAs很强的自适应性和种群优化技术,通过引入ACO算法实现节点布局全局范围的调整.计算和仿真结果表明,该方法能使用计算机自动生成的PERT网络图节点达到最小,布局能更有效合理有效,从而有效地解决了大规模软件项目中工程评审评估问题.该算法扩大了搜索范围,自适应地调整路径选择概率的确定策略和信息量更新策略,可以使选择的路径尽量短以满足实时性应用,又能实现节点布局全局范围的调整.
 
      参考文献:
       [1]  韩万江, 吕勇. 软件项目管理[M]. 北京: 电子工业出版社, 2010.
       [2]  王颖, 谢剑英. 一种基于蚁群算法的多媒体网络多播路由算法[J]. 上海交通大学学报, 2002, 36(4): 526-531. 
       [3]  MANIEZZO V, CARBONARO A. An ants heuristic for the frequency assignment problem[J]. Future Generation Computer Systems, 2000, 16 (8): 927-935.
       [4]  DORIGO M, GAMBARDELLA L M. Ant colony system: acooperative learninig approach to the traveling sales man problem [J]. IEEE Tran sactions on Evolutionary Computation, 1997, 1(1): 53- 66.
       [5]  王海枚, 游志胜. 基于遗传算法与模糊控制的建模方法[J]. 电子科技大学学报, 2002, 31(3): 266-269.
       [6]  毕军, 付梦印, 张宇河. 计算机工程与应用[J]. 电子科技大学学报, 2003, 35(3): 77-81. 
      [7]  刘评, 高飞, 杨云. 基于遗传算法和蚁群算法融合的QoS 路由算法[J]. 计算机应用研究, 2007, 35(9): 224-227.
      [8]  徐刚, 马光文. 基于蚁群算法的梯级水电站群优化调度[J]. 水力发电学报, 2005, 36(8): 78: 1-5. 
      [9]  崔梦天, 钟勇, 赵海军. ACOGA算法的多媒体网络QoS路由实现[J]. 电子科技大学学报, 2009, 38(2), 266-269.
       [10]  周洞汝. PERT图的计算机自动生成[J]. 机电工程, 1989(4): 22-23.
      作者介绍:

      崔梦天: 西南民族大学计算机科学与技术学院,电子科技大学计算机科学与工程学院,
      张荣虎:四川邮电职业技术学院 
      程国忠:西华师范大学(本文于2012年发表于《西南民族大学学报(自然科学版)》)
分享到:

免责声明:
  1、项目管理信息化网发布的所有资讯与文章是出于为业界传递更多信息之目的,并不意味着赞同其观点或证实其描述。其原创性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺,请浏览者仅作参考,并请自行核实相关内容。
  2、本站部分内容转载于其他网站和媒体,版权归原作者或原发布媒体所有。如文章涉及版权等问题,请联系本站,我们将在两个工作日内进行删除或修改处理。敬请谅解!

延伸阅读:

Copyright ©2017-2019 项目管理信息化网 版权所有 京ICP备17062359号-9 如转载本站文章,请注明原作者和原发布媒体

本着互联网分享精神,本站部分内容转载于其他网站和媒体,如内容涉及版权等问题,请联系本站进行删除或修改处理

客服电话:010-89506650 89504891 非工作时间可联系:18701278071(微信) QQ在线:574888227

新闻与原创文章投稿:tougao#cpmta.com 客服邮箱:info#cpmta.com(请将#换成@)

我国唯一的项目管理信息化门户网站,国内项目管理软件资讯服务提供商,隶属卓橡公司

本站微信公众号

本站微信公众号