From Metaheuristics to Exact Methods: A CP-SAT Approach for Multi-Objective Healthcare Workforce Scheduling
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Comparative Analysis of Evolutionary Algorithms for Energy-Aware Production Scheduling
The energy transition is driving rapid growth in renewable energy generation, creating the need to balance energy supply and demand with energy price awareness. One such approach for manufacturers to balance their energy…
Evolutionary AlgorithmsSchedulingAn Ontology of Preference-Based Multiobjective Metaheuristics
User preference integration is of great importance in multi-objective optimization, in particular in many objective optimization. Preferences have long been considered in traditional multicriteria decision making (MCDM) …
Decision MakingImproved Quick Hypervolume Algorithm
In this paper, we present a significant improvement of Quick Hypervolume algorithm, one of the state-of-the-art algorithms for calculating exact hypervolume of the space dominated by a set of d-dimensional points. This v…
Evolutionary AlgorithmsImpact of diversity on bounded archives for multi-objective local search
This work tackles two critical challenges related to the development of metaheuristics for Multi-Objective Optimization Problems (MOOPs): the exponential growth of non-dominated solutions and the tendency of metaheuristi…
Biclustering Algorithms Based on Metaheuristics: A Review
Biclustering is an unsupervised machine learning technique that simultaneously clusters rows and columns in a data matrix. Biclustering has emerged as an important approach and plays an essential role in various applicat…
Survey