Logic-based benders decomposition methods for the distributed flexible job shop scheduling problem

The Distributed Flexible Job Shop Scheduling Problem (DFJSP) is a well-known NP-hard optimization problem with widespread applications in production scheduling. It involves assigning jobs to factories, allocating operations to machines, and sequencing operations on each machine, which presents significant computational challenges. Although heuristic and metaheuristic approaches have been extensively studied, the exploration of exact algorithms for solving DFJSP remains limited. This paper addresses this gap by proposing three logic-based Benders decomposition (LBBD) frameworks specifically designed for the DFJSP, leveraging the problem’s decomposable structure to achieve optimal or near-optimal solutions with quantifiable quality guarantees within strict time limits. In each LBBD framework, the DFJSP is decomposed into a master problem and several subproblems based on specific decomposition schemes. The corresponding Mixed-Integer Linear Programming (MILP) models and Constraint programming (CP) models for these problems are formulated and solved alternately. Additionally, a hybrid optimization approach is developed by integrating LBBD with CP and heuristic search strategies. The proposed method includes an enhanced CP model with targeted improvements to boost its solving efficiency and incorporates a critical path-based local search strategy to further refine the solution quality. Moreover, several strong subproblem relaxation schemes are incorporated into the master problem under different LBBD frameworks. Comprehensive evaluations on an extended benchmark dataset containing 286 instances demonstrate that the hybrid algorithm achieves an average optimality gap of less than 1.2%. Compared to state-of-the-art MILP, CP, and heuristic methods, the proposed approach delivers superior solution quality and computational efficiency, establishing a new benchmark for solving the DFJSP.