探索教学排课难题：ITC 2007 Track 3课程排课问

问题描述

将每个讲座安排到一个时间段，并分配到一个房间。

业务约束和目标

硬限制：
• 教师冲突：一个教师在同一时间段内不能有两个讲座。
• 课程表冲突：一个课程表在同一时间段内不能有两个讲座。
• 教室占用：同一时间段内不能有两个讲座在同一个教室。
• 不可用时间段（根据数据集指定）：一个特定的讲座不能被安排在一个特定的时间段。

软限制：
• 教室容量：一个教室的容量不应该小于其讲座的学生人数。
• 最少工作日数：相同课程的讲座应该分布在最少的工作日数内。
• 课程紧凑度：属于同一课程的讲座应该相邻（即在连续的时间段内）。
• 教室稳定性：相同课程的讲座应该被分配到同一个教室。

此问题由 2007 年国际时间稳定竞争 3 定义。

问题规模
让我们来看一下官网上给出的案例中，不同数据规模所对应的搜索空间大小情况：

comp01 has 24 teachers, 14 curricula, 30 courses, 160 lectures, 30 periods, 6 rooms
and 53 unavailable period constraints with a search space of 10^360.
comp02 has 71 teachers, 70 curricula, 82 courses, 283 lectures, 25 periods, 16 rooms
and 513 unavailable period constraints with a search space of 10^736.
comp03 has 61 teachers, 68 curricula, 72 courses, 251 lectures, 25 periods, 16 rooms
and 382 unavailable period constraints with a search space of 10^653.
comp04 has 70 teachers, 57 curricula, 79 courses, 286 lectures, 25 periods, 18 rooms
and 396 unavailable period constraints with a search space of 10^758.
comp05 has 47 teachers, 139 curricula, 54 courses, 152 lectures, 36 periods, 9 rooms
and 771 unavailable period constraints with a search space of 10^381.
comp06 has 87 teachers, 70 curricula, 108 courses, 361 lectures, 25 periods, 18 rooms
and 632 unavailable period constraints with a search space of 10^957.
comp07 has 99 teachers, 77 curricula, 131 courses, 434 lectures, 25 periods, 20 rooms
and 667 unavailable period constraints with a search space of 10^1171.
comp08 has 76 teachers, 61 curricula, 86 courses, 324 lectures, 25 periods, 18 rooms
and 478 unavailable period constraints with a search space of 10^859.
comp09 has 68 teachers, 75 curricula, 76 courses, 279 lectures, 25 periods, 18 rooms
and 405 unavailable period constraints with a search space of 10^740.
comp10 has 88 teachers, 67 curricula, 115 courses, 370 lectures, 25 periods, 18 rooms
and 694 unavailable period constraints with a search space of 10^981.
comp11 has 24 teachers, 13 curricula, 30 courses, 162 lectures, 45 periods, 5 rooms
and 94 unavailable period constraints with a search space of 10^381.
comp12 has 74 teachers, 150 curricula, 88 courses, 218 lectures, 36 periods, 11 rooms
and 1368 unavailable period constraints with a search space of 10^566.
comp13 has 77 teachers, 66 curricula, 82 courses, 308 lectures, 25 periods, 19 rooms
and 468 unavailable period constraints with a search space of 10^824.
comp14 has 68 teachers, 60 curricula, 85 courses, 275 lectures, 25 periods, 17 rooms
and 486 unavailable period constraints with a search space of 10^722.

建模分析

来看下下官网例子中的类图：

先看身为@PlanningEntity的Lecture对象，它有一个@PlanningVariable注解的period属性和room属性，这两个属性都是@PlanningVariable注解的，说明这两个属性都是需要进行规划的。
再看Lecture对象的Course属性，它是一个常量属性，说明Course对象是不需要进行规划的。
Lecture的意思是讲座，Course的意思是课程，Period的意思是时间段，Room的意思是教室。

模型的设计目的就是，要将每个讲座安排到一个时间段，并分配到一个房间。

约束分析

硬约束

教师冲突：一个教师在同一时间段内不能有两个讲座。conflictingLecturesDifferentCourseInSamePeriod方法

@ProblemFactCollectionProperty
    private List<CourseConflict> calculateCourseConflictList() {
        List<CourseConflict> courseConflictList = new ArrayList<>();
        for (Course leftCourse : courseList) {
            for (Course rightCourse : courseList) {
                if (leftCourse.getId() < rightCourse.getId()) {
                    int conflictCount = 0;
                    if (leftCourse.getTeacher().equals(rightCourse.getTeacher())) {
                        conflictCount++;
                    }
                    for (Curriculum curriculum : leftCourse.getCurriculumSet()) {
                        if (rightCourse.getCurriculumSet().contains(curriculum)) {
                            conflictCount++;
                        }
                    }
                    if (conflictCount > 0) {
                        courseConflictList.add(new CourseConflict(leftCourse, rightCourse, conflictCount));
                    }
                }
            }
        }
        return courseConflictList;
    }

这段代码的意思是，遍历所有的课程，将课程的冲突客成加入到courseConflictList集合中，冲突的条件有两种：

两个课程的教师相同。
两个课程的课程集合有交集。

leftCourse.getId() < rightCourse.getId()的作用是，避免重复计算，比如1-2和2-1是同一个冲突，只需要计算一次即可。接下来，看下约束设计的代码部分：

