Memetic Algorithms for the High School Timetabling Problem

This work presents the application of Memetic Algorithms for the High School Timetabling Problem. The addressed model of the problem was proposed by the Third International Timetabling Competition (ITC), which released many instances from educational institutions around the world and attracted seventeen competitors. The Memetic Algorithm uses as subroutine the winner algorithm of the Third ITC in the refinement phase. It consists in apply a mixed Simulated Annealing - Iterated Local Search approach to all the individuals in the population at each iteration. The Memetic Algorithms were able to overcome the winner of Third ITC solver, beating it in 10 out of 16 instances. Most of them were instances with less than 1,000 lessons to schedule, thus, we conclude that the Memetic Algorithm approach is suitable, especially to small instances of the problem.