Scheduling under multi-skill workforce constraints: A novel Logic-Based Benders Decomposition Approach

This research is motivated by a real-world production planning problem encountered in the screen printing industry. The production system is modeled as a Dual-Resource-Constrained Re-entrant Flexible Flow Shop Problem (DRCRFFSP), which is a variant of the classical Re-entrant Flow Shop Problem (RFSP). Unlike to the standard Flow Shop Problem (FSP), where jobs progress through all stages in a fixed sequence once, the re-entrant characteristic considered here allows jobs to revisit specific stages multiple times before completion. Additionally, the problem involves a heterogeneous, multi-skilled workforce and requires skilled workers to operate the machines throughout the entire processing time. As a result, the schedule must not only adhere to precedence constraints but also account for resource limitations while ensuring that tasks are assigned to workers with the necessary skills.

Given that the FSP with $n$ jobs and more than two machines is NP-hard \cite{pinedo2008scheduling}, designing efficient solution methods for such an extended setting is particularly challenging. Prior work introduced a constraint programming (CP) formulation and a hybrid genetic algorithm \cite{mlekusch_hartl_2024}, which were able to generate feasible solutions quickly for large-scale instances, although with limited ability to prove optimality.

To address these limitations, the present research introduces an exact solution method based on a novel Logic-Based Benders Decomposition (LBBD) scheme. In most existing benders decomposition approaches for scheduling problems involving resource flexibility, the assignment problem usually acts as the master problem \cite{juvin2023logic}. In contrast, this methodology uses a decomposition in which the scheduling problem acts as the master problem. It fixes the
timing of operations, while a graph colouring subproblem with forbidden colours handles the assignment of operations under skill constraints and identifies combinations of operations that cannot be assigned.

Computational results demonstrate that the proposed exact method outperforms an integrated CP approach in terms of the number of instances solved to optimality and the strength of the bounds obtained for instances that remain unsolved within the time limit. Overall, these results show that the proposed LBBD scheme is an effective exact solution method for the DRCRFFSP and may also be suitable for other complex scheduling problems with limited multi-skilled resources.