A discrete differential evolution algorithm for multi-objective permutation flowshop scheduling

Abstract

The more practical and interesting versions of the permutation flowshop scheduling problem (PFSP) have a variety of objective criteria to be optimized simultaneously. Multi-objective PFSP is also a relevant combinatorial multi-objective optimization problem. In this paper we propose a multi-objective evolutionary algorithm for PFSP by extending the previously proposed discrete differential evolution (DE) scheme for single-objective PFSP. This is the first application of the algebraic-based discrete DE to multi-objective problems. The algorithm is extended by adopting a variety of crossover and multi-objective selection operators. Among these, the multi-objective α-selection is a novelty of this work and can be decoupled from DE and used also in other evolutionary algorithms. The other crossover and selection operators have been taken from the existing literature and, where required, have been adapted to the problem at hand. An experimental evaluation has been conducted on all the three bi-objective PFSPs among the makespan, total flowtime and total tardiness criteria. The results show that the proposed approach is competitive with respect to the state-of-the-art algorithms.