优化会议安排：使用OptaPlanner解决硬性和软性限制

引言

问题描述

会议室分配，将每个会议分配到一个开始时间和一个房间。会议的持续时间不同。

约束条件

硬性限制：
• 房间冲突：两个会议不能在同一时间使用同一个房间。
• 必需出席：一个人不能在同一时间有两个必需出席的会议。
• 必需房间容量：一个会议必须安排在可以容纳所有与会者的房间中。
• 开始和结束在同一天：一个会议不应该跨越多天安排。
中等限制：
• 首选出席：一个人不能在同一时间有两个首选出席的会议，也不能同时有一个首选出席的会议和一个必需出席的会议。
软性限制：
• 越早越好：尽早安排所有会议。
• 会议之间的休息时间：任意两个会议之间应该有至少一个时间间隔的休息时间。
• 会议重叠：为了最小化并行会议的数量，使人们不必选择一个会议而放弃另一个会议。
• 先分配较大的房间：如果有一个较大的房间可用，任何会议都应该分配到该房间，以便尽可能容纳更多的人，即使他们没有报名参加那个会议。
• 房间稳定性：如果一个人有两个连续的会议，它们之间的时间间隔小于等于两个时间格，则最好安排在同一个房间中。

问题规模

50meetings-160timegrains-5rooms has 50 meetings, 160 timeGrains and 5 rooms with a
search space of 10^145.
100meetings-320timegrains-5rooms has 100 meetings, 320 timeGrains and 5 rooms with a
search space of 10^320.
200meetings-640timegrains-5rooms has 200 meetings, 640 timeGrains and 5 rooms with a
search space of 10^701.
400meetings-1280timegrains-5rooms has 400 meetings, 1280 timeGrains and 5 rooms with a
search space of 10^1522.
800meetings-2560timegrains-5rooms has 800 meetings, 2560 timeGrains and 5 rooms with a
search space of 10^3285.

模型设计

求解类图

约束分析

硬约束

• 房间冲突：两个会议不能在同一时间使用同一个房间。

protected Constraint roomConflict(ConstraintFactory constraintFactory) {
        return constraintFactory.forEachUniquePair(MeetingAssignment.class,
                equal(MeetingAssignment::getRoom),
                overlapping(assignment -> assignment.getStartingTimeGrain().getGrainIndex(),
                        assignment -> assignment.getStartingTimeGrain().getGrainIndex() +
                                assignment.getMeeting().getDurationInGrains()))
                .penalizeConfigurable((leftAssignment, rightAssignment) -> rightAssignment.calculateOverlap(leftAssignment))
                .asConstraint("Room conflict");
    }

forEachUniquePair寻找出唯一的pair对，若是一个room，则检查开始和的grainIndex和endIndex是否存在重叠，calculateOverlap计算出重叠的部分作为惩罚。

• 会议不能出时间限制

protected Constraint avoidOvertime(ConstraintFactory constraintFactory) {
        return constraintFactory.forEachIncludingNullVars(MeetingAssignment.class)
                .filter(meetingAssignment -> meetingAssignment.getStartingTimeGrain() != null)
                .ifNotExists(TimeGrain.class,
                        equal(MeetingAssignment::getLastTimeGrainIndex, TimeGrain::getGrainIndex))
                .penalizeConfigurable(MeetingAssignment::getLastTimeGrainIndex)
                .asConstraint("Don't go in overtime");
    }

