The consultation timetabling problem at Danish high schools

Simon Kristiansen, Matias Sørensen, Michald B. Herold, Thomas Riis Stidsen

    Research output: Contribution to journalJournal articleResearchpeer-review

    Abstract

    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.
    Original languageEnglish
    JournalJournal of Heuristics
    Volume19
    Pages (from-to)465-495
    ISSN1381-1231
    DOIs
    Publication statusPublished - 2013

    Keywords

    • High school
    • Timetabling
    • Metaheuristics
    • Integer programming
    • Adaptive Large Neighborhood Search
    • F-Race tuning

    Fingerprint Dive into the research topics of 'The consultation timetabling problem at Danish high schools'. Together they form a unique fingerprint.

    Cite this