An effective two-stage iterated greedy algorithm for distributed flowshop group scheduling problem with setup time

The distributed flow shop group scheduling problem (DFGSP) has wide industrial applications. Due to the strong coupling of DFGSP, three issues should be solved, such as assigning groups to factories, arranging the sequence of groups in each factory and scheduling the sequence of jobs in each group. Meanwhile, the calculation for the objective has a high time complexity. To solve the above problems, we first build a mixed-integer linear programming model of DFGSP and verify its correctness by using the Gurobi solver. By exploring the implicit characteristics of the problem, two rapid evaluation methods based on group insertion and job insertion are designed to accelerate the evaluation of the objective. Then, an effective two-stage iterated greedy algorithm (tIGA) is proposed to solve the above three coupled subproblem. In the proposed tIGA, two intra-factory and inter-factory cooperative neighborhood search strategies and two intra-group and inter-group enhanced search strategies are proposed, respectively, to improve the search breadth and depth. The results of comprehensive statistical experiments on 810 test instances show that the proposed algorithm significantly outperforms the compared ones in terms of objective values and relative percentage increase values, and demonstrates the effectiveness of the proposed tIGA.