引言
问题描述
会议室分配，将每个会议分配到一个开始时间和一个房间。会议的持续时间不同。
约束条件
硬性限制：
• 房间冲突：两个会议不能在同一时间使用同一个房间。
• 必需出席：一个人不能在同一时间有两个必需出席的会议。
• 必需房间容量：一个会议必须安排在可以容纳所有与会者的房间中。
• 开始和结束在同一天：一个会议不应该跨越多天安排。
中等限制：
• 首选出席：一个人不能在同一时间有两个首选出席的会议，也不能同时有一个首选出席的会议和一个必需出席的会议。
软性限制：
• 越早越好：尽早安排所有会议。
• 会议之间的休息时间：任意两个会议之间应该有至少一个时间间隔的休息时间。
• 会议重叠：为了最小化并行会议的数量，使人们不必选择一个会议而放弃另一个会议。
• 先分配较大的房间：如果有一个较大的房间可用，任何会议都应该分配到该房间，以便尽可能容纳更多的人，即使他们没有报名参加那个会议。
• 房间稳定性：如果一个人有两个连续的会议，它们之间的时间间隔小于等于两个时间格，则最好安排在同一个房间中。
问题规模
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 **
forEachUniquePair(RequiredAttendance.class, equal(RequiredAttendance::getPerson))的目的是找出同一个Person必须参加的会议组，forEachUniquePair的
目的是为了不重复的对。- 下面这段代码的目的是，先是找出
Pari对里左边的Meeting，在MeetingAssignment中已经分配的Meeting，目的是为了下一步计算冲突做数据准备。然后是找出右边Pair里
的Meeting，其筛选条件是Pair里左右的里分配会议的时间范围存在重叠，若存在则惩罚。
.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() <= 2))
.penalizeConfigurable()
.asConstraint("Room stability");
}
代码看着复杂，一步步分析下来：
- 使用
constraintFactory.forEach(Attendance.class)遍历所有出席（Attendance）对象。 - 使用
join连接两个出席对象，要求这两个对象属于同一个人，但参加的会议不同（filtering条件）。 - 使用
join连接一个会议分配（MeetingAssignment）对象，要求该对象分配给了第一个出席对象参加的会议（equal条件）。 - 再次使用
join连接一个会议分配对象，要求该对象分配给了第二个出席对象参加的会议，并且其开始时间早于第一个出席对象参加的会议的开始时间（equal和lessThan条件）。 - 使用
filtering条件进一步筛选会议分配对象，要求第一个会议分配对象和第二个会议分配对象分配的会议不在同一个房间中，并且它们之间的时间差不超过2个时间粒度（GrainIndex）。 - 使用
penalizeConfigurable()方法将约束转换为一个可配置的惩罚（penalty）。
惩罚的核心就是：同一人两个相差不超过2个时间粒度的会议，如果分配在不同的房间中，就会被惩罚。
求解结果
如果需要转载文章，必须注明原出处和作者，感谢您的理解和支持。
