OptiSchedule

OptiSchedule is a Python workforce scheduling engine with Google OR-Tools CP-SAT and a deterministic greedy baseline. It assigns employees to dated shifts subject to staffing, availability, working-time and skill requirements, while balancing employee preferences and workload. This project focuses on an explicit mathematical formulation, strict input validation and independently checked solutions.

Installation

Python 3.13 and OR-Tools 9.15 are the target environment. From the repository root:

python -m venv .venv
.\.venv\Scripts\Activate.ps1
python -m pip install -r requirements.txt

On macOS/Linux, activate with source .venv/bin/activate instead. OR-Tools is the engine's only third-party runtime dependency; pytest is used for tests. No web server, database or frontend is required.

Usage

python main.py
python main.py data/example.json
python main.py data/example.json --algorithm greedy
python main.py data/example.json --preference-weight 2 --fairness-weight 3 --time-limit 10
python -m pytest -q

The default JSON path is resolved relative to main.py, so the default command also works when launched from another directory. Explicit relative input paths are resolved from the current directory. CLI settings override the JSON config.

The CLI prints solver status, measured solver wall time, objective value, preference score, fairness, a schedule grouped by date and employee hours. It exits with code 0 when a solution exists, 1 when none is available, and 2 on invalid input or file errors. Importing main.py does not run the solver.

Continuous integration

The test workflow runs on every push and pull request with Python 3.13 on Ubuntu and Windows. Each job installs benchmarks/requirements.txt, which includes the main dependencies and Matplotlib, checks dependency compatibility, and runs the full pytest suite. This includes the CLI subprocess tests, small benchmark integration cases and plot generation; the recorded performance experiment is not rerun by CI.

Run the same checks locally from the repository root, with the virtual environment activated:

python -m pip install -r benchmarks/requirements.txt
python -m pip check
python -m pytest -q

Each CI job has a ten-minute timeout. Both operating systems report their results even if one fails, and a newer push cancels an older run for the same branch or pull request. The workflow uses read-only repository permissions.

Structure

src/scheduler/
    __init__.py     Public API
    models.py       Employee, Shift, Availability, SchedulingProblem, SolverConfig
    validation.py   Domain validation and interval operations
    loading.py      Strict JSON parsing
    engine.py       Decision variables, constraints and objective
    solver.py       Common strategy dispatcher (CP-SAT by default)
    solvers/
        cp_sat.py   CP-SAT execution
        greedy.py   Deterministic greedy construction, no OR-Tools dependency
    metrics.py      Shared hard-constraint audit and metric calculations
    result.py       Structured results and statuses
data/example.json   Seven employees, three dates, nine overlapping shifts
data/greedy_trap.json A small feasible instance that defeats greedy
benchmarks/         Seeded generator, bounded runner, CSV analysis and plots
results/            Raw runs, metadata, instance/solution snapshots and figures
tests/              Constraint, objective, validation, integration and CLI tests
main.py             Command-line entry point
pytest.ini          Test discovery and src import path
requirements.txt    OR-Tools and pytest

The old root-level models.py and scheduler.py are replaced by the package. The former shift-name-based API is intentionally replaced by typed domain objects and explicit IDs. The checkout's main.py and pytest configuration handle the src import path; no packaging/build dependency is needed for this sprint.

Input contract

The JSON object has employees, shifts and an optional config:

{
  "employees": [{
    "id": "alice",
    "name": "Alice",
    "availability": [{
      "date": "2026-09-07", "start_time": "08:00", "end_time": "16:00"
    }],
    "min_hours": 0,
    "max_hours": 8,
    "skills": ["backend"],
    "preferences": {"mon-am": 10}
  }],
  "shifts": [{
    "id": "mon-am",
    "name": "Morning engineering",
    "date": "2026-09-07",
    "start_time": "08:00",
    "end_time": "12:00",
    "required_workers": 1,
    "required_skills": {"backend": 1}
  }],
  "config": {
    "preference_weight": 1,
    "fairness_weight": 1,
    "time_limit_seconds": 30,
    "num_workers": 1,
    "random_seed": 0
  }
}

