Healthcare

Skilled nurse rostering

Healthcare systems around the world face rising demand for care. At the same time, nurses are harder to recruit and retain. Nursing is physically and psychologically hard, and nurses often work under time pressure. Shift work can make it difficult for nurses to plan their lives and stay in the profession. Roster optimization cannot solve the shortage or make the work itself easier. It can still make rosters fairer and more workable for nurses by respecting rest and contract rules, sharing nights and weekends more evenly, and accommodating preferences where coverage allows. By covering each shift with the required skills, it can also help healthcare organizations keep services running. Nurse rostering is one application of personnel scheduling. This broader class of scheduling problem appears in transport, manufacturing, retail, and other services. This page sets out the problem, solves one small instance, and has the result checked.

View Markdown

The problem

A ward runs the same shifts every day, commonly an early shift, a late shift, and a night shift. A planning period can cover four weeks or longer. Across that period, a scheduler makes one decision for each nurse on each day: which shift they work, or whether they take the day off. A nurse works at most one shift per day. Each shift needs enough staff with the qualifications the ward requires. Some roles require registered nurses; others need staff trained in a particular area, such as eye care. The completed table of those decisions is the roster.

Nurses’ requests and the ward’s staffing needs often conflict, so a roster usually leaves some requests unmet.

Nurses’ contracts and preferences

  • Maximum working hours. Each nurse’s contract can set a limit on total working hours over a period. For example, a nurse with a 75-hour limit over two weeks can work ten 7.5-hour shifts. An 11th shift would exceed that limit. These periods can be shorter than the roster and can overlap, so a shift near the end of one period also counts inside the next one. Shifts also differ in length, and a night shift is usually the longest, so it uses more of the limit than an early or late shift.
  • Rest between shifts. A nurse should not work an early or late shift on the day after a night shift. For example, working a night shift on Monday and an early shift on Tuesday violates this rule.
  • Consecutive working days. Nurses should work no more than six days in a row. Some contracts also require at least two consecutive working days. Under those contracts, working one day between two days off does not meet the minimum.
  • Complete weekends. Contracts identify weekends when working only Saturday or only Sunday is discouraged. For a weekend covered by the rule, working Saturday and taking Sunday off can add a penalty.
  • Number of working weekends. Nurses should work no more than three weekends over the four-week period. Working every Saturday counts as four working weekends, even if every Sunday is a day off.
  • Consecutive night shifts. Some contracts discourage single night shifts and favor runs of at least two nights. A night shift between two days off is an example of an isolated night.
  • Personal preferences. Nurses can request particular shifts, working days, or days off. For example, a nurse may ask to work a late shift on Monday and take Saturday off.

Ward staffing requirements

  • Nurses per shift. The ward sets a staffing target for each shift, with a minimum and a maximum around it. An early shift may have a target of four nurses, a minimum of two, and a maximum of six. A shift adds a penalty when it does not have exactly the target number of nurses. The penalty is much larger when the number is below the minimum or above the maximum.
  • Required qualifications. Each shift needs enough nurses with the required qualifications. An early shift may need at least one registered nurse and one nurse trained in eye care. A nurse with both qualifications can count toward both requirements.
  • Variation by shift and day. Staffing needs can differ between early, late, and night shifts, and between weekdays and weekends. The late-shift target may be three nurses on weekdays and two on weekends. The required qualifications can differ in the same way. A ward may need a registered nurse on every early and late shift from Monday to Friday, but not on the weekend.

Finding a roster with the lowest penalty

Unmet requests and rule violations add penalty points to the roster. Some rules matter much more than others, so their weights can be far apart. A violation of a high-weight rule may count for more than many violations of a low-weight rule. A higher weight makes a violation more costly, but does not forbid it. The optimization goal is to find a roster with the lowest total penalty.

The model boundary

This model creates a roster for an existing team over one planning period. It does not decide how many nurses the team needs or which shifts the ward runs.

It also treats each planning period separately. It does not use the previous roster, so rest and consecutive-day rules apply only within the period being scheduled. A production model could use earlier rosters to balance night and public-holiday shifts more evenly over time, and account for any compensatory leave or pay those shifts earn under the nurses’ contracts.

Where the data comes from

The rules and figures in this case come from a real rostering problem at the ophthalmology ward of Queen’s Medical Centre University Hospital NHS Trust in Nottingham. Petrovic and Beddoe based their study on rosters the ward supplied. The shift pattern, the contract limits, and the staffing bands come from that ward. This case is a reconstruction of the ward’s problem, not a copy of its records.

A scheduler’s own data would come from staff records, the competency register, the leave and absence system, and the contracts and union agreements that set hours and rest. No system holds the penalty weights. A planner sets those from experience. The model reads no patient data of any kind, and this page publishes no roster for a real nursing team.

A small worked example

This example rosters one ward of 19 nurses for four weeks. Each day runs three shifts: early (E), 07:00 to 14:45; late (L), 13:30 to 21:15; night (N), 21:00 to 07:15. An early or late shift counts 7.5 hours. A night shift counts 10 hours. Of the 19 nurses, 16 are registered nurses, and 12 are trained in eye care; ten hold both qualifications, and one holds neither. The nurses also requested 378 specific shifts or days off, and 55 of those requests are marked high priority. Refusing a high-priority request costs 1000 points, and refusing any other costs 1 point. The table below shows what the ward needs on each shift, not the nurses’ requests.

DaysShiftMinimumTargetMaximumAlso needed
Weekdaysearly (E)2461 registered nurse, 1 nurse trained in eye care
Weekdayslate (L)2351 registered nurse, 1 nurse trained in eye care
Weekdaysnight (N)1121 nurse trained in eye care
Weekendsearly (E)2351 nurse trained in eye care
Weekendslate (L)1241 nurse trained in eye care
Weekendsnight (N)1131 nurse trained in eye care

QMC-2.json — the instance this example solves

Optimal roster

This optimal roster is the solution CP-SAT found for the QMC-2.json instance. The OpenConstraint MCP server executed that run. CP-SAT proved that no roster costs less, and an independent checker accepted this one. No rule is violated across all 84 shifts in the four weeks.

  • 07:00 to 14:45
  • 13:30 to 21:15
  • 21:00 to 07:15
  • RN, ET filled where the nurse is a registered nurse or trained in eye care
  • Over the target more nurses on duty than the ward asks for
  • Under the target fewer nurses on duty than the ward asks for
WEEK 1WEEK 2WEEK 3WEEK 4MTWTFSSMTWTFSSMTWTFSSMTWTFSSRN ETSHIFTSUNMETALEEEENNLEELLEEEEL172BLEEELELL83CLLELEEELEELEE133DELNLEN6EELEEELLELEEEELE15FELEELLLELE101GLLLLNNNNNNN11HEELEELELEELE123ILNNLLEENNE10JELE33KLLLLLLL71LLEEEEENN8MEENNEEELEEEEEEEELL18NLLEELEELELLL125OELLEELLNNEEEE131PEEENNELELEE112QNNLELELELLLELL142RELEENNNLLLLE12SEELLEEEE81NURSES ON DUTYEach row is one shift. Each number counts the nurses on duty that day. Rings mark the 2 that miss the target.E4444433444443344444234444433L3333323333332233333223333322N1111111111111111111111111111total penalty = 29 points

The figure’s UNMET column shows that 27 of the nurses’ 378 shift and day-off requests go unmet, costing 1 point each. The figure also rings the two shifts that miss the ward’s staffing target. One late shift carries a nurse more than the target, which costs 1 point; one early shift carries a nurse fewer, which costs 1 point. Both stay inside the ward’s minimum and maximum, so neither breaks a rule. Nothing else is charged, so the roster’s penalty is 29 points. Each penalty shown costs 1 point. The instance charges 1000 points for refusing a high-priority request, and 1000 points for staffing a shift below the ward’s minimum or above its maximum. This roster pays neither penalty, and it breaks no contract rule. Night coverage meets the ward’s target on all 28 nights, so the figure rings no night shift.

The CP model

The completed roster gives each nurse a shift or a day off on every day of the period. The constraint programming (CP) model turns the scheduling rules into variables, constraints, and an objective. Broken rules and unmet requests add penalties, each at its own weight. A rule that sets a number, such as the minimum nurses on a shift, charges its weight for every nurse missing. The excerpts below show selected parts of the model in Python.

Assigning nurses to shifts

For each nurse, each day, and each shift, the model creates one true-or-false variable. When the variable is true, that nurse works that shift on that day. When every variable for that day is false, the nurse takes the day off. Once the model has built that day’s shift variables, it allows at most one of them to be true. A nurse never works two shifts in one day.

for employee in instance.employees:
    for day in range(instance.num_days):
        literals: list[cp_model.IntVar] = []
        for shift in instance.shift_types:
            variable: cp_model.IntVar = self.model.new_bool_var(
                f"x_{employee.id}_{day}_{shift}"
            )
            self.x[employee.id, day, shift] = variable
            literals.append(variable)

        # …
        self.model.add_at_most_one(literals)
model.py — _build_assignment_variables(), lines 222–235, four lines omitted

Covering every shift by skill

A cover block sets a minimum, maximum, and target headcount for one shift, optionally for one skill. A block with no skill counts every nurse assigned to that shift. A block for one skill counts only the nurses who have that skill. The model charges a penalty for any shortfall below the minimum. Exceeding the maximum or missing the target also adds a penalty, each at its own weight. The excerpt leaves out the similar code for the maximum and the target.

staff: list[Employee] = [
    employee
    for employee in instance.employees
    if block.skill is None or block.skill in employee.skills
]
prefix: str = "" if block.skill is None else "skill "
assigned = sum(
    self.x[employee.id, day, shift] for employee in staff for shift in block.shifts
)
if block.min is not None:
    self._add_cover_penalty(
        f"{prefix}Min understaffing",
        block.min - assigned,
        weights["MinUnderStaffing"],
        block.min,
    )
model.py — _build_cover(), lines 403–418

Charging broken rules and unmet requests

A contract rule describes a pattern of shifts over a few days, such as no early shift on the day after a night shift. That pattern matches when a nurse works a night shift on one day and an early shift on the next. The model checks every day the pattern could start. Each hit is a true-or-false variable that is true only when every part of the pattern holds. The model then counts the hits. This rule sets its limit at zero, so the model charges for every hit.

hits: list[cp_model.IntVar] = []
for pattern in match.patterns:
    for start in self._candidate_starts(pattern, match):
        literals: list[cp_model_helper.Literal] = [
            self.literals.symbol_literal(employee.id, start + offset, symbol)
            for offset, symbol in enumerate(pattern.symbols)
        ]
        hits.append(self._hit_variable(employee.id, literals))
# …
self._add_clamped_penalty(
    "rule", match.limit.label, sum(hits), match.limit, len(hits)
)
model.py — _build_employee_rules(), lines 333–350, seven lines omitted

The method _add_clamped_penalty calculates how far a roster goes past a maximum, or how far it falls short of a minimum. The model calls it for contract rules and for caps on working hours. Suppose a nurse may work at most three of the four weekends. Working all four gives an excess of one. By contrast, working only two gives a negative excess, and nothing should be charged. The penalty variable represents the amount to charge. That is why it can never fall below zero, and why penalty >= excess stops it from understating a violation. The objective multiplies the penalty by the limit’s weight and minimizes the total, so the solver pushes it to the lowest value both bounds allow. In the weekend example, the penalty is therefore one in the first case and zero in the second.

def _add_clamped_penalty(
    self,
    group: str,
    key: str,
    observed: cp_model.LinearExprT,
    limit: Limit,
    observed_upper: int,
) -> None:
    # …
    excess = observed - limit.count if limit.sense == "max" else limit.count - observed
    upper: int = observed_upper - limit.count if limit.sense == "max" else limit.count
    penalty: cp_model.IntVar = self.model.new_int_var(
        0, max(upper, 0), f"pen_{key}_{len(self.penalties)}"
    )
    self.model.add(penalty >= excess)
    # …
    self.penalties.append(
        PenaltyTerm(group=group, key=key, expression=penalty, weight=limit.weight)
    )
model.py — _add_clamped_penalty(), lines 281–317, docstring and four lines omitted

A request covers either a whole day, whatever the shift, or particular shifts on that day. holds is true when the nurse works what the request covers. The expression 1 - holds if request.wants else holds is zero when holds matches what the nurse asked for, and one when it does not. The objective multiplies it by the request’s weight, so only an unmet request adds to the total penalty.

holds: cp_model.IntVar = (
    self.works[request.employee_id, request.day]
    if request.shifts is None
    else self.literals.in_shifts_literal(
        request.employee_id,
        request.day,
        request.shifts,
        "".join(request.shifts),
    )
)
self.penalties.append(
    PenaltyTerm(
        group="request",
        # …
        expression=1 - holds if request.wants else holds,
        weight=request.weight,
    )
)
model.py — _build_requests(), lines 485–505, four lines omitted

Minimizing the total penalty

objective() returns an expression, not a number. It multiplies every penalty in self.penalties by its own weight and adds them together. That one expression covers the broken rules, the shifts that miss the ward’s staffing levels, and the unmet requests.

def objective(self) -> cp_model.LinearExprT:
    return sum(term.weight * term.expression for term in self.penalties)
model.py — objective(), lines 507–508

The model minimizes that expression to find a roster with the lowest total penalty.

builder.model.minimize(builder.objective())
model.py — solve(), line 518

How the result is checked

Using the instance’s rules, an independent checker recomputes the roster’s total penalty from shift coverage at each skill level, contract rules on rest and working patterns, workload limits, and unmet requests. It verifies that the reported penalty matches that total.

The checker does not search for a lower-penalty roster. The solver’s “optimal” status establishes that none exists for this model and input data.