MOEA/DEP: An Algebraic Decomposition-Based Evolutionary Algorithm for the Multiobjective Permutation Flowshop Scheduling Problem

Algebraic evolutionary algorithms are an emerging class of meta-heuristics for combinatorial optimization based on strong mathematical foundations. In this paper we introduce a decomposition-based algebraic evolutionary algorithm, namely MOEA/DEP, in order to deal with multiobjective permutation-based optimization problems. As a case of study, MOEA/DEP has been experimentally validated on a multiobjective permutation flowshop scheduling problem (MoPFSP). In particular, the makespan and total flowtime objectives have been investigated. Experiments have been held on a widely used benchmark suite, and the obtained results have been compared with respect to the state-of-the-art Pareto fronts for MoPFSP. The experimental results have been analyzed by means of two commonly used performance metrics for multiobjective optimization. The analysis clearly shows that MOEA/DEP reaches new state-of-the-art results for the considered benchmark.