安排学生上课
我正在为学校的一个业余项目制作一个网站，学生可以在其中输入他们需要参加的课程、他们想要或不想上课的日期以及他们何时不能上课或不想上课。基本原则是有课程，每个课程在不同时间有许多部分，由不同的教授供学生选择。对于新生级别的课程，每个课程可以有 30 多个不同的部分。我在 mysql 数据库中有类和部分，并且我一直在 php 中编码。
到目前为止，我已经可以正常工作了，但我想让它更快。我一直在阅读有关其他调度问题的信息，但我正在寻找我正在做的事情的具体细节。这并不是从头开始制定时间表。它根据可用的部分制定时间表，并根据学生输入的内容对它们进行排名。目前，对于少数可能的部分，它运行得很快。但当可能的时间表达到大约 300,000 个时，需要大约 30 秒的时间来对所有内容进行比较和排名。我一直在通过改变时间表的生成方式来改进它，但我想更快。我从暴力生成转向使用基于树的方法。
我不是在寻求家庭作业帮助，也不是要求有人为我做这件事。我只是想通过我可以学习的现有问题和算法来指明正确的方向。
I am making a website for a side project at school where students enter the classes they need to take, what days they want or don't want classes, and when they cant have or don't want classes. The basics are there are classes, and each class has many sections at different times with different professors that a student can choose from. With the freshman level classes, there can be over 30 different sections for each class. I have the classes and sections in a mysql database and I have been coding in php.
So far I have it working but I want to make it faster. I have been reading about other scheduling problems but I am looking for specifics to what I am doing. This isn't making schedules from scratch. It is making schedules from what sections are available and ranking them based on what the students inputs. Currently for few possible sections, it runs fast. But when the possible schedules get to about 300,000, it takes around 30 seconds to compare and rank everything. I have been improving it by changing how schedules are generated but I want to faster. I switched from brute force generating to using a tree based method.
I'm not asking for homework help or for someone to do this for me. I just want to be pointed in the right direction with already existing problems and algorithms that I can learn about.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
还记得八皇后拼图吗？我当然希望你能这样做，如果没有的话，先去解决它，然后再回来处理你的调度任务。
您已经从暴力转向树结构。现在是时候进行分支绑定了。无论你所说的“良好的时间表”是什么意思，170000 都太多了——你没有对你的树进行足够的修剪。我认为每个学生的真正好的时间表不会超过 20-50 个，除非他们上的课很少并且非常灵活。
Remember the eight queens puzzle? I sure hope you do, if not, go and solve it first, then come back to your scheduling task.
You have already moved from brute force to a tree structure. Now it's time for branch and bound. Whatever you mean by "good schedules", 170000 is too much — you do not prune your tree enough. I do not think that there could be more than 20-50 really good schedules for each student, unless they take very few classes and are extremely flexible.
尝试元启发法，例如禁忌搜索或模拟退火。
蛮力和分支定界的规模还不够大。
看看我在 drools planner 中的课程示例，由 ITC2007 定义。
它可能是您的用例的高级形式（不包括 gui/db）。
Try metaheuristics such as tabu search or simulated annealing.
Brute force and branch and bound don't scale up enough.
Take a look at my curriculum course example in drools planner, as defined by ITC2007.
Its probably an advanced form of your use case (not counting gui/db).
看看这个。它可能不完全是你想要的，但你可以得到一些设计想法。
Have a look at this. It may not be exactly what you want but you can get some design ideas.