一种改进的求解RACP问题的路径重连方法研究

Solving the Resource Availability Cost Problem Based on Improved Path Relinking

讨论了在规定时间内以最小资源代价完成一项工程调度的问题(RACP),这是一个NP-Hard问题。现有文献针对RACP问题的研究较少,并且主要的求解方法是将RACP问题转化为若干个资源受限下的项目调度问题(RCPSP)。采用活动列表AL(Activity List)编码方案,引入路径重连方法直接对RACP问题进行优化;并针对路径重连的参考级更新过程进行改进。最后,基于PSPLIB测试用例库设计了算例,并与遗传算法进行了结果比较。实验结果表明基于改进的路径重连算法能够非常有效的求解RACP问题,且运行效果明显优于遗传算法。

A project scheduling problem with the objective of minimizing resource availability costs is considerd,which all the activities have to be executed in a given time of completion（makespan）.This is a NP-hard optimization problem.There were few solutions for solving the RACP in the literature,and most of them prefer to change it into a series of RCPSP.The activity list（AL） representations is adopted and directly optimized the RACP with the introduction of path relinking.Furthermore,the procedure of reference set updating is improved.Eventually,the simulation instances were chosen from the PSPLIB.it is also compard to the Genetic Algorithm（GA）.The experimental findings suggeste that the improved path relinking method could effectively solve the RACP problem and could produce a better result than the GA.