Skip to content

Rota Algorithm Technical Reference

Overview

The rota generator produces medical staff rotas for primary care practices. It allocates clinician shifts across working days (Monday-Friday, excluding bank holidays) while respecting contractual obligations, leave, and staffing minimums.

The generator uses a six-phase pipeline that progresses from fully determined shifts (fixed working days, must-work commitments) through to optimised discretionary allocation. The core innovation is the deficit-based allocation algorithm (Phase 3), which ensures balanced shift distribution by repeatedly directing new shifts to the days and clinicians most in need. Phase 5 then uses Google's CP-SAT constraint solver to refine the rota globally across multiple competing objectives.

Design principles:

  • Deterministic: the same inputs produce the same rota (Phases 1-4, 6; Phase 5 is also deterministic with the same solver seed).
  • Incremental: each phase builds on the outputs of prior phases.
  • Respects hard constraints: leave, cannot-work days, and pinned shifts are never violated.
  • Fair: allocation is proportional to WTE (whole-time equivalent) percentage.

Generation Pipeline

flowchart TD
    START([Start: date range + clinicians]) --> P1

    P1["Phase 1<br/>Fixed Shifts<br/><i>rota_generation/phases/phase1_fixed_shifts.py</i>"]
    P1 --> P2

    P2["Phase 2<br/>Alternate Week Patterns<br/><i>rota_generation/phases/phase2_alternate_weeks.py</i>"]
    P2 --> P3

    P3["Phase 3<br/>Deficit-Based Fill<br/><i>rota_generation/phases/phase3_deficit_filling.py</i>"]
    P3 --> P4

    P4["Phase 4<br/>Partner Minimum Shifts<br/><i>rota_generation/phases/phase4_minimum_shifts.py</i>"]
    P4 --> P5

    P5["Phase 5<br/>CP-SAT WTE Optimisation<br/><i>rota_generation/optimization/engine.py</i>"]
    P5 --> P6

    P6["Phase 6<br/>Duty Doctor Assignment<br/><i>rota_generation/phases/phase6_duty_doctors.py</i>"]
    P6 --> DONE([Rota complete])

    style P1 fill:#e8f5e9
    style P2 fill:#e3f2fd
    style P3 fill:#fff3e0
    style P4 fill:#fce4ec
    style P5 fill:#f3e5f5
    style P6 fill:#e0f7fa

Each phase creates shifts in the database. Later phases can see shifts created by earlier phases and take them into account.

Phase Details

Phase 1: Fixed Shifts

Source: rota_generation/phases/phase1_fixed_shifts.py

Purpose: Assign non-negotiable shifts that are contractually required -- salaried fixed working days, partner must-work days, and locum bookings.

What it allocates:

Shift type Trigger Notes
Salaried working days WorkingTerm.fixed_working_days matching the day of week STANDARD, FULL duration
Partner must-work days WorkingTerm.must_work_days matching the day of week STANDARD, FULL duration
Locum bookings LocumBooking records with dates in the range STANDARD, FULL duration

Key constraints:

  • Skips bank holidays.
  • Skips dates where the clinician has approved leave.
  • Skips dates where a shift already exists (prevents duplicates).
  • Processes each clinician's working terms independently; ongoing terms (no end date) are clamped to the generation date range.

Edge cases:

  • A clinician may have both a LOCUM term and separate locum bookings; both are combined to find all booked dates.
  • Locum bookings store dates as string lists (booking.dates) rather than date ranges; each string is parsed individually.

Phase 2: Alternate Week Patterns

Source: rota_generation/phases/phase2_alternate_weeks.py

Purpose: Apply Week A / Week B alternating patterns for clinicians who do not work the same days every week (typically salaried doctors on flexible contracts).

What it allocates:

  • STANDARD, FULL shifts on the days specified by the pattern for the appropriate week.
  • All created shifts have is_pinned=True -- they survive regeneration.

Key constraints:

  • Start date is adjusted to the first full Monday on or after the requested start date. If the start date is midweek, shifts begin the following Monday.
  • Bank holidays are skipped.
  • Approved leave and active sick leave are skipped.
  • Existing SCHEDULED shifts are not overwritten (prevents double-booking).

