## Nurse rostering: design choices

While designing and implementing the Nurse Rostering example for Drools Planner, I am faced with a difficult design choice. In this blog I ‘ll describe the problem, the choices and my decision.

## Concepts and domain classes

• Employee: a person

• For example:

• Ann

• Beth

• Carla

• Number of Employees: problem specific

• Presume 20 Employees

• ShiftType: part of a day

• For example:

• E: Early from 6:00 till 14:00

• L: Late from 14:00 till 22:00

• Number of ShiftTypes: problem specific

• Presume 4 ShiftTypes

• ShiftDate: simply a date (year, month and day)

• For example:

• 2010-01-01

• 2010-01-02

• Number of ShiftTypes: problem specific

• Presume 100 ShiftDates

• Shift: a ShiftType on a certain ShiftDate

• For example:

• 2010-01-01 E

• 2010-01-01 L

• 2010-01-02 E

• Number of Shifts: ShiftDates * ShiftTypes

• 4 * 100 = 400 Shifts

• Each shift has to be covered by a number of required Employees

• requiredEmployeeSize: problem and shift specific

• Presume a requiredEmployeeSize of 3 for every shift

• Can a shift may have more employees working than there are required? No, not in the competition.

• Optional feature moreEmployeesThanRequired: Support more employees working on a shift than required to be modeled as a soft constraint.

• For example: 5 Employees working on a shift that requires 3 Employees.

• This might be needed so an Employee can get a full week’s work.

• EmployeeAssignment: an Employee working in a certain Shift

• For example:

• Ann -> 2010-01-01 E

• Beth -> 2010-01-01 E

• Carla -> 2010-01-01 L

• Only the EmployeeAssignment class changes during planning.

• Although I could also used an Employee List on Shift, I already know I wanted a design with a separate EmployeeAssignment class.

• This way, the Shift class does not change once the planning starts moving things around.

• Also, the score rules will be simpler. They will not contain backwards chaining statements such as “contains”. For example:

• rule “canNotWorkOnSunday”
when
$e : Employee() EmployeeAssignment(employee ==$e, shift.shiftDate.dayOfWeek == DayOfWeek.SUNDAY);
then …

• The EmployeeAssignment class only has an Employee field and a Shift field at the moment, nothing more.

## Constraints and score rules

There are 2 hard constraints:

• oneAssignmentPerDay

• Each Employee may only work 1 Shift per day (so only 1 Shift per ShiftDate).

• Optional feature multipleAssignmentsPerDay: Support 2 shifts on the same day (for example 2 shifts of 4 hours) to be modeled as a soft constraint.

• requiredEmployeeSizePerShift

• Each Shift must be equal to its requiredEmployeeSize.

• Optional feature moreEmployeesThanRequired: Support more employees working on a shift than required to be modeled as a soft constraint.

The soft constraints do not factor into this design decision at the moment.

## Moves

What kind of planning moves can we expect?

• ChangeMove

• Give an Employee an extra Shift or take one Shift away.

• SwitchMove

• Between 2 Employees, trade 1 Shift of each Employee.

Later on, more course-grained moves can be added too.

## Design alternatives

Let’s take a look at the design alternatives and their advantages (+) and disadvantages (-).

### Alternative 1:

• Introduce the concept of “active” EmployeeAssignments.

• Make an EmployeeAssignment for every combination of Employee and Shift

• Mark each EmployeeAssignment if it is active or not

• The class EmployeeAssignment gets an extra a boolean field called “active”.

• For example:

• Ann -> 2010-01-01 E is ACTIVE

• Ann -> 2010-01-01 L is INACTIVE

• Ann -> 2010-01-02 E is INACTIVE

• Ann -> 2010-01-02 L is ACTIVE

• EmployeeAssignment size: Employees * Shifts

• 20 * 400 = 8000 EmployeeAssignments

• Impact on score rules:

• oneAssignmentPerDay is natural (+)

• An Employee with 2 active EmployeeAssignments on the same ShiftDate

• Optional feature multipleAssignmentsPerDay is possible

• requiredEmployeeSizePerShift is an accumulate (-)

• A Shift where the count of active EmployeeAssignments is too little (or too big)

Optional feature moreEmployeesThanRequired is possible

• Move design:

• EmployeeChangeMove is easy (+)

• Turns one EmployeeAssignments active or inactive.

• Only doable if one of the 2 traded EmployeeAssignments is active

• So most EmployeeSwitchMoves are not doable.

### Alternative 2:

• Introduce the concept of “required” and “optional” EmployeeAssignments.

• Make an required EmployeeAssignment for each required assignment per shift

• The class EmployeeAssignment gets an extra a boolean field called “required”.

• An required EmployeeAssignment never has a null Employee

• Make an optional EmployeeAssignment for each optional assignment per shift

• An optional EmployeeAssignment can have a null Employee

• For example:

• Ann -> 2010-01-01 E required

• Beth -> 2010-01-01 E optional

• Ann -> 2010-01-02 E required

• null -> 2010-01-02 E optional

• required EmployeeAssignment size: requiredEmployeeSize * Shifts

• 3 * 400 = 1200 EmployeeAssignments

• optional EmployeeAssignment size: (Employees – (requiredEmployeeSize * ShiftTypes)) * Shifts

• (20 – (3 * 4)) * 400 = 3200 EmployeeAssignments

• total EmployeeAssignment size

• 1200 + 3200 = 4400 EmployeeAssignments

• Impact on score rules:

• oneAssignmentPerDay is natural (+)

