NEH-Based heuristics for the distributed blocking flowshop with makespan criterion

The distributed blocking flowshop scheduling problem (DBFSP) that is an important generalization of the traditional blocking flowshop scheduling problem (BFSP), in which the blocking constraint has to be considered. The NEH heuristic is regarded as the best constructive heuristic for the permutation flowshop scheduling problem. Naderi and Ruiz proposed the NEH2 for the distributed permutation flowshop scheduling problem by adding a factory assignment rule to the Nawaz-Enscore-Ham (NEH) heuristic. In this paper, a priority rule is first presented for generating initial sequence for the NEH2. Then, the proposed rescheduling operator is applied in NEH insertion procedure. Additionally, we generated a sequence containing all job twice, and then the solution for the problem is constructed by applying the NEH insertion procedure on each element of the sequence. Based on the above ideas, we proposed three NEH-based heuristics, namely NEH2E, NEH2Een and NEH2EE. Computational results demonstrate that the proposed heuristics perform significantly better than the original NEH2.