An iterated greedy algorithm for the distributed permutation flowshop scheduling problem with preventive maintenance to minimize total flowtime

Abstract

In recent years the distributed permutation flowshop scheduling problem (DPFSP) has been widely studied. In this paper we extended the DPFSP by considering preventive maintenance (PM) operation to prevent machines from breaking down after the long process. An iterated greedy (IG) algorithm is developed to minimize total flowtime. A heuristic with swapping operator is proposed to initialize the IG. After that the destruction phase and construction phase are modified to fit our problem. A local search is then applied to further improve the solution generated in the construction stage. At last a simple simulated annealing-like acceptance criterion is used to prevent local optimal situations. Comparison with three state-of-the art algorithms in the recent literature based on 225 instances shows the high performance of our IG algorithm for solving the DPFSP with PM operation.