Subject: Course timetabling with interacting departments

From: Clarissa Van Hoyweghen <[email-masked]>
Date: Tue, 25 Apr 2000 16:48:14 +0100

Hello,

I am a Belgian PhD student working on genetic algorithms and I'm not
well into the field of timetabling. I'm studying constraint satisfaction

problems which I believe are similar to clustered or hierarchical
timetabling problems. Could someone point me to relevant papers on this
subject?

Thanks,

Clarissa Van Hoyweghen

The following is a more detailed description of what I mean by
"clustered/hierarchical timetabling":

Suppose I want to solve a course timetabling problem for a university.
The problem can be divided in different subproblems, each subproblem
represents a course timetabling problems for a department. A few
teachers give courses at different departments. They force
synchronization between the different subproblems. (Is this the right
terminology?)

Looking at all possible solutions of the timetabling problem, I see that

some courses can only be given at one specific time. For example because

the teacher can only give that particular course at that fixed time. I'd

say that these courses belong to the "backbone" of this problem. If the
synchronisation between the subproblems is done before the courses
belonging to the backbone have their right time slot, it is possible
that these courses will never get assigned the right time slot and that
the solution of the problem never will be found. Therefore I propose
following strategy: First try to find the backbone and assign time slots

to these courses. Then synchronize the subproblems, assign time slots
to the courses given by teachers giving courses at different
departments.
Finally, assign time slot to the rest of the courses.