An evolution strategy approach for the distributed blocking flowshop scheduling problem

Abstract

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.