Kristiansen, Simon1; Sørensen, Matias1; Herold, Michald B.3; Stidsen, Thomas Riis1
1 Department of Management Engineering, Technical University of Denmark2 Management Science, Department of Management Engineering, Technical University of Denmark3 MaCom A/S
In the different stages of the educational system, the demand for efficient planning is increasing. This article treats the $$\mathcal NP $$ NP -hard Consultation Timetabling Problem, a recurrent planning problem for the high schools in Denmark, which has not been described in the literature before. Two versions of the problem are considered, the Parental Consultation Timetabling Problem (PCTP) and the Supervisor Consultation Timetabling Problem (SCTP). It is shown that both problems can be modeled using the same Integer Programming model. Solutions are found using the state-of-the-art MIP solver Gurobi and Adaptive Large Neighborhood Search (ALNS), and computational results are established using 300 real-life datasets. These tests show that the developed ALNS algorithm is significantly outperforming both Gurobi and a currently applied heuristic for the PCTP. For both the PCTP and the SCTP, it is shown that the ALNS algorithm in average provides results within 5 % of optimum. The developed algorithm has been implemented in the commercial product Lectio, and is therefore available for approximately 95 % of the Danish high schools.
Journal of Heuristics, 2013, Vol 19, p. 465-495
High school; Timetabling; Metaheuristics; Integer programming; Adaptive Large Neighborhood Search; F-Race tuning