在Timefold/Optaplanner中为长课时Lesson分配连续Timeslot的问题

问题核心 #

现有1小时粒度的Timeslot（周一至周五8:00-16:00），Lesson时长可大于1小时，需实现：

• 长时长课程必须分配连续的Timeslot
• 确保这些时段不被其他课程占用

之前方案的问题分析 #

1. 拆分课程为子块失败：未处理规划变量timeslot初始为null的情况，约束中直接调用getTimeslot()会引发空指针，且缺少对子块必须同房间、连续时段的强约束。
2. Joiners.overlapping无效：仅检查课程的单个Timeslot时段，未考虑长课程自身覆盖的整个时间范围，导致冲突检测不完整。

方案一：不拆分课程，通过约束实现连续时段分配 #

关键约束实现 #

需添加两类硬约束：

1. 长课程必须分配连续的Timeslot：验证课程的起始Timeslot之后，有足够多的连续时段覆盖其总时长
2. 房间时间冲突约束：检查所有课程的时间范围（含长课程的完整时长）是否与其他课程重叠

修正后的约束代码 #

import java.time.LocalTime;
import java.util.List;

public class TimetableConstraintProvider implements ConstraintProvider {

    @Override
    public Constraint[] defineConstraints(ConstraintFactory constraintFactory) {
        return new Constraint[] {
                // 1. 长课程必须分配连续的Timeslot
                longLessonContinuousTimeslot(constraintFactory),
                // 2. 房间时间冲突约束（覆盖所有课程的完整时长）
                roomConflict(constraintFactory)
        };
    }

    Constraint longLessonContinuousTimeslot(ConstraintFactory constraintFactory) {
        return constraintFactory.forEach(Lesson.class)
                // 筛选时长大于1小时的课程
                .filter(lesson -> lesson.getDuration().toHours() > 1)
                // 排除未分配Timeslot的课程（初始状态）
                .filter(lesson -> lesson.getTimeslot() != null)
                // 检查是否有足够的连续Timeslot
                .filter(lesson -> {
                    Timeslot startSlot = lesson.getTimeslot();
                    long requiredSlots = lesson.getDuration().toHours();
                    // 获取当天同一时段后的所有连续Timeslot
                    List<Timeslot> sameDaySlots = lesson.getTimetable().getTimeslots().stream()
                            .filter(slot -> slot.getDayOfWeek().equals(startSlot.getDayOfWeek()))
                            .filter(slot -> slot.getStartTime().isAfter(startSlot.getStartTime()))
                            .sorted((s1, s2) -> s1.getStartTime().compareTo(s2.getStartTime()))
                            .toList();
                    // 验证连续时段数量是否足够
                    for (int i = 0; i < requiredSlots - 1; i++) {
                        if (i >= sameDaySlots.size()) {
                            return false;
                        }
                        Timeslot expectedNext = sameDaySlots.get(i);
                        LocalTime expectedStartTime = startSlot.getStartTime().plusHours(i + 1);
                        if (!expectedNext.getStartTime().equals(expectedStartTime)) {
                            return false;
                        }
                    }
                    return true;
                })
                .penalize(HardSoftScore.ONE_HARD)
                .asConstraint("Long lesson must have continuous timeslots");
    }

    Constraint roomConflict(ConstraintFactory constraintFactory) {
        return constraintFactory.forEachUniquePair(Lesson.class,
                        // 排除未分配Timeslot或房间的课程
                        Joiners.filtering((lesson1, lesson2) -> lesson1.getTimeslot() != null && lesson2.getTimeslot() != null
                                && lesson1.getRoom() != null && lesson2.getRoom() != null),
                        // 检查同一房间
                        Joiners.equal(Lesson::getRoom),
                        // 检查时间范围重叠（覆盖课程完整时长）
                        Joiners.overlapping(
                                lesson -> lesson.getTimeslot().getStartTime(),
                                lesson -> lesson.getTimeslot().getStartTime().plus(lesson.getDuration()),
                                lesson -> lesson.getTimeslot().getStartTime(),
                                lesson -> lesson.getTimeslot().getStartTime().plus(lesson.getDuration())
                        ))
                .penalize(HardSoftScore.ONE_HARD)
                .justifyWith((lesson1, lesson2, score) -> new RoomConflictJustification(lesson1.getRoom(), lesson1, lesson2))
                .asConstraint("Room conflict");
    }
}

补充说明 #

• 在约束中先过滤掉timeslot或room为null的课程，避免空指针异常
• 房间冲突约束中，计算课程的实际结束时间（起始时段的开始时间+课程总时长），而非单个Timeslot的结束时间

方案二：正确拆分长课程为子块 #

如果必须拆分课程，需确保子块满足以下约束：

1. 所有子块必须分配连续的Timeslot
2. 所有子块必须分配同一房间
3. 子块之间不能被其他课程插入

修正后的子课程关联与约束 #

1. 修改Lesson类，添加父课程关联

@PlanningEntity
public class Lesson {
    // 原有字段...
    // 父课程（仅子块有值）
    private Lesson parentLesson;
    // 子块索引（从0开始）
    private int blockIndex;

    // Getters & Setters
}

2. 添加子块约束

Constraint lessonBlockContinuity(ConstraintFactory constraintFactory) {
    return constraintFactory.forEachUniquePair(Lesson.class,
                    Joiners.equal(Lesson::getParentLesson),
                    Joiners.filtering((b1, b2) -> b1.getBlockIndex() + 1 == b2.getBlockIndex()),
                    Joiners.filtering((b1, b2) -> b1.getTimeslot() != null && b2.getTimeslot() != null))
            // 检查两个子块的时段是否连续
            .filter((b1, b2) -> !b2.getTimeslot().getStartTime().equals(
                    b1.getTimeslot().getStartTime().plusHours(1)))
            .penalize(HardSoftScore.ONE_HARD)
            .asConstraint("Lesson blocks must be continuous");
}

Constraint lessonBlockSameRoom(ConstraintFactory constraintFactory) {
    return constraintFactory.forEachUniquePair(Lesson.class,
                    Joiners.equal(Lesson::getParentLesson),
                    Joiners.filtering((b1, b2) -> b1.getRoom() != null && b2.getRoom() != null))
            .filter((b1, b2) -> !b1.getRoom().equals(b2.getRoom()))
            .penalize(HardSoftScore.ONE_HARD)
            .asConstraint("Lesson blocks must be in the same room");
}

注意事项 #

• 初始问题中Timeslot类缺少getEndTime()方法，建议补充：

public LocalTime getEndTime() {
    return startTime.plus(duration);
}

• 确保Lesson能访问到全局的Timeslot列表（可通过在Lesson中添加getTimetable()方法实现）

内容的提问来源于stack exchange，提问作者Aiman Daniel