Mixed-integer and constraint programming formulations for distributed open shop scheduling problem with makespan minimization
针对多工厂分布式开放车间调度问题，提出三种混合整数线性规划和两种约束规划模型，并开发了一种混合整数与约束规划混合的元启发式算法，在大型实例上平均偏差低至1%。
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.