The high-school timetabling problem consists in assigning all the lectures of a high school to the time periods in such a way that no teacher (or class) is involved in more than one lecture at a time and other side constraints are satisfied. The problem is NP-complete and is usually tackled using heuristic methods. This paper describes a solution algorithm (and its implementation) based on Tabu Search. The algorithm interleaves different types of moves and makes use of an adaptive relaxation of the hard constraints. The implementation of the algorithm has been successfully experimented in some large high schools with various kinds of side constraints.
Tabu search techniques for large high-school timetabling problems
SCHAERF, Andrea
1996-01-01
Abstract
The high-school timetabling problem consists in assigning all the lectures of a high school to the time periods in such a way that no teacher (or class) is involved in more than one lecture at a time and other side constraints are satisfied. The problem is NP-complete and is usually tackled using heuristic methods. This paper describes a solution algorithm (and its implementation) based on Tabu Search. The algorithm interleaves different types of moves and makes use of an adaptive relaxation of the hard constraints. The implementation of the algorithm has been successfully experimented in some large high schools with various kinds of side constraints.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
