应用遗传模拟退火算法实现资源受限项目调度  

Genetic simulated annealing algorithm for resource-constrained project scheduling problem

作　　者：喻小光[1,2] 战德臣[1] 聂兰顺[1] 

机构地区：[1]哈尔滨工业大学计算机科学与技术学院,哈尔滨150001 [2]华侨大学计算机科学与技术学院,福建泉州362021

出　　处：《计算机工程与应用》2009年第24期17-20,共4页Computer Engineering and Applications

基　　金：国家高技术研究发展计划(863)/CIMS主题No2006AA04Z150;No2007AA01Z128~~

摘　　要：针对以最小化项目工期为目标的资源受限项目调度问题(RCPSP),提出将模拟退火算法融合到遗传算法中,以改善遗传算法局部搜索性能,增强进化能力的遗传模拟退火算法——RCPSPGSA。在每次进化迭代过程中,下一代种群的个体需经过模拟退火算法改进,并通过在每次迭代结束前进行降温操作保证遗传算法和模拟退火算法具有相同的收敛方向和速度。算法在RCPSP标准测试问题库PSPLIB上进行数值仿真实验,并采用正交实验分析法解决参数选择问题。实验结果证明选择的参数组合具有突出的性能,RCPSPGSA是求解RCPSP的有效算法。A novel hybrid meta-heuristic algorithm,entitled as RCPSPGSA,is proposed for solving the Resource-Constrained Project Scheduling Problem（RCPSP）.The algorithm incorporates the Simulated Annealing algorithm（SA） into genetic algorithm in order to improve local searching performance and boost up evolution capability.In each evolution iteration GA generates a new temporary population,and after that SA is used for improving every individual in it and at the mean time the next gap population is generated.For the sake of keeping the same convergence direction and speed of ＇GA and SA, the cooling procedure occurs at the end of each evolution iteration.Simulation experiments are performed on the standard project instance sets of PSPLIB,and orthogonal experiment method is introduced to solve the parameter selection problem.Parameter combinations selected by this method are proved to be outperformed.Experimental results show that RCPSPGSA improves solution quality for J30,J60,J90 sets and not bad for J120.

关 键 词：资源受限项目调度 遗传模拟退火算法 混合元启发算法 正交实验法 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]