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

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