创建学校时间表的算法

Question

我一直想知道是否有创建学校时间表的算法的已知解决方案。基本上，它是关于为给定的类(class)-学科-教师关联优化“时间分散”(在教师和类(class)情况下)。我们可以假设我们在输入中有一组相互关联的类(class)、类(class)科目和教师，并且时间表应该在上午 8 点到下午 4 点之间。

我想可能没有准确的算法，但也许有人知道一个很好的近似或开发它的提示。

Answer 1

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

确认这既是一个难题又是人们一直在寻求解决方案的一个确认是检查这个(长)list of (mostly commercial) software scheduling tools

由于涉及大量变量，其最大来源通常是教员的愿望;-)...，通常是考虑枚举所有可能的组合是不切实际的 .相反，我们需要选择一种访问问题/解决方案空间子集的方法。
- 遗传算法 ，在另一个答案中引用的是(或者，恕我直言，似乎)能够很好地执行这种半引导搜索(问题是为下一代保留的候选者找到一个好的评估函数)
- Graph Rewriting方法也可用于此类组合优化问题。

我想建议 ，而不是专注于自动调度生成器程序的特定实现。一些可以应用的策略，在问题的定义层面 .
一般的基本原理是，在大多数现实世界的调度问题中，需要做出一些妥协，而不是所有明示和暗示的约束:将完全满足。因此，我们通过以下方式帮助自己:

定义和排列所有已知约束

通过手动提供一组额外的约束来减少问题空间。这可能看起来违反直觉，但例如通过提供一个初始的、部分填充的时间表(比如大约 30% 的时隙)，以完全满足的方式所有约束，并且通过考虑这个部分时间表不可变，我们显着减少了生成候选解决方案所需的时间/空间。附加约束的另一种帮助方式是，例如“人为”添加一个约束，以防止在一周的某些天教授某些科目(如果这是每周计划......)；这种类型的约束导致减少问题/解决方案空间，通常不会排除大量优秀的候选者。

确保可以快速计算问题的某些约束。这通常与用于表示问题的数据模型的选择有关；这个想法是能够快速选择(或删除)一些选项。

重新定义问题并允许一些约束被打破，几次，(通常是朝向图的末端节点)。这里的想法是要么删除一些限制来填充日程表中的最后几个空位，要么让自动日程表生成器程序停止完成整个日程表，而不是为我们提供一打左右的列表候选人。人类通常更擅长完成谜题，如图所示，可能会打破一些限制，使用通常不会与自动化逻辑共享的信息(例如，“下午没有数学”规则有时可能会被打破对于“高级数学和物理”类(class)；或“打破琼斯先生的要求之一比打破史密斯女士的要求更好...... ;-) )

在校对这个答案时，我意识到提供一个明确的答复是很害羞的，但它仍然充满了实用的建议。我希望这会有所帮助，毕竟这是一个“难题”。