Constraint conflictingLecturesDifferentCourseInSamePeriod(ConstraintFactory factory) {
        return factory.forEach(CourseConflict.class)
                .join(Lecture.class,
                        equal(CourseConflict::getLeftCourse, Lecture::getCourse))
                .join(Lecture.class,
                        equal((courseConflict, lecture1) -> courseConflict.getRightCourse(), Lecture::getCourse),
                        equal((courseConflict, lecture1) -> lecture1.getPeriod(), Lecture::getPeriod))
                .filter(((courseConflict, lecture1, lecture2) -> lecture1 != lecture2))
                .penalize(ONE_HARD,
                        (courseConflict, lecture1, lecture2) -> courseConflict.getConflictCount())
                .asConstraint("conflictingLecturesDifferentCourseInSamePeriod");
    }

这段代码的意思是，遍历所有的课程冲突，然后将冲突的课程的时间段相同的情况过滤出来，然后将冲突的课程的冲突次数作为惩罚值，这样就可以保证不会出现冲突的情况了。

同样的课程在同一时间段内只能有一个讲座： conflictingLecturesSameCourseInSamePeriod方法

Constraint conflictingLecturesSameCourseInSamePeriod(ConstraintFactory factory) {
        return factory.forEachUniquePair(Lecture.class,
                equal(Lecture::getPeriod),
                equal(Lecture::getCourse))
                .penalize(ONE_HARD,
                        (lecture1, lecture2) -> 1 + lecture1.getCurriculumSet().size())
                .asConstraint("conflictingLecturesSameCourseInSamePeriod");
    }

一个房间在同一时间段内只能有一个讲座：roomOccupancy方法

Constraint roomOccupancy(ConstraintFactory factory) {
        return factory.forEachUniquePair(Lecture.class,
        equal(Lecture::getRoom),
        equal(Lecture::getPeriod))
        .penalize(ONE_HARD)
        .asConstraint("roomOccupancy");
        }

不可用时间段（根据数据集指定）：unavailablePeriodPenalty方法

Constraint unavailablePeriodPenalty(ConstraintFactory factory) {
        return factory.forEach(UnavailablePeriodPenalty.class)
                .join(Lecture.class,
                        equal(UnavailablePeriodPenalty::getCourse, Lecture::getCourse),
                        equal(UnavailablePeriodPenalty::getPeriod, Lecture::getPeriod))
                .penalize(ofHard(10))
                .asConstraint("unavailablePeriodPenalty");
    }

软约束

一个教室的容量不应该小于其讲座的学生人数：roomCapacity方法

Constraint roomCapacity(ConstraintFactory factory) {
        return factory.forEach(Lecture.class)
                .filter(lecture -> lecture.getStudentSize() > lecture.getRoom().getCapacity())
                .penalize(ofSoft(1),
                        lecture -> lecture.getStudentSize() - lecture.getRoom().getCapacity())
                .asConstraint("roomCapacity");
    }

这个约束的目的是，希望一个教室的容量不应该小于其讲座的学生人数，如果小于，那么就会有惩罚值。为什么不是硬约束呢？因为如果是硬约束，那么就会导致无法找到解，因为有些课程的学生人数是大于教室容量的（大家可以站着，相信多数同学在大学都经历过），所以这里使用软约束。

每个课程尽量满足最小的天数：minimumWorkingDays方法

Constraint minimumWorkingDays(ConstraintFactory factory) {
        return factory.forEach(Lecture.class)
                .groupBy(Lecture::getCourse, countDistinct(Lecture::getDay))
                .filter((course, dayCount) -> course.getMinWorkingDaySize() > dayCount)
                .penalize(ofSoft(5),
                        (course, dayCount) -> course.getMinWorkingDaySize() - dayCount)
                .asConstraint("minimumWorkingDays");
    }

这个约束的目的是希望每个课程的讲座尽量满足最小的天数，比如某个课程的最小天数是3天，那么这个课程的讲座应该尽量安排在3天，如果安排在2天，那么就会有惩罚值。

• 教室稳定性：相同课程的讲座应该被分配到同一个教室。roomStability方法

Constraint roomStability(ConstraintFactory factory) {
        return factory.forEach(Lecture.class)
                .groupBy(Lecture::getCourse, countDistinct(Lecture::getRoom))
                .filter((course, roomCount) -> roomCount > 1)
                .penalize(HardSoftScore.ONE_SOFT,
                        (course, roomCount) -> roomCount - 1)
                .asConstraint("roomStability");
    }

很容易理解这段代码，根据Course分组，去重后的Room数量大于1的情况，就是分配了不同的教室。

课程紧凑度：属于同一课程的讲座应该相邻（即在连续的时间段内）。 periodSpread方法

Constraint curriculumCompactness(ConstraintFactory factory) {
        return factory.forEach(Curriculum.class)
                .join(Lecture.class,
                        filtering((curriculum, lecture) -> lecture.getCurriculumSet().contains(curriculum)))
                .ifNotExists(Lecture.class,
                        equal((curriculum, lecture) -> lecture.getDay(), Lecture::getDay),
                        equal((curriculum, lecture) -> lecture.getTimeslotIndex(), lecture -> lecture.getTimeslotIndex() + 1),
                        filtering((curriculum, lectureA, lectureB) -> lectureB.getCurriculumSet().contains(curriculum)))
                .ifNotExists(Lecture.class,
                        equal((curriculum, lecture) -> lecture.getDay(), Lecture::getDay),
                        equal((curriculum, lecture) -> lecture.getTimeslotIndex(), lecture -> lecture.getTimeslotIndex() - 1),
                        filtering((curriculum, lectureA, lectureB) -> lectureB.getCurriculumSet().contains(curriculum)))
                .penalize(ofSoft(2))
                .asConstraint("curriculumCompactness");
    }

这个代码看起来复杂，但是其实很简单，就是遍历所有的课程，join关联出已分配此课程的讲座，判断相邻（前后）的两个讲座是否属于同一个课程，如果不是，则惩罚值加2。
两个ifNotExists判断的目的是，若前或者后都有相同课程的讲座，则不惩罚。