optaplanner 调度 AI 是否适合优化大学日程？

Question

Optaplanner school timetabling 示例显示的问题与我需要解决的问题不同。

问题：

让我们上三门课：数学、英语、历史

所有这些课程都提供多个时间段（并行），学生可以为每个时间段选择一个。

假设：

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

我想为这些课程中的每一个找到最佳可能的时间段。最好我的意思是间隔最少的那个，更重要的是，让你有最多空闲时间的那个。

示例问题的最佳解决方案可能类似于

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

不留空档，同时提供 4 天免费。

这对 OptaPlanner 可行吗？还是我应该使用不同的求解器？我注意到Lesson对象只有一个TimeSlot而不是一个列表，这让我觉得不支持这种时间表优化。

Answer 1

从描述来看，您的问题似乎是“学生计划自己的时间表”（而学校时间表是“教师为所有学生制定学校时间表”）。

我会这样建模：

@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 ...
}

这利用了 value range provider on a planning entity，这意味着每个规划实体都有自己的值范围（并且不会尝试课程的 non-existing TimeSlot）。

我使用了 CourseSection，因为课程可以分为多个部分（1 个讲座 + 2 个教程、2 个讲座等），并且每个部分都有一个 CourseSection。（如果课程只有一个lecture section，那么就只有一个CourseSection，如果课程一个lecture+tutorial，就有两个CourseSection，等等）。

对于最小化间隙约束，我会使用实验性连续区间约束收集器。要使用它，您需要添加 OptaPlanner Examples as a maven dependency or copy it from the source code of examples；一旦我们确定 API （可能会发生变化，因为它仍处于实验阶段），它最终将被移入 ConstraintCollectors。使用连续间隔约束收集器，它将如下所示：

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);
}

对于最大空闲天数限制，我会把它写成“最小化工作天数”，如下所示：

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

最后，我们需要确保没有两个课程部分重叠：

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);
}

请注意，在我提供的限制条件下，工作日较少的解决方案总是优于工作日较多的解决方案，即使工作日较少的解决方案有 8 小时的差距。您可能想要对允许的最大间隙添加额外的约束（您可以使用检查 IntervalBreak.getLength() 的过滤器来实现）。

optaplanner 调度 AI 是否适合优化大学日程？

Is optaplanner scheduling AI suitable for optimising a college schedule?

optaplanner