DOI:10.18178/wcse.2019.06.001
A new Neighborhood Structure and its fast Evaluation Strategy in using Iterated Local Search to Solve Single Machine Scheduling
Abstract—In this paper, a new neighborhood structure called Block Exchange and its fast evaluation strategy are proposed when using the Iterated Local Search (ILS) algorithm to solve the single machine scheduling problem without setup times. Applying the proposed ILS algorithm which adopts the Block Exchange neighborhood and fast evaluation strategy to solve 125 public benchmark instances, we achieve highly competitive results compared with the other two ILS algorithms adopt two neighborhoods widely used in the previous literature for single machine scheduling, respectively. Specifically, ILS with Block Exchange neighborhood and fast evaluation strategy finds the best-known results for all the 125 instances, while the other two ILS algorithms can not obtain the best-known results for 97 and 92 instances. The experimental results show that the proposed Block Exchange neighborhood and its fast evaluation strategy are highly effective and efficient.
Index Terms—single machine scheduling, neighborhood structure, Iterated Local Search, Block Exchange.
Hongyun Xu , Quan OuYang
School of Mathematics & Computer Science, JiangHan University, CHINA
Cite: Hongyun Xu , Quan OuYang, "A new Neighborhood Structure and its fast Evaluation Strategy in using Iterated Local Search to Solve Single Machine Scheduling," Proceedings of 2019 the 9th International Workshop on Computer Science and Engineering, pp. 1-5, Hong Kong, 15-17 June, 2019.