CP-SAT Employee Scheduling: Modeling 300 Employees

The problem: monthly rostering at scale

Consider a real scheduling problem: 300 employees across multiple functional groups, each holding one or more qualifications. 50 shift types with different start times, end times, and break structures. 30 days to plan. Variable daily staffing needs that depend on the day of the week and operational cycles.

Each employee has a contract type (full-time, part-time, student) that determines their monthly target hours, days off, and weekend rules. Some employees have pre-assigned absences: holidays, vacations, fixed days off. The solver must respect all of these while producing a schedule that covers every staffing need, distributes workload fairly, and complies with labour regulations.

This article describes the exact CP-SAT model we use to solve this problem. Every variable, constraint, and objective described here runs in production.

Decision variables

The model starts with three types of variables:

Assignment variables

assign[e, d, s]  # Boolean: employee e works shift s on day d

One Boolean variable for every possible employee-day-shift combination. For 300 employees, 30 days, and 50 shifts, that is up to 450,000 variables. In practice, the number is lower because employees can only be assigned to shifts matching their qualifications.

Day-off variables

is_off[e, d]  # Boolean: employee e does not work on day d

One variable per employee per day. 300 × 30 = 9,000 variables. These are linked to the assignment variables: is_off[e, d] = 1 if and only if no shift is assigned to employee e on day d.

Aggregate variables

total_minutes[e]            # Integer: total worked minutes for employee e
total_shifts_per_function[e, f]  # Integer: shifts worked by e in function f

These are derived variables that the solver computes from the assignment variables. They are used in equity objectives to measure how fairly work is distributed across the team.

Hard constraints

Hard constraints are non-negotiable. If the solver cannot satisfy all of them simultaneously, the problem is declared INFEASIBLE. No schedule is produced.

One shift per day

# For each employee e, for each day d:
sum(assign[e, d, s] for s in all_shifts) <= 1

An employee works at most one shift per day. Combined with is_off, this means each employee-day is either exactly one shift or a day off.

Minimum rest between shifts (11 hours)

Labour regulations require a minimum rest period between the end of one shift and the start of the next. The standard is 11 hours. Instead of computing time differences at solve time, we pre-compute toxic pairs: pairs of shifts (s1, s2) where shift s1 on day d followed by shift s2 on day d+1 would violate the 11-hour rule.

# For each toxic pair (s1, s2), for each employee e, for each day d:
assign[e, d, s1] + assign[e, d+1, s2] <= 1

Pre-computing toxic pairs is significantly more efficient than encoding time arithmetic in the model. For 50 shift types, the number of toxic pairs is typically 200-400, which generates a manageable number of constraints.

Qualification enforcement

# If employee e does not hold qualification for shift s:
assign[e, d, s] = 0  (for all days d)

Each shift belongs to a function (e.g. security, logistics, maintenance). Each employee holds qualifications for specific functions. The solver can only assign an employee to a shift if they are qualified. In practice, this is implemented by simply not creating the assign variable for invalid employee-shift combinations, which reduces model size.

Pre-assigned absences

# HOLIDAY, VACATION, FIXED_OFF on day d for employee e:
assign[e, d, s] = 0  (for all shifts s)
is_off[e, d] = 1

Absences are injected as fixed values before the solver runs. The solver does not decide whether an employee is on holiday. It respects the pre-assigned absence and optimises everything else around it.

Soft objectives

Soft constraints are goals the solver tries to achieve but can violate if necessary. Each violation adds a penalty to the objective function. The solver minimises the total penalty score: lower is better.

Coverage

The most critical objective. For each function, each day has a staffing need (e.g. "3 security agents on Monday"). The solver penalises every uncovered slot.

# For each function f, for each day d:
assigned_count = sum(assign[e, d, s] for e qualified for f, s in function f)
missing = max(0, need[f, d] - assigned_count)
penalty += missing * WEIGHT_COVERAGE

Days off

Each employee has a target number of days off per month (derived from contract type and working days in the month). The solver penalises missing days off.

# For each employee e:
actual_off = sum(is_off[e, d] for d in month)
missing_off = max(0, target_off[e] - actual_off)
penalty += missing_off * WEIGHT_DAYS_OFF

Weekend guarantee

Each employee should get at least one full weekend off (Saturday + Sunday) per month. Employees with contract type "student" are excluded from this constraint.

# For each employee e (non-student):
has_weekend_off = max over all weekends w of:
    (is_off[e, saturday_w] AND is_off[e, sunday_w])
penalty += (1 - has_weekend_off) * WEIGHT_WEEKEND

Workload equity (days worked)

Within each functional group, the difference in total days worked between the employee who works the most and the one who works the least should be minimal. Employees with holidays or vacations are excluded from the equity calculation to avoid penalising the solver for absences it cannot control.

