A complex model of high school timetabling is presented, which originates from the problem-setting in the timetabling software of the online high school ERPsystem Lectio. An Integer Programming formulation is described in detail, and a twostage decomposition is suggested. It is proven that both of these formulations are NP-hard. A heuristic based on Adaptive Large Neighborhood Search is also applied. Using 100 real-life datasets, comprehensive computational results are provided which show that the ALNS heuristic outperforms the IP approaches. The ALNS heuristic has been incorporated in Lectio, and is currently available to almost 200 dierent high schools in Denmark. Furthermore, a conversion of the datasets into the XHSTT format is described, and some datasets are made publicly available.
High School Timetabling; Modeling; Integer Programming; Decomposition; Adaptive Large Neighborhood Search
Main Research Area:
Dtu Management Engineering Report
Department of Management Engineering, Technical University of Denmark, 2013