Constructing School Timetables Using Tabu Reward Algorithm

The construction of timetables for universities or schools is an extremely complex problem, whose manual solution requires much effort. The Class/Teacher Timetabling Problem (CTTP) deals with the weekly scheduling of encounters between teachers and classes of an educational institution. Since CTTP is a NP-hard problem for nearly all of its variants, the use of heuristic methods for its resolution is justified. This paper presents an efficient Tabu Search (TS) heuristic with new memory based intensification strategy for CTTP. In Addition some algorithms to detect semi-lessons and double lessons which are common in Iranian schools have been presented.

Keywords:

Genetic Algorithm , Timetabling , School Scheduling