项目优化调度的病毒协同进化遗传算法

Vol.15,No.1©2004JournalofSoftware软件学报1000-9825/2004/15(01)0049项目优化调度的病毒协同进化遗传算法胡仕成1+,徐晓飞1,李向阳21(哈尔滨工业大学计算机科学与技术学院,黑龙江哈尔滨150001)2(哈尔滨工业大学管理学院,黑龙江哈尔滨150001)AVirusCoevolutionGeneticAlgorithmforProjectOptimizationSchedulingHUShi-Cheng1+,XUXiao-Fei1,LIXiang-Yang21(SchoolofComputerScienceandTechnology,HarbinInstituteofTechnology,Harbin150001,China)2(SchoolofManagement,HarbinInstituteofTechnology,Harbin150001,China)+Correspondingauthor:Phn:[phone],E-mail:[e-mail],(1):49~57.: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,技术经济,管理与决策信息系统.50JournalofSoftware软件学报2004,15(1)的成本最低,其操作特点是既可以通过遗传操作在父子代群体之间纵向传播进化基因进行全局搜索,又可以通过病毒感染操作在同一代群体内横向传播进化基因进行局部搜索.利用模板理论对算法的性能进行了分析.理论分析和实验结果表明,算法的搜索性能优于一般的遗传算法.算法对于不同优化目标的多模式项目调度问题可以同时求得一个满足次序约束的项目活动的最优调度顺序和满足资源约束的最优资源模式.关键词:资源约束项目调度;多模式;成本优化;病毒进化;遗传算法中图法分类号:TP18文献标识码:A在制造企业的生产计划、经营计划和项目管理中,项目调度(projectscheduling,简称PS)是一个重要的优化问题,PS需要解决在满足一定的约束条件下达到某种最优的目标,如工期最短、成本最小等,从而满足企业的某种经营目的,同时,很多组合优化问题都可以归结为PS的特例,如车间作业调度[1]等,因此研究PS具有广泛的实用价值和理论意义.PS的约束包括活动之间的先后次序约束和资源限量约束,资源包括可重复使用的资源和不可重复使用的资源[2],每个活动的运作模式也可以有多种(multi-mode)[3],这样的PS称为MPS(multi-modeprojectscheduling),PS是一个NP-hard问题,有两种以上的不可重复使用的资源约束的MPS是一个NP-complete[4]问题.Kolisch[5]提出了比较完整的求解PS的串行和并行的理论和方法,Kolisch[6]等人给出了求解PS的局部搜索算法,Reych[7]采用了分支定界方法对PS进行求解,Fayez[8]和Taeho[9]等人对MPS进行了研究,并给出了启发式求解方法,Joanna[10]采用了模拟退火算法对MPS进行求解.以上算法的研究仅限于以时间为目标的PS,对企业来说,成本也是一个重要的经营目标,因此对以成本为目标的PS的研究同样具有重要意义.根据病毒进化理论[11],病毒是一种特有的生物,具有一种特有的感染功能,它能获得一个个体的染色体基因,并且感染给另一个个体,使得该个体的部分染色体基因发生相应的变化,从而改变该个体的遗传信息,这种遗传信息又通过遗传传递给下一代,从而大大加速了生物的进化换代.1996年,Kubota提出了基于病毒进化理论的遗传算法VEGA(virusco-evolutiongeneticalgorithm),并成功地用于求解旅行商问题[11]、自组织制造系统的调度问题[12]、弹道规划问题[13]、背包问题[14]等,显示了求解NP-hard优化问题的优越性.VEGA在进化计算过程中产生两种群体:主群体和病毒群体.主群体对应问题的解空间,进行GA的遗传操作,在上下代群体之间纵向传递进化基因,实施解空间的全局搜索.病毒群体进行病毒感染操作,在同代个体之间横向传递进化基因,实施解空间的局部搜索,VEGA将主群体的全局进化和病毒群体的局部进化进行动态结合,从而快速得到问题的全局近似最优解.本文将针对以成本为目标的MPS提出一种病毒协同进化遗传算法MPS-VEGA(multi-modeprojectscheduling-virusco-evolutiongeneticalgorithm).1问题描述一个MPS可以描述为:活动集1},{0,1,nV,0和1n分别表示虚拟的起始活动和结束活动;活动)(Vjj有多个模式}||,,1{jjMM,{1}10nMM;活动j在模式jm下的提前期)(jjmjMmΖpj,01110npp;第)(ρRkk种可重复使用的资源(称为资源ρ)单位时间限量为ρkR,单位成本为ρkc,活动j在模式jm下所消耗的资源量为ρkjjmr,01110ρknρkrr;第)(υRkk种不可重复使用的资源(称为资源υ)限量为υkR,单位成本υkc,活动j在模式jm下所消耗的资源量为υkjjmr,01110υknυkrr.如何确定活动的调度顺序1),0)(,...,(1010njjjjJnn(),...,(10njj为1),(0,1,n的一个排列),模式),...,(10njjmmM和开始时间),...,10njjSSS((10,0nSS项目工期),使得项目活动满足次序约束关系,单位时间内资源ρ限量约束和项目工期内资源υ限量约束的条件下项目的成本最优.按照Brucker[15]的分类表示方法问题可表示为jCrecpMPS||,jCrecpMPS||在于求得活动的最优调度顺序和资源模式,这是一个NP-hard问题,当2||R时是一个NP-complete[4]问题,当活动的模式向量M一旦确定,活动j的模式μ便确定了活动的提前期、资源ρ和资源υ的消耗量,单位资源的成本是一定的,活动j的成本也便确定:胡仕成等:项目优化调度的病毒协同进化遗传算法51,)()(][υμμjjjρμμμμRkυkjυkpSStRkρkjρkυjρjjjrcrcCCCC则项目的成本jC也随之确定,同时jCrecpMPS||退变为经典的max||CrecpPS(工期最小的单模式项目调度问题).定义1.如果J(M或S)满足次序约束、单位时间内资源ρ限量约束或项目工期内资源υ限量约束,则称J(M或S)次序可行,资源ρ可行或资源υ可行,记为J(M或S)T,J(M或S)或J(M或S).如果J,M和ST,并且M和S对应于同一个J,则称),,(SMJ为jCrecpMPS||的一个调度,记为),,(SMJT.定义2.向量的两种运算,连接和裁剪\.设有向量),,,,(54321和),,,,(54321vwvwvv,则:(1)),,,,,,,(-53154321vwvwvvv,称为v连接到w;(2)),,,,,,,(53154321wvwv,称为w连接到v;(3)),,(\531v,称为w按v裁剪;(4)),,(\531wvvvvvwv,称为v按w裁剪.显然,向量的这两种运算和集合对应的运算不同在于:向量运算后仍然是一个向量,且