doi:10.16186/j.cnki.1673-9787.2021030060

Received:2021/03/07

Revised:2021/06/18

Published: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