Neighborhood Combination Search for Single-Machine Scheduling with Sequence-Dependent Setup Time
作者机构：College of System EngineeringNational University of Defense TechnologyChangsha 410015China School of Artificial IntelligenceJianghan UniversityWuhan 430056China Xi’an Satellite Control CenterXi’an 710043China School of Computer Science and TechnologyHuazhong University of Science and TechnologyWuhan 430074China CCF
出 版 物：《Journal of Computer Science & Technology》 (计算机科学技术学报（英文版）)
年 卷 期：2024年第39卷第3期
页 面：737-752页
核心收录：
学科分类：08[工学] 0835[工学-软件工程] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）]
基 金：supported by the National Natural Science Foundation of China under Grant Nos.62202192 71801218 and 72101094
主 题：single-machine scheduling sequence-dependent setup time neighborhood combination search token-ring search hybrid evolutionary algorithm
摘 要：In a local search algorithm,one of its most important features is the definition of its neighborhood which is crucial to the algorithm s *** this paper,we present an analysis of neighborhood combination search for solv-ing the single-machine scheduling problem with sequence-dependent setup time with the objective of minimizing total weighted tardiness(SMSWT).First,We propose a new neighborhood structure named Block Swap(B1)which can be con-sidered as an extension of the previously widely used Block Move(B2)neighborhood,and a fast incremental evaluation technique to enhance its evaluation ***,based on the Block Swap and Block Move neighborhoods,we present two kinds of neighborhood structures:neighborhood union(denoted by B1UB2)and token-ring search(denoted by B1→B2),both of which are combinations of B1 and ***,we incorporate the neighborhood union and token-ring search into two representative metaheuristic algorithms:the Iterated Local Search Algorithm(ILSnew)and the Hybrid Evolutionary Algorithm(HEA_(new))to investigate the performance of the neighborhood union and token-ring ***-sive experiments show the competitiveness of the token-ring search combination mechanism of the two *** on the 120 public benchmark instances,our HEA_(new)has a highly competitive performance in solution quality and computational time compared with both the exact algorithms and recent *** have also tested the HEA,new algorithm with the selected neighborhood combination search to deal with the 64 public benchmark instances of the single-machine scheduling problem with sequence-dependent setup *** is able to match the optimal or the best known results for all the 64 *** particular,the computational time for reaching the best well-known results for five chal-lenging instances is reduced by at least 61.25%.
维普期刊数据库