CS Paper Radar

From Metaheuristics to Exact Methods: A CP-SAT Approach for Multi-Objective Healthcare Workforce Scheduling

Vipul Patel, Anirudh Deodhar, Dagnachew Birru

cs.AI math.OC ·submitted 2026-08-31 08:17 UTC · v1
published

Abstract

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.

Comment
13 pages, 10 tables. Accepted at MODeM Workshop, IJCAI-ECAI 2026. Extends arXiv:2607.05177

Closest papers

Nearest neighbours by meaning across the whole index.

Bi-Objective Receding-Horizon Scheduling of Nurses and Hospital Service Robots

eess.SY ·2026-10-25 ·Khatere Ghorbani-Moghadam, Roya Khalili-Amirabadi
published similarity 0.63
Abstract · Ghorbani-Moghadam, K., and Khalili-Amirabadi, R. (2026). Bi-objective receding-horizon scheduling of nurses and hospital service robots. Jou…

This paper studies the joint scheduling of nurses and hospital service robots as a bi-objective mixed-integer linear programming problem. The formulation represents heterogeneous nursing skills, alternative skill-coverage modes, nurse availability and temporal rules, workload balance, robot task capability, charging and battery dynamics, and human supervision. Robot workload relief is credited only when an eligible service is actually executed, and explicit supervision-load variables deduct the corresponding nurse capacity from clinical coverage. The receding-horizon formulation also includes a cross-window night--morning constraint and a terminal battery reserve. The computational study is presented as numerical verification on synthetic hospital-like instances rather than clinical validation. Under the proposed formulation, the eight-nurse reference case gives $Z_1=0.78$ and $Z_2=3.164$. A common-budget comparison on B20 seed~1 yields total shortage $53.70$ for the integrated model, compared with $58.03$ for sequential nurse--robot scheduling and $59.46$ for the nurse-only baseline. Additional experiments examine multiple epsilon budgets on a larger B30 instance, sensitivity to robot-relief/supervision parameters and objective weights, and one-day versus two-day rolling horizons against a static full-horizon reference. The battery and routing representations remain aggregate planning approximations, and the scalability evidence is interpreted accordingly. No patient records or real hospital staff data are used, so the results establish model behavior and comparative numerical evidence rather than practical clinical effectiveness.

0.30

Exact SAT and Constraint Programming for Job Shop Scheduling with Time-Varying Peak Power Constraints

cs.LO ·2026-08-26 ·Huy Tuan Nguyen, Duc Trung Kim Nguyen, Khanh To Van
benchmark similarity 0.61
Abstract

The Job Shop Scheduling Problem with Power Requirements (JSPPR) extends the classical job shop scheduling problem by imposing time-varying limits on instantaneous power consumption. Previous studies have used a mixed-integer linear programming formulation and the GRASP x ELS metaheuristic, but no SAT-based exact approach or constraint programming model has been reported. This paper develops the first exact SAT and constraint programming (CP) formulations for the JSPPR. On the 35 published benchmark instances, both SAT and CP prove global optimality for all instances and obtain identical optimal makespans, substantially improving upon the best previously reported results. They also establish four improved makespan values over the GRASP x ELS results reported in the original study. CP proves optimality faster than SAT, while both exact approaches substantially improve the optimality coverage of the MILP formulations, which prove optimality on only 6 and 10 instances using CPLEX and Gurobi, respectively. The certified optimal solutions also reveal inconsistencies in several previously reported benchmark results, including makespans below the proven optimum. We provide corrected optimal makespans and a complete set of certified optimal results for the JSPPR benchmark, establishing a reliable reference for future studies.

0.26

Minimizing the makespan in job shop scheduling under conflict graph constraints

cs.DM math.OC ·2026-09-03 ·Nour Elhouda Tellache, Abdenour Azerine
similarity 0.53
Abstract

