Effective metaheuristics for scheduling a hybrid flowshop with sequence-dependent setup times

摘要

This paper proposes a total of nine algorithms to minimize the makespan for the hybrid flowshop scheduling problem with sequence-dependent setup times. The first six algorithms are trajectory-based metaheuristics, including three variants of iterated local search and three variants of iterated greedy. The remaining three algorithms are population-based metaheuristics, namely, the improved fruit fly optimization, the improved migrating birds optimization, and the discrete artificial bee colony optimization. We present some advanced and effective technologies, including three mixed neighborhood structures, an enhanced perturbation method, and an enhanced destruction and construction procedure for the trajectory-based metaheuristics. We propose a path-relinking-based cooperative search, a diversity control scheme, and a diversified initialization approach for the improved fruit fly optimization. We calibrate the parameters and operators for the proposed algorithms by means of a design of experiments approach. To evaluate the proposed algorithms, we present several adaptations of other recent well-known meta-heuristics for the problem and conduct a comprehensive set of computational and statistical experiments to demonstrate the effectiveness of the presented algorithms. Among them, the discrete artificial bee colony optimization is the best-performing algorithm and it is able to improve 126 out of the 240 best known solutions for the benchmarks in the literature.