摘要
针对以最小化项目工期为目标的资源受限项目调度问题(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.
出处
《计算机工程与应用》
CSCD
北大核心
2009年第24期17-20,共4页
Computer Engineering and Applications
基金
国家高技术研究发展计划(863)/CIMS主题No2006AA04Z150
No2007AA01Z128~~
关键词
资源受限项目调度
遗传模拟退火算法
混合元启发算法
正交实验法
resource-constrained project scheduling
genetic simulated annealing
hybrid meta-heuristic
orthogonal experiment method
