动态调度系统使用什么算法？
我计划开发一个专家系统，自动适应学校教师的工作量（时间、教学量等），并生成与某个系主任想要分配的内容至少 90% 准确的班级、房间某个学期的时间表。
使用什么算法？启发式？优化？非常感谢任何建议或帮助！
I'm planning to develop an expert system that automatically fits the school faculty's work load (time, teaching load, etc), and generate class sections, room that is at least 90% accurate with what the Director of a certain department wants to assign the schedule for a certain semester.
What algorithm to use? Heuristics? Optimization? Any suggestions or help is highly appreciated!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
以下是一些一般性观察：
1) 很少从头开始尝试手动调度。相反，有人从上一年的时间表开始，并根据需求的变化对其进行修改。用计算机模拟这一过程的一种方法是使用爬山算法，该算法反复尝试一些小的改变来改进迄今为止的解决方案。然后可以按照当前的时间表开始。
2) 手动过程是否会终止并得出结论：这些要求总体上无法实现并且必须放弃其中一些要求？在这种情况下，您的算法必须足够透明，以便可以理解失败，或者至少能够提出此类更改（例如，通过最大化惩罚函数，使其能够生成不满足所有原始约束的“最不坏”的解决方案）。我知道一个案例，复杂的基于约束的方法被更简单的算法所取代，因为基于约束的系统的失败没有提供足够的用户反馈。
3) 奇怪的是，下一代系统根本没有使用复杂的调度。粗略地说，事实证明，在必须做出决策时，复杂的调度决策的所有后果都无法预见，而且从长远来看，一个可以无限期维持的简单可预测的调度比不断地重新安排日程，以获取短暂的小优势。
Here are some general observations:
1) Manual scheduling is rarely attempted from scratch. Instead, somebody starts with the schedule for the previous year and alters it to take account of changes in requirements. One way of mimicing this with a computer is to use a hill-climbing algorithm, which repeatedly tries a number of small changes to improve a solution so far. This can then be started off at the current schedule.
2) Does the manual process ever terminate with the conclusion that the requirements are collectively unachievable and that some of them must be dropped? In that case your algorithm must be transparent enough that failures can be understood, or at least capable of proposing such changes (e.g. by maximising a penalty function which allows it to produce a "least bad" solution which does not satisfy all of the original constraints). I know of one case where a sophisticated constraint-based approach was replaced by a much simpler algorithm because failures of the constraint-based system did not give enough user feed back.
3) Curiously enough, the next generation system did not use sophisticated scheduling at all. It turned out - roughly speaking - that at the time the decisions had to be made not all of the consequences of sophisticated scheduling decisions could be forseen, and, in the long run, a simple predictable schedule that could be maintained indefinitely was more productive than constantly rearranging schedules to grab small momentary advantages.
我的两个朋友在课堂项目中做了类似的事情。他们使用模拟退火启发式。他们的结论是，这可能不是完成这项工作的最佳工具。
嘿，知道什么不该做会很有用，对吧？ :)
Two friends of mine did something similar for a class project. They used the simulated annealing heuristic. They concluded that it might not be the best tool for the job.
Hey, knowing what not to do can be useful, right? :)
查看课程课程Drools Planner 的课程安排示例（恐怕是开源的，java） 。它使用元启发式方法，例如模拟退火和禁忌搜索。
Take a look at the curriculum course lesson scheduling example of Drools Planner (open source, java I am afraid). It uses meta-heuristics such as
simulated annealingandtabu search.这是一篇关于使用遗传算法进行动态调度的论文...您可能会发现这里的一些想法很有用......即使域不同，我认为这个想法更普遍适用。
Here is a paper on dynamic scheduling using genetic algorithms... you might find some of the ideas here useful... even if the domain isn't the same, I think the idea is more generally applicable.