关键词: 资源受限项目调度, 粒子群优化, 双向路径重连, 均匀块交叉, 双种群进化

Abstract: To solve Resource-Constrained Project Scheduling Problem (RCPSP),a new Double-Population Quasi Particle Swarm Optimization (DPQ-PSO) was proposed.Based on the optimization principle of basic PSO,the position update formula was redefined by abandoning the velocity part and introducing a new component of diversity information.The subtraction between positions,the multiplication of a subtraction by scalar and the addition between positions were also redefined.For the problem-specific characteristics of PCPSP,a particle was represented by an activity list,and a new bidirectional path relinking was used to implement the subtraction.A selection operation was used to implement the scalar multiplication,and a new uniform block crossover was used to fulfill the addition.For the population diversity,a double-population parallel evolutionary mechanism was also incorporated in the algorithm.The Taguchi method of design-of-experiment was utilized to find out the best combinations of parameter values in DPQ-PSO.The simulation test for problem sets of J30,J60 and J120 in PSPLIB and a real assembly project case were conducted,and the results showed that DPQ-PSO was superior to the current PSO-based algorithms.The effectiveness of proposed algorithm was also verified by comparing with some other heuristic algorithms.

Key words: resource-constrained project scheduling, particle swarm optimization, bidirectional path relinking, uniform block crossover, double-population evolution