问创建课程表的算法

EN

这个问题是NP-！

简而言之，我们需要探索所有可能的组合，以找到可接受的解决方案列表。由于在不同学校出现问题的情况不同(例如:教室是否有限制?一些班级有时会分成小组吗?这是每周的时间表吗？等)没有一个众所周知的问题类可以对应于所有的调度问题。也许，与这些问题有许多相似之处。

确认这既是一个困难的问题，也是人们长期寻求解决方案的问题，就是检查这个(长)

由于涉及到大量的变量，其中最大的来源通常是教员的愿望;-)...，考虑枚举所有可能的组合通常是不切实际的。相反，我们需要选择一种访问问题/解决方案空间的子集的方法。

在另一个答案中引用的

• Genetic算法似乎很适合执行这种半引导搜索(问题是为下一个generation)
• 方法保留的候选者找到一个好的评估函数也适用于这种类型的组合优化问题。

与其专注于自动时间表生成器程序的特定实现，我想建议一些可以应用的策略，在问题定义( definition of problem )的层面上。

一般的理由是，在大多数现实世界的调度问题中，将需要一些妥协，而不是所有的约束，明示和暗示:将完全满足。因此，我们通过以下方式帮助自己：

• 通过手动提供一组附加约束来定义和排序所有已知的问题空间。

这看起来可能有悖于直觉，但例如，通过提供一个初始的、部分填满的时间表(比如大约30%的时隙)，以一种完全满足所有约束的方式，并且通过考虑这个部分时间表是不可变的，我们可以显著减少产生候选解决方案所需的时间/空间。

另一种附加约束的帮助方式是例如“人为地”添加约束，该约束阻止在一周中的某些天教授某些科目(如果这是每周的日程安排...)；这种类型的约束导致减少问题/解决方案空间，而通常不排除大量的良好candidates.

• Ensuring，即可以快速计算问题的一些约束。这通常与用于表示问题的数据模型的选择有关；其思想是能够快速地选择(或剪除)问题的一些options.

• Redefining，并允许一些约束被打破几次(通常是朝向图形的末端节点)。这里的想法是要么消除一些限制-填充时间表中的最后几个空位，要么让自动时间表生成器程序在完成整个时间表之前停止，而是为我们提供一个大约12个合理候选者的列表。正如所指出的，人类通常更有能力完成难题，可能会打破一些限制，使用通常不会与自动逻辑共享的信息(例如，“高级数学和物理”课程有时不能违反“下午没有数学”规则；或者“打破琼斯先生的一个要求比违反史密斯女士的一个要求更好... ;-) )

在校对这个答案时，我意识到它很难给出明确的答复，但它仍然充满了实际的建议。我希望这对解决这个“难题”有帮助。

真是一团糟。王室的烂摊子。为了补充已经非常完整的答案，我想指出我的家庭经历。我的母亲是一名教师，她曾经参与到这个过程中。

事实证明，拥有一台计算机来做到这一点不仅本身很难编码，而且也很难，因为有一些条件很难指定给预先烘焙的计算机程序。示例：

• 是一名教师，在你们学校和另一所学院任教。显然，如果他在10点半结束课程，他不能在10点半从你的住处开始上课，因为他需要一些时间在institutes.
• two教师之间来回奔波。一般来说，不让两个结过婚的老师在同一个班级上是很好的做法。因此，这两个老师必须有两个不同的班级，两个老师结婚了，他们的孩子在同一所学校上学。(
• )同样，你必须阻止两位老师在他们孩子所在的特定班级授课。
• 学校有单独的设施，比如一天班级在一所学院，另一天班级在另一所学院。
• 学校共享实验室，但这些实验室只在某些工作日开放(例如，出于安全原因，在额外人员较多的情况下)教师更喜欢放假:一些老师喜欢周一，一些老师喜欢周五，一些老师喜欢周三。
• 你不应该遇到这样的情况:你不应该在第一个小时上历史课，然后上三个小时的数学课，再上一个小时的历史课。这对学生没有意义，对老师也没有意义。
• 你应该把论点平均分布。一周的头几天只有数学，然后一周剩下的时间只有literature.
• you应该给一些老师连续两个小时做评估测试，这是没有意义的。

正如你所看到的，这个问题不是NP完全的，而是NP疯狂的。

所以他们所做的就是他们有一张带有小塑料插页的大桌子，他们移动插页直到得到令人满意的结果。他们从不从头开始:他们通常从上一年的时间表开始并进行调整。

有一个课程安排跟踪和考试安排跟踪。许多研究人员参加了那次比赛。尝试了许多启发式和元启发式算法，但最终局部搜索元启发式算法(如禁忌搜索和模拟退火)明显优于其他算法(如遗传算法)。

看看一些决赛选手使用的两个开源框架：

• JBoss OptaPlanner (Java，开源source)
• Unitime (Java，开源)-面向大学的更多