Teacher time schedule algorithm

Question

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.

Solution 1

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)

Solution 2

I've tackled similar planning/scheduling problems in the past and the AI technique that is often best suited for this class of problem is "Constraint Based Reasoning".

It's basically a brute force method like Laurenty suggested, but the approach involves applying constraints in an efficient order to cause the infeasible solutions to fail fast - to minimise the computation required.

Googling "Constraint Based Reasoning" brings up a lot of resources on the technique and its application to scheduling problems.

Solution 3

I think you might be missing some constraints.

One would prefer where possible to have teachers scheduled to classes for which they are certified.

One would suspect that the classes that are requested, and the expected headcount in each would be significant.

I think the place to start would be to list all of your constraints, figure out a data structure to represent them.

Then create some sort of engine to that builds a trial solution, then evaluates it for fitness according to the constraints.

You could then throw the fun genetic algorithms part at it, and see if you can get the fitness to increase over time as the genes mix.

Start with a small set of constraints, and increase them as you see success (if you see success)

There might be a way to take the constraints and shoehorn them together with something like a linear programming algorithm.

I agree. It sounds like a fun challenge

Solution 4

This reminds me of this blog post about scheduling a conference, with a video explanation here.

How I would do it:

Have the population include two things:

• Who teaches what class (I expect the teachers to teach one subject).
• What a class takes on a specific time slot.

This way we can't have conflicts (a teacher in 2 places, or a class having two subjects at the same time).

The fitness function would include:

• How many time slots each teacher gives per week.
• How many time slots a teacher has on the same day (They can't have a full day of teaching, this too must be balanced).
• How many time slots of the same subject a class has on the same day (They can't have a full day of math!).

Maybe take the standard deviation for all of them since they should be balanced.

Solution 5

Answering my own question:

The FET project mentioned by gnud uses this algorithm:

Some words about the algorithm: FET uses a heuristical algorithm, placing the activities in turn, starting with the most difficult ones. If it cannot find a solution it points you to the potential impossible activities, so you can correct errors. The algorithm swaps activities recursively if that is possible in order to make space for a new activity, or, in extreme cases, backtracks and switches order of evaluation. The important code is in src/engine/generate.cpp. Please e-mail me for details or join the mailing list. The algorithm mimics the operation of a human timetabler, I think.

Link

---

Following up the "Constraint Based Reasoning" lead by Stringent Software on Wikipedia lead me to these pages which have an interesting paragraph:

Solving a constraint satisfaction problem on a finite domain is an NP-complete problem in general. Research has shown a number of polynomial-time subcases, mostly obtained by restricting either the allowed domains or constraints or the way constraints can be placed over the variables. Research has also established relationship of the constraint satisfaction problem with problems in other areas such as finite model theory and databases.

View more solutions

Comments

[Sklivvz]

The headcount would be fixed (say x classes of y students). All teachers are equally certified. At least in Italian schools that is... ;)

[Sklivvz]

The problem is, I suspect that even generating a bad, but sane solution is almost np-hard... Should I generate a random one to start with? That really doesn't sound feasible

[EvilTeach]

Ya, omitting those constraints simplifies things. I think sitting down and drawing a picture of possible data structures for the constraints would be a good step. Do the part you know, and the rest may become visible.

[EvilTeach]

Ya, I probably would generate a large initial set, run them through fitness, then start breeding them, injecting new random ones intermittently, if they start to die off too fast. You are really gonna have to do it, to see what happens.

[Feek]

I don't agree. I think that a hybrid between CP-OR and then maybe AI. I have seen good academic generic solutions with CP-OR mix but this research field never gets any money so it seems that we are doomed.

[Geoffrey De Smet]

Brute force usually hits the wall at about n=10 (depends on the use case). The thing is, even if you double your processing power, the wall hardly moves. Smart forms of brute force (backtracking, pruning) etc may move the wall to n=20 but no further. In my experience, Tabu Search and Late Acceptance works best (much better than Genetic Algorithms).