School Timetabling Using Heuristic Search

This paper concerns a computer system which produces the bulk of the timetable for a large comprehensive school in England. The complexities of the school's lesson structure are discussed and the various constraints and objectives described. The timetable thus produced was successfully implemented for the academic year starting in September 1994 and was considered by the school to represent a marked improvement on previous timetables as well as being achieved much more swiftly. The solution method involves four phases of heuristic search with little or no manual intervention necessary. In contrast with other timetabling systems, the system completes all the difficult parts of the process to a high-quality standard, with only the final straightforward stages being left to the timetabler. Details of the solution method are outlined and dyiscussed in further detail in an appendix, especially the more innovative parts which involve a form of tabu search with influential diversification guided by the values of the subcosts as well as the overall cost. The system could be generalised so as to be applied to other schools.