使用哪种算法为学校生成时间表

我正在研究一个简单的应用程序，它将为学校生成时间表（每日计划）。我已经阅读了算法的基础知识，但从哪里开始感到困惑。
使用哪种算法为学校生成时间表

问题：
分配老师考虑到了很多限制类相似：
1）除
2）教师
3的专长）持续不超过2类..等

不言而喻，不应该有重叠。基本上我需要每天为固定数量的工作时间分配N个教师到M班（8）。

的输入：
1）总与他们的专门知识的沿的类
2）教师数
3）的受试者/每一类
4）每天每类讲座数
5课程）像每天老师，每每周老师总工作小时最低/最高工时等

我的问题等柔性约束：
1）它是正确的把它看作是带有多重约束的分配问题？
2）我应该使用哪种算法？（匈牙利算法？）
3）我应该从一开始就得到整套约束，然后生成表格，还是应该在中间步骤完成？

我是初学者学习/实现算法，所以任何帮助指向我在正确的方向赞赏！谢谢。

2010-02-21 Checksum

我发现了一个PostScript文件，讲述了一个**禁忌搜索**（http://en.wikipedia.org/wiki/Tabu_search）算法，用于为教师分配课程（http://www.uv.es/sestio /TechRep/tr01-01.ps）。这主要是数学启发式。我希望它给你一些方向。 – 2010-02-21 05:57:42

这是重复的。几周前我回答了这个问题：http://stackoverflow.com/questions/2177836/algorithm-for-creating-a-school-timetable – 2010-02-21 07:17:03

@Stefano，无价的链接！谢谢 – Checksum 2010-02-21 12:09:51

你选择了一个简单的问题开始。像这样的调度优化是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。

来源

2010-02-21 07:14:14 stimms

这个问题每周至少会出现一次，答案（包括我的）总是相同的。我想我们应该在调度算法中创建一个特定的标记（如果不存在的话）。

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

来源

2010-02-21 07:59:59 Grembo

使用哪种算法为学校生成时间表

回答

相关问题