Enhanced Logic-Based Benders Decomposition Approaches for Flexible Job Shop Scheduling Benchmark Problem with Discrete Operation Sequence Flexibility

In real manufacturing environments, several operations within a job may not adhere to a strict processing sequence and can be executed at arbitrary positions. However, the traditional flexible job shop scheduling problem (FJSP) typically assumes that operations of the same job follow a predefined processing order. To address this gap, this paper studies the FJSP with discrete operation sequence flexibility (FJSPDS) to minimize the makespan. First, a mixed-integer linear programming (MILP) model is developed to solve small-sized instances optimally. Second, a logic-based Benders decomposition (LBBD) framework is designed by integrating the proposed MILP model with a constraint programming (CP) model. Guided by the “divide-and-conquer” principle, the LBBD approach can effectively handle medium- and large-scale instances. Third, two enhancement techniques are introduced to further boost the performance of the LBBD framework. The first is a hybrid genetic algorithm combined with CP (GA-CP), which provides tighter upper bounds and accelerates the convergence of the LBBD. The second is a critical path-based cut-strengthening heuristic that enhances Benders optimality cuts. Experiments are conducted on 110 benchmark instances. Compared with existing MILP models, the proposed MILP formulation employs fewer constraints and can obtain optimal solutions for all small-scale instances. Furthermore, the enhanced LBBD framework improves 47 best-known solutions compared with state-of-the-art methods.