Which algorithm to use for generating time table for schools

Question

I'm working on a simple application that will generate time table (daily planner) for schools. I've read up basics of algorithms, but confused as to where to start.

The problem:
Allocate teachers to classes taking into consideration a lot of constraints like:
1) Subject
2) Expertise of teacher
3) Not more than 2 classes continuously.. etc

It goes without saying that there should be no overlapping. Basically I need to assign N teachers to M classes with a fixed number of working hours everyday (8).

The inputs:
1) Total number of classes
2) Teachers along with their subject expertise
3) Subjects/Courses for each class
4) Number of lectures per class per day
5) Other flexible constraints like minimum/maximum working hours for a teacher per day, total working hours per teacher per week, etc

My questions:
1) Is it right to look at it as an assignment problem with multiple constraints?
2) Which algorithm should I use? (Hungarian algorithm?)
3) Should I start by getting the whole set of constraints at one go, and then generate the table, or should it be done in intermediate steps?

I'm a beginner to learning/implementing algorithms, so any help to point me in the right direction appreciated! Thanks.

Answer 1

You've picked a doozy of a problem to start with. Scheduling optimization like this is NP complete. There are a ton of papers on how to deal with problems like this the class of problem is known as constrain satisfaction. You can perform an exhaustive search which is easiest but is also very time consuming, if you have more than a handful of classes it won't work. You might take a look at solver foundation which is a suite of tool for .net for solving these sorts of things. Scott Hanselman did a podcast about it here http://www.hanselminutes.com/default.aspx?showID=209 and you can find more about it here http://code.msdn.microsoft.com/solverfoundation. If you fancy doing it yourself try looking at GSAT or otherwise some of these evolutionary algorithms look interesting http://www.springer.com/engineering/book/978-3-540-48582-7.

Answer 2

This question keeps coming up at least once a week here and the answers (including mine) are always the same. I think we should create a specific tag on scheduling algorithms if one doesn't exist.

I'll reiterate that the most suitable solution technique for scheduling problems like this are in the area of constraint programming. While other optimization techniques are OK for small problems, formulation often is painful for some constraints. Consider all of the integer variables you have to create for some simple constraints. Because the problem often requires a bunch of feasible schedules (or to determine infeasibility) rather than an optimal solution, CP is the preferred approach since that's what it's designed to do. Most other approaches require a user to "force" an optimality condition on the problem where one doesn't really exist.