A DE-based algorithm for reentrant permutation flow-shop scheduling with different job reentrant times

摘要

The m-machine reentrant permutation flow-shop scheduling problem with different job reentrant times (MRPFSSP_DJRT) is a more practical optimization problem in semiconductor manufacturing industries. However, this important problem has not attracted any attention from an academic standpoint. In this work, a differential evolution (DE) algorithm with two strategies is proposed for solving MRPFSSP_DJRT. Firstly, a largest-order-value (LOV) rule based on random key representation is presented to convert the continuous values of individuals in DE to operation-based job permutations. Then, after the DE-based exploration, an Interchange-based local search with two problem-dependent strategies (i.e., speed-up strategy and change neighborhood strategy) is developed and incorporated into DE to enhance the exploitation ability. Simulation results and comparisons show the effectiveness of the proposed algorithm.