Timetabling using Constraint Logic Programming

OData support
Supervisor:
Dr. Mann Zoltán Ádám
Department of Computer Science and Information Theory

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.

Downloads

Please sign in to download the files of this thesis.