Subject: Some questions on a timetable problem for schools

From: "Manolis A. Metaxakis" <[email-masked]>
Date: Fri, 17 Mar 2000 18:58:08 +0200

I am a teacher in high school in Greece and I teach Computer lessons to students. I know nearly nothing about timetabling and scheduling problems from the point of view of operational research.

   The problem of school timetable is very essential for all high schools in Greece and I think there is no software that REALLY solves it. I would like to know if there is a method or algorithm that REALLY can solve the following problem:

   There are teachers or group of teachers, classes or group of classes and rooms or group of rooms. We know all the combinations of  "the teacher T teaches in Class C at Room R" in a week, but if every teacher, every class and every room must teach or must be teached for example k periods in a week, K, T and C are available only k periods in a week for this to be done and we know those periods.

   We try to find which period of the week must be assigned to which combination of the "the teacher T teaches in Class C at Room R"  for every of these combinations.

   That algorithm must say if there is a solution and which is that solution or that there is not a solution at all.

   Of course I do not mean a method that tests all the possible situations back and forth until a solution is found or not, but a method that solves every problem directly step by step (not back and forth) and be able to find  one or many or ALL the solutions or to say from the beginning that there is no solution at all (because of the given constraints) and NOT just to try and perhaps find A solution.

  If the answer is that there is not such method - algorithm, how important is if someone has a solution for that? Which similar problems can be solved if there is such algorithm?

   Every information (anything) would be very much appreciated.

   Thanks for reading my e-mail!

Best regards!

Manolis  A. Metaxakis
Rethimno, Crete
Greece
[email-masked]