An Effective DE-EDA for Permutation Flow-shop Scheduling Problem

Aiming at the permutation flow-shop scheduling problem (PFSSP) with makespan criterion, a combination algorithm based on differential evolution (DE) and estimation of distribution algorithm (EDA), namely DE-EDA, is proposed. Firstly, DE-EDA combines the probability-dependent macro information extracted by EDA and the individual-dependent micro information obtained by DE to execute the exploration, which is helpful in guiding the global search to explore promising solutions. Secondly, in order to make DE well suited to solve PFSSP, a convert rule named smallest-ranked-value (SRV) is designed to generate the discrete job permutations from the continuous values. Thirdly, a sequence-learning-based Bayes posterior probability is presented to estimate EDA's probability model and sample new solutions, so that the global information of promising search regions can be learned precisely. In addition, a simple but effective two-stage local search is embedded into DE-EDA to perform the exploitation, and thereafter numerous potential solution(s) with relative better fitness can be exploited in some narrow search regions. Finally, simulation experiments and comparisons based on 29 well-known benchmark instances demonstrate the effectiveness of the proposed DE-EDA.