Employee rostering with Optaplanner. Hard constraint is broken but hard score is not deducted

Viewed 38

I am using Optaplanner for shift rostering. I have an "atLeast12HoursBetweenTwoShifts" constraint that prevent the same employee having 2 shift assignments within 12 hours. This constraint should penalize any invalid pairs of shift assignments with a hard score of (12 - the hourly duration between the 2 shift assignments). However, after I run the solver, I can see shift assignments that violates this rule appear in the solution without any hard score deduction such as the following:

15:24:02.832 [main        ] INFO  Solving started: time spent (43), best score (-25init/0hard/0soft), environment mode (REPRODUCIBLE), move thread count (NONE), random (JDK with seed 0).
15:24:02.881 [main        ] INFO  Construction Heuristic phase (0) ended: time spent (92), best score (0hard/-109soft), score calculation speed (3682/sec), step total (25).
15:24:07.789 [main        ] INFO  Local Search phase (1) ended: time spent (5000), best score (0hard/-105soft), score calculation speed (136883/sec), step total (33460).
15:24:07.790 [main        ] INFO  Solving ended: time spent (5000), best score (0hard/-105soft), score calculation speed (134313/sec), phase total (2), environment mode (REPRODUCIBLE), move thread count (NONE).

...

ShiftAssignment{shiftId='1', employeeId=4, employeeRoles=[Design], roleRequired='Design', time=2022-11-24,09:00~12:00}
ShiftAssignment{shiftId='1', employeeId=5, employeeRoles=[Design], roleRequired='Design', time=2022-11-24,09:00~12:00}
ShiftAssignment{shiftId='2', employeeId=3, employeeRoles=[Clean], roleRequired='Clean', time=2022-11-24,15:00~17:00}
ShiftAssignment{shiftId='3', employeeId=2, employeeRoles=[Dev], roleRequired='Dev', time=2022-11-24,20:00~23:00}
ShiftAssignment{shiftId='3', employeeId=6, employeeRoles=[Design, Dev], roleRequired='Dev', time=2022-11-24,20:00~23:00}

ShiftAssignment{shiftId='1', employeeId=5, employeeRoles=[Design], roleRequired='Design', time=2022-11-25,09:00~12:00}
ShiftAssignment{shiftId='1', employeeId=6, employeeRoles=[Design, Dev], roleRequired='Design', time=2022-11-25,09:00~12:00}
ShiftAssignment{shiftId='2', employeeId=3, employeeRoles=[Clean], roleRequired='Clean', time=2022-11-25,15:00~17:00}
ShiftAssignment{shiftId='3', employeeId=1, employeeRoles=[Dev], roleRequired='Dev', time=2022-11-25,20:00~23:00}
ShiftAssignment{shiftId='3', employeeId=2, employeeRoles=[Dev], roleRequired='Dev', time=2022-11-25,20:00~23:00}

In this case employee with id 6 should not have shift at 9:00~12:00, 2021-12-25 because he took the shift at 20:00~23:00, 2021-12-24 (just 10 hours between those 2 shift assignments). Those 2 shift assignments are scheduled without hard score deduction to indicate the break of rule. It's like Optaplanner forgot applying "atLeast12HoursBetweenTwoShifts" constraint on those 2 shift assignments. Why this situation happened and what should I do to prevent such situation?

My models that are related to this problem:

@Data
@PlanningEntity
public class ShiftAssignment {

    @PlanningId
    private String id;

    @PlanningVariable(valueRangeProviderRefs = "employeeRange")
    private Employee employee;

    private String role;

    private Shift shift;

    private Map<String, Boolean> conflicts = new HashMap<>() {{
        put("hourlyGap", false);
        put("dailyGap", false);
    }};

    public ShiftAssignment(String id, String role, Shift shift) {
        this.id = id;
        this.role = role;
        this.shift = shift;
    }

    public ShiftAssignment(String id, String role, Shift shift, Employee employee) {
        this.id = id;
        this.role = role;
        this.shift = shift;
        this.employee = employee;
    }

    public ShiftAssignment() {
    }

    public LocalDate getDate() {
        return shift.getEndAt().toLocalDate();
    }
}
@Data
public class Employee {

    private Long id;

    private String name;

    private Set<String> roleSet;

    public Employee(Long id, String name, Set<String> roleSet) {
        this.id = id;
        this.name = name;
        this.roleSet = roleSet;
    }

    public Employee() {
    }
}
@Data
@PlanningSolution
public class Schedule {

    @PlanningScore
    private HardSoftScore score;

    @ValueRangeProvider(id = "employeeRange")
    @ProblemFactCollectionProperty
    private List<Employee> employeeList;

