An optimal block knowledge driven backtracking search algorithm for distributed assembly No-wait flow shop scheduling problem

The distributed assembly flow shop scheduling problem (DAFSP) is an important scenario in manufacturing system. In this paper, an optimal block knowledge driven backtracking search algorithm (BKBSA) is proposed to solve the distributed assembly No-wait flow shop scheduling problem (DANWFSP) with the objective of minimizing the completion time of assembly process. In BKBSA, three constructive heuristics are proposed to generate a competitive initial solution. Block-shifting based on block knowledge is embedded in the mutation strategy of BKBSA. The proposed block-shifting ensures that the optimal subsequence of a candidate solution is not destroyed in the mutation operation. The similarity between candidate solutions is utilized as feedback indicator to control the utilization of block-shifting. In addition, the VND algorithm based on factory-to-factory is proposed to further improve the optimal solution. Finally, the BKBSA and the other three state-of-the-art algorithms for DANWFSP are tested on 810 large-scale instances and 900 small-scale instances. The statistical analysis results show that BKBSA is an effective algorithm to solve DANWFSP. (C) 2021 Elsevier B.V. All rights reserved.

Automated summary

This paper proposes an optimal block knowledge-driven backtracking search algorithm (BKBSA) to solve the distributed assembly No-wait flow shop scheduling problem (DANWFSP), with constructive heuristics for generating initial solutions, block-shifting based on knowledge, and feedback control using similarity between candidate solutions. Additionally, a VND algorithm is proposed for further optimization. Test results on large-scale and small-scale instances show that BKBSA is an effective algorithm for solving DANWFSP.