Roster/Timetable generation

Question

I'm working on a tool to generate a timetable for employee up to a month taking into account commercial and labor law constraints. Few challenges and difference from similar problem:

• The shift concept contains breaks split up to half an hour.
• There is no concept of full 8 shifts as the referred similar problem. e.g. There is a need to have 2 resources at 8am, 2.5 resources at 3PM (e.g. give half hour break)..
• and regular constraints like hours per day, hours before break, break time...

Possible solutions is to rely on using a solver aka OR-Tools and Optaplanner. any hints?

Answer 1

If you go with OptaPlanner and don't want to follow the Employee Rostering design of assigning 8 hours Shifts (planning entities) to Employees (planning value), because of your 2th constraint, then you could try to follow the Cheap Time Example design, something like this:

@PlanningEntity public class WorkAssignment {
     Employee employee;
     @PlanningVariable PotentialShiftStartTime startTime
     @PlanningVariable int durationInHalfHours
}

PotentialShiftStartTime is basically any time a shift can validly start, so Mon 8:00, Mon 8:30, Mon 9:00, etc.

The search space will be huge, in this free form way, but there are tricks to improve scalability (Nearby Selection, pick early for CH, Limited Selection for CH, ...).

To get out of the free form way (= to reduce the search space), you might be able to combine startTime and durationInHalfHours into PotentialShift, if for example it's not possible to start a 8 hour shift at 16:00 in the afternoon. But make sure the gain is huge before introducing that complexity.

In any case, the trouble with this design is determining how many WorkAssignment instances to create. So you'll probably want to create the max number possible per employee and work with nullable=true to ignore unused assignments.