Scheduling Students to Classes

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.

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.

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.