符长虹,吴顺祥,王文渊
(1.厦门大学自动化系,福建厦门361005;2.中国中铁四局集团有限公司,合肥230023)
灰色PERT算法在项目工期中的研究与应用
符长虹1,吴顺祥1,王文渊2
(1.厦门大学自动化系,福建厦门361005;2.中国中铁四局集团有限公司,合肥230023)
为提高PERT网络中关键路线与关键工序决策的可靠性,减少求解的复杂性,文章根据工序时间不确定的特点,结合灰色系统理论,提出了工序时间为区间灰数的灰色PERT网络,并且根据实际工序时间概率分布的特点,提出了工序时间的正态分布模型,该方法避免了决策中片面采用均匀分布区间灰数描述模糊评价的局限性,更好地体现了工序“最可能时间”、“最悲观时间”与“最乐观时间”三者概率分布的特点。另外,考虑到工程计划能否在规定工期内顺利完成这一随机现象,提出了相应的灰色PERT算法。最后,通过实例分析,说明该灰色PERT算法能够有效避免片面采用均匀分布区间灰数的局限性,且计算出项目工程在规定工期内完成的可能概率,更加符合实际项目工期的决策,具有较好的可行性和高效性,拓展了这一领域的研究与应用。
PERT网络;灰色理论;均值白化值;正态分布;标准差;关键路线
考虑到经典PERT网络中工序完成时间受许多内、外诸因素影响,导致其具体数值无法确定,只能通过估计最乐观时间a、最可能时间m与最悲观时间b来进行关键路线与关键工序的决策,然而本文结合灰色系统理论,基于工序完成时间在区间[a,b]内变化的特点,提出了工序完成时间为区间灰数的灰色PERT网络。但是根据经典PERT网络中三种估计时间概率分布的特点,文献[1]等的工序完成时间片面采用均匀分布区间灰数来描述模糊评价的方法则会产生严重的失真,因此本文针对这个局限性,考虑到三种估计时间近似服从正态分布的特点,提出了工序完成时间服从正态分布的分布模型。文献[2]等的PERT网络中忽略了每一条路线在规定项目工期内实际完成该项目的“可能性”这一随机现象,因此本文为更全面、更科学、更有效地研究PERT网络,提出了相应的灰色PERT算法,该算法通过求出每项工序完成时间区间灰数的均值白化值以及标准差,接着求出每条线路上所有工序完成时间区间灰数的均值白化值之和以及标准差,进而求出每条线路上所有工序完成时间区间灰数的均值白化值之和所对应的概率系数以及在规定工期内完成项目的概率,最后根据概率的大小决策关键线路与关键工序,通过实例分析,说明该灰色PERT算法具有较好的可行性和高效性,减少了信息失真与决策失误。
考虑到经典PERT网络通过三种估计时间,即最乐观时间a、最可能时间m与最悲观时间b,来决策关键线路与关键工序,结合灰色系统理论以及工序完成时间在最乐观时间与最悲观时间之间变化,即在[a,b]之间变化,本文介绍工序完成时间为区间灰数的灰色PERT网络,如图1所示,其中对应的工序时间灰数为hi(茚)∈
本文又考虑到经典PERT网络中三种估计时间的概率分布情况,根据实际情况,工序完成时间区间灰数不可能片面认为服从均匀分布,这会造成决策的严重失真,因此提出了基于正态分布的工序完成时间,如图2所示[3][4]。
由图3可知,本文可以确定正态分布的参数,其中正态分布的数学期望根据正态分布3σ的原则,即p (x∈[ai,bi])=0.997,可得方差
在灰色PERT网络中,考虑到项目计划能否在规定工期内完成项目这一随机现象,本文结合灰色理论,利用各条线路上所有工序完成时间区间灰数的均值白化值之和所对应的概率,来进行关键路线以及关键工序的决策,具体的灰色PERT网络算法步骤如下:
步骤1在灰色PERT网络中,找出所有的路线,记为xi(i=1,2,…,n),以及第xi条线路上的工序,其时间灰数分别记为(j=1,2,…,m),其中hij(茚)表示第xi条线路上第j道工序的时间灰数;
步骤2计算出灰色PERT网络中各个工序时间灰数的均值白化值hi(茚軜)以及对应的方差σi,并分别计算出第xi条线路上所有工序时间灰数的均值白化值hi(茚軜)之和以及标准差:
其中,σxi表示第xi条线路上项目完成时间的标准差;
步骤3根据规定的项目计划总工期T,分别计算出每条路线上所有工序时间灰数的均值白化值hi(茚軜)之和的概率系数:
步骤4根据公式(3)计算出的概率系数分别计算每条线路在所有工序时间灰数的均值白化值hi(茚軜)之和下完成该项目的概率:
步骤5对公式(4)求得的概率进行排序,其中概率最小所对应的路线则为关键路线,其上的工序则为关键工序。
某实际项目中共有9道工序,每项工序的持续时间如表1所示[1][2]。
表1 各工序的持续时间
表1所对应的灰色PERT网络如图3所示。
步骤1该灰色PERT网络中共有5条线路,分别如下:
第x1条:1→3→5→6,共3项工序:h3(茚)、h5(茚)和h6(茚),分别记为h11(茚)、h12(茚)和h13(茚);
第x2条:1→3→4→5→6,共4项工序:h3(茚)、h4(茚)、h7(茚)和h6(茚),分别记为h21(茚)、h22(茚)、h23(茚)和h24(茚);
第x3条:1→3→4→6,共3项工序:h3(茚)、h4(茚)和h8(茚),分别记为h31(茚)、h32(茚)和h33(茚);
第x4条:1→2→3→4→6,共4项工序:h1(茚)、h2(茚)、h4(茚)和h8(茚),分别记为h41(茚)、h42(茚)、h43(茚)和h44(茚);
第x5条:1→2→4→6,共3项工序:h1(茚)、h9(茚)和h8(茚),分别记为h51(茚)、h52(茚)和h53(茚)。
步骤2计算各个工序时间灰数的均值白化值hi(茚軜)以及对应服从正态分布的方差σi:工序1→2:其工序持续时间区间灰数为h1(茚)∈[1,3],
同理,其余工序持续时间,期望以及方差如表2所示。
表2 其余各个工序持续时间灰数的均值白化值以及方差
根据公式(1)计算出各条线路上所有工序时间灰数的均值白化值hi()之和(见表3)。
表3 各线路上所有工序时间灰数的均值白化值之和
根据公式(2)计算每条线路上项目完成时间的标准差如下:
同理可以求得其余线路的标准离差:
σx2=0.782,σx3=0.866,σx4=0.928,σx5=0.782
步骤3根据公式(3)计算在规定项目计划总工期为T= 20的情况下各条线路所对应的概率系数:
同理可求得其余路线上所对应的概率系数(见表4)。
表4 其余路线所对应的概率系数
表5 其余线路所对应的概率
步骤4根据公式(4)求得各条路线上所有工序时间灰数的均值hi()白化值之和的概率:
同理可求得其余路线上所对应的概率:
步骤5根据步骤4求得的各路线对应概率进行排序,其中概率最小对应的路线即为所求关键路线:故有关键路线为x3:1→3→4→6,如图3中粗线所示。
本文针对决策中采用均匀分布区间灰数描述模糊评价值的局限性,考虑到正态分布模型能够更准确、更有效表示工序完成时间的概率分布特点,以及项目计划是否能在规定工期内完成项目的可能性这一随机现象,提出了应用正态分布区间灰数来决策灰色PERT网络中关键路线与关键工作的算法。通过实例证明,该方法具有较好的可行性和高效性,为这一领域提供了关键路线以及关键工序决策的新方法,可供从事PERT网络的技术人员与管理人员参考。
[1]崔邯龙,李万庆,孟文清.张艳杰,灰色网络计划中的关键线路确定方法研究[J].数学的实践与认识,2009,38(8).
[2]杨应玖,杨毅,杨念.论灰色网络计划技术[J].武汉水利电力大学学报,1998,31(3).
[3]谢乃明,刘思峰.考虑概率分布的灰数排序方法[J].系统工程理论与实践,2009,29(4).
[4]刘琳,陈云翔,葛志浩,基于正态分布区间数的概率测度及多属性决策[J].系统工程与电子技术,2008,30(4).
[5]Chao-Chin Chung,Ho-Hsien Chen,Pao-Chuan Hsieh.Optimization of the Monascus Purpureus Fermentation Process Based on Multiple Performance Characteristics[J].Journal of Grey System,2008, 11(2).
[6]Wen-Fang Hsieh,Kun-Li Wen.A New Approach of Grey Decision-Making[J].Journal of Grey System,2009,12(2).
[7]Guo-Dong Li,Daisuke Yamaguchi,Masatake Nagai,Masatoshi Kitaoka.A Research on Grey Model by Grey Interval Analysis[J]. Journal of Grey System,2006,9(2).
[8]Ping-Yi Hu.Using A Grey Multipurpose Decision System for Car Purchasing[J].Journal of Grey System,2004,7(1).
[9]Long-qing Shen,Jian-feng Yu,Hai-wei Yang.Research on Algorithms for Critical Path of PERT Network with Lowering Conditions[J].Application Research of Computers,2006,(1).
[10]刘思峰,党耀国,方志耕.灰色系统理论及其应用[M].北京:科学出版社,2004.
(责任编辑/易永生)
F224
A
1002-6487(2011)05-0152-03
国家自然科学基金资助项目(60704042);国家“十一五”科技支撑计划项目(2007BAK34B04)
符长虹(1986-),男,湖南岳阳人,硕士,研究方向:不完备系统与数据挖掘。
吴顺祥(1966-),男,湖南邵阳人,博士,教授,研究方向:不完备系统。
王文渊(1985-),女,河南鸡西人,助理工程师,研究方向:工程设计。