Metaheuristics for high school timetabling

Metaheuristics for high school timetabling

0.00 Avg rating0 Votes
Article ID: iaor2001736
Country: United States
Volume: 9
Issue: 3
Start Page Number: 275
End Page Number: 298
Publication Date: Mar 1998
Journal: Computational Optimization and Applications
Authors: , ,
Keywords: education
Abstract:

In this paper we present the results of an investigation of the possibilities offered by three well-known metaheuristic algorithms to solve the timetable problem, a multi-constrained, NP-hard, combinatorial optimization problem with real-world applications. First, we present our model of the problem, including the definition of a hierarchical structure for the objective function, and of the neighborhood search operators which we apply to matrices representing timetables. Then we report about the outcomes of the utilization of the implemented systems to the specific case of the generation of a school timetable. We compare the results obtained by simulated annealing, tabu search and two versions, with and without local search, of the genetic algorithm. Our results show that GA with local search and tabu based on temporary problem relaxations both outperform simulated annealing and handmade timetables.

Reviews

Required fields are marked *. Your email address will not be published.