首页|Neighborhood Combination Search for Single-Machine Scheduling with Sequence-Dependent Setup Time

Neighborhood Combination Search for Single-Machine Scheduling with Sequence-Dependent Setup Time

扫码查看
原文链接
  • 万方数据
  • 维普
In a local search algorithm,one of its most important features is the definition of its neighborhood which is crucial to the algorithm's performance.In 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 efficiency.Second,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 B2.Third,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(HEAnew)to investigate the performance of the neighborhood union and token-ring search.Exten-sive experiments show the competitiveness of the token-ring search combination mechanism of the two neighborhoods.Tested on the 120 public benchmark instances,our HEAnew has a highly competitive performance in solution quality and computational time compared with both the exact algorithms and recent metaheuristics.We have also tested the HEAnew 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 time.HEAnew is able to match the optimal or the best known results for all the 64 instances.In particular,the computational time for reaching the best well-known results for five chal-lenging instances is reduced by at least 61.25％.

single-machine schedulingsequence-dependent setup timeneighborhood combination searchtoken-ring searchhybrid evolutionary algorithm

刘晓路、徐宏云、陈嘉铭、苏宙行、吕志鹏、丁俊文

展开 >

College of System Engineering,National University of Defense Technology,Changsha 410015,China

School of Artificial Intelligence,Jianghan University,Wuhan 430056,China

Xi'an Satellite Control Center,Xi'an 710043,China

School of Computer Science and Technology,Huazhong University of Science and Technology,Wuhan 430074,China

展开 >

National Natural Science Foundation of ChinaNational Natural Science Foundation of ChinaNational Natural Science Foundation of China

622021927180121872101094

2024

10.1007/s11390-023-2007-6

计算机科学技术学报(英文版)
中国计算机学会

计算机科学技术学报(英文版)

CSTPCD
影响因子：0.432
ISSN：1000-9000
年,卷(期)：2024.39(3)