# For each group g:
gap = max_days_worked[g] - min_days_worked[g]
penalty += gap * WEIGHT_WORKLOAD_EQUITY

Qualification equity (shifts per function)

Within each group, shifts should be distributed fairly across qualification types. An employee qualified for both security and logistics should not be assigned exclusively to security while others only get logistics.

# For each group g, for each function f:
gap = max_shifts[g, f] - min_shifts[g, f]
penalty += gap * WEIGHT_QUALIF_EQUITY

Consecutive working days

Working more than 6 consecutive days is penalised. This is a soft constraint rather than a hard one because in some edge cases (short-staffed periods), the solver may need to exceed 6 days to maintain coverage.

# For each employee e, for each window of 7 consecutive days:
if all 7 days are worked: penalty += WEIGHT_CONSECUTIVE

Isolated days off

A single day off surrounded by two working days is less restful than consecutive days off. The solver penalises these isolated days off to encourage clustering.

# For each employee e, for each day d (not first or last):
if is_off[e, d] AND NOT is_off[e, d-1] AND NOT is_off[e, d+1]:
    penalty += WEIGHT_ISOLATED_OFF

Penalty calibration

The penalty weights create a priority hierarchy. The solver will sacrifice lower-priority objectives to preserve higher-priority ones.

Objective	Penalty weight	Priority
Missing coverage	Very high	Highest
No weekend guaranteed	High	High
Consecutive days > 6	High	High
Missing days off	Medium	Medium
Isolated day off	Medium	Medium
Qualification equity gap	Low	Low
Workload equity gap	Very low	Lowest

The rationale: an uncovered shift (highest weight) is always worse than a missing day off (medium weight). A missing day off is worse than a slightly unfair distribution. This hierarchy ensures the solver makes the right trade-offs when it cannot satisfy everything perfectly.

A good schedule typically scores in a predictable range. A score of zero would mean every objective is perfectly met, which is rarely possible with real-world data. The penalty breakdown shows exactly where the score comes from, giving the planner clear guidance on what to adjust in the input data.

Model size in practice

Here is what the model looks like for different operation sizes:

Employees	Boolean variables	Constraints (approx.)	Soft penalty terms
100	~80,000	~120,000	~15,000
150	~130,000	~200,000	~25,000
200	~180,000	~300,000	~35,000
300	~280,000	~500,000	~55,000

These numbers assume qualification filtering (not creating variables for invalid employee-shift pairs). Without filtering, the 300-employee model would have 450,000 Boolean variables. Filtering typically removes 30-50% of them.

Performance benchmarks

Measured on a standard server (8 cores, 16 GB RAM), using CP-SAT's multi-threaded search with 8 workers:

Employees	Time to first solution	Time to best solution	Optimality gap
100	< 30 seconds	2-3 minutes	< 1%
150	~1 minute	3-5 minutes	1-2%
200	~2 minutes	8-15 minutes	2-5%
300	~4 minutes	15-30 minutes	3-8%

"Time to first solution" is how quickly the solver finds a feasible schedule. "Time to best solution" is how long it takes to converge to the best score within the configured time limit. The "optimality gap" is the difference between the best solution found and the theoretical lower bound.

In practice, the solver finds a good solution quickly, then spends the remaining time improving it incrementally. The planner can configure the time limit based on their patience and quality requirements. CP-SAT always returns the best solution found within the allotted time.

Practical tips for scaling CP-SAT

Reduce the variable space

Do not create assign[e, d, s] for combinations that are impossible. If employee e is not qualified for shift s, or if e has a pre-assigned absence on day d, skip the variable entirely. This can reduce the model by 30-50%.

Pre-compute toxic pairs

Computing rest period violations at model build time (as a list of forbidden shift pairs) is much faster than encoding time arithmetic in CP-SAT. The solver handles Boolean implications efficiently.

Use multi-threaded search

CP-SAT runs multiple search strategies in parallel. Set num_workers to the number of available CPU cores. On an 8-core machine, this typically reduces solve time by 3-5x compared to single-threaded search.

Exclude absences from equity

Employees on holiday or vacation should be excluded from intra-group equity calculations. Otherwise, the solver penalises itself for a gap it cannot close, wasting search effort on an impossible objective.

Set a meaningful time limit

For 100-150 employees, 5 minutes is usually sufficient. For 200-300+, allow 15-30 minutes. The solver's anytime behaviour means it always has a valid solution ready, even if interrupted early. A longer time limit produces a marginally better score, not a fundamentally different schedule.

Monitor the objective breakdown

When the total penalty score is high, look at the breakdown. If 80% of the penalty comes from coverage gaps, the problem is understaffing, not solver tuning. If equity penalties dominate, the groups may be unbalanced. The penalty structure turns the solver into a diagnostic tool.