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

4 comments:

  1. In alternative 3, ShiftSwitchMove between 2 different ShiftDates will probably have to be implemented as a DoubleShiftSwitchMove.
    Copying from the TravelingTournament example, we could probably even make a MultipleShiftListRotateMove.

    ReplyDelete
  2. There's actually a very interesting alternative 4:

    Keep EmployeeAssignment with just an Employee and a Shift field (nothing else).
    Instead also create moves which add and remove EmployeeAssignment instances (instead of just changing them).

    ReplyDelete
  3. I've updated this post with the ability to do the 2 optional features and 2 more alternatives: 2B and 4. In light of those updates, I 've also adjusted my conclusion.

    ReplyDelete
  4. I got this private comment which makes a good point: "In talking with some nurses, double shifts are sometimes required, depending on the shift length. In some hospitals, nurses work 8 hour shifts and, sometimes, 2 shifts in a day could be required. In other hospitals shifts are 12 hours, in which case 2 shifts are not possible."

    ReplyDelete