Staff Rota Scheduling with Google OR-Tools CP-SAT

The rota problem

A gym rota looks, from the outside, like a straightforward scheduling problem. You have shifts to fill, staff to fill them, and a week in which to do it. The reality is less tidy. Each shift needs a specific head-count and at least one qualified person in each required role: a duty manager, two trainers on the gym floor, a lifeguard poolside, a receptionist at the front desk. Each employee has fixed days off, holidays, and a contract that sets a lower and upper bound on how many shifts they can work in a week. Someone who finishes a closing shift at 22:00 cannot start the following morning's opening shift at 06:00 without breaching the eleven-hour minimum rest period under the Working Time Regulations. Weekend shifts are unpopular and, if the same people draw them every week, they will notice. Individual shift preferences exist, and where possible it is reasonable to honour them.

A diligent person with a spreadsheet can manage this for perhaps a dozen employees. At 30 staff across three shifts and seven days, the number of possible assignments is large enough that finding any valid rota by hand is non-trivial, and finding a fair one that distributes weekend shifts equitably, respects every constraint, and honours preferences where possible is not realistically achievable without automation. This is a constraint satisfaction problem, and Google's OR-Tools CP-SAT solver is a natural fit for it.

Operations Research

Operations Research (OR) is the application of mathematical methods to decision problems: given a set of options, a set of constraints, and an objective, find the best possible choice. Workforce scheduling is a classic OR problem. The options are which employee works which shift; the constraints are the rules that make a rota legal; the objective is to minimise the spread of work across the team. Understanding the main families of OR method helps explain why CP-SAT is the right tool here rather than an alternative approach.

Linear programming (LP) optimises a linear objective over continuous variables. It works well for resource allocation problems where quantities can be fractional: how much of each ingredient to use, how much capital to allocate to each project. Real scheduling deals in whole people working whole shifts, which means binary decision variables, which is the territory of integer programming (IP). IP handles discrete decisions naturally but is harder to solve than LP. Constraint programming (CP), the approach used here, takes a different route: rather than solving a system of inequalities with an algebraic engine, it declares constraints as logical predicates and searches the space of valid assignments using propagation and backtracking. CP tends to outperform IP on problems with many combinatorial constraints, which is precisely what a rota with availability windows, rest gap rules, skill requirements, and a fairness objective looks like.

The domain model

Before defining the model, it helps to be clear about what is being represented. Two dataclasses carry all of the domain knowledge the solver needs.

@dataclass
class Employee:
    name: str
    skills: frozenset[str]
    contract: str
    unavailable: frozenset[str] = frozenset()


@dataclass
class ShiftDemand:
    total: int
    skills: dict[str, int] = field(default_factory=dict)

Employee holds what the model needs to know about each person: their name, the roles they are qualified to cover, their contract type, and any days they are unavailable this week. ShiftDemand describes what a shift requires: a minimum head-count and a per-skill minimum. Having staff qualified across multiple roles is what gives the solver room to find a good rota; the more multi-skilled the team, the more options are available when constraints tighten.

DEMAND = {
    "weekday": {
        "Opening": ShiftDemand(5, {"reception": 1, "trainer": 2, "lifeguard": 1, "manager": 1}),
        "Midday":  ShiftDemand(6, {"reception": 1, "trainer": 2, "lifeguard": 1, "manager": 1, "instructor": 1}),
        "Closing": ShiftDemand(5, {"reception": 1, "trainer": 2, "lifeguard": 1, "manager": 1}),
    },
    "weekend": {
        "Opening": ShiftDemand(6, {"reception": 1, "trainer": 2, "lifeguard": 1, "manager": 1, "instructor": 1}),
        "Midday":  ShiftDemand(5, {"reception": 1, "trainer": 2, "lifeguard": 1, "manager": 1}),
        "Closing": ShiftDemand(4, {"reception": 1, "trainer": 1, "lifeguard": 1, "manager": 1}),
    },
}

A weekday Opening shift needs 5 people in total, with at least one each covering reception, manager, and lifeguard, and at least two trainers on the gym floor. Weekend Opening shifts need 6, reflecting busier morning trade. Weekend Closing shifts drop to 4. The solver reads this structure and generates the coverage constraints automatically; adjusting a headcount or adding a shift type requires only a change to DEMAND, not to the model.

Constraint programming and CP-SAT

