Is optaplanner scheduling AI suitable for optimising a college schedule?

Question

Optaplanner school timetabling examples show different problems than what I need to solve.

The problem:

Let's have three courses: Math, English, History

All these courses offer multiple timeslots (parallels) and the student gets to choose one of them for each.

Let's say:

Math: Monday: 9:00 - 10:00, Tuesday: 10:00 - 11:00

English: Monday: 9:00 - 10:00, Tuesday: 11:00 - 12:00, 14:00 - 15:00, Friday: 16:00 - 17:00

History: Tuesday: 10:00 - 11:00, Friday: 10:00 - 11:00

I would like to find the best possible timeslot for each of these courses. By the best I mean the one with the least amount of gaps and, more importantly, the one which lets you have the most free days.

The optimal solution for the example problem might be something like

Tuesday: Math: 9:00 - 10:00, History: 10:00 - 11:00, English: 11:00 - 12:00

leaving no gap and simultaneously giving 4 free days.

Is this possible with OptaPlanner or should I use a different solver? I noticed that the Lesson object only has a single TimeSlot instead of a list, which makes me think that this kind of timetable optimisation is not supported.

Answer 1

From the description, it appears your problem is "Student planning their own schedule" (whereas school timetabling is "Teachers planning the school timetable for all students").

I would model it like this:

@PlanningEntity
public class CourseSection {
    private List<TimeSlot> availableTimeslots;

    @PlanningId // needed for forEachUniquePair
    private String courseSectionIdentifier;

    @PlanningVariable(valueRangeProviderRefs = {"timeslotRange"})
    private TimeSlot selectedTimeslot;

    @ValueRangeProvider(id="timeslotRange")
    public List<TimeSlot> getTimeslotRangeForCourse() {
        return availableTimeslots;
    }
    
    // getters and setters ...
}

This takes advantage of value range provider on a planning entity, meaning each planning entity gets it own value range (and non-existing TimeSlot for the course will not be tried).

I used CourseSection, since courses could be divided into multiple sections (1 lectures + 2 tutorial, 2 lectures, etc.), and you would have one CourseSection for each of those sections. (If the course only one lecture section, then there is only one CourseSection, if the course a lecture + tutorial, there are two CourseSections, etc.).

For the minimize gaps constraint, I would use the experimental consecutive interval constraint collector. To use it, you would either need to add OptaPlanner Examples as a maven dependency or copy it from the source code of examples; it will eventually be moved into ConstraintCollectors once we are certain of the API (which is subject to change as it still in experimental). With the consecutive interval constraint collector, it will look like this:

Constraint minimizeGaps(ConstraintFactory constraintFactory) {
    return constraintFactory.forEach(CourseSection.class)
        .groupBy(section -> section.getSelectedTimeslot().getDayOfWeek(),
                 ExperimentalConstraintCollectors.consecutiveTemporalIntervals(
                         section -> section.getSelectedTimeslot().getStartTime(),
                         section -> section.getSelectedTimeslot().getEndTime()))
        .flattenLast(ConsecutiveIntervalInfo::getBreaks)
        .penalize("Minimize Gaps", HardMediumSoft.ONE_SOFT);
}

For the maximize free days constraints, I would write it as "minimize working days" like this:

Constraint minimizeWorkingDays(ConstraintFactory constraintFactory) {
    return constraintFactory.forEach(CourseSection.class)
        .groupBy(section -> section.getSelectedTimeslot().getDayOfWeek())
        .penalize("Minimize Working Days", HardMediumSoft.ONE_MEDIUM);
}

Finally, we need to make sure no two course sections overlap:

Constraint noOverlappingCourseSections(ConstraintFactory constraintFactory) {
    return constraintFactory.forEachUniquePair(CourseSection.class,
               Joiners.equal(section -> section.getSelectedTimeslot().getDayOfWeek()),
               Joiners.overlapping(
                   section -> section.getSelectedTimeslot().getStartTime(),
                   section -> section.getSelectedTimeslot().getEndTime()))
        .penalize("Overlapping sections", HardMediumSoftScore.ONE_HARD);
}

Note in the constraints I provided, a solution with less working days is ALWAYS preferred to a solution with more working days, even if the solution with less days has a 8 hour gap. You might want to add an additional constraint on the maximum gap allowed (which you can do with a filter that checks IntervalBreak.getLength()).