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

Abstract

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.