Rotating timetable algorithm?

Question

I'm trying to generate a teaching timetable, where a teacher has a set number of pupils to teach indivudually (eg for music lessons) once a week. The pupils have to rotate, ie not be taught at the same time week on week (the minimum gap allowable between lessons at the same time I call the 'rotation period'). To come up with the simplest form is trivial:

        Week 1  Week 2  Week 3  Week 4  Week 5  Week 6
10.00   Alice   Edgar   David   Charles Bertha  Alice
10.30   Bertha  Alice   Edgar   David   Charles Bertha
11.00   Charles Bertha  Alice   Edgar   David   Charles
11.30   David   Charles Bertha  Alice   Edgar   David
12.00   Edgar   David   Charles Bertha  Alice   Edgar

But I want the user to be able to add rules, eg Alice can't make 10.30 or 11.00 on Week 3, etc. I started with a simple backtracking loop but soon realised that the number of possibilities makes this umfeasible. I'm not a very experienced programmer, and do I realise this might be leading me into advanced programming techniques. But if someone could give me some ideas on how to approach the problem I'd be very grateful. I have of course looked round for help but most of the discussion seems to be for the more complicated task of generating a whole school timetable. Is genetic programming something to look into for this? I'm building the program as a web page using php.

Answer 1

IF you are assuming that each student must come each week and never on the same time each week, you'd have very similar rule-set to Sudoku. If this is the case, you may want to consider looking up some of the algorithms used their to solve that problem because they would be nearly the same for this as far as solution exploration and rules.

I know the Sudoku solvers out there work for 9 by 9 and solve in fractions of a second. Depending on the size of your classes/weeks the techniques there may till be applicable without going into heuristic solvers (or genetic-algorithms etc). I'd suggest wiki and look at backtracking, exact cover or (what they call) brute-force.

If that does not help. Could you clarify what rules you are expecting from your final schedules? Such as minimizing the number of swaps from "default" schedule, or some such? Also, is there any reason you are looking at it as multiple week problem? Could the problem be reduced to a per week problem with no link/connection between weeks? Lastly, how are you representing your exceptions? How are you indicating which times are bad for which students?

Answer 2

Working this out algorithmically is likely to be very computationally expensive, but possible for small numbers of students such as the 6 in your example.

One thing that works in your favour (compared to more general timetabling problems) is the constraint that students have to have a lesson at a different time each week. This significantly reduces the search space. I think I'm right in saying the number of possible permutations are:

n! * (n - 1)!

with n being the number of students, and also the number of weeks the timetable has been generated for.

To solve this problem, generate the set of all valid timetables, and as you do so, check each generated timetable against the set of constraints specified by the student(s).

You presumably don't need to store any of these timetables: if you generate a timetable that doesn't fail any constraint, then publish it; if it does, skip to the next timetable.

If you don't have many constraints this method should generate a valid timetable quickly. On the other hand, if there are enough constraints to make a timetable impossible then there are a huge number of checks required to ensure no timetable is valid (at 6 students there are 86,400 checks but this rapidly rises with the number of students.)

Your idea of using genetic computation to solve this problem probably wouldn't work given your requirements. GC is good at quickly finding a good solution to a problem (and has been used successfully in timetabling problems) but is useless at proving that a solution does not exist.

Answer 3

Many thanks for the various bits of advice. The sudoku link was very helpful for the list of approaches which might be used. I think I've found a way forward with the problem so this is a kind of answer:

I'm using two simple simple backtracking loops, one for each column and one for each slot within it. The most constrained column is calculated each time, and if a column can't be filled, that one is cleared and we go back to the last filled one. Each slot has remembered its array of possibles, so we can carry on from where we left off. The first loop looks for a neat block of pupils as in the example above. If this fails a similar loop allows a column to start and finish later if there are more slots than pupils. If this still doesn't work a third loop allows gaps in a column (not so good for the teacher). If anyone wants to see it in action so far, it's here: http://www.studio-soft.co.uk/timetables/

(only the first loop active at the moment).

gregston