Effective heuristics and metaheuristics for the distributed fuzzy blocking flow-shop scheduling problem

In consideration of the uncertainty of manufacturing system, this paper investigates a distributed fuzzy blocking flow-shop scheduling problem (DFBFSP) in which there are multiple homogeneous factories and each one is set as a flow shop with no intermediate buffers between any consecutive machines. The processing time is uncertain and represented by the fuzzy number. The objective is to minimize the fuzzy makespan among all factories. To address this problem, two constructive heuristics (i.e., INEH and DPFNEH) are firstly proposed based on the problem-specific knowledge and the NEH heuristic. The INEH employs the spread value of fuzzy processing time to generate the initial job sequence. The DPFNEH assigns the partial jobs to factories by reducing the total expected idle time and blocking time. Afterwards, two iterated greedy (IG) methods are presented in which the proposed constructive heuristic is employed to generate the initial solution with high quality. A novel plateau exploration based local search is incorporated to enhance the quality of solutions. To keep the search vitality, an improved acceptance criterion based on the fuzzy characteristic is designed to avoid falling into the local optimum. Finally, a comprehensive computational experiment and comparisons with the state-of-the-art methods in the literature are conducted based on an extended benchmark set and a new evaluation indicator. The results show that the proposed constructive heuristics and IG methods can effectively and efficiently solve the considered problem.