Mathematical models and algorithms for a high school timetabling problem

This paper investigates a high school timetabling problem in a case study related to Kuwait’s public educational system, which is concerned with assigning teachers to classes and time-slots. Because a direct solution to an initially formulated comprehensive mixed-integer programming model for generating weekly teacher schedules was found to be untenable for practical-sized realistic test instances, we propose in this paper two decomposition approaches to the underlying problem. A two-stage modeling solution approach is presented first, where the initial stage determines weekly time-slots for the classes, based on which, the second stage then assigns teachers to classes. Instead of generating weekly schedules within the model itself, we propose another mixed-integer programming formulation that selects valid combinations of weekly schedules from the set of all feasible schedules, and we design a column generation solution framework to exploit its inherent special structure. Computational results are presented for the proposed solution approaches using several real as well as simulated realistic test problems pertaining to high schools in Kuwait.