Timetabling is a well-known problem: it is mainly associated with educational institutions, but it can be found in other areas as well. When planning a timetable, we have to arrange a given number of classes in a way that is suitable for everyone involved: no one has to attend two or more classes at the same time.
In addition to the usual requirements, we may want to create a timetable that meets some other requirements as well: for example, if a teacher has only a few lessons on a given day, it is generally better to arrange those lessons in a way that they come right after one another, so that the teacher won’t have a lot of idle time. Although we’re not obliged to meet these requirements, these will result in a better timetable. Such a requirement is called a soft constraint, as opposed to hard constraints which we always have to meet.
Two years ago I created an application which solved timetabling problems using a genetic algorithm, this year I applied constraint logic programming.
In this thesis, following a review of my previous work, I give a short summary of declarative and logic programming, as well as the Prolog language. Next, I show the model which was the basis of the timetabling problems I solved, as well as the Prolog implementation of that model.
I describe the particular steps involved in the implementation of the algorithm starting from a simple algorithm which was designed to solve one particular test case, to the general solution which can handle all the constraints given in the specification. I summarize the problems I encountered during my work along with the solutions I applied to those problems.
The application is able to create a simple timetable which meets the given constraints in the dataset. If there are soft constraints present, the algorithm will try to optimize the solution using those constraints.