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

Resource Constrained Project Scheduling Problem Based on Simulated Annealing Differential Evolution Algorithm

资源约束项目调度问题是工程管理领域研究的热点之一,但无论是模型构建还是求解均有一定的难度,尤其是模型求解已被证明是NP-hard问题。鉴于此,构建了以工期最短为优化目标的项目调度模型,为便于求解,将模型的显性约束和隐性约束做了适当处理,并利用差异演化算法较强的记忆能力和全局收敛能力以及模拟退火的局部跳出能力,将模拟退火算法和差异演化算法进行有效结合。通过工程实例,分别采用遗传算法、差异演化算法以及模拟退火差异演化算法进行求解。结果表明,3种算法都可以收敛到最优解,但论文算法具有较大的搜素范围与局部寻优能力,同时求解的稳定性指标明显优于遗传算法和差异演化算法。

Resource constrained project scheduling problem is one of the hotspots in research of project management. But bothmodels building and solving have the certain difficulty. Especially models solving has been proved to be NP - hard problem. In viewof this, this article constructed the project scheduling model of the shortest time limit as the optimization goal after explicit andimplicit constraints of models have been appropriately treated for solving. Simulated annealing algorithm and differential evolution iscombined effectively to take advantage of strong ability of memory and global convergence ability of differential evolution and thelocal jumping out of the ability of and simulated annealing. Through engineering examples, genetic algorithm, difference evolutionalgorithm and simulated annealing difference evolution algorithm have been programmed to solve respectively. Results show that thethree kinds of algorithm can converge to the optimal solution, but the paper algorithm has a larger scope of search and localoptimization ability, and solving stability index is superior to genetic algorithm and differential evolutionary algorithm.