• IDs are nonempty strings, unique within employees or shifts. Names need not be unique. Preferences reference shift IDs; absent scores mean 0 and negative integer scores express undesirable assignments. Scores need not be provided for every shift.
• Dates use YYYY-MM-DD; times use local HH:MM, with minute precision. Every interval is within a single date and must have end_time > start_time. Availability is the union of an employee's intervals on that date. Adjacent or overlapping windows are accepted; even a one-minute gap prevents assignment. An empty availability list means unavailable everywhere.
• max_hours is required in JSON. min_hours defaults to 0; skills, preferences and required_skills default to empty collections. Min/max hours apply to the entire input horizon, not separately per day/week. Fractional hours must convert exactly to whole minutes (e.g. 1.25 = 75 minutes).
• required_workers and each skill quota must be positive integers. Every skill quota must be at most the required headcount. Skill names are case-sensitive labels, not references to a separate registry. A skill absent from the workforce is valid input that makes the relevant staffing requirement infeasible.
• At least one employee is required. An empty shift list is valid, but positive minimum-hour obligations then make the instance infeasible.
• Unknown fields, duplicate JSON keys/IDs/skills, missing fields, invalid dates, bad references, booleans in numeric fields, nonfinite values and inconsistent bounds raise ValidationError. Numeric input and objective bounds are checked to prevent integer overflow. Python-created problems undergo domain validation before model construction too.

Mathematical model

The Boolean decision variable x[e,s] is 1 exactly when employee e works shift s. All durations and load constraints use integer minutes.

Hard constraints:

1. An employee must be available for the complete shift.
2. Each shift receives exactly required_workers employees.
3. Each employee's total duration lies between min_hours and max_hours.
4. An employee cannot work two overlapping shifts. Intervals are half-open: 08:00–12:00 and 12:00–16:00 may both be assigned to the same person.
5. For each skill quota, at least that many assigned employees possess the skill. Remaining team members need not possess it. A multiskilled employee may count toward several quotas in the same shift; these are team competency counts, not distinct exclusive role positions.

Let p[e,s] be preference scores, L[e] the assigned minutes, and define:

P = sum(e,s) p[e,s] * x[e,s]
F_minutes = sum(e < f) |L[e] - L[f]|
F_hours = F_minutes / 60

Reported objective (maximize): preference_weight * P - fairness_weight * F_hours
CP-SAT integer objective:      60 * preference_weight * P - fairness_weight * F_minutes

Each absolute difference is represented by an integer variable constrained with add_abs_equality. Multiplication by 60 preserves the optimum without rounding fractional hours. The audit recomputes the scaled objective from assignments using integer arithmetic and compares it exactly with CP-SAT's integer evaluation of the model objective expression using CpSolver.value. Only the final reported value is divided by 60. This avoids premature rounding when large preference and fairness terms nearly cancel, and prevents a relative float tolerance from hiding a small formulation error at a large objective magnitude. Both weights are nonnegative integers; either or both may be zero. Metrics are still calculated from actual assignments when their objective weight is zero.

For example, a feasible schedule with 17 preference points, a 1001-minute pairwise gap, preference weight 2107480217 and fairness weight 2147482339 has scaled objective 1, hence reported objective 1/60. Computing the weighted penalty in floating-point hours first produced 0.01666259765625 and caused CP-SAT result extraction to raise an objective-audit error. Regression tests use a rational oracle for positive, negative and zero cancellation, cover both algorithms, and check that an intentionally incorrect model objective is rejected. The CSV analyzer restores whole minutes before checking the weighted objective too. Reported objectives and solver bounds remain floating-point values; the exact integer check concerns the incumbent's objective, not the solver's bound.

The explicit display/CSV name is pairwise workload gap sum (hours), with CSV column pairwise_workload_gap_sum_hours. The Python field fairness_pairwise_hours is preserved for compatibility. Lower values mean more equal loads; 0 means all employees have equal hours. For example, loads [8, 0, 8, 0] have a pairwise gap sum of 32 hours, whereas [4, 4, 4, 4] have 0. With two employees and two four-hour shifts, a preference gain of 10 for concentrating the work competes with an eight-hour fairness penalty: fairness weight 2 favors splitting the shifts.

This is a weighted tradeoff, not a lexicographic objective. Equal weights do not imply equal numerical contributions. Pairwise fairness treats every employee equally, including employees with limited availability; it is not proportional to contractual capacity and grows with workforce size. Tune weights for the input and business priorities. Hard constraints always take precedence.

Sprint 1 audit: the example loads are [12, 8, 12, 8, 12, 8, 12] hours. There are four employees at 12 hours and three at 8 hours, so exactly 4 * 3 = 12 unordered pairs have a four-hour difference. Thus F_hours = 12 * 4 = 48 h. This is an accumulated pairwise difference, not 48 hours of overtime or a 48-hour difference between the busiest and least busy employee. The formulation was retained. For size comparisons, the CSV additionally reports mean_pairwise_workload_gap_hours = F_hours / binomial(n, 2) (0 for one employee). That descriptive normalization does not change the optimized objective.

