Sunday, March 28, 2010

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

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)?