An effective differential evolution algorithm for permutation flow shop scheduling problem

The permutation flow shop problem (PFSSP) is an NP-hard problem of wide engineering and theoretical background. In this paper, a hybrid differential evolution (DE) called L-HDE is proposed to solve the flow shop scheduling problem which combines the DE with the individual improving scheme (IIS) and Greedy-based local search. First, to make DE suitable for PFSSP, a new Largest-Rank-rule (LRV) based on a random key is introduced to convert the continuous position in DE to the discrete job permutation so that the DE can be used for solving PFSSP. Second, the NEH heuristic was combined with the random initialization to initialize the population with certain quality and diversity. Third, the IIS-based local search is used for improving the diversity of population and enhancing the quality of the solution with a certain probability. Fourth, the Greedy-based local search is designed to help the algorithm to escape from local minimum. Additionally, simulations and comparisons based on PFSSP benchmarks are carried out, which show that our algorithm is both effective and efficient.