基于模拟退火差异演化算法的资源约束项目调度问题研究.pdfVIP

第 28 卷 第 3 期 工 程 管 理 学 报 Vol. 28 No. 3 2014 年 06 月 Journal of Engineering Management Jun. 2014 基于模拟退火差异演化算法的 资源约束项目调度问题研究 李高扬 1，李万庆 2 （1. 华南农业大学 水利与土木工程学院，广东 广州 510642，E-mail：Lgy2001_2004@163.com； 2. 河北工程大学 经济与管理学院，河北 邯郸 056038） 摘 要：资源约束项目调度问题是工程管理领域研究的热点之一，但无论是模型构建还是求解均有一定的难度，尤其是模型 求解已被证明是 NP-hard问题。鉴于此，构建了以工期最短为优化目标的项目调度模型，为便于求解，将模型的显性约束和 隐性约束做了适当处理，并利用差异演化算法较强的记忆能力和全局收敛能力以及模拟退火的局部跳出能力，将模拟退火算 法和差异演化算法进行有效结合。通过工程实例，分别采用遗传算法、差异演化算法以及模拟退火差异演化算法进行求解。 结果表明，3种算法都可以收敛到最优解，但论文算法具有较大的搜素范围与局部寻优能力，同时求解的稳定性指标明显优 于遗传算法和差异演化算法。 关键词：资源约束；项目调度；模拟退火；差异演化 中图分类号：TU12 文献标识码：A 文章编号：1674-8859（2014）03-109-04 Resource Constrained Project Scheduling Problem Based on Simulated Annealing Differential Evolution Algorithm LI Gao-yang1，LI Wan-qing2 （1. College of Water Conservancy and Civil Engineering，South China Agricultural University，Guangzhou 510642，China， E-mail：Lgy2001_2004@163.com；2. School of Economic and Management，Hebei University of Engineering，Handan 056038，China） Abstract：Resource constrained project scheduling problem is one of the hotspots in research of project management. But both models building and solving have the certain difficulty. Especially models solving has been proved to be NP - hard problem. In view of this，this article constructed the project scheduling model of the shortest time limit as the optimization goal after explicit and implicit constraints of models have been appropriately treated for solving. Simulated annealing algorithm and differential evolution is combined effectively to take advantage of strong ability of memory and global convergence ability of differential evolution and the local jumping out of the ability of and simulated annealing. Through engineering examples，genetic algorithm，difference evolution algorithm and simulated annealing difference evolution algorithm have been programmed to solve respectively. Resul