algorithm - 安排学生上课

Question

我正在为学校的一个业余项目制作一个网站，学生可以在其中输入他们需要参加的课程，他们想要或不想上课的日子，以及他们什么时候不能上课或不想上课。基础是有课程，每个课程在不同时间有很多部分，学生可以选择不同的教授。对于新生级别的课程，每个课程可以有30多个不同的部分。我在 mysql 数据库中有类和部分，我一直在用 php 进行编码。

到目前为止，我已经让它工作了，但我想让它更快。我一直在阅读其他调度问题，但我正在寻找我正在做的事情的细节。这不是从头开始制定时间表。它正在根据可用的部分制定时间表，并根据学生的输入对它们进行排名。目前对于少数可能的部分，它运行得很快。但是当可能的时间表达到大约 300,000 时，需要大约 30 秒来比较和排列所有内容。我一直在通过更改时间表的生成方式来改进它，但我想更快。我从蛮力生成切换到使用基于树的方法。

我不是在寻求家庭作业帮助或有人为我做这件事。我只想指出我可以学习的现有问题和算法的正确方向。

Answer 1

还记得八皇后之谜吗？我当然希望你这样做，如果没有，先去解决它，然后再回到你的调度任务。

您已经从蛮力转移到了树结构。现在是分支和绑定的时候了。不管你所说的“好的时间表”是什么意思，170000 太多了——你没有修剪你的树。我认为每个学生不会有超过 20 到 50 个非常好的时间表，除非他们上的课很少并且非常灵活。

Answer 2

尝试元启发式算法，例如禁忌搜索或模拟退火。蛮力和分支和绑定的规模不够大。

看看 ITC2007 定义的 drools planner 中的课程示例。它可能是您用例的高级形式（不包括 gui/db）。

Answer 3

看看这个。它可能不是您想要的，但您可以获得一些设计理念。