Results and verification

solve_schedule(problem) returns a ScheduleResult with typed assignment pairs of employee/shift IDs, hours keyed by employee ID, objective, preference total, pairwise fairness in hours, algorithm identity, total algorithm runtime and solve time. solve_time_seconds is CP-SAT search wall time, or greedy construction/audit time. runtime_seconds includes domain validation, model construction where applicable, solving and result auditing; it excludes module imports and JSON I/O. Zero-hour employees are included when a solution exists.

OPTIMAL means optimality was proven; FEASIBLE means a solution exists but its optimality has not been proven. INFEASIBLE means no solution exists. UNKNOWN means no solution/proof was obtained before stopping (a zero time limit exercises this case). MODEL_INVALID is represented defensively; normal model validation raises a clear error before solving. When no solution exists, assignments/hours are empty and objective/preference/fairness are None, not fabricated zeros.

Greedy returns FEASIBLE only after a complete hard-constraint audit. Its FAILURE means it could not construct a solution, not a proof of infeasibility. Both strategies use solve_schedule(problem, algorithm="cp_sat" | "greedy"). CP-SAT additionally reports its best objective upper bound when an incumbent exists; the maximization gap is upper_bound - incumbent, in objective units. No relative percentage is used because the weighted objective can be zero or negative. A FEASIBLE incumbent is never labeled optimal.

The example contains 72 required worker-hours, differentiated availability, preferences, four skill labels and hour bounds. The planning decisions are computed at runtime. Solver timing and tie-breaking can vary by machine/version. The measured scope of the synthetic benchmark is recorded below; it is not a claim about arbitrary production scheduling instances.

Tests check unavailable workers, exact headcount, minimum/maximum hours, minute precision, overlaps, skill quotas, preference selection, fairness tradeoffs, invalid inputs and no-solution outcomes. A tiny exhaustive-enumeration oracle checks the optimal objective across several weight settings. An independent audit recalculates every hard constraint and metric on the example from the returned assignments. CLI tests run the actual entry point in subprocesses.

Scope

This sprint covers fixed, same-day shifts and a single local calendar. Overnight shifts, time zones/DST, breaks, rest periods, overtime costs, recurring weekly rules, exclusive role allocation and explanations of infeasibility are not yet modeled. Supporting them correctly requires explicit additional domain rules. The pairwise formulation is intentionally straightforward and has quadratic terms in employee and shift counts. Performance outside the measured workload families is unknown. There is no frontend, API, Docker setup or database.

Greedy baseline

The greedy implementation uses only the Python standard library and shares the domain validation, result format and metric audit with CP-SAT. Importing/running this strategy does not import OR-Tools. For each shift in (date, start_time, id) order it filters employees by complete availability, remaining maximum-hour capacity and absence of overlaps with earlier assignments.

It then fills one position at a time, ranking eligible employees lexicographically:

1. Most currently unmet skill quotas to which the employee contributes.
2. Most minutes of the employee's unmet minimum-hour obligation satisfied.
3. Largest incremental weighted objective gain, using the current loads: 60 * preference_weight * preference - fairness_weight * delta_pairwise_minutes.
4. Lowest current workload, then lexicographically smallest employee ID.

Loads and skill deficits are updated after each choice. Once a team is filled, every quota must be satisfied. There is no lookahead, repair or backtracking. A shortage of candidates, an unsatisfied quota, or a final unmet minimum-hour obligation returns FAILURE with an explanation. Partial construction is discarded; it is never published as a valid schedule. All complete schedules are audited before returning FEASIBLE. Determinism concerns assignments and scores, not measured runtimes.

This baseline prioritizes local skill/minimum-hour needs before its objective score. It does not optimize the global weighted objective. Evaluating each candidate's fairness change scans all employees, so the ranking work is O(sum(required_workers) * employees^2) before availability/overlap checks. It is deliberately simple, but is not a linear-time greedy implementation.

A local decision that causes failure

data/greedy_trap.json contains two four-hour shifts:

Employee	Availability	Maximum	Skill	Morning preference
Alice	08:00–16:00	4 h	backend	10
Bob	08:00–12:00	4 h	none	1

The morning shift needs one worker; the afternoon needs one backend worker. Greedy picks Alice in the morning, leaving no eligible afternoon worker. CP-SAT assigns Bob in the morning and Alice in the afternoon, finding the proven optimum with preference score 6, gap sum 0 h and objective 6 under this file's weights.

