Heuristic methods for school timetabling problems

Abstract

This project aims to develop efficient and effective heuristic algorithms to solve school timetabling problems, since the applicability of exact algorithms for this purpose is limited. Initially, we intend to address the high school timetabling problem due to its theoretical and practical importance. In a previous project we developed, for this problem, two new graph-based large scale neighborhood operators for local search algorithms. We also built a dataset with 102 instances. Six algorithms based on ILS (Iterated Local Search) and three based on VNS (Variable Neighborhood Search) incorporating the operators developed have been implemented and tested in the proposed dataset and in a second dataset from literature. The results obtained were consistent with those obtained by state-of-the-art methods. In this project, our objective is to extend the methods developed, in order to increase the effectiveness, flexibility and efficiency of these approaches. In particular, we intend to study large scale neighborhood operators based on integer programming models. Such operators will be combined with local search metaheuristics to develop new algorithms to solve the problem. We also intend to incorporate new case studies (instances) in the existing dataset, making it, an even more representative compilation of real-world situations.