A Combination of Genetic Algorithms and Local Search to Solve a Real Data University Timetable Scheduling Problem

The problem of generating a University timetable is a very complex one because it comprises a lot of parameters (courses, classrooms and their capacities, lectures, professors, students' and professors' preferences etc.) which should be combined successfully. In order to contribute to the solution of this problem we developed a Hybrid Genetic Algorithm (HGA). Generally, a genetic algorithm simulates the nature of the chromosomes in biology, which are comprised of cells called genes. More specifically we adapted to the specificities of this complicated problem a genetic algorithm and we enriched it with prototype local search methods so as to enhance the optimization process. The main contribution of this work is the integration of new techniques that guarantee the integrity of the timetables which are simulated as chromosomes. Our algorithm was based on the real dataset of University of Udine, Italy, and achieves feasible results within a few minutes