使用哪种算法来生成学校时间表
我正在开发一个简单的应用程序，它将为学校生成时间表（每日计划表）。我已经阅读了算法的基础知识，但对从哪里开始感到困惑。
问题：
为班级分配教师时要考虑到许多限制，例如：
1) 主题
2) 老师的专业知识
3）连续不超过2个班级..等等
不言而喻，不应该有重叠。基本上我需要分配 N 个老师到 M 个班级，每天有固定的工作时间（8）。
输入：
1) 班级总数
2) 教师及其学科专业知识
3) 每个班级的科目/课程
4) 每天每班授课次数
5) 其他灵活的限制，例如教师每天的最小/最大工作时间、每个教师每周的总工作时间等
我的问题：
1）将其视为具有多个约束的分配问题是否正确？
2）我应该使用哪种算法？ （匈牙利算法？）
3）我应该从一次性获取整套约束开始，然后生成表，还是应该在中间步骤中完成？
我是学习/实现算法的初学者，因此任何帮助我指明正确方向的帮助都值得赞赏！谢谢。
I'm working on a simple application that will generate time table (daily planner) for schools. I've read up basics of algorithms, but confused as to where to start.
The problem:
Allocate teachers to classes taking into consideration a lot of constraints like:
1) Subject
2) Expertise of teacher
3) Not more than 2 classes continuously.. etc
It goes without saying that there should be no overlapping. Basically I need to assign N teachers to M classes with a fixed number of working hours everyday (8).
The inputs:
1) Total number of classes
2) Teachers along with their subject expertise
3) Subjects/Courses for each class
4) Number of lectures per class per day
5) Other flexible constraints like minimum/maximum working hours for a teacher per day, total working hours per teacher per week, etc
My questions:
1) Is it right to look at it as an assignment problem with multiple constraints?
2) Which algorithm should I use? (Hungarian algorithm?)
3) Should I start by getting the whole set of constraints at one go, and then generate the table, or should it be done in intermediate steps?
I'm a beginner to learning/implementing algorithms, so any help to point me in the right direction appreciated! Thanks.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
你选择了一个棘手的问题作为开始。像这样的调度优化是NP完全的。有大量关于如何处理此类问题的论文，此类问题被称为约束满足。您可以执行详尽的搜索，这是最简单的，但也非常耗时，如果您有多个类，则它将不起作用。您可以看一下 Solver Foundation，它是一套用于解决此类问题的 .net 工具。斯科特汉塞尔曼做了一个关于它的播客
此处http://www.hanselminites.com/default.aspx?showID=209 你可以在这里找到更多相关信息
http://code.msdn.microsoft.com/solverfoundation。如果您喜欢自己尝试查看 GSAT，或者其中一些进化算法看起来很有趣 http://www.springer.com/engineering/book/978-3-540-48582-7。
You've picked a doozy of a problem to start with. Scheduling optimization like this is NP complete. There are a ton of papers on how to deal with problems like this the class of problem is known as constrain satisfaction. You can perform an exhaustive search which is easiest but is also very time consuming, if you have more than a handful of classes it won't work. You might take a look at solver foundation which is a suite of tool for .net for solving these sorts of things. Scott Hanselman did a podcast about it
here http://www.hanselminutes.com/default.aspx?showID=209 and you can find more about it here
http://code.msdn.microsoft.com/solverfoundation. If you fancy doing it yourself try looking at GSAT or otherwise some of these evolutionary algorithms look interesting http://www.springer.com/engineering/book/978-3-540-48582-7.
这个问题在这里每周至少出现一次，而且答案（包括我的）总是相同的。我认为我们应该在调度算法上创建一个特定的标签（如果不存在的话）。
我将重申，对于此类调度问题最合适的解决方案技术是约束规划领域。虽然其他优化技术对于小问题来说是可以的，但对于某些约束而言，公式化通常是痛苦的。考虑您必须为一些简单约束创建的所有整数变量。因为问题通常需要一堆可行的时间表（或确定不可行性）而不是最优解决方案，所以 CP 是首选方法，因为这就是它的设计目的。大多数其他方法要求用户“强制”解决实际上不存在的问题的最优条件。
This question keeps coming up at least once a week here and the answers (including mine) are always the same. I think we should create a specific tag on scheduling algorithms if one doesn't exist.
I'll reiterate that the most suitable solution technique for scheduling problems like this are in the area of constraint programming. While other optimization techniques are OK for small problems, formulation often is painful for some constraints. Consider all of the integer variables you have to create for some simple constraints. Because the problem often requires a bunch of feasible schedules (or to determine infeasibility) rather than an optimal solution, CP is the preferred approach since that's what it's designed to do. Most other approaches require a user to "force" an optimality condition on the problem where one doesn't really exist.