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 ...