Constraint programming is a paradigm for solving combinatorial problems by declaring variables, their domains, and constraints over those variables, then letting a solver search for a valid assignment. You are not writing an algorithm that constructs a rota step by step; you are describing what a valid rota looks like, and the solver finds one. This distinction matters in practice: a constructive algorithm has to be revised whenever a new rule is introduced, whereas a constraint model simply gains a new constraint and continues to work. This model has not changed since the rest-gap rule was added; adding a new contract type will not change it either.

CP-SAT is Google's implementation of this approach, part of the OR-Tools library. It operates on integer and Boolean variables and solves problems by combining constraint propagation (narrowing variable domains based on what constraints imply) with conflict-driven clause learning (recording contradictions encountered during search and using them to prune future branches). In practice, CP-SAT is fast on tightly-constrained scheduling problems and returns one of two statuses: OPTIMAL, meaning the best possible solution under the objective function has been found and proven, or FEASIBLE, meaning a valid solution was found but the solver ran out of time before proving it could not be improved. For a 30-person weekly rota, optimal solutions typically emerge in a few seconds.

Decision variables

The model's core decision is binary for each combination of employee, day, and shift: does this person work this shift on this day? A Boolean variable for each triple encodes exactly that.

def _create_variables(self) -> None:
    """works[name, day, shift] == 1  iff that person works that shift."""
    for e in self.roster:
        for d in self.days:
            for s in self.shifts:
                self._works[e.name, d, s] = self.model.new_bool_var(
                    f"works_{e.name}_{d}_{s}"
                )

For 30 employees, 7 days, and 3 shifts, this produces 630 Boolean variables. The solver assigns each a value of 0 or 1 such that every hard constraint is satisfied and the objective is minimised. In principle the search space is 2^630, which is astronomically large; constraint propagation eliminates the vast majority of that space before the solver ever searches it, which is what makes CP-SAT tractable on problems of this scale.

Hard constraints

Hard constraints define what constitutes a valid rota at all. Violating any of them produces a rota that cannot be used, so the solver treats them as absolute. The first is straightforward: a person can work at most one shift per day.

def _one_shift_per_day(self) -> None:
    for e in self.roster:
        for d in self.days:
            self.model.add_at_most_one(
                self._works[e.name, d, s] for s in self.shifts
            )

add_at_most_one is CP-SAT's dedicated encoding for this pattern. It propagates more efficiently than an equivalent sum(vars) <= 1 constraint because the solver understands the specific semantics and applies stronger pruning rules. The constraint is 'at most one' rather than 'exactly one' because employees may have days off on which they work no shift at all.

Coverage requirements are more involved. Each shift needs a minimum total head-count, and within that total, at least a specified number of qualified staff in each role. The demand profile differs between weekdays and weekends, handled by the day_type helper that maps a calendar day to the appropriate demand dictionary.

def _meet_coverage(self) -> None:
    for d in self.days:
        required = self.demand[day_type(d)]
        for s in self.shifts:
            need = required[s]
            self.model.add(
                sum(self._works[e.name, d, s] for e in self.roster)
                >= need.total
            )
            for skill, count in need.skills.items():
                qualified = [e for e in self.roster if skill in e.skills]
                self.model.add(
                    sum(self._works[e.name, d, s] for e in qualified)
                    >= count
                )

The rest gap constraint addresses the late-to-early transition. A closing shift finishes at 22:00; the following opening shift starts at 06:00. That is eight hours between the end of one and the start of the next, below the eleven-hour minimum required under the Working Time Regulations 1998. Rather than modelling clock times explicitly, the model bans the specific consecutive pairing directly. This is simpler than time arithmetic, correct, and easy to extend: any new forbidden pairing requires only an additional entry in FORBIDDEN_CONSECUTIVE.

def _enforce_rest(self) -> None:
    for e in self.roster:
        for today, tomorrow in zip(self.days, self.days[1:]):
            for late, early in self.forbidden:
                self.model.add(
                    self._works[e.name, today, late]
                    + self._works[e.name, tomorrow, early]
                    <= 1
                )

Contract limits

Each employee's contract sets a minimum and maximum number of shifts for the week. The model introduces an auxiliary integer variable for each employee's weekly total, posts a sum equality to link it to the Boolean work variables, then adds the bounds. Storing the variable in self._weekly_total makes it available to the objective function later.

