Teacher time schedule algorithm
This is a problem I've had on my mind for a long time. Being the son of a teacher and a programmer, it occurred to me early on... but I still haven't found a solution for it.
So this is the problem. One needs to create a time schedule for a school, using some constraints. These are generally divided in two categories:
Sanity Checks
- A teacher cannot teach two classes at the same time
- A student cannot follow two lessons at the same time
- Some teachers must have at least one day off during the week
- All the days of the week should be covered by the time table
- Subject X must have exactly so-and-so hours each week
- ...
Preferences
- Each teacher's schedule should be as compact as possible (i.e. the teacher should work all hours for the day in a row with no pauses if possible)
- Teachers that have days off should be able to express a preference on which day
- Teachers that work part-time should be able to express a preference whether to work in the beginning or the end of the school day.
- ...
Now, after a few years of not finding a solution (and learning a thing or two in the meanwhile...), I realized that this smells like a NP-hard problem.
Is it proven as NP-hard?
Does anyone have an idea on how to crack this thing?
Looking at this question made me think about this problem, and whether genetic algorithms would be usable in this case. However it would be pretty hard to mutate possibilities while maintaining the sanity check rules. Also it's not clear to me how to distinguish incompatible requirements.
A small addendum to better specify the problem. This is applied to Italian school style classrooms where all students are associated in different classes (for example: year 1 section A) and the teachers move between classes. All students of the same class have the same schedule, and have no choice over which lessons to attend.
Answer
I am one of the developer that works on the scheduler part of a student information system. During our original approach of the scheduling problem, we researched genetic algorithms to solve constraint satisfaction problems, and even though we were successful initially, we realized that there was a less complicated solution to the problem (after attending a school scheduling workshop)
Our current implementation works great, and uses brute force with smart heuristics to get a valid schedule in a short amount of time. The master schedule (assignment of the classes to the teachers) is first built, taking in consideration all the constraints that each teacher has while minimizing the possibility of conflicts for the students (based of their course requests). The students are then scheduled in the classes using the same method.
Doing this allows you to have the machine build a master schedule first, and then have a human tweak it if needed.
The scheduler current implementation is written in perl, but other options we visited early on were Prolog and CLIPS (expert system)