    @PlanningEntityCollectionProperty
    private List<ShiftAssignment> shiftAssignmentList;

    public Schedule(List<Employee> employeeList, List<ShiftAssignment> shiftAssignmentList) {
        this.employeeList = employeeList;
        this.shiftAssignmentList = shiftAssignmentList;
    }

    public Schedule() {
    }
}

My constraint provider class:

public class ScheduleConstraintProvider implements ConstraintProvider {

    @Override
    public Constraint[] defineConstraints(ConstraintFactory constraintFactory) {
        return new Constraint[]{
            atLeast12HoursBetweenTwoShifts(constraintFactory),
            atMostOneShiftPerDay(constraintFactory),
            evenlyShiftsDistribution(constraintFactory),
            onlyRequiredRole(constraintFactory)
        };
    }

    public Constraint atLeast12HoursBetweenTwoShifts(ConstraintFactory constraintFactory) {
        // any employee can only work 1 shift in 12 hours

        return constraintFactory
            .forEachUniquePair(
                ShiftAssignment.class,
                Joiners.equal(ShiftAssignment::getEmployee),
                Joiners.lessThanOrEqual(
                    (shiftAssignment1) -> shiftAssignment1.getShift().getEndAt(),
                    (shiftAssignment2) -> shiftAssignment2.getShift().getStartAt()
                )
            )
            .filter((firstShift, secondShift) -> Duration.between(
                firstShift.getShift().getEndAt(),
                secondShift.getShift().getStartAt()
            ).toHours() < 12)
            .penalize(
                "atLeast12HoursBetweenTwoShifts",
                HardSoftScore.ONE_HARD,
                (first, second) -> {
                    int breakLength = (int) Duration.between(
                        first.getShift().getEndAt(),
                        second.getShift().getStartAt()
                    ).toHours();
                    return 12 - breakLength;
                });
    }

    public Constraint atMostOneShiftPerDay(ConstraintFactory constraintFactory) {
        // an employee can only work 1 shift per day

        return constraintFactory
            .forEachUniquePair(
                ShiftAssignment.class,
                Joiners.equal(ShiftAssignment::getEmployee),
                Joiners.equal(ShiftAssignment::getDate)
            )
            .penalize(
                "atMostOneShiftPerDay",
                HardSoftScore.ONE_HARD
            );
    }

    public Constraint evenlyShiftsDistribution(ConstraintFactory constraintFactory) {
        // try to distribute the shifts evenly to employees

        return constraintFactory.forEach(ShiftAssignment.class)
            .groupBy(ShiftAssignment::getEmployee, ConstraintCollectors.count())
            .penalize(
                "evenlyShiftsDistribution",
                HardSoftScore.ONE_SOFT,
                (employee, shifts) -> shifts * shifts);
    }

    public Constraint onlyRequiredRole(ConstraintFactory constraintFactory) {
        // a shift can only be assigned to employees with roles it needs

        return constraintFactory
            .forEach(ShiftAssignment.class)
            .filter(
                shiftEmployee -> {
                    String requiredRole = shiftEmployee.getRole();
                    Set<String> providedRoles = shiftEmployee.getEmployee().getRoleSet();

                    return !providedRoles.contains(requiredRole);
                }
            )
            .penalize(
                "onlyRequiredRole",
                HardSoftScore.ONE_HARD,
                (shiftEmployee) -> 12
            );
    }

}

My main app:

        SolverConfig solverConfig = new SolverConfig();

        solverConfig
            .withSolutionClass(Schedule.class)
            .withEntityClasses(ShiftAssignment.class)
            .withConstraintProviderClass(ScheduleConstraintProvider.class)
            .withTerminationSpentLimit(Duration.ofSeconds(5));

        SolverFactory<Schedule> scheduleSolverFactory = SolverFactory.create(solverConfig);

        Schedule dataset = Data.generateData();

        Solver<Schedule> solver = scheduleSolverFactory.buildSolver();
        Schedule schedule = solver.solve(dataset);
        
        SolutionPrinter.printResult(schedule);
1 Answers

Write a ConstraintProviderTest (just like in the quickstarts) to verify if your constraints behave the way you expect them to behave. Don't do that through calling solve().

Why? It allows you to test your constraints quickly and in isolation.

In this case employee with id 6 should not have shift at 9:00~12:00, 2021-12-25 because he took the shift at 20:00~23:00, 2021-12-24 (just 10 hours between those 2 shift assignments).

I suspect if you write such a unit test for the hard constraint that prevents this and you feed this data to the constraint verifier of that constraint, you'll get 0 hard constrains broken (because your ending score is 0hard already). From there, it will be a lot easier to debug what's going and fix it, or when that fails, post a much shorter StackOverflow question focused only on the constraint that is problematic.

Related