多项目无节奏流水施工时间成本置换优化分析

多项目无节奏流水施工时间成本置换优化分析第24卷第2期2010年04月工程管理JournalofEngineeringManagementV_0l_24No.2April.2010多项目无节奏流水施工时间成本置换优化分析王勇胜2,梁昌勇,姜利赢(1.合肥工业大学管理学院,安徽合肥230009,Email:aa4506;2.东北电力大学建筑工程学院,吉林吉林132012;3.中国石油吉林石化有机合成厂,吉林吉林132022)摘要:无节奏流水施工是施工组织的常见形式.文章考虑了多项目环境下多模式的无节奏流水施工组织,并结合传统的timecost置换问题进行了建模求解.目标函数直接采用双目标形式,并基于NSGAII非劣排序思想进行了算法设计.仿真测试表明,改进的算法能够有效的获得较优的离散time.cost曲线,可以为复杂环境下的无节奏流水施工组织与实施提供决策支持.关键词:无节奏流水施工;多项目;多模式;timecost置换;NSGAII中图分类号:F407.9文献标识码:A文章编号:16748859(2010)0215604OptimizationModelingandSolutionaboutDiscreteTime-CostTrade一0ffProbleminNonrhythmFlowProcesswithMultiprojectConditionWANGYongsheng2LIANGChangyong.JIANGLiying(1.SchoolofManagement,HefeiUniversityofTechnology,Hefei230009,China,Email:aa4506;2.SchoolofCivilandArchitecture,NortheastDianliuniversity,Jilin132012,China;3.WorkshopofRubber,OrganicComposedFactoryofJilinPetroleumCo.,Jilin132022,China)undertheconditionsofmultiprojectandmultimode,thispapermodeledtheproblemcombingwithconventionaldiscretetimecostobjectiveexpression.ThealgorithmwasdesignedbasedonNSGAIImethodology.Thesimulationresultsshowthattheimprovedalgorithmcangettheoptimaldiscretetimecostcurve,whichcanprovidedecisionmakingsupportfortheconstructionorganizationandimplementationinnonrhythmflowprocessunderthecomplexenvironmentKeywords:nonrhythmflowprocess;multiproject:multimode:timecosttradeoff;NSGAII无节奏流水施工是工程项目管理中较为常见的施工组织形式,很多学者对此进行了研究J,但多局限于单项目情况,多项目环境下的研究则相对较少3.timecost置换问题是工程项目中一类传统的优化问题,一般假设时间和成本具有反向关系,即时间缩短则成本增加,延长时间则可节省成本,通过优化可以得出较为实用的timecost曲线,为工程项目建设提供参考.离散状态下的timecost收稿15t期:2010一叭一l6.基金项目:国家自然科学基金重点项目(70631003)国家自然科学基金(70871034);国家863项目(2006AA04A126).置换问题在学术上可以归结为多模式组合优化问题l4,即以模式为决策变量进行建模求解.本文的研究定位于多项目环境下无节奏流水施工组织timecost置换优化研究,并在考虑timecost置换问题天然具有多目标特性的基础上【6.7J,改变了简单转换为单目标的处理方式8】,直接进行了多目标优化求解,以获得更符合工程实际的time.cost曲线.l多目标混合整数规划模型建立考虑某群体工程有JV个规模不等的项目,拟对工作性质相同的某施工阶段(如土方工程,混凝土工程等)进行无节奏流水施工,施工过程数(工艺)为G.每个施工过程在各施工段均有个模式可供第2期王勇胜,等:多项目无节奏流水施工时间成本置换优化分析选择.用,1,f表示各项目的施工段数,则总施工段数为D=Ii,i=1,不同的施工段按所属项目用进行统一编号,其中Jl,D.将的不同排列组合用集合表示,不同的将对应不同的时间和成本.由于是多项目环境,中的排列将受到项目选择次序的约束,同时也受到项目内施工方向的约束.本文考虑如下约束设置:一是选定项目次序后,同一个项目内的各个段必须连续依次进行施工.二是同一项目中各施工段只采用正反两种施工方向,这样考虑比较符合施工现场的实际情况.下面用一个例子来说明多项目环境下施工段的排列组合情况.有两个项目,项目1划分2个施工段,用d】,表示,项目2划分3个施工段,用,d4,ds.则根据上述约束设置有可行的施工段排列组合为:1一一幽d5;一一以_幽一;_1一-幽一以;d2一l以一幽以.对于这样的排列组合,即使在单一模式下,随着项目数和施工段数的增加,其可行的施工段排列就已经呈指数性的增长了.对于多模式情况,在确定可行施工段组合的同时,还要考虑各工艺模式的选择.以表示模式选择变量,其中,=1时表示工艺i在施工段选择模式m;=0时则表示没有选择.优化的目的就是确定较优的排列组合集合,同时选择出各施工段各工艺的执行模式.据此可建立如下多目标混合整数规划模型:G一1d(D)MrainTime=Ki+XGdm/_一_一_一i=17ldf11m=1Gd(D)MminCost=,c,i=1d(1)m=lG厅d(D)t=1i=1d(1)Ki=maxsum(i,1),maxsum(i,h+1)一sum(i+1,)(h=1,D一1;Itd,=I,J);XO,1,i=1,G;m=1,)式中,minTime为总工期函数;minCost为总成本函数;第3式为模式选择约束;ridCid.为工艺i在施工段选择模式k时的时间和成本;为流水步距,采用潘式方法获得;sum(i,1)为工艺i在7/a施工段排列和所选模式下的时间累积数列.对于上述模型,智能优化算法是比较好的求解方式m】.本文基于NSGAII非劣排序的思想,进行算法设计,并将改进算法计算结果与NSGA-II源码获得的结果进行了比较.2算法改进措施及步骤根据问题特点采用如下编码和解码方式:编码采用双链表编码,第一链表为施工段排列链表;第二链表为模式链表,为各工艺在各施工段上随机选择施工模式.由于无节奏流水施工不同的工艺有相同的施工段排列,因此模式链表的长度为施工段链表的G倍.解码方式是根据生成的双链表,计算各模式的成本之和形成总成本,结合潘式方法计算总工期.2.1算法改进措施2.1.1初始种群的多样化产生方式对于施工段链表,采用重复性比较方式,以获得与已产生个体不同的新个体;对于模式链表,采用频率记忆方法进行新个体的生成【l,其频率计算公式为:1/sldmPidm贰式中,S为以前产生的个体中,模式m被分配给i工艺段的次数,该方法是指某工艺的某个段如果以前被分配某模式较多,那么新个体产生时,该段再被分配该模式的概率就会减少.2.1.2交叉变异一是施工段链表采用以项目为单位的一点交叉,变异按一定概率对某项目内的施工方向进行反向变异.二是模式链表交叉采用文献121中的方法,从种群中随机选择两个父代个体,子代每个基因以0.7的概率来自父个体1,以O.3的概率来自父个体2.变异选用文献131中的方法,在链表中随机选取两个不相同的点P,q,Rp<q,将q位置的值赋于P位置,原P位置到g一1位置的值依次后移一位,形成新个体.2.1.3种群重组中的精英保留和多样性保持策略NSGAII中采用的种群重组方法是将父代和子代组成的联合种群中(2p)等级最高的个体选择进入下一代,其不足是使一些虽然等级较低但多样性较好的个体失去了进一步进化的机会.本文提出一种新的精英保留与多样性协同策略.设定比例,用来表示新种群中有pop个个体来源于联合工程管理第24卷种群的精英解,即等级最高的解.(卜r)pop个个体采用比例缩减的方式获得,即在联合种群中去除已经采用的pop个个体,计算剩余各等级个体数量占总个体(2一,)pop的比例,并按非劣等级顺序选择各等级中多样性最好的前/(2一r)(为各非劣等级中个体的数量)个个体加入到新种群.由于计算中存在取整误差,且数量较小,采用随机增加或减少精英个体的方式进行处理,使新种群数量正好为pop.由于采用比例缩减复制的原则,使等级最低的个体也有机会参与进化.为保证算法的收敛,该策略应用于前genr代,即算法前面部分充分保持多样性,进行深度搜索,后面部分则仍然采用选择等级最高个体进行复制的方法,使算法收敛.因此确定合理的genr和gen(总代数)之间的比例关系就显得极为重要.通过仿真测试取0.10.2;genr取1/41/lOgen时可以获得较好的收敛效果.2.2改进算法步骤步骤如下:(1)采用多样性初始种群生成方法产生pop个个体.(2)计算目标值.(3)按NSGAII进行非劣排序,并且计算拥挤距离.(4)进行交叉,变异操作.(5)采用本文精英保留和多样性保持措施进行种群重组.(6)如果迭代次数没有达到,返回第2步,否则进行下一步.(7)输出timecost曲线和计算结果.3算例分析有6个项目(,F)的施工区,如图1所示.方框为各项目的施工段划分,方框内为施工段编号.田囡A田臣工CD臣工臣工咽E图1多项目施工段划分简图本文采用双模式情景,各模式数据见表1,数据进行了整数化处理,更换表中数据可直接应用于具体的工程实际.表1各模式时间与成本数据参数设置:交叉概率取0.8,变异概率取0.1.种群规模pop=200,迭代次数gen分别选取200代,500代,取:0.15;genr=1/10gen.NSGAII采用源码设置,只进行了必要的离散化处理,分别见图2和图3.从图2和图3中可以看出改进的算法可以有效的求得timecost置换的pareto前沿,并且优于NSGAII的求解结果.两个500代中解的示例,分别见表2和表3.图2200代时timecost离散曲线第2期王勇胜,等:多项目无节奏流水施工时间成本置换优化分析?159?cOstxl04图3500代时time.cost离散曲线表2施工段链表及目标值注:0表示正常模式;1表示赶工模式.4结语本文对常见的工程项目无节奏流水施工进行了扩展研究,其结果适用于多项目多模式环境下的施工组织,进一步研究考虑模式信息不确定情况下的优化选择,并设计更好的多目标优化算法.并且可以获得较为理想的timecost曲线,可以为施工方案选择和多项目管理决策提供支持,具有较好的应用价值和应用前景.参考文献:1方良平,姜炜.无节奏流水施工方法在施IJr,序优选中的应用【J_山西建筑,2008,34(14):207208.2任宏,蔡伟光.无节奏流水施工优化模型及其动态规划算法J】.重庆大学(自然科学版),2007,30(5):135137.3丛培经.工程项目管理M.北京:中国建筑工业出版社,2003.particleswarmoptimizationforsolvingmultimoderesourceconstrainedprojectschedulingproblemsJ.AppliedMathematicsandComputation.195(2008):99308.searchformulti-moderesource-?constrainedprojectschedulingwithscheduledependentsetuptimesJ.EuropeanJournalofOperationalResearch.187(2008):12381250.6】彭武良,王成恩.一种多模式资源受限的离散时间成本平衡问题J.东北大学(自然科学版),2008,29(8):10771099.7ohammadR.Ranjbar,FereydoonKlanfar.Solvingthediscretetime/resourcetradeoffprobleminprojectschedulingwith-geneticalgorithmsJ】.AppliedMathematicsandComputation.191(2007):451456.8刘士新.项目优化调度理论与方法M】.北京:机械工业出版社,2007.9KalyanmoyDeb,AFastandElitistMultiobjectiveGeneticAlgorithm:NSGAII.IEEETRANSACTIONSONEVOLUTIONARYCOMPUTATIONJ.VOL.6,NO.2,APRIL2002.10崔逊学.多目标进化算法及其应用M】.北京:国防工业出版社,2006.11Ranjbar,M.etal,Ahybridscattersearchforthediscretetime/resourcetradeoff,EuropeanJournalofOperationalResearch(2007).oi:10.1016/j.on2007.10.042.12WM.Spears,K.A.DeJong,OnthevirtuesofparameterizeduniformcrossoverC.in:proceedingsoftheFourthInternationalConferenceonGeneticAlgorithms,1991:230236.13PeiChannChang,JihChangHsieh,ChihYuanWang.AdaptivemultiobjectivegeneticalgorithmsforschedulingofdrillingoperationinprintedcircuitboardindustryJ.AppliedSoftComputing,7(2007):800806.作者简介:王勇胜(1970一),项目管理;梁昌勇(1965一),项目管理,智能决策,姜利赢(1972一),管理,项目管理.男,博士研究生,研究方向:工程与男,教授,博士生导师,研究方向:优化算法研究;女,高级技师,研究方向:化工运行