An effective multi-start iterated greedy algorithm to minimize makespan for the distributed permutation flowshop scheduling problem with preventive maintenance

In recent years, distributed scheduling problems have been well studied for their close connection with multi-factory production networks. However, the maintenance operations that are commonly carried out on a system to restore it to a specific state are seldom taken into consideration. In this paper, we study a distributed permutation flowshop scheduling problem with preventive maintenance operation (PM/DPFSP). A multi-start iterated greedy (MSIG) algorithm is proposed to minimize the makespan. An improved heuristic is presented for the initialization and re-initialization by adding a dropout operation to NEH2 to generate solutions with a high level of quality and disperstiveness. A destruction phase with the tournament selection and a construction phase with an enhanced strategy are introduced to avoid local optima. A local search based on three effective operators is integrated into the MSIG to reinforce local neighborhood solution exploitation. In addition, a restart strategy is adpoted if a solution has not been improved in a certain number of consecutive iterations. We conducted extensive experiments to test the performance of the presented MSIG. The computational results indicate that the presented MSIG has many promising advantages in solving the PM/DPFSP under consideration.