We study the job shop scheduling problem with a conflict graph, in which adjacent jobs cannot be processed simultaneously on different machines, with the objective of minimizing the makespan. We establish a polynomial equivalence with a resource-constrained job shop problem having unit-capacity resources and binary resource requirements The problem is strongly NP-hard even on two machines with unit-time operations. For this setting, we derive an optimal-makespan formula and a linear-time algorithm when the conflict graph is a cluster graph, given the clique partition. We also develop a polynomial-time $4/3$-approximation algorithm for arbitrary conflict graphs on two machines when each job has exactly two unit-time operations. For the general problem, we propose four mixed-integer linear formulations, lower bounds, and a genetic algorithm with active, non-delay, and hybrid decoding procedures. Computational experiments on instances derived from the Lawrence and Taillard benchmarks and on randomly generated generalized job shop instances evaluate the proposed methods and show that the genetic algorithm generally improves on constructive heuristics.

0.33

Continuity-First Lexicographic Optimization for Home-Care Resource Allocation

cs.LO ·2026-09-14 ·Tuyen Van Kieu, Khanh Ngoc Do, Khanh Van To
benchmark similarity 0.51
Abstract · 5 pages, 2 figures, 2 tables. Submitted to ICIIT 2027

Home-care allocation must balance continuity of care, caregiver overtime, and caregiver-service compatibility. The published formulation of the Home-Care Optimal Resource Allocation Problem (HCORAP) uses a weighted policy (Weighted) to combine these outcomes, allowing compatibility gains to offset poorer continuity or additional overtime. We introduce LEX-COS, a lexicographic objective for HCORAP that first minimizes continuity violations, then overtime, and finally maximizes compatibility. We give an exact MaxSAT implementation and construct HCORAP-LC, a reproducible 48-instance synthetic evaluation suite with limited caregiver capacity. Compared with Weighted, LEX-COS reduces both continuity violations and overtime in 42 of 48 instances, without increasing either measure in any instance, while yielding lower compatibility. In 36 instances, LEX-COS achieves better continuity and lower overtime than every Weighted-optimal allocation. On the separate 48-instance Original benchmark, Gurobi and CPLEX, two leading commercial MIP solvers, resolve every instance under both policies and are substantially faster than EvalMaxSAT. EvalMaxSAT also resolves the full benchmark under LEX-COS. Within EvalMaxSAT, replacing sorting networks with Totalizer improves runtime under Weighted, with no clear gain under LEX-COS. These results characterize the effects of giving continuity and overtime explicit priority in home-care allocation.

0.30

Surrogate-Assisted Genetic Programming with Phenotypic Characterisation in Dynamic Multi-Mode Project Scheduling

cs.NE cs.AI ·2026-09-13 ·Yuan Tian, Yi Mei, Mengjie Zhang
similarity 0.51
Abstract · 15 pages, 18 figures, 7 tables

Dynamic multi-mode resource-constrained project scheduling requires decisions to be made under precedence constraints, limited resources, multiple execution modes, and uncertain activity durations. Genetic programming (GP) can automatically evolve heuristic rules for such problems, but its simulation-based fitness evaluation is computationally expensive. This study investigates phenotypic characterisation (PC) in surrogate-assisted GP to evolve higher-quality scheduling heuristics under a fixed budget of full simulation-based fitness evaluations. A key question is how GP individuals should be encoded into phenotypic characterisations to support effective fitness estimation. To answer this question, three PC encoding schemes with different levels of information richness are designed: priority-value encoding, which preserves raw rule outputs; rank encoding, which captures candidate ordering; and binary encoding, which represents final scheduling decisions. These encodings are combined with different distance metrics to measure behavioural similarity between GP individuals. The experimental results show that binary encoding with Euclidean distance provides the most effective and robust surrogate guidance. Further analyses show that surrogate estimation accuracy alone does not fully explain the performance differences. The PC representation also determines how effectively phenotypically redundant offspring are removed and how much behavioural diversity is retained after preselection. Ablation experiments further demonstrate that duplicate removal and surrogate preselection provide complementary benefits, with their combination producing the largest improvement. These findings highlight that effective surrogate-assisted GP depends not only on identifying promising offspring, but also on controlling redundancy and preserving useful diversity during evolutionary search.

0.27

Solving Distributed Flexible Job Shop Scheduling Problem Using SAT

cs.LO ·2026-10-10 ·Phuong Dang Anh, Duc Nguyen Kim Trung, To Van Khanh
benchmark similarity 0.51
Abstract

