Course Scheduling Algorithms: why use of DFS or Graph coloring is not suggested?

Question

I need to develop a Course Timetabling software which can allot timeslots and rooms efficiently. This is a curriculum based routine, not post-enrollment based. And efficiently means classes are assigned timeslots according to staff time preferences and also need to minimize 1st year-2nd year class overlap so that 2nd year students can retake the courses they've failed to pass.(and also for 3rd-4th yr pair).

Now, at first i thought that would be an easy problem, but now it seems different. Most of the papers i've looked on uses Genetic Algorithm/PSO/Simulated Annealing or these type of algorithm. And i'm still unable to interpret the problem to a GA problem. what i'm confused about is why almost none of them suggests DFS or Graph-coloring algorithm?

Can someone explain the scenario if DFS/graph-coloring is used? Or why they aren't suggested or tried.

Velate

Depending on the details, your problem is probably "NP-Complete". If so, for all known exact algorithms the time increases exponentially with problem size. For anything other than very small problems you will have to use some sort of approximate heuristic, not an exact algorithm. General graph coloring is definitely NP-Complete. – Dendy

To expand a little, any commonly occurring hard problem has known good heuristics that achieve a reasonable combination of accuracy and performance for that problem. Unless I were embarking on a major research project, I would go with one of the commonly recommended methods. – Dendy

Job Scheduling, or "Time-tabling" problems tend to be NP-Complete if several real-world constraints are brought in. With a lot of simplification, they can be in P Time. So DFS like searches are an option, but not the preferred method. It is just that several other optimization techniques (that you've found) are more suited for this class of problems. – Levant

Too-rapid invocation of "NP-complete" is the bane of reasonable discussions of scheduling algorithms. Many real-world problems can be solved in P proportional to acceptable error. Vazirani's "Approximation Algorithms" is a must-have for the bookshelf for those doing this type of work: amazon.com/Approximation-Algorithms-Vijay-V-Vazirani/dp/… – Elbertina

If the problem size is small enough I'd suggest brute force (e.g. DFS) since this is guaranteed to find the optimal solution, but once the problem size gets too large it will cause brute force to take way too long. – Tillis

Answer 1

My experience with solving this problem for a complex department, is that the hard constraints (like no overlapping of courses that are taken by the same population, and hard constraints of the teachers) are rather easily solvable by exact methods. I modeled the problem with 0-1 integer linear programming, and solved it with a SAT-based tool called minisat+. Competitive commercial tools like cplex can also solve it. So with today's tools there is no need to approximate as suggested above, even when the input is rather large. Now, optimizing the solution is a different story. There can be many (weighted) objectives, and finding the solution that brings the objective to minimum is indeed very hard computationally (no tool that I tried can solve it within 24 hours), but they reach near optimum in a few hours (I know it is near optimum because I can compute the theoretical bound on the solution).

Cornered

It depends on the size of the problem but this certainly how I'd start. No reason to write an algorithm when you can hit it with a MIP hammer first and see if it's good enough. Writing the model also has the very useful added benefit of making you think about the problem and make sure you have the right constraints and objective(s). – Orchitis

Answer 2

This document describes applying a GA approach to university time-tabling, so it should be directly applicable to your requirement: Using a GA to solve university time-tabling

Abet

I have updated the link - not sure what happened but I must have extracted the URL incorrectly. Sorry. – Abet