Edge cases:

  • If the adjusted start date falls after the end date, no shifts are created.
  • The pattern alternates indefinitely: week 0 = Week A, week 1 = Week B, week 2 = Week A, etc.

Phase 3: Deficit-Based Fill

Source: rota_generation/phases/phase3_deficit_filling.py

Purpose: Fill staffing gaps by allocating partner shifts to days below minimum staffing, prioritising days with the largest deficit and clinicians furthest from their WTE target.

This is the core allocation phase. See Deficit-Based Allocation for a detailed explanation.

What it allocates: STANDARD shifts for partner clinicians.

Key constraints:

  • Only partners with active working terms are candidates.
  • Candidates must not be on leave for the target date.
  • Candidates must not already have a shift on the target date.
  • Candidates must not have reached their max_shifts_per_week limit.
  • Partners: cannot work on days listed in their cannot_work_days.
  • Salaried doctors: can only work on their fixed_working_days (if included in the clinician list).

Parameters:

Parameter Effect
mondays_only Only generate Monday shifts. Used by callers to prioritise Monday staffing without over-allocating.
skip_mondays Generate shifts only for Tuesday-Friday. Mutually exclusive with mondays_only.

Edge cases:

  • Reporting period is aligned to full weeks (Monday-Friday boundaries).
  • When no candidates have positive deficiency (all are at or above target), the phase can still allocate to meet minimum staffing unless mondays_only is set.
  • Completion percentage is used for tie-breaking rather than raw deficiency, which ensures part-time clinicians are treated fairly relative to their individual targets.

Phase 4: Partner Minimum Shifts

Source: rota_generation/phases/phase4_minimum_shifts.py

Purpose: Ensure each partner meets their contractual weekly minimum shift count (WorkingTerm.minimum_shifts_per_week).

What it allocates: Additional STANDARD shifts for partners who are below their weekly minimum.

Algorithm:

  1. Iterate week by week through the date range.
  2. For each clinician, count existing STANDARD and DUTY shifts in the week.
  3. If the count is below minimum_shifts_per_week, calculate additional shifts needed.
  4. Sort days in the week by staffing deficit (highest first).
  5. Allocate shifts on deficit days, respecting leave, cannot-work days, and existing shifts.

Key constraints:

  • Skips clinicians with minimum_shifts_per_week = None (no minimum requirement).
  • Respects cannot_work_days from the working term.
  • Respects approved leave.
  • Does not create duplicate shifts on days where the clinician already has one.

Phase 5: CP-SAT WTE Optimisation

Source: rota_generation/optimization/engine.py and supporting modules.

Purpose: Globally optimise the distribution of partner STANDARD shifts across the date range to satisfy multiple competing fairness and staffing objectives.

See CP-SAT Optimisation for full details.

What it adjusts: Only unpinned partner STANDARD shifts are decision variables. The solver can create new shifts or delete existing ones. Salaried shifts, locum shifts, pinned shifts, and DUTY shifts are fixed.

Phase 6: Duty Doctor Assignment

Source: rota_generation/phases/phase6_duty_doctors.py

Purpose: Assign duty doctor responsibilities to clinicians already working on each day.

What it allocates: Converts existing STANDARD shifts to DUTY shifts (does not create new shifts from scratch).

Algorithm:

  1. Determine duty doctor requirement per day (from SystemConfiguration).
  2. Post-bank-holiday days require additional duty doctors (configurable: duty_doctors_post_bank_holiday).
  3. Salaried doctors are prioritised: a salaried clinician already working a STANDARD shift on the target day has that shift converted to DUTY.
  4. Salaried constraints: only one duty per week, no consecutive weeks of duty.
  5. Partners fill remaining slots: partners already working a STANDARD shift are selected based on WTE-adjusted duty count (lowest count first).
  6. When insufficient clinicians are available, an alert is created via AlertService.

Key constraints:

Constraint Applies to Description
One duty per week Salaried Cannot do duty twice in the same week
No consecutive duty weeks Salaried Cannot do duty in two adjacent weeks
Duty from existing shift All Duty is assigned by converting an existing STANDARD shift
WTE-adjusted fairness Partners Duty count is uprated by 1/wte for comparison