The Distributed Flexible Job Shop Scheduling Problem (DFJSP) requires the joint determination of factory assignment, machine selection, and operation sequencing to minimize the makespan. This paper presents an exact SAT-based approach built on an efficient SAT formulation that exploits problem structure through propagation, symmetry breaking, and incremental SAT solving to effectively address these coupled decisions. The proposed method is evaluated on 76 standard benchmark instances from the Fattahi, Brandimarte, and rdata datasets under two- and three-factory configurations. Together with previously established results, the new SAT optimality certificates bring the total number of proven-optimal instances to 72 out of 76, including three newly certified instances; for two of these instances, SAT also improves the previous best-known makespans. Across the benchmark configurations, SAT achieves the best results on four of the five configurations and remains competitive with strong exact approaches such as CP and LBBD1_CPIL, as well as existing metaheuristic methods. These results demonstrate that the proposed SAT framework is an effective exact approach for the DFJSP, combining strong solution quality with rigorous optimality certification and offering a complementary exact method for future DFJSP studies and evaluations on additional benchmark instances.

0.13

APEX: An Extensible Model for Agent-Assisted Production Scheduling

cs.AI cs.NE ·2026-09-27 ·Felix J. Grumbach, Stefan Görlitz
benchmark similarity 0.51
Abstract

Production scheduling requires realistic models that reflect operational constraints and efficient methods that balance competing goals. Putting these methods into use also requires data integration, model adaptation and specialist expertise. We present APEX, an extensible production scheduling framework built around a general model and hybrid multiobjective search. Agent assistance supports both scheduling and model refinement: agents prepare data and explore scenarios in natural language, while coding agents help implement and test new constraints and objectives. Shared construction and checking procedures connect these adaptations to the scheduling core. We benchmark eight APEX configurations against NSGA-II, SPEA2, MOEA/D and SMS-EMOA on 69 public job-shop, flexible job-shop and permutation flow-shop instances, assessing workload completion time (makespan), total job flowtime and computation time. Hybrid configurations achieve the best aggregate solution quality, although the leading method depends on the problem class and objective. A separate synthetic workflow study uses OpenAI's GPT-6-astra as an interaction layer between the human planner and the algorithmic core, testing rule additions, plan and objective changes, and what-if comparisons. All 24 sessions completed the requested changes and passed independent checks of saved models and schedules. A separate coding evaluation produced six native implementations of an additional objective or hard constraint through predefined extension hooks. All passed independent checks without modifying the core.

0.20

Compact MaxSAT Encodings for Balanced Waiting in B2B Meeting Scheduling

cs.LO ·2026-11-19 ·Tuyen Van Kieu, Long Duc Nguyen, Minh Duc Dang Vu, Khanh Van To
theoryunusual similarity 0.51
Abstract · 29 pages, 5 figures, 14 tables. Submitted to the Journal of Artificial Intelligence Research. Extends the RIVF 2026 conference paper availab…

Business-to-business (B2B) meeting schedules can leave participants with long and uneven waits. Earlier break-based B2B models count interruptions without measuring their duration. Our earlier work minimizes the range of participant idle totals, but a minimum range can still leave long waits. We study lexicographic optimization of idle range, maximum idle, and total idle, in that order. Waiting is measured in empty slots between a participant's first and last meetings. Balance compares idle totals among participants requesting at least two meetings. Using weighted maximum satisfiability (MaxSAT), we prove preservation of feasible schedules, objective costs, and priorities. Compact-Base retains our earlier feasibility encoding; Compact-Objective adds objective-specific representations. We compare both with Direct, an independent implementation based on the 2022 MaxSAT model. Encoding comparisons use three repetitions per encoding-objective-instance combination on 226 variants of 20 base instances. Schedule-quality comparisons use break, range, and lexicographic objectives with the same encoding and feasible set. Across nine objective-dataset comparisons, Compact-Objective had the lowest median clause count and lower median peak memory than Direct. Runtime rankings changed in comparisons with the same solver build and computing environment. On 84 instances solved optimally under all three quality objectives, selected lexicographic schedules preserved the optimal idle range. Compared with selected range-only schedules, maximum idle decreased on 11 instances and total idle on 56. On 68 instances also solved optimally under range-then-total optimization, the selected schedules matched the three-tier criterion values. Compact-Base supplied the larger clause reduction relative to Direct; Compact-Objective reduced clauses further.

0.38