A hybrid genetic algorithm for distributed hybrid blocking flowshop scheduling problem

This paper addresses a distributed hybrid blocking flowshop scheduling problem (DHBFSP) with makespan criterion. Based on the distributed hybrid flowshop scheduling problem (DHFSP) and blocking constraints, a mathematical model of mixed integer linear programming for the DHBFSP is proposed, and a hybrid genetic algorithm is developed. Eight new heuristics are defined in the process of population initialization according to the blocking characteristics of the problem, and five heuristic rules are chosen through experiments for population initialization and the rest of the individuals are generated randomly. Offspring individuals are obtained through crossover and mutation operations, while an offspring selection strategy is proposed to make decisions in the population offspring selection. The destruction and reconstruction (DR) operation is performed for the optimal individuals of the offspring population to optimize their individual structures, and a local search method is adopted for the deep search of individuals. Compared with other existing meta-heuristics, the proposed hybrid genetic algorithm performs better on benchmarks and the local search method VND_LS3 has a comprehensively strong search capability.