用约束求解技术精准排班，零违规且兼顾多目标优化。
From Metaheuristics to Exact Methods: A CP-SAT Approach for Multi-Objective Healthcare Workforce Scheduling
- 基于约束规划建模，分时段分解调度以控休息时间
- 18组数据均零违规，最优解在80人规模下仍高效
- 适合医疗排班、复杂规则调度场景，可直接部署
医疗人力资源调度是需同时满足劳动法规、人力覆盖、员工偏好与成本目标的NP难问题。现有方法（遗传算法、整数规划、约束编程）仅建模6-12个层级约束，无法保证合规性，且缺乏对多角色、多技能异质性、强制休息中点控制、按病情权重的工时公平性、子时段粒度、跨周稳定性及跨午夜班次的支持。本文提出CP-SAT：一种针对多角色、多技能医疗排班的约束规划模型。该模型强制执行14条硬约束，确保零违规；通过统一加权惩罚函数优化15项软目标。创新包括：基于时段窗的分解实现休息中心化控制、按病情权重分配工时公平性、从15分钟至1天的多粒度调度、跨周稳定性保障，以及网格偏移预处理将跨午夜班次映射为单日调度而不修改求解器。在18个实例上评估：5个合成医院单元（10-33名护士）、10个INRC-II基准（5-80名护士，最长8周周期）、3个NRP-23兼容实例（10-25名护士，含跨午夜夜班）。结果：所有18个实例均无硬约束违反；证明了INRC-II n005w4的最优性（目标值118，间隙0.0%，耗时104秒）；可行解扩展至179,800变量和351,425约束（80名护士）；服务品质较MOGA提升50%-67%；模型规模近似线性增长，约每名员工4,400变量。该模型共执行29个约束（14个硬约束，15个软约束），接近行业平均的三倍。
原文摘要 · Abstract (English)
Healthcare workforce scheduling is an NP-hard optimization problem requiring simultaneous satisfaction of labor regulations, coverage requirements, employee preferences and cost objectives. Existing approaches (genetic algorithms, integer programming, constraint programming) model 6-12 constraints at shift-level granularity and cannot guarantee regulatory compliance. They also lack support for multi-role, multi-skill heterogeneity, mandatory break scheduling with midpoint control, acuity-weighted workload equity, sub-shift granularity, inter-week stability, and cross-midnight shifts. This paper presents CP-SAT: a Constraint Programming formulation for multi-role, multi-skill healthcare scheduling. CP-SAT enforces 14 hard constraints guaranteeing zero regulatory violations, while optimizing 15 soft objectives via a unified weighted penalty function. Contributions include a shift-window decomposition enabling break scheduling with centrality control, acuity-weighted workload equity, multi-granularity resolution from 15 minutes to 1 day, inter-week stability, and grid-offset preprocessing mapping cross-midnight shifts into a single scheduling day without solver changes. CP-SAT is evaluated on 18 instances: five synthetic hospital units (10-33 nurses), 10 INRC-II benchmarks (5-80 nurses, up to 8-week horizons) and 3 NRP-23 compatible instances (10-25 nurses) with cross-midnight Night shifts. Results: zero hard-constraint violations across all 18 instances by construction; proven optimality on INRC-II n005w4 (objective 118, gap 0.0%, 104s); feasible schedules scaling to 179,800 variables and 351,425 constraints (80 nurses); service quality improved 50-67% over MOGA; and model size scaling near-linearly at approximately 4,400 variables per employee. The formulation enforces 29 total constraints (14 hard, 15 soft), nearly three times the industry average.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。