Timetabling algorithms on Java platform

OData support
Supervisor:
Dr. Kővári Bence András
Department of Automation and Applied Informatics

The task of creating timetables is most commonly used in educational institutions, although we can find examples in everyday life. In schools the main goal is to create a timetable that fits all classes and teachers. It has to optimally utilize the participant’s time and the school’s resources. Creating such a timetable is not a trivial task. We can’t possibly examine all the timetables due to the lack of time, so the best possible solution is to use complex algorithms.

For my concrete project I choose timetabling problems, developed by the International Timetabling Competition. The organizers of the competition precisely defined the inputs and the expected attributes of the timetables. These tasks describe real timetable planning problems of an Italian university.

I made a program based on genetic algorithms in Java language. In the first part of my thesis I described the competition and the genetic algorithms as well. Designing of the task included elaborating the details of the software and the genetic algorithm. The next step was the implementation of my solution. The first tests of the program pointed out the need for the optimization of the performance, so this had to be done before further work. At the beginning the results (timetables) were not good enough, so I decided to modify some of the genetic operators and I also added some newer ones. These changes could improve on the found timetables.

The completed algorithm is able to create timetables according to the conditions set by the competition. Iteratively, it can improve their quality to a certain point. In addition, it can generate a solution for creating an optional timetable if the input is in the right format (equals with the inputs of the competition).

Downloads

Please sign in to download the files of this thesis.