Article ID: | iaor20083886 |
Country: | Netherlands |
Volume: | 13 |
Issue: | 6 |
Start Page Number: | 543 |
End Page Number: | 556 |
Publication Date: | Dec 2007 |
Journal: | Journal of Heuristics |
Authors: | Avella Pasquale, Vasil'ev Igor, D'Auria Bernardo, Salerno Saverio |
Keywords: | heuristics, optimization: simulated annealing, heuristics: local search, timetabling |
In this paper we report on a computational experience with a local search algorithm for High-school Timetabling Problems. The timetable has to satisfy ‘hard’ requirements, that are mandatory, and should minimize the violation of ‘soft’ constraints. In our approach, we combine Simulated Annealing with a Very Large-Scale Neighborhood search where the neighborhood is explored by solving an Integer Programming problem. We report on a computational experience validating the usefulness of the proposed approach.