Comparing Solution Approaches for a Complete Model of High School Timetabling

Matias Sørensen, Thomas Riis Stidsen

    Research output: Book/ReportReportResearch

    331 Downloads (Pure)

    Abstract

    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.
    Original languageEnglish
    PublisherDTU Management Engineering
    Number of pages44
    ISBN (Print)978-87-92706-98-0
    Publication statusPublished - 2013
    SeriesDTU Management Engineering Report
    Number5.2013

    Keywords

    • High School Timetabling
    • Modeling
    • Integer Programming
    • Decomposition
    • Adaptive Large Neighborhood Search

    Fingerprint Dive into the research topics of 'Comparing Solution Approaches for a Complete Model of High School Timetabling'. Together they form a unique fingerprint.

    Cite this