python main.py data/greedy_trap.json --algorithm greedy
python main.py data/greedy_trap.json --algorithm cp_sat

Greedy can work well when capacity and skills have slack and early choices do not consume resources needed later. CP-SAT considers those dependencies globally and can establish feasibility, infeasibility and optimality, subject to its time limit. Greedy's speed can be useful when a satisfactory local solution suffices; its success does not imply optimality and its failure does not imply impossibility.

Reproducible synthetic benchmarks

Install the optional plotting dependency separately:

python -m pip install -r benchmarks/requirements.txt
python benchmarks/generate_instances.py --employees 10 --required-workers 2 --seed 42 --output data/generated.json
python benchmarks/run_benchmarks.py --employees 10 25 50 100 --seeds 0 1 2 3 4 --time-limit 5 --output results/reproduced.csv
python benchmarks/analyze_results.py results/reproduced.csv
python benchmarks/plot_results.py results/reproduced.csv --output-dir results/reproduced_figures

All generation/solver parameters are available through --help. The complete command for the recorded main experiment was:

python benchmarks/run_benchmarks.py --employees 10 25 50 100 --seeds 0 1 2 3 4 --days 5 --shifts-per-day 3 --staffing-ratio 0.2 --availability-probability 0.6 --number-of-skills 3 --preference-min 0 --preference-max 10 --min-hours 4 --max-hours 16 --preference-weight 10 --fairness-weight 1 --time-limit 5 --num-workers 1 --solver-seed 0 --output results/benchmark_results.csv

Existing CSVs are protected from accidental replacement; use a new output path or explicitly pass --overwrite. Analysis and plot scripts can be rerun without rerunning the solvers. The main raw CSV, summary, metadata and figures are saved in the working tree as artifacts of actual executions, without any Git commit.

Generator and experimental controls

Generator version 1 uses a local random.Random(seed). It creates one to three adjacent four-hour shifts per day, starting at 08:00, and a fixed first date of 2026-09-07. Skill membership is sampled independently with probability 0.45, with at least one skill per employee when skills exist. Preferences are uniform integers in the configured inclusive range. Both hour bounds apply to the entire horizon, and are shared by employees in this synthetic family.

With ensure_feasible=True (default), a shuffled cyclic rotation allocates a balanced witness with exact headcounts and no duplicated worker within a shift. Parameter combinations whose whole-shift capacities cannot support this witness are rejected. Availability is sampled per employee/shift with the requested probability, then forced on for witness assignments. Thus 0.6 is the background probability, not a claim that the final availability density is exactly 60%. For each shift, up to two skills present in the witness team receive a positive quota, capped by both the team's supply and max(1, required_workers // 3). The complete witness is audited before returning an instance. Neither solver receives the witness as a hint or initial solution. --no-ensure-feasible removes these guarantees, permitting naturally infeasible instances.

The main experiment contains 20 distinct instances and 40 measured solver calls: four workforce sizes, five seeds, both algorithms on each exact same instance. Headcount is ceil(0.2 * employees) per shift (2, 5, 10, 20); the horizon remains five days / 15 shifts. Total required labor is 120, 300, 600 and 1,200 hours. Minimum/maximum hours are 4/16, leaving a balanced 12-hour witness per employee. Weights are preference 10 / fairness 1 for all sizes, and solver seed is always 0.

Runs execute serially in fresh subprocesses, alternating algorithm order by seed parity. There are no concurrent solver calls, hidden warm starts or retries chosen to improve the reported result. runtime_seconds measures algorithm work including validation/model building/extraction/audit, excluding imports, file I/O, generation and process startup. process_wall_seconds separately measures the entire subprocess call. Each CP-SAT search has a five-second limit, one worker, and an outer process deadline of 25 seconds, which also protects model building. The worker is terminated on TIMEOUT; no incumbent is invented. Its algorithm runtime and quality are then missing, and its observed process wall time remains available. Summary timing counts (timed_runs) expose such censored runs.

The time limit already supported by the core is preserved: OPTIMAL is a proof, FEASIBLE is an incumbent without an optimality proof, and UNKNOWN means no incumbent/proof was obtained. A solver reaching its search limit does not imply that its total process wall time equals the configured limit.

CSV, metrics and aggregation

