How to avoid using multiple planning entities in a task assignment problem?

Question

I am trying to avoid implementing a second genuine planning entity in my model. This is essentially a combination of nurse rostering and task assignment:

The business process is to assign staff members to activities over a time period (typically a week or two). Each activity may require multiple staff. The system is also required to determine which staff members are at work, on days off, or on leave for each day, in accordance with their employment contract (a hard constraint).

A simplified version of the relevant model components is below. I have omitted some boilerplate (accessors, etc.) for clarity:

enum DayType {
    WORKING,
    LEAVE,
    OFF
}

@DeepPlanningClone
class StaffMember {
    final int contractedDays;
    final Collection staffDays;
}

@DeepPlanningClone
class Day {
    final LocalDate date;
    final Collection staffDays;
    final Collection activities;
}

@DeepPlanningClone
class Activity {
    final Day day;
    final Collection assignments;
}

@PlanningEntity
class Assignment {
    final Activity activity;
    // Skill requirements, etc., for this assignment

    // Nullable as business prefers to leave unassigned rather
    // than assign an underskilled staff member. Also filtered to
    // exclude StaffMemberDay instances from different Days to the
    // Activity.
    @PlanningVariable(valueRangeProviderRefs = {"staffDays"}, nullable = true)
    StaffMemberDay assignedStaffMemberDay;
}

@PlanningEntity
class StaffMemberDay {
    final StaffMember staffMember;
    final DayType request;
    final DayType override;

    @InverseRelationShadowVariable(sourceVariableName = "assignedStaffMemberDay")
    Collection assignments;

    @CustomShadowVariable(
        variableListenerClass = StaffMemberDayVariableListener.class,
        sources = {@PlanningVariableReference(variableName = "assignments")})
    DayType actual;
}


class StaffMemberDayVariableListener implements VariableListener {

    // afterEntityAdded, afterVariableChanged, etc., just call updateVariables()

    protected void updateVariables(ScoreDirector scoreDirector, StaffMemberDay day) {
        scoreDirector.beforeVariableChanged(day, "actual");

        if (day.override != null) {
            // human planner has decided
            day.actual = day.override;
        } else if (request == DayType.WORKING) {
            // people are always at work if they want to be
            day.actual = DayType.WORKING;
        } else if (day.assignments.size() == 0) {
            // can grant any leave / day off request, otherwise day off.
            // solver should never give leave unless specifically requested
            if (day.request != null) {
                day.actual = day.request;
            } else {
                day.actual = DayType.OFF;
            }
        } else {
            // assigned an activity, required to be at work.
            day.actual = DayType.WORKING;
        }

        scoreDirector.afterVariableChanged(day, "actual");
    }
}

// Constraints

// Solver assigned a staff member that the human planner had
// explicitly wanted to be off or on leave.
factory.forEach(Assignment.class)
       .filter(a -> a.assignedStaffMemberDay.actual != DayType.WORKING)
       .penalize(HardMediumSoftScore.ONE_HARD);

// Staff are paid while on leave, so only days off are excluded.
factory.forEach(StaffMemberDay.class)
       .filter(x -> x.actual != DayType.OFF)
       .groupBy(StaffMemberDay::getStaffMember, count())
       .penalize("contractViolated",
                 HardMediumSoftScore.ONE_HARD
                 (sm, n) -> Math.abs(sm.contractedDays - n));

// Unqualified assignment: 2 medium per missing skill
// Empty assignment: 1 medium.

I am trying to find a way to make StaffMemberDay.actual = WORKING when not assigned anything, without implementing a second genuine planning variable on StaffMemberDay. It is possible (but improbable) that there may be insufficient activities to ensure each staff member meets their contract, so this edge case must be covered.

At the moment, the only other way I can think of is to create a dummy Activity for each Day with enough Assignment objects and a soft penalty if left empty. I can do this as part of my solution loading code, but the whole idea seems a bit of a kludge:

factory.forEachIncludingNullVars(Assignment.class)
       .filter(x -> x.assignedStaffMemberDay == null && x.activity.isDummy)
       .penalize(HardMediumSoftScore.ofSoft(10));

factory.forEachIncludingNullVars(Assignment.class)
       .filter(x -> x.assignedStaffMemberDay == null && !x.activity.isDummy)
       .penalize(HardMediumSoftScore.ONE_MEDIUM);

Some additional points:

The business refuses to entertain the concept of multi-stage planning, even if it were designed to ensure a minimum skill mix on each day, or enabled them to better optimise their other objectives.
I have previously modelled this with StaffMemberDay using a genuine planning variable and Assignment assigning StaffMember directly. As expected, it got stuck in local optima which required a custom move that would almost never improve the solution under normal conditions, and wasn't selected often enough to escape the local optimum in a reasonable timeframe when it occurred.
From reading the documentation and Geoffrey's comments on here and optaplanner-dev that good use cases for multiple genuine entities are rare, I am very hesitant to go down that path (again).

Any comments, thoughts or suggestions would be greatly appreciated. Sorry if I should have asked this on optaplanner-dev, but both seem friendly & supportive.

How to avoid using multiple planning entities in a task assignment problem?

0 Answers