安排学生上课

我正在为学校的一个侧面项目制作一个网站，学生可以进入他们需要上课的课程，他们想要或不想上课的日子，以及他们不能上课或不上课时。基础知识是有课程的，每个课程都有不同时间的不同部分，有不同的教授，学生可以从中选择。通过新生水平课程，每个班级可以有30多个不同的部分。我有一个MySQL数据库中的类和部分，我一直在PHP编码。安排学生上课

到目前为止，我有它的工作，但我想让它更快。我一直在阅读其他日程安排问题，但我正在寻找具体的工作。这不是从头开始制定计划。它正在制定哪些部分可用的时间表，并根据学生输入的内容对其进行排名。目前只有几个可能的部分，它运行速度很快。但是，当可能的时间表达到约30万时，大约需要30秒来比较和排名。我一直在通过改变时间表的生成方式来改进它，但我希望更快。我从暴力生成转换为使用基于树的方法。

我不是要求功课帮助或有人为我做这个。我只想指出正确的方向，我已经可以了解到现有的问题和算法。

来源

2010-03-11 iloveboxcutters

您是否分析过当前算法的时间复杂度？ – Anurag 2010-03-11 07:02:56

7类，50,400个可能的时间表，总时间：6.47082304955秒，每个时间表的秒数：7788.80825733秒，每个时间表的秒数：0.000128389346221，好的时间表：24,330。 8类，201,600可能的时间表，总时间：18.2666659355秒，每个时间表的秒数：11036.4967921秒，每个时间表的秒数：9.06084619817E-5，良好的时间表：59,024。 |为9班，806,400可能的时间表，总时间：60.9230577946秒，每个时间表的秒数：13236.3677923秒，每个时间表的秒数：7.55494268286E-5，良好的时间表：172,912 – iloveboxcutters 2010-03-11 07:49:13

我拥有它的方式使得时间表是它把第一个在沿着0级的节点中的类节，然后在1级上，如果没有冲突，则将下一个类节添加到每个子节点。并为每个班级做到这一点。在它添加了所有的类之后，所有的路径都是一个很好的时间表。做它像树一样减少我的时间和数量的比较强大的暴力强行它。 – iloveboxcutters 2010-03-11 07:55:53

-1

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

来源

2010-03-11 07:06:30

-1对不起，这看起来并不相关。他希望找到时间表的方式，而不是在网页上显示日历。 – 2011-01-11 17:20:21

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

您已经从暴力转移到树结构。现在是时间branch and bound。无论你的“好日程安排”是什么意思，170000是太多了—你不修剪你的树足够。我不认为每个学生可能有超过20-50个非常好的时间表，除非他们的班级非常少，而且非常灵活。

来源

2010-03-11 14:27:46 AVB

尝试metaheuristics，如禁忌搜索或模拟退火。暴力和分支和界限不足够放大。

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

来源

2011-01-11 15:10:43

安排学生上课

回答

相关问题