摘要
针对资源受限项目调度问题,提出了一种基于多邻域的局部搜索算法。在算法中,设计了两种不同结构的搜索邻域,分别为交换邻域和插入邻域。算法中先使用交换邻域进行较大范围的局部搜索,然后再用插入邻域进行小范围内的精细搜索。两种邻域的交替使用有利于产生尽可能多的多样性解。为了使搜索能够跳出当前邻域,避免陷入局部最优,设计了一种基于均匀交叉操作的邻域移动方法来逐步移动邻域范围。此外,通过双向对齐技术提高每次求得的解的质量,而对具有相同工期的调度方案,则设计了一种新的时间压缩指标用来选择其中的最有潜力者。对标准测试库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.
作者
何杰光
崔得龙
DONG Jiawei;ZHANG Dongmei;CHENG Lihua;FAN Fang;SHEN Shuqian;QIU Cailin;ZENG Wanwen(College of Environmental and Biotechnical Engineering, Guangdong University of Petrochemical Technology, Maoming 525000, China;Maoming inspection institute, Guangdong Special Equipment Inspection and Research Institute, Maoming 525000, China;Maoming Branch of China petrochemical co. LTD. , Maoming 525000, China)
出处
《广东石油化工学院学报》
2018年第1期27-32,共6页
Journal of Guangdong University of Petrochemical Technology
基金
国家自然科学基金项目(61672174)
茂名市科技计划项目(2017287)
广东石油化工学院人才引进项目(2016rc02)
关键词
资源受限项目调度
局部搜索
交换邻域
插入邻域
邻域移动
Resource - constrained project scheduling
Local search
Swap - based neighborhood structure
Insert - based neighborhood structure
Neighborhood move
Double justification