Shift Plan Solver

Scheduling 15+ employees across 5 daily shift slots for a full month is NP-hard. This solver does it in under 2 minutes.

Built with Google OR-Tools' CP-SAT solver, this project tackles a real workforce scheduling problem: assigning day, night, on-call, and ambulance shifts while respecting rest rules, fairness constraints, personal preferences, and weekend duties.

The Problem

A healthcare facility needs to fill 5 shift slots every day of the month:

Code	Type	Description
DS	Day Shift	On-premise day shift
DC	Day Call	On-call day shift
AMB	Ambulance	Ambulance on-call (day only)
NS	Night Shift	On-premise night shift
NC	Night Call	On-call night shift

With each employee having different capabilities, target hours, and personal constraints, the solution space is enormous. Brute force won't work — constraint programming will.

How It Works

roster.csv + preferences.yaml + Schedule.xlsx
                    │
                    ▼
            ┌───────────────┐
            │  Config Loader │──→ ScheduleConfig
            └───────────────┘
                    │
                    ▼
            ┌───────────────┐
            │  Excel Reader  │──→ Pre-filled schedule
            └───────────────┘         (vacations, duty weekends,
                    │                  locked shifts)
                    ▼
            ┌───────────────┐
            │   CP-SAT      │──→ Optimal assignment
            │   Solver       │    (or best feasible)
            └───────────────┘
                    │
                    ▼
            ┌───────────────┐
            │  Validator     │──→ Report + violations
            └───────────────┘
                    │
                    ▼
            ┌───────────────┐
            │  Excel Writer  │──→ Solved schedule
            └───────────────┘

Hard Constraints (must be satisfied)

Constraint	Description
One person per slot	Each of the 5 daily slots has exactly 1 assignee
Vacation blocking	Days marked X are completely blocked
Free weekends	Weekend days without D (duty) marker are blocked
Duty weekend minimum	Each D weekend pair (Sa+So) requires at least 1 shift
12-hour rest	No day shift after night shift (or vice versa)
Max 3 consecutive days	No more than 3 working days in a row
Max 4 per 7-day window	Rolling weekly shift cap
Shift restrictions	Per-employee allowed shift types (day-only, night-only)
Max day shifts	Per-employee monthly cap on DS/DC assignments
On-premise/on-call balance	50/50 split (±1) between on-premise and on-call
Separation pairs	Specific employee pairs never share a time window
Monthly constraints	Ad-hoc blocked shifts for specific dates

Soft Preferences (optimized via objective function)

Preference	Weight	Effect
Slot coverage	20	Fill every slot (highest priority)
3-day block penalty	12	Prefer 2-day blocks over 3-day streaks
Target shifts	10	Stay within each person's min/max range
On-premise/on-call alternation	8	Alternate DS↔DC and NS↔NC between consecutive days
Companion balancing	5	Distribute junior night companion load evenly
Even distribution	3	Spread shifts across the month (minimize weekly variance)
Personal preferences	configurable	Day preferences, avoidances, shift affinities

All weights are configurable via preferences.yaml.

Quick Start

git clone https://github.com/matoautomato/shift-plan-solver.git
cd shift-plan-solver
python3 -m venv .venv && source .venv/bin/activate
pip install -e ".[dev]"

# Solve the example schedule
shift-planner solve data/example/Schedule_Example.xlsx --dry-run

# Generate an empty template for a new month
shift-planner template 4 2026

# Run tests
pytest

Configuration

roster.csv — Employee Database

name,target_shifts_min,target_shifts_max,target_amb,allowed_shifts,max_day_shifts,has_preferred_schedule,weekend_group
Lena M.,12,12,2,DS;DC;AMB;NS;NC,,false,A
Carla F.,8,10,1,DS;DC;AMB,2,false,A
Stefan W.,10,10,0,NS;NC,,false,B

Column	Description
target_shifts_min/max	Acceptable shift count range
target_amb	Target ambulance (AMB) shifts per month
allowed_shifts	Semicolon-separated shift types this person can work
max_day_shifts	Monthly cap on DS/DC (empty = unlimited)
has_preferred_schedule	If true, locked shifts from Excel are preserved and rolling-window constraint is relaxed
weekend_group	A or B — for weekend rotation

preferences.yaml — Scheduling Rules

weights:
  coverage: 20
  target: 10
  balance: 8
  spread: 3
  block3: 12
  companion: 5

separation_pairs:
  - ["Lena M.", "Hanna B."]

preferences:
  Jonas K.:
    prefer_shifts_on:
      thursday: [DS, DC]
    weight: 2
  Maria R.:
    avoid:
      wednesday: [NS, NC]
      thursday: [DS, DC]
    weight: 2
  Finn D.:
    affinity: [NS, NC, weekend]
    weight: 3

companion_balancing:
  senior: "Lena M."
  juniors: ["Jonas K.", "Finn D.", "Eva R."]
  weight: 4

Data Directory Resolution

The solver looks for roster.csv and preferences.yaml in this order:

1. --data <dir> CLI flag
2. SHIFT_PLANNER_DATA environment variable
3. data/example/ (default — ships with fictional data)

This means you can keep real production data in a separate directory (e.g., data/production/, which is gitignored) and point to it at runtime.

Tech Stack

Component	Why
Python 3.11+	For constraint modeling
Google OR-Tools CP-SAT	Constraint solver, handles the combinatorial explosion
openpyxl	Excel read/write — the input/output format the facility uses
PyYAML	Human-friendly config format for preferences

License

MIT