High school institutions face a number of important planning problems during each schoolyear. This Ph.D. thesis considers two of these planning problems: The High School Timetabling Problem (HSTP) and the Consultation Timetabling Problem (CTP). Furthermore a framework for handling various planning problems is considered, known as the Generalized Meeting Planning Problem (GMPP). The view taken on these problems is that they are mathematical optimization problems, where the goal is to _nd the optimal solution (from the set of all feasible solutions). This view allows state-of-the-art methods from the _eld of Operations Research to be applied. This thesis is composed of three parts. The _rst part introduces the relevant methodologies of Operations Research, describes the considered optimization problems, summarizes the scienti_c articles and lists the scienti_c contributions of the thesis. The second part contains the main scienti_c papers composed during the Ph.D. study. The third part of the thesis also contains scienti_c papers, but these are included as an appendix. In the HSTP, the goal is to obtain a timetable for the forthcoming school-year. A timetable consists of lectures scheduled to time-slots, and each lecture has a number of resource requirements. The goal is to obtain a schedule such that the individual timetable for each resource ful_lls a number of requirements. Two versions of the HSTP are considered: The Generalized High School Timetabling Problem (GHSTP) (based on the publicly available XHSTT format for modeling instances and solutions of the HSTP) and the Danish High School Timetabling Problem (DHSTP). For both problems a complex Mixed-Integer Programming (MIP) model is developed, and in both cases are empirical tests performed on a large number of real-life datasets, which show that the MIP model is a challenge to solve for a state-of-the-art generic MIP-solver. A heuristic based on Adaptive Large Neighborhood Search (ALNS) is developed for the GHSTP, and this heuristic was part of the _nal round of International Timetabling Competition 2011 (ITC2011). An ALNS heuristic is also developed for the DHSTP, and computational results show that this is currently the best known solution algorithm. Furthermore, the thesis shows the relation between the GHSTP and the DHSTP, and instances of the DHSTP are made publicly available in the XHSTT format. An extension of the Two-Stage Decomposition (TSD) method is also shown in this thesis, which makes the TSD capable of handling both the GHSTP and the DHSTP. In a TSD approach, a MIP model is split into two separate models which are solved in sequence, while maintaining optimality (as far as possible). This reduces the total amount of variables signi_cantly compared to the original MIP model. Whether or not the TSD is an exact solution method in the context of GHSTP and DHSTP is determined by certain characteristics of a given dataset. For both the GHSTP and the DHSTP, the TSD is capable of producing lower bounds, even though it might not be an exact method for the dataset at hand. For the DHSTP, the TSD is shown to be theoretically capable of producing near-optimal solutions for an arbitrary dataset, and computational results show that the TSD provides both better solutions and better bounds than the original MIP model. For the GHSTP, the TSD is an exact method for the majority of the considered datasets. However, in this case the computational results do not clearly show that the TSD outperforms the original MIP model. An algorithm hybridizing MIP and metaheuristics is developed and applied to both the GHSTP and the DHSTP. This algorithm is part of the recent trend called matheuristics, which is a promising class of solution approaches for many types of optimization problems. In the implemented matheuristic, a MIP solver is used as a low-level search mechanism, and an adaptive layer of the algorithm guides the search on the overall level. In terms of the GHSTP, this matheuristic has shown to be competitive with the winner of Round 2 of ITC2011. For the DHSTP, the algorithm outperforms the exact approaches, but not the ALNS algorithm when compared on a low time-limit. Given a time-limit of two hours, the matheuristic obtains solutions which are within 15.2% of optimum in average for 100 real-life dataset of the DHSTP. The CTP has not been described in the scienti_c literature before. The problem consists of scheduling meetings between a single student and a number of teachers to time-slots. The primary aim of a meeting is to allow the teachers to provide feedback to the student w.r.t. educational progress. A proof of NP-hardness is given, and a MIP model is developed. Also for this problem, an ALNS heuristic is shown to perform very well, producing solutions that are within 3% of optimum in average on 200 real-life datasets. The GMPP is a framework for handling a number of di_erent planning problems. The goal of the GMPP is to schedule meetings between certain resources to time-slots, such that no resource attends more than one meeting at any time. A model of the problem is proposed which is based on a Column Generation approach. A key feature of this model is that most problem-speci_c constraints are handled by the subproblem of the Column Generation algorithm. This leads to a Branch-and-Price algorithm for the GMPP which is independent of these problem-speci_c details, but still applicable to a range of optimization problems. As a test-case for the GMPP, the CTP is used. The Branch-and-Price algorithm obtains solutions within 3% of optimum in average on the same set of instances as the ALNS algorithm. The thesis show that real-world high school timetabling problems are a challenge to solve for exact methods, even with the recent advances of generic MIP solvers and when applying state-of-the-art techniques such as TSD. In a practical setting for these problems, the tests performed in this thesis show that heuristics in general produce the best solutions. However, exact methods which can provide bounds on optimum are valuable for evaluating the performance of the heuristics. For the CTP, the performance of an exact algorithm (the Branch-and-Price algorithm) is competitive with the performance of the tested heuristic (the ALNS heuristic). This shows that it is possible to use exact methods for CTP in a practical setting.
Main Research Area:
Stidsen, Thomas Riis, Pisinger, David, Herold, Michael B.
Department of Management Engineering, Technical University of Denmark, 2013