{
  "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.",
  "abstract_shown": true,
  "affiliations": [],
  "article_type": null,
  "arxiv": "2608.30419",
  "author_total": 3,
  "authors": [
    {
      "name": "Vipul Patel"
    },
    {
      "name": "Anirudh Deodhar"
    },
    {
      "name": "Dagnachew Birru"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/9hxhqvdvhqwkx.bib",
  "cited_by": 0,
  "doi": "10.48550/arxiv.2608.30419",
  "fulltext_url": null,
  "id": "9hxhqvdvhqwkx",
  "issns": [],
  "landing_url": "https://arxiv.org/abs/2608.30419",
  "language": null,
  "licence": "CC-BY-NC-ND-4.0",
  "licence_label": "CC BY-NC-ND 4.0",
  "licence_source": "article",
  "licence_url": "http://creativecommons.org/licenses/by-nc-nd/4.0/",
  "metadata_licence": "CC0-1.0",
  "native_subjects": [
    [
      "arxiv",
      "cs.AI"
    ],
    [
      "arxiv",
      "math.OC"
    ],
    [
      "openalex",
      "1803|Scheduling and Timetabling Solutions"
    ]
  ],
  "openalex": "W7204888226",
  "pdf_url": "https://arxiv.org/pdf/2608.30419",
  "pmcid": null,
  "pmid": null,
  "published": "2026-08-31",
  "publisher": null,
  "ris": "https://research.draconitic.com/paper/9hxhqvdvhqwkx.ris",
  "sources": [
    {
      "first_seen": "2026-10-30T12:18:04Z",
      "native_id": "2608.30419",
      "source": "arxiv",
      "url": "https://arxiv.org/abs/2608.30419"
    }
  ],
  "subjects": [
    {
      "field": "mathematics",
      "origin": "arxiv:math.OC",
      "subfield": "optimisation-control"
    }
  ],
  "title": "From Metaheuristics to Exact Methods: A CP-SAT Approach for Multi-Objective Healthcare Workforce Scheduling",
  "title_text": "From Metaheuristics to Exact Methods: A CP-SAT Approach for Multi-Objective Healthcare Workforce Scheduling",
  "type": "preprint",
  "updated_at": "2026-10-30T12:18:04Z",
  "url": "https://research.draconitic.com/paper/9hxhqvdvhqwkx",
  "venue": "arXiv",
  "versions": []
}