results/benchmark_results.csv contains one row per real call, including full generator/solver settings, seed and SHA-256 of the canonical input. The adjacent metadata records UTC timestamps, Python/OR-Tools and dependency versions, platform, CPU description, source digest and all configs. benchmark_results_artifacts/n<size>_seed<seed>/ stores the input, witness and both actual solver results, including assignments. Results are audited again in the parent process before inclusion in the CSV.

Metric	Definition / interpretation
feasible	1 only for a complete audited solution; success rate uses all seeds
assigned_workers	Number of returned employee–shift assignment pairs
coverage	Returned assignment count / required assignment count; 1 on success, 0 when construction is discarded or no incumbent exists
covered_shifts	Number of fully staffed shifts in the returned complete solution
total_employee_hours	Sum of actual employee hours; missing without a solution
preference_score	Sum of preference points for actual assignments; larger is better
pairwise_workload_gap_sum_hours	Sum of absolute load gaps over unordered employee pairs; smaller is better
mean_pairwise_workload_gap_hours	Previous metric / number of unordered pairs; used in the size-comparison plot
objective_value	10 * preference_score - pairwise_workload_gap_sum_hours in this experiment
best_objective_bound	CP-SAT upper bound on the maximized objective; missing for greedy/no incumbent
absolute_objective_gap	Upper bound minus incumbent, clamped to 0 for numerical noise; not a percentage

The analyzer separates every distinct experiment configuration, algorithm and size. It reports mean/median runtime, status counts, timed-run count, feasibility and coverage using all seeds. Quality averages use only the seeds on which both algorithms succeeded, and expose the number of paired successes. This avoids comparing one algorithm's easy successes with another's broader set. Missing quality is never replaced by zero. Different weights, staffing, horizons or generation settings are not pooled; mismatched input hashes/duplicate rows are rejected. Plotting requires one comparable experiment profile per CSV.

Preference plots use points per assignment instead of totals that mechanically grow with staffing. Fairness plots use mean pairwise gaps instead of sums that mechanically grow with the number of pairs. Neither normalization makes distinct instances identical; comparisons remain descriptive within this generator family. Runtime shading shows observed min–max across seeds, not a confidence interval.

Recorded results — 2026-09-06

Environment: Python 3.13.5, OR-Tools 9.15.6755, Windows 11 (10.0.26200), Intel64 Family 6 Model 165 Stepping 2. Plotting used matplotlib 3.11.1. The initial eight-call pilot (10/25 employees, seeds 0/1, one-second limit) is retained separately as results/pilot.csv and is not pooled with the main series.

The following are measured means over five paired successes per size. Runtime is algorithm time in seconds; preference is points per assignment; gap is the unnormalized pairwise workload gap sum in hours.

Employees	Algorithm	Feasible	Proven optimal	Mean runtime (s)	Preference/assignment	Gap sum (h)
10	CP-SAT	5/5	5/5	0.0796	7.7467	41.6
10	Greedy	5/5	—	0.0014	6.9400	177.6
25	CP-SAT	5/5	5/5	0.0863	8.2853	0.0
25	Greedy	5/5	—	0.0069	6.9707	524.8
50	CP-SAT	5/5	5/5	0.2322	8.4467	0.0
50	Greedy	5/5	—	0.0406	7.3667	1049.6
100	CP-SAT	5/5	5/5	1.0728	8.4707	0.0
100	Greedy	5/5	—	0.3180	7.4600	3198.4

All 20 CP-SAT calls proved optimality; all greedy calls returned feasible solutions. No main-series UNKNOWN, INFEASIBLE, FAILURE or TIMEOUT occurred. CP-SAT had better average preferences and smaller average workload gaps at every tested size, with greater runtime. These are separate observations, not a claim that a weighted optimum must improve every component in every instance.

The small nonzero CP-SAT gap at 10 employees is expected: maximizing the weighted objective can favor extra preference points over perfect equality, even though the generator's balanced witness exists. Greedy succeeding on all generated instances is also consistent with its failure on the hand-crafted trap: the synthetic family is conditioned on feasibility and has substantial flexibility.

The fairness sum has size-dependent weight relative to preference totals. Even with unchanged coefficients, increasing headcount changes that tradeoff. This experiment measures employee/assignment/pairwise-variable growth at a fixed 15-shift horizon, not general scalability in days, overlaps or tight capacity. Five seeds are exploratory, not enough for strong statistical generalizations. There are no measured production workloads, memory measurements or claims above 100 employees. Timings can vary; reproducibility is supported by seeds, canonical input snapshots and configuration, not a guarantee of bit-identical wall times.

Plots generated directly from the raw CSV: