Constraint Optimizing Algorithm

On-Call Optimizer uses constraint programming algorithms to solve the challenge of producing an optimal schedule.

Goals

To determine what an optimal schedule looks like, On-Call Optimizer is programmed with a series of goals that are desired for a schedule. A perfect schedule would meet every goal, an optimal schedule comes as close as possible to meeting each goal given the constraints dictated by the shift configuration of the schedule and the availability information for each of the members.

The goals that On-Call Optimizer tries to achieve focus on maximizing the balance of the schedule over the mid to long term, while also maintaining the quality of each individual assignment in the short term. Typical goals that On-Call Optimizer tries to achieve include:

• A member should not be assigned to a shift blocked in their availability information.
• Each member should have a fair share of shifts, taking into account weekends, holidays and out-of-business hours shifts as distinct types.
• A member should be assigned a shift marked as preferred in their availability information.
• A member should not have consecutive shifts.

High Level Overview

On-Call Optimizer uses a constraint satisfying algorithm to find an solution (aka assignment) that is both feasible and comes closest to meeting each goal.

The input to the algorithm starts with a set of variables referenced by a tuple of (start time, assignee role, member). So for an example assignment for a single primary assignee in a schedule of 5 members for 7 shifts, there will be 35 different shift variables input into the algorithm.

Next hard constraints which determine whether or not a particular assignment is feasible or not are configured. In the simplest case the only hard constraint would be that the sum of all variables matching (start time, assignee type, *) must be equal to 1 - e.g. only solutions that assign a single member to a shift are feasible.

After the hard constraints additional constraints representing each desired goal for the schedule are configured. Goal based constraints utilize a weight factor rather than requiring equality to a fixed value and match against particular combination of shift variables that are set to represent each potential solution, A score is calculated for each constraint in each potential solution by multiplying the value of the matching shift variables against the weight of the constraint. The overall sum of these scored constraints is reported as the “cost” of the assignment solution, and the assignment solution with the lowest overall cost represents the optimal assignment given the set of inputs.

Example weighting factors

Illustrative weighting factors for the typical goals above might look like the following:

• Any assignment matching a blocked shift: >2.0, ensuring that such assignments are only ever used as a last resort if no other possibilities exist.
• Any shift assignment above or below the ideal balance are penalized: 1.0
• Any assignment of a preferred shift: -0.5, the negative weighting results in a favourable score, making any assignment containing this shift preferred over an assignment that does not.
• Any consecutive shift assignment for a member: 0.3

In practice the specific weighting factors used are much more complex and are selected based on On-Call Optimizer’s accumulated expertise of the ideal weightings for different schedule configuration patterns.

BEST_MEMBER

The “BEST_MEMBER” placeholder is used in the shift configuration for each schedule to denote that the assignee for the specified shift should be chosen from among the members of the schedule based on the output of the above algorithm.

Therefore the “BEST_MEMBER” for a shift will be the member assigned to the shift variable for that shift in the solution that resulted in the lowest overall cost.

Importantly “best” does not mean “perfect”. In situations where there are competing constraints, the best solution may require assigning a member to consecutive shifts or ignoring their preferences in order to achieve an overall optimum assignment.