forEachIncludingNullVars的目的是查询，PlainningVariable变量允许为空的Entity即MeetingAssignment对象。
然后因为是双变量，所以filter的是过滤出了startingGrain不等于null，其实就是分配了会议时间。
ifNotExists(equal(last,grainIndex)，目的是出现会议时长超过了时间颗粒的限制，如下图：

加入Meeting在周五下午grainIndex是49初开始，需要3个小时，那么结束的lastTimeGrainIndex是51，但是整个TimeGrain里并没有51的index，此约束的目的是这个，并非字面意思为了限制加班。

• 必需房间容量：一个会议必须安排在可以容纳所有与会者的房间中。

protected Constraint requiredRoomCapacity(ConstraintFactory constraintFactory) {
        return constraintFactory.forEachIncludingNullVars(MeetingAssignment.class)
                .filter(meetingAssignment -> meetingAssignment.getRequiredCapacity() > meetingAssignment.getRoomCapacity())
                .penalizeConfigurable(
                        meetingAssignment -> meetingAssignment.getRequiredCapacity() - meetingAssignment.getRoomCapacity())
                .asConstraint("Required room capacity");
    }

这个很容易理解：meetingAssignment -> meetingAssignment.getRequiredCapacity() > meetingAssignment.getRoomCapacity()

• 开始和结束在同一天：一个会议不应该跨越多天安排

protected Constraint startAndEndOnSameDay(ConstraintFactory constraintFactory) {
        return constraintFactory.forEachIncludingNullVars(MeetingAssignment.class)
                .filter(meetingAssignment -> meetingAssignment.getStartingTimeGrain() != null)
                .join(TimeGrain.class,
                        equal(MeetingAssignment::getLastTimeGrainIndex, TimeGrain::getGrainIndex),
                        filtering((meetingAssignment,
                                timeGrain) -> meetingAssignment.getStartingTimeGrain().getDay() != timeGrain.getDay()))
                .penalizeConfigurable()
                .asConstraint("Start and end on same day");
    }

会议的开始时间的日期，与会议结束的日期不是同一天。
equal(MeetingAssignment::getLastTimeGrainIndex, TimeGrain::getGrainIndex) 组合出会议结束时间相等的时间颗粒。
filtering((meetingAssignment,
timeGrain) -> meetingAssignment.getStartingTimeGrain().getDay() != timeGrain.getDay()) 过滤出不在同一天的数据，则进行惩罚。

• **必须参加会议的硬约束 - requiredAttendanceConflict **

.join(MeetingAssignment.class,
        equal((leftRequiredAttendance, rightRequiredAttendance, leftAssignment) -> rightRequiredAttendance
        .getMeeting(),
        MeetingAssignment::getMeeting),
        overlapping((attendee1, attendee2, assignment) -> assignment.getStartingTimeGrain().getGrainIndex(),
        (attendee1, attendee2, assignment) -> assignment.getStartingTimeGrain().getGrainIndex() +
        assignment.getMeeting().getDurationInGrains(),
        assignment -> assignment.getStartingTimeGrain().getGrainIndex(),
        assignment -> assignment.getStartingTimeGrain().getGrainIndex() +
        assignment.getMeeting().getDurationInGrains()))

Medium约束

• requiredAndPreferredAttendanceConflict

必须参加会议和优先参加会议的中等约束冲突，代码分析可以参考requiredAttendanceConflict。

• preferredAttendanceConflict

优先参加会议的中等约束冲突，代码分析可以参考requiredAttendanceConflict。

Soft约束

• doMeetingsAsSoonAsPossible

这个约束的目的是，尽早安排所有会议，其实就是惩罚会议的结束时间，开始时间越早结束时间就越短，惩罚就越小。

• oneBreakBetweenConsecutiveMeetings

任意两个会议之间应该有至少一个时间间隔的休息时间。代码比较简单就不分析了。

• overlappingMeetings

会议重叠：为了最小化并行会议的数量，使人们不必选择一个会议而放弃另一个会议。

greaterThan((leftAssignment) -> leftAssignment.getMeeting().getId(),
                                (rightAssignment) -> rightAssignment.getMeeting().getId())

约束代码里这部分的目的是为了减少重复的重叠计算，与lessThan一样。

• assignLargerRoomsFirst

先分配较大的房间：如果有一个较大的房间可用，任何会议都应该分配到该房间，以便尽可能容纳更多的人，即使他们没有报名参加那个会议。

lessThan(MeetingAssignment::getRoomCapacity, Room::getCapacity))
        .penalizeConfigurable((meetingAssignment, room) -> room.getCapacity() - meetingAssignment.getRoomCapacity())

这段代码的会达到一个效果，约大的Room空的越多扣分越多，如此就会尽量分配大房间。

• roomStability

房间稳定性：如果一个人有两个连续的会议，它们之间的时间间隔小于等于两个时间格，则最好安排在同一个房间中。

protected Constraint roomStability(ConstraintFactory constraintFactory) {

        return constraintFactory.forEach(Attendance.class)

                .join(Attendance.class,

                        equal(Attendance::getPerson),

                        filtering((leftAttendance,

                                rightAttendance) -> leftAttendance.getMeeting() != rightAttendance.getMeeting()))

                .join(MeetingAssignment.class,

                        equal((leftAttendance, rightAttendance) -> leftAttendance.getMeeting(),

                                MeetingAssignment::getMeeting))

                .join(MeetingAssignment.class,

                        equal((leftAttendance, rightAttendance, leftAssignment) -> rightAttendance.getMeeting(),

                                MeetingAssignment::getMeeting),

                        lessThan((leftAttendance, rightAttendance, leftAssignment) -> leftAssignment.getStartingTimeGrain(),

                                MeetingAssignment::getStartingTimeGrain),

                        filtering((leftAttendance, rightAttendance, leftAssignment,

                                rightAssignment) -> leftAssignment.getRoom() != rightAssignment.getRoom()),

                        filtering((leftAttendance, rightAttendance, leftAssignment,

                                rightAssignment) -> rightAssignment.getStartingTimeGrain().getGrainIndex() -

                                        leftAttendance.getMeeting().getDurationInGrains() -

                                        leftAssignment.getStartingTimeGrain().getGrainIndex()