A Pattern-Based Decomposition Algorithm for Multi-Workstation Human Resource Allocation Under Spatial-Temporal Constraints

This paper addresses a human resource allocation problem with spatial-temporal constraints (HRAP-SC) in the parallel assembly of complex products, such as satellites and aircraft. It involves coordinating a limited pool of multi-skilled workers across geographically distributed workstations, subject to rigorous constraints including team collaboration requirements, operation priorities, technological tail times (e.g., curing), and strict 8 h workdays. Existing exact approaches typically fail to converge due to the combinatorial explosion arising from the strong coupling of shared resources across workstations, while meta-heuristic methods often suffer from performance instability caused by hyper-parameter sensitivity. To overcome these limitations, we propose a pattern-based decomposition algorithm (PDA), a novel parameter-free exact solution framework. By exploiting the inherent symmetry of identical jobs and parallel workstations, PDA defines a set of canonical patterns to drastically reduce the search space. It employs an efficient traversal mechanism reinforced by rigorous mathematical bounds and pruning rules to eliminate unpromising solutions. Computational experiments demonstrate that PDA significantly outperforms state-of-the-art Mixed-Integer Programming (MIP) and Constraint Programming (CP) solvers. Unlike standard solvers, which frequently time out (3600 s), PDA strictly evaluates only a single pattern when proving optimality, and robustly scales to large industrial instances (e.g., six jobs comprising 78 operations) to provide high-quality schedules. By successfully solving complex scheduling problems that remain intractable for monolithic solvers, PDA provides a robust and automated decision-support tool for production management in complex manufacturing systems.