Multi-objective Flow Shop Scheduling Using Differential Evolution

This paper proposes an effective Differential Evolution (DE) based hybrid algorithm for Multi-objective Permutation Flow Shop Scheduling Problem (MPFSSP), which is a typical NP-hard combinatorial optimization problem. In the proposed Multi-objective Hybrid DE (MOHDE), both DE-based searching operators and some special local searching operators are designed to balance the exploration and exploitation abilities. Firstly, to make DE suitable for solving MPFSSP, a largest-order-value (LOV) rule based on random key representation is developed to convert the continuous values of individuals in DE to job permutations. Then, to enrich the searching behaviors and to avoid premature convergence, a Variable Neighborhood Search (VNS) based local search with multiple different neighborhoods is designed and incorporated into the MOHDE. Simulation results and comparisons with the famous random-weight genetic algorithm (RWGA) demonstrate the effectiveness and robustness of our proposed MOHDE.