• An Employee with 2 EmployeeAssignments on the same ShiftDate

Optional feature multipleAssignmentsPerDay is possible

• requiredEmployeeSizePerShift is build-in (?)

• No need to write a score rule (+)

• Less moves, smaller search space (+)

• Could make it harder to escape from a local optimum region and create a score trap (-)

• Optional feature moreEmployeesThanRequired is still possible

• Move design:

• EmployeeChangeMove is incomplete (-)

• Gives one EmployeeAssignment another Employee or null

• A required EmployeeAssignments can never get null

• It’s impossible to remove an Employee from a certain Shift if that Employee is assigned into a required EmployeeAssignment

• A more complex move can move in another employee which has an optional EmployeeAssignment for that shift

• If and only if such an optional EmployeeAssignment exists.

• EmployeeSwitchMove is natural (+)

• Not doable if the 2 traded EmployeeAssignments have the same Shift

### Alternative 2B:

• All EmployeeAssignments are “required”, there are no “optional” EmployeeAssignments.

• Make an EmployeeAssignment for each required assignment per shift

• An EmployeeAssignment never has a null Employee

• For example:

• Ann -> 2010-01-01 E

• Ann -> 2010-01-02 E

• EmployeeAssignment size: requiredEmployeeSize * Shifts

• 3 * 400 = 1200 EmployeeAssignments

• Impact on score rules:

• oneAssignmentPerDay is natural (+)

• An Employee with 2 EmployeeAssignments on the same ShiftDate

Optional feature multipleAssignmentsPerDay is possible

• requiredEmployeeSizePerShift is build-in (?)

• No need to write a score rule (+)

• Less moves, smaller search space (+)

• Could make it harder to escape from a local optimum region and create a score trap (-)

• Optional feature moreEmployeesThanRequired is NOT possible

• Move design:

• EmployeeChangeMove is easy (+)

• Gives one EmployeeAssignment another Employee (never null)

EmployeeSwitchMove is natural (+)

• Not doable if the 2 traded EmployeeAssignments have the same Shift

### Alternative 3:

• Make an EmployeeAssignment for every combination of Employee and ShiftDate

• The EmployeeAssignment class gets an extra field ShiftDate.

• An EmployeeAssignment cannot have a Shift with a different ShiftDate.

• An Employee that does not work on a certain ShiftDate has a Shift null.

• For example:

• Ann on 2010-01-01 -> 2010-01-01 E

• Beth on 2010-01-01 -> 2010-01-01 E

• Ann on 2010-01-02 -> 2010-01-02 E

• Beth on 2010-01-02 -> null

• EmployeeAssignment size: Employees * ShiftDates

• 20 * 100 = 2000 EmployeeAssignments

• Impact on score rules:

• oneAssignmentPerDay is build-in (?)

• No need to write a score rule (+)

• Less moves, smaller search space (+)

• Optional feature multipleAssignmentsPerDay is NOT possible: Utterly impossible to give an Employee 2 Shifts on the same day (-)

• Even if the 2 Shifts are only 4 hours long

• Even if the hospital really needs it

• requiredEmployeeSizePerShift is an accumulate (-)

• A Shift where the count of EmployeeAssignments is too little (or too big)

• Optional feature moreEmployeesThanRequired is possible

• Move design:

• ShiftChangeMove is easy (+)

• Give one EmployeeAssignment another Shift or null

• Do not generate a ShiftChangeMove for an EmployeeAssignment a Shift with a different ShiftDate

• ShiftSwitchMove is a complicated (-)

• Only doable if the 2 traded EmployeeAssignments have a different Shift

• Switching 2 Shifts on different ShiftDates is hard. However my experiment showed that without such a move, it does not rival against alternative 2B.

### Alternative 4:

• Keep EmployeeAssignment with just an Employee and a Shift field (nothing else).

• An EmployeeAssignment never has a null Employee

• For example:

• Ann -> 2010-01-01 E

• Beth -> 2010-01-01 E

• Ann -> 2010-01-02 E

• EmployeeAssignment size: not fixed. Probably at least requiredEmployeeSize * Shifts and maybe at most double.

• Probably at least 3 * 400 = 1200 EmployeeAssignments and maybe at most 2 * 1200 = 2400 EmployeeAssignments.

• Impact on score rules:

• oneAssignmentPerDay is natural (+)

• An Employee with 2 EmployeeAssignments on the same ShiftDate

Optional feature multipleAssignmentsPerDay is possible

• requiredEmployeeSizePerShift is an accumulate (-)

• A Shift where the count of active EmployeeAssignments is too little (or too big)

Optional feature moreEmployeesThanRequired is possible

• Move design:

• EmployeeChangeMove is easy (+) (but requires EmployeeAssignmentAddMove and EmployeeAssignmentRemoveMove too)

• Gives one EmployeeAssignment another Employee (never null)

• EmployeeAssignmentAddMove and EmployeeAssignmentRemoveMove is hard (-)

• Creates or removes one EmployeeAssignment from the solution. There might a lot of potential to optimize a MoveFactory which generates both moves.

• EmployeeSwitchMove is natural (+)

• Not doable if the 2 traded EmployeeAssignments have the same Shift

## Design decision

After writing down this updated analysis and an experiment with alternative 3, I ‘ve chosen for alternative 2B. However, if the use case would require to support optional features multipleAssignmentsPerDay and moreEmployeesThanRequired, I would extend it to alternative 4.

Do you think I made the right decision? Why (not)?