Class scheduling

Question

The problem is like that:

a school has got different classes. Each class has a weekly schedule (8 hours english, 6 hours maths, 2 hours art, etc.). Each teacher has got a certain number of hours in a subset of classes. (I guess school is like that almost everywhere).

Some additional constraits can be added, for example:

1. teacher X will not work on Monday
2. teacher Y needs two consecutive hours in a certain class and so on.

The goal is to find a schedule that optimizes a cost function for constraints.

Finally this is a calssical NP problem i guess. It can be solved using space state search (we try all the possible combinations, using some smart way of searching, and we choose the best solution possible).

• Is this feasible? (combinations are huge, for 10 classes and 30 hours per class and 7 subjects it is around 10^253, even if some substantial pruning is possible: i guess a SAT solver can handle something like that).

• Is there any alterantive to complete search, even if approximated?

Answer 1

This is a Constraint Satisfaction Problem. As mentioned in the link, one of the ways to solve these is using local search methods like min-conflicts or forward checking. You're not guaranteed an optimal solution, but you generally get a "good" solution in a relatively short amount of time.

If you happen to be using Prolog, the clpfd library (Constraint Logic Programming over Finite Domains) is very powerful.