Local search hybridization of a genetic algorithm for solving the University Course Timetabling Problem

Abstract: The University Course Timetabling Problem (UCTP) is the problem of assigning locations (lecture halls, computer rooms) and time slots (time and date) to a set of events (lectures, labs) while satisfying a number of constraints such as avoiding double-bookings. Many variants of problem formulations exist, and most realistic variants are thought to be NP-hard. A recent trend in solving hard scheduling problems lies in the application of hybrid metaheuristics, where improvements are often found by hybridizing a population-based approach with some form of local search. In this paper, an implementation of a Genetic Algorithm (GA) that solves the UCTP is hybridized with local search in the form of Tabu Search (TS). The results show significant improvements to the performance and scalability over the non-hybridized GA. Two application strategies for the TS are investigated. The first strategy performs a switch-over from the GA to the TS, while the second interleaves the two algorithms. The effectiveness of each application strategy is seen to depend on the characteristics of the individual algorithms.