《Mathematics》：A Pattern-Based Decomposition Algorithm for Multi-Workstation Human Resource Allocation Under Spatial-Temporal Constraints
编辑推荐：
本文研究了复杂产品（如卫星和飞机）并行装配过程中带有空间—时间约束的人力资源分配问题（HRAP-SC）。该问题涉及在地理分散的多个工位之间协调有限数量的多技能工人，同时满足严格约束，包括团队协作需求、作业优先级、工艺尾时间（例如固化）以及严格的 8 h 工作日
本文研究了复杂产品（如卫星和飞机）并行装配过程中带有空间—时间约束的人力资源分配问题（HRAP-SC）。该问题涉及在地理分散的多个工位之间协调有限数量的多技能工人，同时满足严格约束，包括团队协作需求、作业优先级、工艺尾时间（例如固化）以及严格的 8 h 工作日。现有精确方法通常由于多工位间共享资源强耦合所引发的组合爆炸而难以收敛，而元启发式方法则常因超参数敏感性导致性能不稳定。为克服上述局限，研究人员提出了一种模式分解算法（PDA），这是一种新颖的、无参数的精确求解框架。该方法通过利用同构作业与并行工位的内在对称性，定义一组规范模式（canonical patterns），从而大幅压缩搜索空间。PDA 采用由严格数学界和剪枝规则强化的高效遍历机制，以排除无前景解。计算实验表明，PDA 显著优于当前先进的混合整数规划（MIP）和约束规划（CP）求解器。与经常在 3600 s 内超时的标准求解器不同，PDA 在证明最优性时严格上仅需评估单一模式，并且能够稳健扩展至大型工业实例（例如包含 78 道工序的 6 个作业），从而提供高质量调度方案。通过成功求解对整体式求解器而言仍难处理的复杂调度问题，PDA 为复杂制造系统中的生产管理提供了一种稳健且自动化的决策支持工具。
该论文发表于《Mathematics》，聚焦工业 4.0 与智能制造背景下复杂产品并行装配中的多工位人力资源分配问题。研究背景在于，卫星、商用飞机等复杂产品的总装过程包含大量零部件、严格工艺约束与较长执行周期，传统串行装配模式已难以满足柔性化与定制化生产需求，因此并行装配过程（parallel assembly processes, PAPs）逐渐成为主流。然而，PAPs 虽提高了作业并行性，却也显著加剧了共享资源同步的复杂度。尤其在多个固定工位同时作业时，有限的多技能工人需要跨工位配置，且不同工人熟练度不同、同一工序往往要求多人同时协作，造成强烈的跨工位资源竞争。与此同时，作业还受到严格的优先关系、工艺尾时间以及 8 h 工作日历约束的共同作用，任务可跨工作区间中断，但单次工序的人力指派又保持非抢占特性。正因为空间分布与时间边界共同耦合，该问题成为系统效率提升的核心瓶颈。
现有研究虽已将该类问题视为多技能资源受限项目调度问题（multi-skilled resource-constrained project scheduling problem, MS-RCPSP）的推广，但多数成果仍集中于单工位环境，尚缺乏同时处理分布式空间约束、多工位物流竞争、日历约束与尾时间约束的统一框架。元启发式方法虽具可扩展性，却缺乏最优性保证，且对实例依赖的超参数较敏感；混合整数规划（mixed-integer programming, MIP）和约束规划（constraint programming, CP）虽在逻辑约束表达上更强，但面对多工位共享资源的强耦合时，整体式建模易出现组合爆炸，难以在大规模实例中收敛。因此，开展此项研究的必要性在于：需要一种既保留精确算法最优性保证、又能突破整体式求解瓶颈的新型方法，以支撑复杂制造环境中的自动化排产决策。
研究人员围绕带空间—时间约束的人力资源分配问题（HRAP-SC）建立了系统性的建模与求解框架。论文首先对问题进行形式化定义，同时构建了 MIP 模型与 CP 模型，并证明该问题具有 NP-hard 性质。随后，研究人员提出优先规则构造启发式（priority-rule-based constructive heuristic, PBCH）作为快速可行解生成器与上界提供器；针对单工位情形，进一步设计精确迭代算法（Exact Iterative Algorithm, EIA），利用顺序支配、剪枝性质与关键“割点工序”（articulation operation，指在工序优先图中起严格时序桥接作用的工序）加速精确求解；在多工位场景中，则提出论文的核心贡献——模式分解算法（pattern-based decomposition algorithm, PDA），通过定义规范模式，将作业—工位分配问题转化为整数划分驱动的模式遍历问题，并在每个模式下调用 CP 进行精确子问题求解，同时结合上下界评估与平衡优先搜索策略实现高效剪枝。最终，实验结果显示，PDA 在多工位大规模实例上明显优于 CPLEX 与 CP Optimizer 等商业求解器，能够在不少实例中仅评估 1 个模式即完成最优性证明，从而恢复复杂问题的计算可处理性。
就方法而言，作者主要使用了 4 类关键技术。首先，基于实际复杂产品装配特征构建 HRAP-SC 的 MIP 与 CP 数学模型，统一表达工序优先关系、尾时间、多人协同与 8 h 工作日历。其次，提出 PBCH 以空闲工人优先规则快速构造可行调度，并为精确求解器提供热启动。再次，在单工位场景下构建 EIA，结合命题剪枝和割点工序变量固定缩小搜索树。最后，在多工位场景下提出 PDA，借助作业同质性与工位同质性构造规范模式、计算上下界并结合 CP 精确求解模式子问题。实验实例为作者基于真实项目特征生成的基准算例，而非外部生物或临床样本队列。
在研究结果部分，论文按模块逐步展示了方法性能与理论效果。
在“3. A Priority-Rule-Based Constructive Heuristic”部分，研究人员提出 PBCH，并论证其在整体框架中的三重作用：可独立快速求解一般实例、可为 MIP/CP 提供紧上界与热启动、也可为 PDA 提供模式上界。该方法通过“作业释放”和“工序贪婪调度”两阶段迭代构造方案，在时间计算中显式处理资源同步、工作日历投影、协同加工时长计算以及跨周期中断完成时间。其意义在于为后续精确算法提供高质量起点。
在“3.2. Justification of the Priority Rule Design”部分，作者通过理论分析指出，相较于效率优先规则，空闲工人优先规则更适合多工位场景。原因在于，若贪婪地优先分配高效率工人，容易使其因跨工位转移或等待而形成局部瓶颈，而其他工人则被闲置；相反，空闲工人优先更能平衡整体负载、降低空间竞争。
在“4. An Exact Iterated Algorithm for the Single-Workstation Scenario”部分，研究人员给出了单工位精确迭代算法。首先，命题 1 证明在单工位情形下总存在最优的顺序调度，因此无需遍历全部作业排列；其次，命题 2 给出基于工作区间边界的提前终止剪枝规则，使得无需总是求到全部 n 个作业子集即可验证整体最优；再次，定义割点工序，并由命题 3 证明这类工序在单工位最优解中应尽早加工且采用最短处理时间的工人组合。由此，模型可以预先固定部分变量，显著减轻求解器负担。该部分说明，借助问题结构性质，单工位子问题可被高效精确求解，为多工位分解奠定基础。
在“5.1. Symmetry Analysis and Canonical Patterns”部分，作者分析了问题中的两类核心对称性：作业对称性和工位对称性。由于所有作业具有相同工序集、优先关系与处理要求，交换任意两个作业不会改变目标值；由于所有工位同构，仅工作负载排列不同的方案在本质上等价。基于此，研究人员定义了规范模式，即满足总作业数守恒、每个工位非空、并按非增序排列的作业数向量。该定义从根本上消除了工位置换冗余。
在“5.2. Search Space Reduction”部分，作者证明了原始分配空间规模为 k
n，而规范模式集合的规模仅等于整数 n 被拆分为 k 个正部分的划分数。以 6 个作业、3 个工位为例，原始空间为 3
6，而规范模式仅剩 3 种。该结果表明，问题复杂度的很大一部分源自对称冗余，而 PDA 恰恰通过模式化表示提取出真正有区别的结构决策。
在“5.3. Pattern Bound Estimation”部分，研究人员从两个视角构造模式下界。其一是劳动力资源视角下界，通过放松空间与优先约束，仅考虑总工时与工人总能力，并将连续工时投影到离散日历上得到下界；其二是工位分配视角下界，将规范模式中承担最多作业的首工位视为系统瓶颈，假定全体工人专注于该工位上相应数量作业的单工位松弛问题，并调用精确迭代算法求得最优值。最终取两类下界最大值作为模式稳健下界。与此同时，上界由 PBCH 在给定模式映射下生成。这一部分为后续全局剪枝提供了严格依据。
在“5.4. Global Bounds and Pruning Strategy”与“5.5. The Overall Decomposition Framework”部分，作者完整描述了 PDA。算法先生成全部规范模式，再按模式方差升序进行“平衡优先”搜索，因为负载较均衡的模式通常更可能产生更好完工期，从而更早收紧全局上界。对每个模式，若其下界不优于当前最优上界，则直接剪枝；否则先用 PBCH 获取可行解并热启动 CP，再在工位分配固定和全局界约束下精确求解子问题。命题 5 进一步证明 PDA 在有限步内收敛，且能保证全局最优与零最优性间隙。
在“6.3. Empirical Validation of the Heuristic Priority Rule”部分，实验比较了 PBCH 与效率优先变体 PBCH2。结果显示，在单工位场景下，由于不存在跨工位竞争，效率优先规则表现更好；但在多工位分布式环境中，PBCH 持续给出更紧的上界，验证了空闲工人优先规则对于缓解空间瓶颈的理论优势。
在“6.4. Results for Single-Workstation Scenarios”部分，研究人员系统比较了 PBCH、MIP、MIP-W、EIA-MIP、CP、CP-W 和 EIA-CP。结果表明，PBCH 可在 0.01 s 内快速产生可行解，但质量弱于精确算法；MIP 仅在小规模问题上可接受，规模增大后迅速失效；CP 在单工位场景表现出更好的鲁棒性与可扩展性；热启动对 MIP 至关重要，而对 CP 的边际提升较小；EIA 框架能显著增强基础求解器性能，其中 EIA-CP 综合鲁棒性、运行时间与最优性表现最佳。论文还通过提前终止统计证明，命题 2 的剪枝规则能避免大量大规模子问题求解。
在“6.5. Results for Multi-Workstation Scenarios”部分，作者比较了 PBCH、MIP、MIP-W、CP、CP-W 与 PDA。结果显示，标准 MIP 在 3600 s 内对所有测试实例均无法找到可行解；标准 CP 对小规模实例尚可，但随着作业数增加，最优性证明困难且相对间隙较大；MIP-W 虽可找到可行解，但间隙通常仍很高；CP-W 相比标准 CP 改进有限。相比之下，PDA 借助模式分解和 CP-W 子问题求解，稳定获得更高质量解并显著缩小间隙。对一个包含 6 个作业、6 名工人、2 个工位的示例，PDA 仅通过首先求解最平衡模式便得到全局紧上界，随后其余模式均因理论下界高于当前上界而被直接剪枝，展示出极高的搜索效率。
在“6.6. Scalability and Industrial Practical Relevance”部分，研究人员进一步测试了更大规模实例。结果表明，在 3600 s 限制下，PDA 对所有大实例都能找到可行解，平均最优性间隙保持在可接受范围内，并在部分情形下仍能证明全局最优。更重要的是，只要达到最优性，算法宏观上依旧仅评估 1.00 个模式，说明其对称性消解与界剪枝机制具有很强稳定性。结合目标制造场景约约 35 个作业的年产能设定，论文认为该算法的计算能力已能够覆盖实际工业排产粒度。补充实验还表明，即使将传统求解器时限延长到 7200 s，整体式方法仍难摆脱组合爆炸，而 PDA 依旧表现稳健，从而说明分解机制并非简单“延长时间”可以替代。
讨论部分强调，PDA 的有效性源于对问题结构的深入利用，而非单纯依赖通用求解器能力。通过预先在模式层面消除作业与工位对称性，再结合 CP 对时序子问题的高效表达能力，算法成功把原本难以处理的全局耦合问题转化为少量可管理子问题。实验结果不仅说明这种结构化分解显著提升了求解质量和收敛能力，也说明在多工位复杂制造系统中，基于问题结构设计精确算法具有明显优于整体式建模的应用潜力。不过，作者也明确指出该框架当前依赖“作业同质”假设来构造规范模式，因此在异构作业情形下，搜索空间压缩效果可能减弱；此外，当前模型采用确定性参数，尚未覆盖真实车间中的动态扰动。
研究结论部分可译为：本文研究了并行装配过程中一种人力资源分配问题，该问题具有多工位资源竞争、团队协作以及严格时间约束相互耦合的复杂调度特征。为克服整体式求解器面临的计算不可处理性，研究人员提出了一种模式分解算法（PDA）。该方法通过利用问题结构对称性，提供了一个无参数框架，能够有效地将全局资源分配与局部调度解耦。通过集成约束规划（CP）以高效求解子问题，并采用严格的界估计技术对搜索空间进行剪枝，PDA 在保证最优性的同时实现了计算效率最大化。大量计算实验表明，PDA 在解质量和收敛性方面均显著优于先进商业求解器（CPLEX 和 CP Optimizer），尤其适用于来源于真实复杂产品装配的大规模实例。尽管结果令人鼓舞，该研究仍存在一定局限。所提出的 PDA 依赖同构作业假设以构造规范模式并实现对称性破除；在涉及异构作业特征的实际情景中，搜索空间压缩效率可能下降。此外，当前数学模型基于确定性参数，可能尚不足以完整刻画真实车间中的动态扰动。未来研究将围绕这些局限展开，进一步将该框架扩展至随机环境，并考虑加工时间不确定性与设备故障等因素。
