资源受限多项目调度的混合遗传算法  

Hybrid genetic algorithm for resource constrained multi-project scheduling problem

作　　者：应瑛[1] 寿涌毅[1] 李敏[1] 

机构地区：[1]浙江大学管理学院,浙江杭州310058

出　　处：《浙江大学学报（工学版）》2009年第1期23-27,共5页Journal of Zhejiang University：Engineering Science

基　　金：国家自然科学基金资助项目(70401017)

摘　　要：针对资源受限多项目调度问题,提出了改进后的混合遗传算法.该算法基于串行进度生成机制,结合多项目任务列表与项目优先权设计了新的染色体,所设计的交叉算子与变异算子均能保证所得新个体满足项目紧前关系约束,从而有效提高算法搜索效率.算法充分利用不同启发式算法构造初始种群,有效扩大种群多样性以避免过早收敛.算法采用正向逆向调度技术对调度方案进行优化,进一步提高了调度方案的质量.与其他多项目调度启发式算法相比,该算法能有效分配资源,显著缩短项目平均总工期.A new hybrid genetic algorithm was proposed to solve the resource constrained multi-project scheduling problem. The algorithm utilized the serial schedule generation scheme to construct project schedules. A new chromosome was designed integrating the multi-project activity list and individual project priorities. Genetic operators, including crossover and mutation operators, ensured the next generation individuals are always precedence feasible, thus significantly accelerated the searching speed of the algorithm. A variety of heuristics and priority rules were employed to generate the original population so as to increase population diversity and avoid early constringency. A forward-backward scheduling technique was also integrated to improve the schedule quality. Results show that the algorithm can effectively allocate constraint resources to achieve a shorter overall multi-project duration.

关 键 词：遗传算法 项目调度 资源约束 

分 类 号：TB114.1[理学—运筹学与控制论] TP311.5[理学—概率论与数理统计]