刘永利, 张晓阳.一种求解资源约束项目调度问题的改进引力搜索算法[J].河南理工大学学报（自然科学版）,2022,41(4):126-133.

LIU Y L, ZHANG X Y.An improved gravitational search algorithm for solving resource constrained project scheduling problem[J].Journal of Henan Polytechnic University(Natural Science) ,2022,41(4):126-133.

一种求解资源约束项目调度问题的改进引力搜索算法

刘永利, 张晓阳

河南理工大学 计算机科学与技术学院，河南 焦作454000

摘要:引力搜索算法虽然具有较强的搜索能力和较快的收敛速度，但是容易陷入局部最优，且求解精度并不尽如人意。针对具有资源和优先关系约束的资源约束项目调度问题，提出一种改进的引力搜索算法（improved gravitational search algorithm ， IGSA）。该算法将向心力和混沌机制引入引力搜索算法中，一方面通过在不同寻优阶段对参数进行控制，平衡算法中粒子的索能力与开发能力，防止算法陷入局部最优，提高解的精度和加快收敛速度；另一方面当随机 大于混沌序列的值时，对生成的解决方案执行插入或交换操作，增强算法的多样性。为了评 估算法的有效性，在PSPLIB问题实例J30，J60，J90和J120上进行对比实验，结果表明，相较于对比算法，IGSA在求解RCPSP时能更快更准确地得到项目最小完工时间，且能充分利用资源，避免资源浪费。

关键词:改进引力搜索算法;混沌机制;资源约束项目调度问题;向心力

doi:10.16186/j.cnki.1673-9787.2021030060

基金项目:国家自然科学基金资助项目（61872126）

收稿日期:2021/03/07

修回日期:2021/06/18

出版日期:2022/07/15

An improved gravitational search algorithm for solving resource constrained project scheduling problem

LIUYongli , ZHANGXiaoyang

School of Computer Science and Technology， Henan Polytechnic University ，Jiaozuo 454000 ， Henan，China

Abstract: Although gravitational search algorithm has strong search ability and fast convergence speed, it is easy to fall into local optimum, and its solution accuracy is not satisfactory. For resourceconstrained project scheduling problems with resource constraints and priority relationshipconstraints, an improved gravitational search algorithm was proposed. This algorithm introduced the concept of centripetal force and chaotic mechanism into the gravitation search algorithm. By controlling the parameters in different optimization stages , the exploration ability and exploitation ability of the particles could be well balanced,so as to be prevented from falling into the local optimum, and the accuracy and convergence speed of the solution could be improved. When the random number was greater than the value of the chaotic sequence , insert or swap operations were performed on the generated solutions to enhance the diversity. In order to evaluate the effectiveness of the improved algorithm , comparative experiments were carried out on PSPLIB examples J30,J60,J90 and J120.Experimental results showed that,compared with the comparative algorithms,the proposed algorithm could get the minimum project completion time more quickly and accurately,and could make full use of resources to avoid resource waste.

Key words:improved gravitational search algorithm;chaotic mechanism;resource constrained project scheduling problem;centripetal force

一种求解资源约束项目调度问题的改进引力搜索算法_刘永利.pdf