Enhanced branch-and-check for extended flexible job shop scheduling problem with arbitrary precedence graphs

As manufacturing shifts toward personalised and small-batch production, solving large-scale FJSSP instances remains challenging because existing methods often struggle to balance solution quality and computational efficiency in complex environments. This study investigates the extended Flexible Job Shop Scheduling Problem (e-FJSSP) with arbitrary precedence graphs and proposes a Branch-and-Check (BCH) algorithm enhanced by improved lower- and upper-bound strategies. The problem is decomposed into a master problem for operation-to-machine assignment and a subproblem for operation scheduling, which reduces combinatorial complexity by exploiting the independence between assignment and scheduling decisions. To accelerate convergence, we introduce Path Decomposition-based SSP Relaxation (PDSSR) to strengthen lower bounds and a CP-based warm start (CPWS) to provide strong initial upper bounds. The resulting framework, CP-BCHV, scales more effectively than monolithic exact models. In addition, PDSSR can be embedded into an enhanced MILP variant (MILPV). Computational results on the DAFJS, YFJS, and DAHFJS benchmark sets show that CP-BCHV delivers high-quality feasible solutions together with tight bounds and improves 11 best-known solutions for DAFJS. From a managerial perspective, the proposed framework enhances production planning in flexible manufacturing systems by improving coordination between machine assignment and precedence-constrained scheduling.