An effective hybrid DE-based algorithm for flow shop scheduling with limited buffers

The permutation flow-shop scheduling problem (PFSSP) is a typical combinational optimization problem, which is of wide engineering background and has been proved to be strongly NP-hard. In this paper, an effective hybrid algorithm based on differential evolution (DE), namely HDE, is proposed for permutation flow-shop scheduling with limited buffers between consecutive machines to minimize the maximum completion time (i.e. makespan). First, to make DE suitable for solving PFSSP, a largest-order-value (LOV) rule is presented to convert the continuous values of individuals in DE to job permutations. Second, after the DE-based exploration, an efficient local search, which is designed according to the landscape of PFSSP and the generalization of the block elimination properties, is applied to emphasize exploitation. Thus, not only does the HDE apply the parallel evolution mechanism of DE to perform effective exploration (global search), but it also adopts problem-dependent local search to perform exploitation well (local search). Furthermore, the convergence property of HDE is analyzed based on the theory of finite Markov chain. Simulations and comparisons based on benchmarks demonstrate the effectiveness and robustness of the proposed HDE, and the effect of one key parameter on the performance of HDE is investigated as well.