资源描述：
《基于遗传算法的多模式资源约束项目调度问题研究_王为新》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、#72#计算机应用研究2007年基于遗传算法的多模式资源约束项目调度问题研究*王为新,李原,张开富(西北工业大学现代设计与集成制造技术教育部重点实验室,陕西西安710072)摘要:为解决多模式资源约束项目调度问题,提出了一种混合遗传算法的求解方法。该算法采用二维编码方法来表示问题的解,基因的值表示任务的优先权和执行模式,每条染色体对应一个满足逻辑关系约束的可行任务排序,根据染色体所对应的任务调度顺序和执行模式序列可以获得一个满足资源约束的项目调度方案。应用该编码方法进行选择、交叉和变异等遗传操作,能够使搜索范围遍及整个问题解空间。实际应用表明,该算法
2、能快速求得问题的最优解或近似最优解。关键词:多模式;资源约束;项目调度;遗传算法中图法分类号:TP391文献标识码:A文章编号:1001-3695(2007)01-0072-03ResearchofMult-iModeResource-ConstrainedProjectSchedulingProblemBasedonGeneticAlgorithmWANGWe-ixin,LIYuan,ZHANGKa-ifu(StateKeyLaboratoryofContemporaryDesign&IntegratedManufacturingTechnolog
3、yforMinistryofEducation,NorthwesternPolytechnicalUniversity,Xi.anShanxi710072,China)Abstract:ThispaperdevelopesahybridgeneticalgorithmforsolvingMulti-ModeResource-ConstrainedProjectSchedulingProblem(MRCPSP).Theobjectiveistodetermineamodeandastarttmieforeachactivitysuchthatallco
4、nstraintsareobservedandtheprojectdurationisminimized.Atwo-dmiensionalencodingisusedinthealgorithm.Eachgenerepresentsthepriorityandexecutionmodeofanactivity.Afeasibleactivitysortmeetingprecedenceconstraintscanbegeneratedfromagivenchromosome.Itcanconstructaschedulingmeetingresour
5、ceconstraintsbyselectingtheactivitiesandtheirexecutionmodeinorderoftheirappearanceintheactivitysort.Usingtheencodingthealgorithmcangetallpossibleschedulingsthroughgeneticoperators:selection,crossover,mutation.Resultsshowthatthealgorithmcangetnear-optmialsolutionsofMRCPSPrapidly
6、.Keywords:Mult-iMode;Resource-Constrained;ProjectScheduling;GeneticAlgorithm资源约束项目调度问题(RCPSP)指的是一类在满足项目资源约束和任务前后约束的条件下合理安排工程各作业的开始时间,以最小化项目总工期的调度问题。在传统的RCPSP中,每项任务的工期和资源需求量都是固定的,称为单模式资源约束项目调度问题(SRCPSP)。多模式资源约束项目调度问题(MRCPSP)是SRCPSP的扩展,每项任务在执行时有多种工期和资源需求量的组合形式可供选择,与SRCPSP相比MRCP-S
7、P更接近工程实际。MRCPSP与SRCPSP一样也属于NP-hard问题,近年来该问题吸引着越来越多的学者对其进行研究,并提出了各种各样的优化方法,概括起来可分为以下三类:以分支定界法为代表的精确类算法[1,2];基于优先规则的启发式算法[3,4];以遗传算法和模拟退火算法为代表的智能优化算法[5~7]。精确算法能求得小规模问题的最优解,但对大规模问题无能为力;启发式算法和智能优化算法不能保证求得问题的最优解,但在解决大规模问题时能在求解质量和求解效率上获得一种较好的平衡。本文针对MRCPSP提出了一种混合遗传算法的解决策略。1问题描述在进行问题描述
8、之前,先作如下假设:①任务一旦开始必收稿日期:2005-08-14;修返日期:2005-11-24基金项目:
