A multi-phase covering Pareto-optimal front method to multi-objective scheduling in a realistic hybrid flowshop using a hybrid metaheuristic

This paper considers the problem of sequence-dependent setup time hybrid flowshop, scheduling with the objectives of minimizing the makespan and sum of the earliness and tardiness of jobs, and present a multi-phase method. In initial phase, the population will be decomposed into several subpopulations. in this phase we develop a random key genetic algorithm and the goal is to obtain a good approximation of the Pareto-front. In the second phase, for improvement the Pareto-front, non-dominant solutions will be unified as one big population. in this phase, based on the local search in Pareto space concept, we propose multi-objective hybrid metaheuristic. Finally in phase 3, we propose a novel method using e-constraint covering hybrid metaheuristic to cover the gaps between the non-dominated solutions and improve Pareto-front. Generally in three phases, we consider appropriate combinations of multi-objective methods to improve the total performance. The hybrid algorithm used in phases 2 and 3 combines elements from both simulated annealing and a variable neighborhood search. The aim of using a hybrid metaheuristic is to raise the level of generality so as to be able to apply the same solution method to several problems. Furthermore, in this study to evaluate non-dominated solution sets, we suggest several new approaches. The non-dominated sets obtained from each phase and global archive sub-population genetic algorithm presented previously in the literature are compared. The results obtained from the computational study have shown that the multi-phase algorithm is a viable and effective approach. (C) 2009 Elsevier Ltd. All rights reserved.