An evolution strategy approach for the distributed blocking flowshop scheduling problem

doi:10.1016/j.cie.2021.107832

2022-01-01

PRE

Korhan Karabulut

Damla Kızılay *

M. Fatih Taşgetiren

Gao Liang (Liang Gao)

Levent Kandiller

DOI：10.1016/j.cie.2021.107832

原文链接

原文求助

摘要

En 中文

Scheduling in distributed production environments has become common in recent years since the advantages of multi factory manufacturing have been growing. This paper examines the distributed blocking flowshop scheduling problem (DBFSP) to minimize the makespan. Two different mathematical models, namely a mixed-integer programming model and a constraint programming model, were proposed to solve the considered problem to optimality. Due to the NP-Hard nature of the problem, large-size instances cannot be solved by the mathematical models, and an evolutionary algorithm was proposed. Three different NEH-based heuristics were used, and the first three solutions are included in the initial population, whereas the rest is constructed randomly. The offspring population is generated by the self-adaptive destruction and construction (DC) procedure of the iterated greedy algorithm. Self-adaptive DC procedure is achieved by the evolution strategy approach. In the local search part of the algorithm, a variable local search with three neighborhood structures was applied to the solution obtained by the DC procedure. The developed mathematical models initially verified the performance of the metaheuristic algorithm by using small instances. Then, the proposed algorithm was tested on the benchmark suite from the literature. The computational results indicate that the proposed algorithm outperforms the other metaheuristic algorithms from the literature. Finally, the solutions of the 156 best so far were obtained by the proposed algorithm, which is more effective than the existing state-of-the-art methods.

Keyword:

Distributed blocking flowshop scheduling

Destruction and construction

Evolution strategy

Meta-heuristics