A novel solution methods for the Flexible Job Shop Problem

This research presents a novel decomposition approach for the well-known flexible job shop scheduling problem. Due to the NP-hard nature of the job shop problem and its extensions, obtaining optimal solutions remains a significant challenge. The study introduces an exact solution method based on Logic-Based Benders decomposition, which reformulates the original problem into two interrelated subproblems: a non-flexible scheduling problem with cumulative resource constraints, solved using constraint programming and serving as the master problem, and a graph colouring problem with forbidden colours as the subproblem. The proposed decomposition approach is evaluated against a constraint programming model for the integrated problem using a set of benchmark instances from the literature. The results demonstrate that the proposed method is competitive with existing solution techniques and is particularly effective in providing tighter lower bounds than the standalone constraint programming approach.