Mixed-integer and constraint programming formulations for distributed open shop scheduling problem with makespan minimization

We introduce a new variant of the open shop scheduling problem considering multiple and heterogeneous factories to minimize the total scheduling duration (makespan). Given the NP-hardness of the problem, we present exact and approximate algorithms to solve large-sized instances. First, we propose three novel mixed-integer linear programming models based on innovative representations of decision variables. Furthermore, we develop two new constraint programming models for the problem that differ in the constraint representation of distributed operations in each factory. An extensive analysis of exact models was performed, and the constraint programming model presented the best results and the best computational cost to find the first and best solutions. Finally, we developed a matheuristic hybridizing a mixed-integer and constraint programming model based on an innovative decomposition approach to simplify and solve the problem. The results indicate the superiority of the new matheuristic compared to the competitive algorithms for open shop and its recent variants. In all instances sets, the novel matheuristic performed better than benchmarking methods and mathematical programming models, with average relative percentage deviation to the best solution as low as 1%. Computational results point to the capacity of the proposed approach to solve large-sized problems.