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
Let’s start with the relevant 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.
EmployeeSwitchMove is bad (-)
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)?
