An improved hybrid multi-objective parallel genetic algorithm for hybrid flow shop scheduling with unrelated parallel machines

In this paper, we address the hybrid flow shop scheduling problems with unrelated parallel machines, sequence-dependent setup times and processor blocking to minimize the makespan and maximum tardiness criteria. Since the problem is strongly NP-hard, we propose an effective algorithm consisting of independent parallel genetic algorithms by dividing the whole population into multiple subpopulations. Each subpopulation will be assigned with different weights to search for optimal solutions in different directions. To further cover the Pareto solutions, each algorithm is combined with a novel local search step and a new helpful procedure called Redirect. The proposed Redirect procedure tries to help the algorithm to overcome the local optimums and to further search the solution space. When a population stalls over a local optimum, at first, the algorithm tries to achieve a better solution by implementing the local search step based on elite chromosomes. As implementing the local search step is time-consuming, we propose a method to speed up the searching procedure and to further increase its efficiency. If the local search step failed to work, then the Redirect procedure changes the direction and refreshes the population. Computational experiments indicate that our proposed improving procedures are thriving in achieving better solutions. We have chosen two measures to evaluate the performance of our proposed algorithms. The obtained results clearly reveal the prosperity of our proposed algorithm considering both measures we have chosen.