Genetic local search algorithm for multi-objective flowshop scheduling problems

We propose a hybrid algorithm to search for non-dominated solutions of multi-objective flowshop scheduling problems. The proposed hybrid algorithm is constructed by combining a local search procedure with a multi-objective genetic algorithm. A large variety of non-dominated solutions can be obtained by the proposed algorithm with various search directions in the objective space. A tentative set of non-dominated solutions is separately stored from the current populations during the execution of the proposed algorithm. Some of the stored non-dominated solutions are used as elite solutions. In the local search procedure of the proposed algorithm, the number of neighborhood solutions that are examined for each move is limited in order to equally utilize the two different search mechanisms: the local search and the global search by the genetic algorithm. The ability of the proposed algorithm to efficiently search for a large variety of non-dominated solutions is demonstrated by applying it to multi-objective flowshop scheduling problems for minimizing the makespan, the maximum tardiness and the total flowtime.