An Iterated Greedy Algorithm for Distributed Blocking Flowshop Problems with Makespan Minimization

In this paper, we study a distributed blocking flowshop scheduling problem (DBFSP) that is an extension of the traditional blocking flowshop scheduling problem (BFSP), in which an additional decision of which factory to process each job. We propose an iterated greedy (IG) algorithm to minimize makespan among all the factories. First of all, an effective initialization method based on the PW algorithm is used in order to make better use the problem-specific characteristics. Then, an enhanced construction method is developed to further improve the solution obtained at each iteration. At last, after calibration of algorithm parameters, comparison of algorithms is carried out using the well-known 720 instances from the literature. The results demonstrate the effectiveness of the proposed IG algorithm for solving the DBFSP with makespan criterion.