为学校生成课程表应该使用哪个算法？

Question

我正在开发一个简单的应用程序，用于为学校生成时间表（日程），该应用程序涉及到 IT 技术。我已经阅读了算法的基础知识，但在何处开始感到困惑。

问题如下： 安排老师上课，考虑到许多约束条件，例如: 1) 科目 2) 老师的专业技能 3) 不要连续上超过两节课等。 当然不能出现重叠。基本上，我需要将 N 个老师分配给 M 个班级，每天工作小时数固定为 8 小时。

输入信息包括： 1) 班级总数 2) 带有科目专业的教师 3) 每个班级的科目/课程 4) 每天每班的讲课次数 5) 其他灵活的约束条件，如每天老师的最小 / 最大工作小时数，每周老师的总工作小时数等

我的问题是： 1) 是否正确将其视为具有多个约束的分配问题？ 2) 我应该使用哪种算法？（匈牙利算法？） 3) 应该先一口气获得所有约束集，然后再生成时间表，还是应该分步进行？

我是算法的初学者，因此任何指导都会受到赞赏！谢谢。

- Checksum

---

我发现了一个PostScript文件，其中讲述了关于Tabu搜索算法（http://en.wikipedia.org/wiki/Tabu_search）在为教师分配课程（http://www.uv.es/sestio/TechRep/tr01-01.ps）中的应用。它主要是数学启发式方法。我希望它能给你提供一些方向。 - Buhake Sindi

这是一个重复的问题。我几周前已回答过这个问题：https://dev59.com/3nI95IYBdhLWcg3wvgh9 - Stefano Borini

Answer 1

您选择了一个非常棘手的问题。这样的调度优化是NP完全问题。有很多论文介绍如何处理这类问题，这种问题称为约束满足问题。您可以执行详尽搜索，这是最简单的方法，但非常耗时，如果您有超过几个类别，它将无法工作。您可以看一下求解器基础，它是用于.NET的一套工具，用于解决这些问题。Scott Hanselman在此处进行了播客介绍http://www.hanselminutes.com/default.aspx?showID=209，您可以在此处找到更多信息http://code.msdn.microsoft.com/solverfoundation。如果您想自己尝试，请尝试查看GSAT或其他一些进化算法看起来很有趣http://www.springer.com/engineering/book/978-3-540-48582-7。

- stimms

Answer 2

这个问题每周至少出现一次，答案（包括我的）总是相同的。我认为如果还没有特定的调度算法标签，我们应该创建一个。

我要重申，像这样的调度问题最适合的解决技术是约束编程。虽然其他优化技术对于小问题来说还可以，但对于某些约束条件，制定方案通常很痛苦。考虑一下你必须为一些简单的约束条件创建的所有整数变量。因为该问题通常需要一堆可行的时间表（或确定不可行性），而不是最优解，所以CP是首选方法，因为它就是为此而设计的。大多数其他方法需要用户在问题上“强制”一个最优性条件，而实际上并不存在。

- Grembo