Local search techniques for large high school timetabling problems

The high school timetabling problem regards the weekly scheduling for all t he lectures of a high school. The problem consists in assigning lectures to periods in such a nag that no teacher (or class) is involved in more than one lecture at a time, and other constraints are satisfied. The problem is NP-complete and is usually tackled using heuristic methods. This paper desc ribes a solution algorithm (and its implementation) based on local starch t echniques. The algorithm alternates different techniques and different type s of mol es and makes use of an adaptive relaxation of the hard constraints . The implementation of the algorithm has been successfully experimented wi th in some large high schools with various kinds of side constraints.