多邻域局部搜索算法求解资源受限项目调度

Multi-neighborhood Local Search for Resourced-constrained Project Scheduling

针对资源受限项目调度问题,提出了一种基于多邻域的局部搜索算法。在算法中,设计了两种不同结构的搜索邻域,分别为交换邻域和插入邻域。算法中先使用交换邻域进行较大范围的局部搜索,然后再用插入邻域进行小范围内的精细搜索。两种邻域的交替使用有利于产生尽可能多的多样性解。为了使搜索能够跳出当前邻域,避免陷入局部最优,设计了一种基于均匀交叉操作的邻域移动方法来逐步移动邻域范围。此外,通过双向对齐技术提高每次求得的解的质量,而对具有相同工期的调度方案,则设计了一种新的时间压缩指标用来选择其中的最有潜力者。对标准测试库PSPLIB的2 040个测试案例进行了仿真测试,并与其他启发式算法进行比较,验证了算法的有效性。

To solve the Resource - Constrained Project Scheduling Problem （RGPSP） , a new Multi - Neighborhood Local Search （MNLS） arithmetic, which incorporates the Swap - based Neighborhood Structure （ SNS） and the Insert - based Neighborhood Structure （INS） , is proposed. The MNLS first uses the SNS to find the local optimum in a large search space, and then further improve it with the INS. The alternative utilization of these two neighborhoods is facilitated to generate diversified solutions. In order to avoid the local optimum, a Uniform crossover - based Jump Search （UXJS） is also embedded into the MNLS for progressively moving the current neighborhood to a new one. Meanwhile, the quality of each solution at any time is improved by the Double Justification （SDJ） technique. And a new time compression index is designed to select the most potential one among scheduling solutions with the same makespan during the local search. Finally, the proposed algorithm is verified by the 2040 test instances in the PSPLIB. Computational results and comparisons with some state - of - the - art algorithms indicate that MNSL has good competitiveness.