def _apply_contract_limits(self) -> None:
    for e in self.roster:
        limits = self.contracts[e.contract]
        total = self.model.new_int_var(0, len(self.days), f"total_{e.name}")
        self.model.add(total == sum(self._shifts_of(e.name)))
        self.model.add(total >= limits["min_shifts"])
        self.model.add(total <= limits["max_shifts"])
        self._weekly_total[e.name] = total

The objective: fairness

Once the hard constraints have narrowed the feasible space, the objective function selects the best rota within it. Fairness takes clear priority over individual preferences: the solver minimises the spread of total shifts worked across the team and the spread of weekend shifts separately, weighted to reflect their relative importance, with a small reward for granting stated preferences that can break ties without distorting the distribution.

def _balance_and_prefer(self) -> None:
    weekend_days = [d for d in self.days if d in WEEKEND]

    for e in self.roster:
        wknd = self.model.new_int_var(
            0, len(weekend_days), f"weekend_{e.name}"
        )
        self.model.add(
            wknd == sum(self._shifts_of(e.name, days=weekend_days))
        )
        self._weekend_total[e.name] = wknd

    spread_total = self._spread(self._weekly_total.values(), len(self.days))
    spread_weekend = self._spread(
        self._weekend_total.values(), len(weekend_days)
    )

    granted = [
        self._works[name, d, s]
        for name, slots in self.preferences.items()
        for (d, s) in slots
    ]

    self.model.minimize(
        self.WORKLOAD_FAIRNESS * spread_total
        + self.WEEKEND_FAIRNESS * spread_weekend
        - self.PREFERENCE_REWARD * sum(granted)
    )

def _spread(self, totals, upper_bound):
    """Return (max - min) of a set of counts."""
    totals = list(totals)
    highest = self.model.new_int_var(0, upper_bound, "")
    lowest = self.model.new_int_var(0, upper_bound, "")
    self.model.add_max_equality(highest, totals)
    self.model.add_min_equality(lowest, totals)
    return highest - lowest

The _spread helper returns max(totals) - min(totals) as a CP-SAT linear expression, using add_max_equality and add_min_equality to introduce auxiliary variables for the extremes. Minimising this drives the solver towards rotas where the gap between the most and least worked employee is as small as possible. Overall workload fairness carries a weight of 5; weekend fairness carries 3; granting a preference contributes 1 to the negated objective. The weights ensure that preferences can break ties but cannot push the solver into an unfair distribution to satisfy them.

Separating data from model

The most important structural decision in the code is the separation between the GymRotaScheduler class and the DATA section. The class encodes the scheduling rules and rarely needs changing between deployments. What changes week to week is the data: the roster, this week's unavailability, the shift demand profiles, the contract definitions, the list of forbidden consecutive pairings. A manager adjusting weekend headcount or recording a new employee's availability touches only the data; the model interprets it correctly without any modification to the solver logic.

In a production deployment, you would replace the static DATA section with queries against your HR and operations systems: pull the current roster and this week's availability from your workforce management tool, pull shift demand profiles from your configuration database, then pass everything to the same GymRotaScheduler. The clean boundary between data and model is what makes that transition straightforward. The scheduler class expresses the rules; the rules do not change because the data changed.

Running it

The solve method exposes two parameters that directly affect the quality of the result. time_limit is the wall-clock budget in seconds: the solver returns the best solution found within that window, whether or not optimality has been proven. For a 30-person weekly rota, optimal solutions typically emerge within a few seconds, so 30 seconds is a conservative limit. workers controls the number of parallel search threads: CP-SAT's portfolio-based search scales well across cores, and setting this to match your available CPU count is generally the right call.

scheduler = GymRotaScheduler(ROSTER, DEMAND, preferences=PREFERENCES)
solution = scheduler.solve(time_limit=30.0)

if solution is None:
    print(
        "No feasible rota found. "
        "Check that coverage demands do not exceed available qualified staff, "
        "that unavailability does not overlap too heavily, "
        "and that contract limits are not set too tight."
    )
    return

print_rota(solution, ROSTER)

If the solver returns None, no valid rota exists under the current data and constraints. The most common causes are coverage demands that exceed the available qualified staff on a particular shift, too much overlapping unavailability across the team, or contract limits set so tightly that there are not enough shifts to go around. The model surfaces these problems immediately rather than silently producing an invalid rota, which is the correct behaviour when scheduling real staff.