项目优化调度的病毒协同进化遗传算法胡仕成1+,徐晓飞1,李向阳21(哈尔滨工业大学计算机科学与技术学院,黑龙江哈尔滨150001)2(哈尔滨工业大学管理学院,黑龙江哈尔滨150001)AVirusCoevolutionGeneticAlgorithmforProjectOptimizationSchedulingHUShi-Cheng1+,XUXiao-Fei1,LIXiang-Yang21(SchoolofComputerScienceandTechnology,HarbinInstituteofTechnology,Harbin150001,China)2(SchoolofManagement,HarbinInstituteofTechnology,Harbin150001,China)+Correspondingauthor:Phn:+86-451-6419787,E-mail:hu_shicheng@yahoo.com.cn,http://www.cs.hit.edu.cnReceived2002-11-12;Accepted2003-03-24HuSC,XuXF,LiXY.Aviruscoevolutiongeneticalgorithmforprojectoptimizationscheduling.JournalofSoftware,2004,15(1):49~57.http://www.jos.org.cn/1000-9825/15/49.htmAbstract:Inthispaper,aviruscoevolutiongeneticalgorithm(multi-modeprojectscheduling-virusco-evolutiongeneticalgorithm,MPS-VEGA)fortheprecedenceandresourceconstrainedmulti-modeprojectschedulingproblemispresented,andtheencodingofthesolutionandtheoperatorssuchasselection,crossover,mutationandvirus_infectionaregiven.MPS-VEGAisusedtoobtaintheoptimalschedulingsequencesandresourcemodesfortheactivitiesoftheprojectsothattheprojectcostisminimized,whichcantransmitevolutionarygenesnotonlybetweenparentandchildgenerationsverticallybythegeneticoperatorsbutalsointhesamegenerationhorizontallybythevirus_infectionoperatorsoastoperformaglobalsearchandalocalsearch,respectively.TheschematheoremisadoptedtoanalyzetheperformanceofMPS-VEGA.ThetheoreticalanalysisandexperimentalresultsshowthattheMPS-VEGAoutperformstheGA.Forthemulti-modeprojectschedulingproblemwithdifferentoptimizationobjectives,MPS-VEGAcansimutaneouslygivestandardtheoptimalschedulingsequencessubjecttotheprecedenceconstraintsandtheoptimalresourcemodesfortheactivitiesoftheproject.Keywords:resource-constrainedprojectscheduling;multi-mode;costoptimization;virusevolution;geneticalgorithm摘要:针对次序约束和资源约束的多模式项目调度问题提出了一种病毒协同进化遗传算法,并提出了解的编码、选择、交叉、变异和病毒感染操作等.算法用于求解项目活动的一个最优调度顺序和资源模式以使项目的成本最低,其操作特点是既可以通过遗传操作在父SupportedbytheNationalHigh-TechResearchandDevelopmentPlanofChinaunderGrantNos.863-511-944-001,2001AA414010(国家高技术研究发展计划(863));theKeyScience-TechnologyProjectoftheNational‘TenthFive-Year-Plan’ofChinaunderGrantNo.2001BA201A03(国家“十五”重点科技攻关项目)作者简介:胡仕成(1970－),男,湖北浠水人,博士生,主要研究领域为CIMS,管理与决策信息系统;徐晓飞(1962－),男,教授,博士生导师,主要研究领域为CIMS,数据库,管理与决策信息系统;李向阳(1950－),男,教授,博士生导师,主要研究领域为CIMS,技术经济,管理与决策信息系统.第50页共14页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第50页共14页子代群体之间纵向传播进化基因进行全局搜索,又可以通过病毒感染操作在同一代群体内横向传播进化基因进行局部搜索.利用模板理论对算法的性能进行了分析.理论分析和实验结果表明,算法的搜索性能优于一般的遗传算法.算法对于不同优化目标的多模式项目调度问题可以同时求得一个满足次序约束的项目活动的最优调度顺序和满足资源约束的最优资源模式.关键词:资源约束项目调度;多模式;成本优化;病毒进化;遗传算法中图法分类号:TP18文献标识码:A在制造企业的生产计划、经营计划和项目管理中,项目调度(projectscheduling,简称PS)是一个重要的优化问题,PS需要解决在满足一定的约束条件下达到某种最优的目标,如工期最短、成本最小等,从而满足企业的某种经营目的,同时,很多组合优化问题都可以归结为PS的特例,如车间作业...