Edge cases:

  • Working days within each week are shuffled randomly to avoid systematic bias in duty assignment order.
  • Clinicians with no working term overlapping the generation period are excluded.
  • Clinicians with a working term that does not encompass the reporting period are excluded.

Deficit-Based Allocation

Phase 3 uses a greedy deficit-based allocation algorithm. This is the core shift assignment mechanism.

How It Works

flowchart TD
    A[Calculate day deficits<br/>min_required - current_shifts] --> B[Calculate clinician deficits<br/>target_shifts - current_shifts]
    B --> C{Any day with<br/>deficit > 0?}
    C -- No --> DONE([Done])
    C -- Yes --> D[Pick day with<br/>highest deficit]
    D --> E[Build candidate pool<br/>for that day]
    E --> F{Any candidates with<br/>positive deficiency?}
    F -- Yes --> G[Sort by completion %<br/>lowest first]
    G --> H[Allocate shift to<br/>most behind clinician]
    F -- No --> I{Any available<br/>candidates?}
    I -- Yes --> J[Allocate to clinician<br/>with lowest completion %]
    I -- No --> K[Skip day<br/>no one available]
    H --> L[Update deficits]
    J --> L
    K --> M{More days<br/>with deficit?}
    L --> M
    M -- Yes --> D
    M -- No --> DONE

Day Deficit Calculation

For each working day in the date range:

day_deficit = minimum_doctors_for_this_day_of_week - current_shifts_counting_toward_minimum

Days are sorted by deficit in descending order. The day with the highest staffing gap is filled first.

Clinician Deficit Calculation

For each clinician in the reporting period:

wte = working_term.percentage / 100
target_shifts = target_for_full_fte * wte
current_shifts = existing_standard_and_duty_shifts + bank_holidays + leave_days
clinician_deficit = target_shifts - current_shifts

The target accounts for the clinician's FTE fraction. A 0.6 FTE clinician has a lower target than a 1.0 FTE clinician.

Candidate Selection

For the target day, a clinician is eligible when all of the following hold:

  • Has an active working term covering the date range.
  • Not on leave for the target date.
  • Does not already have a shift on the target date.
  • Has not reached max_shifts_per_week for the target week.
  • Can work on this day of week (partner: not in cannot_work_days; salaried: in fixed_working_days).

Allocation Order

Candidates are sorted by completion percentage (ascending):

completion_pct = total_shifts / target_shifts

The clinician with the lowest completion percentage (furthest from their individual target) is allocated first. This ensures part-time clinicians are not disadvantaged by using raw shift counts.

Recalculation

After each allocation, the day deficit is decremented by 1 and the clinician deficit is decremented by 1. This is an incremental update rather than a full recalculation, keeping the algorithm efficient.

CP-SAT Optimisation

Phase 5 uses Google OR-Tools' CP-SAT solver to globally optimise the rota. Unlike the greedy approach in Phase 3, the solver considers the entire date range simultaneously and can rearrange shifts to satisfy multiple competing objectives.

Architecture

flowchart LR
    A[Build Encoding] --> B[Build Model]
    B --> C[Solve]
    C --> D[Decode Solution]

    subgraph Encoding
        A1[Load existing shifts]
        A2[Identify decision variables<br/>unpinned partner STANDARD]
        A3[Collect constraints<br/>leave, cannot-work, pinned, duty]
        A4[Compute WTE targets<br/>available weeks, prior shifts]
    end

    subgraph Model
        B1[Create BoolVar matrix<br/>clinician x date]
        B2[Add hard constraints]
        B3[Build objective function]
        B4[Add solution hint<br/>warm start]
    end

    subgraph Solution
        D1[Create shifts where<br/>assign=1 and no existing]
        D2[Delete shifts where<br/>assign=0 and existing]
    end

Decision Variables

The solver operates on a boolean matrix:

assign[clinician_idx][date_idx] = {0, 1}

Where 1 means the clinician works a STANDARD shift on that date. Only partner clinicians are included in the matrix. Salaried and locum clinicians are accounted for as fixed coverage counts.

Dimensions:

  • n_clinicians: number of eligible partner clinicians.
  • n_dates: number of working dates (Mon-Fri excluding bank holidays).
  • Total variables: n_clinicians * n_dates.

Hard Constraints

Hard constraints are never violated. The solver will report INFEASIBLE if it cannot satisfy all of them simultaneously.

ID Constraint Description
H1 One shift per day Implicit: each variable is boolean, so a clinician can be assigned at most once per date.
H2 No work on leave assign[c][d] = 0 for all dates where clinician c has approved leave.
H3 No work on cannot-work days assign[c][d] = 0 for all dates matching a day-of-week in clinician's cannot_work_days.
H4 Pinned shifts preserved assign[c][d] = 1 for all pinned shift dates. The solver cannot remove these.
H4b DUTY shifts block STANDARD assign[c][d] = 0 for all dates where the clinician has a DUTY shift. The DUTY shift already provides coverage.
H5 Non-partner shifts fixed Salaried and locum shifts are not in the decision matrix; they are counted as fixed coverage.
H6 Bank holidays excluded Bank holidays are not included in the working_dates list, so no variables exist for them.
H7 Floor staffing per day For each day: total_shifts >= ceil(minimum * 0.66). Ensures staffing never falls below 66% of the required minimum.
H8 Max shifts per week For each clinician and week: STANDARD + DUTY shifts <= max_shifts_per_week.
H9 Min shifts per week For each clinician and week: STANDARD + DUTY shifts >= minimum_shifts_per_week (when enough assignable dates exist).

Pinned shift downgrading: If pinned shifts alone would exceed max_shifts_per_week for a clinician in any week, the excess pinned shifts are downgraded to regular (decision-variable) shifts. This prevents INFEASIBLE from the contradiction between H4 and H8. The latest dates in the week are downgraded first to preserve earlier commitments.

Pinned shift conflict handling: Pinned shifts that conflict with approved leave or cannot-work days are silently excluded from the pinned set and logged as warnings, rather than causing INFEASIBLE.

Objective Function (Soft Constraints)

The objective minimises a weighted sum of penalty terms. All terms use integer arithmetic (CP-SAT requirement).

ID Penalty Weight Description
S1 WTE fairness 0 (legacy) Sum of pairwise equivalency deviations across clinicians.
S2 Monday fairness 100 Exponential penalty on pairwise Monday-equivalency differences. Tolerates small gaps, heavily penalises large ones.
S3 Trainer requirement 100 Counts days where a required trainer (specific clinician or group member) is absent on their required day of week.
S4 Doctor affinity 20 For each affinity pair, counts days where exactly one of the pair works.
S5 Weekly evenness 50 For each clinician and week, penalises |weekly_count - target_per_week|. Smooths allocation across weeks.
S6 Day-of-week spread 0 Penalises variance in shift counts across different days of the week per clinician.
S7 WTE target deficit 1000 For each clinician, penalises |shifts_worked - target_shifts|, matching the Partner WTE Availability report's formula. Accounts for available weeks and bank holiday pro-rating.
S8 Moderate staffing 0 Counts staffing gaps in the 84-100% of minimum zone.
S9 Severe staffing 0 Counts staffing gaps in the 66-84% of minimum zone.
S10 Exponential fairness 0 (legacy) Base-2 exponential penalty on pairwise equivalency deviations. Prevents scapegoating.
S11 Report fairness 500 Primary objective. Minimises sum of |fair_difference| using a fixed target-based group rate that matches the Partner WTE Availability report. Uses WTE-adjusted available weeks.
S12 Exponential report fairness 100 Anti-scapegoating companion to S11. Applies piecewise-linear base-2 exponential penalty to individual clinician deviations from their fair share.
S13 Progressive overstaffing 3 For each day above minimum staffing, the k-th extra doctor costs k. 3 extra on one day costs 6; 1 extra on three days costs 3.

Exponential penalty mechanism (S10, S12): Uses piecewise-linear approximation of a base-2 exponential. The deviation range is divided into buckets, and bucket k has marginal cost 2^k. A single clinician 7 shifts above average costs 2^0 + ... + 2^6 = 127, while seven clinicians each 1 shift above costs only 7 * 2^0 = 7.

