Modeling Nurse Scheduling Problem in Python (Part 1-Object Model)
Introduction
Creating a feasible, good schedules for nurses is one of the challenges faced by healthcare providers these days. It is difficult because the planners have to plan nurses adhering to some work-rest rules while maintaining level of service in a healthcare system. This problem is referred as Nurse Scheduling Problem (NRP), and it is known to belong to a mathematical class of NP-Hard. It means, there is no efficient algorithm that can solve them in polynomial time.
In this exercise, a type of NRP is taken from http://www.schedulingbenchmarks.org/nrp/ as a study case. In Part 1, we will model this problem with Object Oriented Programming (OOP) approach. In Part 2, we will model the optimizer using Python Optimization Modeling Object (Pyomo).
As a matter of fact, we actually do not need to build the object models to solve NRP with Pyomo as one optimizer run. We can just read the data and create variables and constraints directly. However, as the problem instance size grows, it is not possible to solve with a single optimizer run. One way to get a reasonably good, but not mathematically optimal solution is by using Neighborhood Search method. For this, it is easier if we have the object model. This will be done in Part 3.
Object model
Global class stores KPI attributes for both hard and soft constraints, as well as general information such as horizon length. It is linked to three main classes: Nurse class, Day class, and ShiftType class.
Nurse class contains information about nurses, such as employee ID and rules for a particular nurse. It is linked to multiple N-M classes such as NurseShiftType class, NurseDay class, and NurseDayShiftType class.
Day class contains information for a particular day, such as day ID, week ID, and a flag to indicate if a day is a weekend.
ShiftType class represents different shift types available on a particular problem instance. It stores information about a shift type, such as shift ID, length of a shift, and list of forbidden shift types that cannot follow a particular shift type.
Between Nurse class and Day class, there is a Nurse Day class that represents a day for every nurse.
Similarly, between Nurse class and ShiftType class, we create NurseShiftType class to store information about maximum number of shift planned as every nurse has a limitation to how many shifts of a certain type can be planned on him/her.
DayShiftType class contains information about number of under coverage and over coverage on a certain day, for a certain shift type.
Lastly, NurseDayShiftType class indicates if a shift type is assigned on a nurse on a certain day. In addition, it could capture penalty for on/off request adherence.
Source Code
The complete code can be found in this Github repository ‘NurseScheduling-ManualModel.ipynb’.
