安排学生上课

Question

我正在为学校的一个次要项目做一个网站，在那里学生们进入他们需要的课程，他们想要或不想要的课程，以及他们不能或不想要课程的时候。基本情况是有课程，每个课程在不同的时间有许多部分，有不同的教授，学生可以从中选择。对于新生级别的课程，每个课程可以有30多个不同的部分。我在mysql数据库中有类和节，并且我一直在用php编写代码。

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

我并不是要你帮我做作业，也不是要别人帮我做这件事。我只想通过已经存在的问题和我可以学习的算法被指引到正确的方向。

Answer 1

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

你已经从蛮力转移到了树形结构。现在是branch and bound的时候了。无论你所说的“良好的时间表”是什么意思，170000都太多了-你没有足够地修剪你的树。我不认为每个学生会有超过20-50个真正好的时间表，除非他们只上了很少的课，而且非常灵活。

Answer 2

尝试元启发式算法，如禁忌搜索或模拟退火。蛮力、分支和界限不能充分放大。

请看我在drools planner中的课程示例，这是由ITC2007定义的。它可能是你的用例的高级形式(不包括gui/db)。

Answer 3

看看this吧。它可能不完全是你想要的，但你可以得到一些设计想法。