Fixed target (S11, S12): The group rate is computed from WTE target shifts, not actual shifts. This prevents the optimizer from reducing total shifts to shrink everyone's fair share -- a perverse incentive that would give fewer shifts overall.

Solver Configuration

Parameter Default Description
time_limit_seconds 60 Maximum wall-clock time for the solver.
num_workers 0 (auto) Number of parallel worker threads.

Solution hint: The existing rota is provided as a warm start. Each decision variable is set to its current value (1 if a shift exists, 0 otherwise). This speeds up convergence.

Encoding Details

The encoding layer (rota_generation/optimization/encoding.py) bridges Django models and CP-SAT variables:

Prior shifts: When the reporting period starts before the generation range, shifts from the prior (context) period are counted per clinician. These give each clinician a "starting balance" so the optimizer can compensate for over- or under-allocation in the prior period.

Available weeks: Weeks where a clinician has any approved annual leave are excluded from their available-week count, matching the Partner WTE Availability report.

WTE-weeks: wte_percentage * available_weeks, stored as an integer (e.g., 80% * 18 weeks = 1440).

Fixed report shifts: Non-optimizer contributions to the WTE report (bank holiday pro-rating, DUTY shifts on bank holidays), stored as tenths of a shift.

Solution Decoding

After solving, the decision matrix is decoded back to database shifts:

  • assign = 1 and no existing shift: create a new STANDARD shift.
  • assign = 0 and existing unpinned shift: delete the shift.
  • Pinned shifts and non-partner shifts are never modified.

Concurrent Task Protection

Source: rota_generation/models.py (RotaGenerationTask)

The RotaGenerationTask model provides application-level locking to prevent concurrent rota generation for the same date range and phase.

How it works:

  1. Before starting a phase, check get_active_task(start_date, end_date, phase) for any task in PENDING or RUNNING status.
  2. If an active task exists, the new request is rejected.
  3. Otherwise, create a new task record via create_task().
  4. The task transitions: PENDING -> RUNNING -> COMPLETED (or FAILED).
  5. Timestamps (started_at, completed_at) and metrics (shifts_created, shifts_deleted) are recorded.

Database indexes support efficient queries on (start_date, end_date, phase, status) and (status, created_at).

Shift Pinning

Pinned shifts (is_pinned=True) are immutable allocations that survive regeneration. The pinning mechanism operates at multiple points:

Creation:

  • Phase 2 (alternate week patterns) creates all its shifts as pinned.
  • Manual pinning via the admin interface sets is_pinned=True on existing shifts.

Protection during regeneration:

  • When confirm_overwrite=True, only unpinned shifts are deleted before regenerating.
  • Phase 5 (CP-SAT): pinned shifts are forced to assign=1 via hard constraint H4. The solver cannot remove them.
  • Pinned shifts that conflict with leave or cannot-work constraints are excluded from the H4 constraint (logged as warnings) to prevent INFEASIBLE.

Downgrading: If pinned shifts exceed a clinician's max_shifts_per_week, the excess (latest dates in the week) are automatically downgraded to decision variables. This resolves the conflict between the "must keep" (H4) and "weekly maximum" (H8) hard constraints.

Rebalancing

Source: rebalancing/rebalancing_service.py

The RebalancingService is designed to recalculate the rota after changes (leave requests, term changes) while respecting a fixed period (a configurable number of weeks from the current date during which shifts cannot be moved).

Current status: DEPRECATED. The service depends on the old RotaGenerator class and has been replaced conceptually by the phase-based system. It is retained as a reference for the intended rebalancing workflow:

  1. Validate that the requested date range starts after the fixed period.
  2. Capture clinician states before rebalancing (shift counts, deficiencies, targets).
  3. Delete all unpinned shifts in the range.
  4. Re-run rota generation phases for the affected range.
  5. Capture after-states and generate a comparison report.

Fixed period: current_date + (fixed_period_weeks * 7) days. Configured via SystemConfiguration.

Comparison report: For each clinician, reports the change in shift count and deficiency between the before and after states.