时间戳

首页 > 解决方案 > 使用 OptaPlanner 创建具有一些棘手约束的学校时间表

constraints - 使用 OptaPlanner 创建具有一些棘手约束的学校时间表

问题描述

我将使用 OptaPlanner 为学校安排时间表。

我们正在制定整个学期的时间表，如有必要，每周可能会略有不同。

有一些棘手的限制需要考虑：

1. 每周时间表

问题

如果我创建一个约束条件，即-1soft不安排与前一周相同的时间，那么 OptaPlanner 将浪费大量时间，然后“意外”找到合适的讲座位置，即使它设法收敛因此，每个主题每周都安排在相同的时间，它永远无法通过一个一个地移动它们来移动整个系列的讲座。（那个局部最优值永远不会被逃避。）

2.跨学生组科目

问题

一个学期有很多时间段，OptaPlanner 会通过随机移动单个讲座来发现同时安排​​所有语言讲座的解决方案的可能性很小。

此外，与问题 1 类似：如果OptaPlanner 确实设法同时安排法语、德语和西班牙语，这些“块”将永远不会移动到其他地方，因为它们是单独的讲座，并且所有讲座都“随机”移动的机会到同一个新插槽很小。即使有很大的禁忌历史长度等等。

到目前为止我的想法

至于问题 1（“每周可预测性”），我正在考虑执行以下操作：

在整个学期计划的构建阶段，我创建了问题的简化版本，将（一组减少的讲座）安排到一个“模板周”中。我们称之为“单周预调度”。然后在整个学期的初始解决方案的构建中重复这个模板周，这是“真正的”计划实体。

然后，本地搜索步骤将只专注于插入 PE 游览等，并调整受影响周的时间表。

至于问题 2，我认为问题 1 的解决方案可能会解决这个问题。在 1 周的日程安排中，假设 OptaPlaner 会意识到应该同时安排语言课程似乎是合理的。

关于通过单周预调度解决的局部最优（“生物学安排在星期二早上”），我想我可以创建一个自定义移动操作，将这些讲座“捆绑”成一个移动。我不知道这有多简单。我真的很想让代码尽可能简单。

问题

我的想法合理吗？有没有更聪明的方法来解决这些问题？如果无论如何我必须创建自定义动作，也许我不需要构建模板周？

有没有办法为动作分配提示或权重？如果是这样，我也许可以生成权重稍大的动作，以调整日程安排以遵守可预测的周数和在同一时间段安排的语言。

标签： constraintsoptaplannertimetable

解决方案

一个问题问得好！

关于你的第一个问题，我建议你看看OptaWeb Employee Rostering和轮换的概念。轮换是“一般情况下的情况”，然后 Planner 可以自由地偏离轮换，但会受到惩罚。一旦您从 UI 中了解了轮换的概念，请查看规划实体Shift以及如何使用employee和rotationEmployee变量来实现轮换。请注意，只有employee是实际@PlanningVariable的，并且rotationEmployee是固定的。

这意味着您必须手动定义旋转，因此您需要自己完成求解器的工作。然而，由于我假设这个操作每学期只进行一次，也许解决方案可能是让一个更简单的求解器首先生成一个合理的一般旋转，然后第二个求解器会接受它并找出具体的必要调整？

关于你的第二个问题，轮换也有帮助。但我在想也许一些移动过滤和自定义移动来帮助 OptaPlanner 移动所有语言类，或者不移动？编写高效的自定义动作并不容易，过滤库存动作很麻烦。所以我只会在其他选项的潜力用尽时才这样做。如果您最终这样做，请查找MoveIteratorFactory.

我的回答有点含糊，因为我们没有深入了解领域模型的细节，但出于设计整体解决方案的目的，它希望能提供足够的线索。

推荐阅读