Enhanced Iterated Local Search Algorithms for the Permutation Flow Shop Problem Minimizing Total Flow Time

摘要

Flow shop scheduling minimizing total flow time is a famous combinatorial optimization problem. Many algorithms have been proposed to solve it. Among them, iterated local search (ILS) is a simple, efficient and effective one. However, in existing ILS, one basic insertion neighborhood is generally used, greatly limiting the search space. In this work, an enhanced iterated local search (EILS) is proposed, using a hybrid of insertion and swap neighborhoods. The perturbation method also plays an important role in ILS. Two perturbation methods, the insertion method and a destruction and construction heuristic are tested in this paper. Both perform significantly better in comparison to three state of the art algorithms, indicating that the hybrid use of insertion and swap neighborhoods is effective for the discussed problem. However, there is no significant difference between the destruction and construction and the insertion perturbation methods.