Solving the Nurse Rostering Problem using Google OR-Tools
Enhancing workforce scheduling with Operational Research
tldr:
- Nurse Rostering is a complex optimization problem and constraint programming is a promising method for solving it.
- Using the cloud, it’s conceivable to automate rotation generation and integrate optimization into the existing enterprise infrastructures.
- Open-source tech can be used to conveniently tackle small and medium instances of NRP, but for large instances, more sophisticated custom algorithms are necessary.
- This post builds on GoogleORTools examples by adding more practical constraints from real world examples: repo.
Intro
The Nurse Rostering Problem (NRP), a.k.a Rotation Automation, focuses on finding an optimal way to assign shifts to nurses in order to create employee rosters (rotations). There is a set of hard constraints that all feasible solutions adhere to. A set of soft constraints define the relative quality between feasible solutions.
Solving NRP is one of the most critical steps of workforce planning in healthcare systems such as hospitals, clinics, long-term care facilities, etc. Commonly, this is a manual process where one (or more) experts with years of experience (and a bank of historical solutions) create a new rotation. This process is initiated when a given unit needs to update its rotation, i.e., re-arrange the shift assignments, due to particular changes in the staffing or requirements (e.g., expansion of the unit, budget variations, change in the staff, and other clinical and operational necessities).
In real-world situations, creating a new rotation could be as simple as changing an existing similar solution or as laborious as a multi-month effort involving numerous experts in more complex instances. Automating the development of the rotations is, therefore, a natural fit as an Operations Research (OR) solution. Productionizing such an OR Product will provide the specialists with the flexibility and assurance of quickly generating new rotations that adhere to the rules and regulations and meet the tactical and operational requirements.
Methods
The academic community and the business world have given NRP much attention. It is a well-known combinatorial optimization problem (e.g., Cheang et. al. 2003, and Ngoo et al. 2022); exact and heuristic methods have been suggested to solve NRP effectively. The accessibility of open-source optimization engines like Google OR-Tools, GLPK, SciPy, etc. and the ongoing improvements in the on-demand availability of affordable computing resources pave the way for productionizing these optimization models and solution algorithms.
Constraint programming (CP) is one of the best-suited methodologies for modelling and solving small and medium-sized practical instances of NRP. In a constraint programming model, feasible solutions are sought, given a set of mathematical constraints on the properties of the solutions. Google OR-Tools is one of the leading open-source optimization engines capable of solving CP models with competitive performance:
Examples of employee scheduling problems are formulated and solved in the documentation of Google OR-Tools. The formulation coded in this post is a modification of the example from the or-tools GitHub repo. To tackle NRP instances used in practical settings, new variables and constraints are added to the OR-Tools example, and the constraints are revised accordingly. The models are solved using the CP-SAT solver.
Definitions
In an NRP instance, there are commonly different types of shifts (off, morning, day, evening, night, etc.) with various but pre-specified start times and lengths. Each nurse may have characteristics, such as particular skill sets, employment type, etc. These are expressed in the CP model’s parameters and constraints. Daily requirements for each type of shift are inputs to the NRP models. Also, the number of open positions for each type (i.e., full-time or part-time) is given. In the context of NRP, these inputs are specified by the management of the nursing units based on budgetary, operational, demand forecasts, clinical aspects, etc.
Hard constraints are usually declared as a collective agreement between unions, government entities, healthcare authorities, and other stakeholders. Therefore, these constraints may vary by location, jurisdiction, hospital, or even by nursing unit. As an example, the following are the hard constraints (published by the BCNU) that partially govern the feasibility of the NRP solutions in BC, Canada:
- The minimum number of consecutive off-shifts is predefined.
- The minimum and the maximum number of consecutive on-shifts are predefined.
- The maximum number of working weekends is predefined.
- The minimum and maximum annual working hours are predefined based on the type of part- or full-time position.
- A set of forbidden/penalized combinations (e.g., a morning shift can not be preceded by a night shift) is given.
- Rotation must be repeatable: given a rotation with H weeks, a new rotation generated by repeating this rotation to cover 2*H weeks must not violate any of the above constraints).
In addition to the constraints imposed by the governing entities, such as the above rules, there are other constraints that are specific to nursing units, sites, etc. An example of these constraints is the number of full-time nurses working on the weekends. The management may decide on a minimum number of full-time (or higher-skilled) employees on any given shift on weekends to assure a certain level of quality. Another example is the required coverage (number of working staff) per shift which is dictated by the budgets, demand, staff availability, etc. These forms of constraints may be formulated as hard or soft constraints. Soft constraints could be weighted based on their importance/desirability in which case minimizing the overall penalty is the objective function in a CP. In the presented model, the following operational constraints are considered:
- No weekend without a full-time staff member: hard constraint.
- The required coverage per day is predefined as soft-constraint.
- The number and placement of pre-specified assignments and force-off (e.g., St. holidays) for each position/nurse are given.
The decision variables in an NRP model are the assignment of nurses on each day:
- Off-shift (O): days that the nurse does not work,
- On-shifts (s): days that the nurse works in a particular shift of type s.
A solution to an NRP instance could be represented as a two-dimension matrix of N*H where N is the number of available employees, and H is the length of the planning horizon (conventionally, the first day is a Friday). This is commonly referred to as a line rotation NRP instance.
Example 1. A basic line-rotation instance
A simple example of a feasible rotation is shown in the figure below. In this instance, the planning horizon is eight weeks and there are five nurses (a.k.a., lines or positions). There are two full-time positions and three part-time positions. There are three types of shifts: day shift (d), off day (O), and force-off shift (FO). Force-off shifts are commonly predetermined, e.g., to ensure a minimum number of statutory holidays for each employee or to meet certain requests from the employee. In this example, each nurse receives two force-off shifts. The maximum number of working weekends is five, with a working weekend defined as when a nurse works Saturday and/or Sunday. The requirements are 3 “day” (d) shifts per day.
Formulation
The decision variables, constraints, and objective function are reflected in the code developed using Google OR-Tools in C#. The input parameters and decision variables defined as the boolean type are defined as follows:
The most fundamental constraint is that exactly one shift must be assigned per day per nurse.
An example of common constraints in NRP, we need to ascertain that the number of consecutive on-shifts assigned to each nurse does not exceed the given limits when it’s a hard constraint (hard_min, hard_max). Also, we want to penalize undesirable violations (SoftMin, MinPenalty, MaxPenalty). To do so, we define a parameter with five values for each shift type and use them to add a set of constraints to the model:
The ¬ sign is the “NOT” or the logical negation symbol. These constraints assert that for any given shift type and nurse, we will never have a sequence longer than the HardMax. To see the full implementation and more details of this type of constraint, see this. To learn more about all the possibilities that a CP-model in OR-Tools offers for formulating real-world constraints, see CPModelBuilder documentation.
Example 2. A medium-sized real instance
A larger instance of NRP is described when we consider:
NumDays = 147 (21 weeks)
Shifts = { "O", "d", "n" }Coverage demand parameters state the number of the required number of shifts per day:
var r_sd = new[]
{
new[] { 7, 3 }, // Friday
new[] { 3, 0 }, // Saturday
new[] { 8, 3 }, // Sunday
new[] { 8, 3 }, // Monday
new[] { 8, 3 }, // Tuesday
new[] { 8, 3 }, // Wednesday
new[] { 8, 3 }, // Thursday
};Sequence constraint parameters define the tolerable range of consecutive assignments for each type of shift. For instance, assume we want to assure a minimum of 2 and a maximum of 5 consecutive assignments of off-shift as a hard constraint. Then we define:
shiftConstrain_0 = (0, 2, 2, 0, 5, 5, 0)to set the hard and soft minimum to 2, and to set the hard and soft maximum to 5, while penalties are set to 0, which means this is a hard constraint and violation is not accepted. This type of constraint could be built using the AddBoolOr method in the OR-Tools:
foreach (var constraint in shiftConstraints)
foreach (int e in Range(NumEmployees))
{
foreach (var start in Range(works.GetLength(0)))
{
var temp = Range(start, start + constraint.HardMax + 1)
.Select(d => d < NumDays
? works[d].Not()
: works[d - NumDays].Not()).ToList();
model.AddBoolOr(temp);
}
}To see other parameters and constraints of this NRP instance, refer to the source code in this GitHub repo.
Solving the Model
Once the model is formulated and coded, the next question is on the computation resources required to solve a mid-size instance of NRP. We commonly use a local environment to test the model before running real instances in the production environment, which is likely a cloud provider environment.
To run the model on a local machine, install Google OR-Tools (see the docs here). Then, clone the repo and run using .Net Core (see here).
The performance of the solver on this NRP instance when run on a machine with a 12th Gen Intel® Core™ i9–12900K (16 core, 24 threads) processor is shown below:
Each run stops as soon as the first optimal solution is found. On average, it took the solver 89 minutes of CPU time and 144 infeasible solutions to find the first optimal solution. These runs resulted in different optimal solutions. To solve the optimization problem, the solution algorithm uses stochastic processes that produce varying results and computation times between runs.
In practice, multiple feasible solutions are needed so that the workforce specialist can select amongst them if necessary. This is easily possible using OR-Tools support for the parallel use of multi-core CPUs (ref. here for a benchmark). Furthermore, by running multiple instances of the model on a cluster, higher computation resources could be utilized when needed.
Future Work
Model Extensions
In practice, many other factors differentiate nurses in terms of their specialty, skill levels, seniority, etc. Also, there are usually many operational and clinical constraints unique to each organization that must be considered. Formulating these parameters and constraints in the NRP models is relatively straightforward; however, as the complexity of the model increases, the computational costs may become unbearable. Soft computing methodologies have proven particularly useful when the most complex practical instances are targeted; see e.g. here and here.
Deployment
NRP solutions in real systems must be integrated with other workforce planning decisions. This poses the opportunity to embed the solutions into the existing IT systems. To achieve this while establishing an organized approach for future development and maintenance, an automated CI/CD pipeline has to be established. User interfaces are required to receive the model inputs, present the results, and perhaps gather nurses’ inputs (e.g., to include nurses’ preferences in the model; see e.g., here).
An attractive option is to use cloud providers such as GCP, AWS, Azure, etc., to productionize OR models similar to those presented here. The required resources in terms of computational time and cost could be minimized by leveraging the accessibility of large computation machines/clusters and the pay-as-you-go costing structure of the cloud.
Practical Implications
Developing efficient rotations is one of the critical steps of workforce planning in healthcare systems. Not only do rotations directly impact the operational capacity and status of the wards, but job satisfaction is also impacted. Therefore, there is commonly a hesitance to alter rotations and NRP solutions are rarely revised at monthly/annual intervals; instead, they are developed/updated when necessary.
Streamlining the process of creating and implementing rotations while providing a way of incorporating nurses’ inputs into this process could lead to a systematic method for developing and maintaining optimized rotations. As such, developing fast and reliable algorithms that can deal with large and complex instances and harnessing cloud resources (to minimize time-to-user, development and deployment costs, and operation costs) is a promising strategy. Correctly implemented, this could lead to significant savings while elevating service quality and job satisfaction.
