Projects per year
Abstract
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 stateoftheart 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 schoolyear. A timetable consists of lectures scheduled to timeslots, 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 MixedInteger Programming (MIP) model is developed, and in both cases are empirical tests performed on a large number of reallife datasets, which show that the MIP model is a challenge to solve for a stateoftheart generic MIPsolver. 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 TwoStage 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 nearoptimal 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 lowlevel 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 timelimit. Given a timelimit of two hours, the matheuristic obtains solutions which are within 15.2% of optimum in average for 100 reallife 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 timeslots. 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 NPhardness 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 reallife 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 timeslots, 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 problemspeci_c constraints are handled by the subproblem of the Column Generation algorithm. This leads to a BranchandPrice algorithm for the GMPP which is independent of these problemspeci_c details, but still applicable to a range of optimization problems. As a testcase for the GMPP, the CTP is used. The BranchandPrice algorithm obtains solutions within 3% of optimum in average on the same set of instances as the ALNS algorithm. The thesis show that realworld high school timetabling problems are a challenge to solve for exact methods, even with the recent advances of generic MIP solvers and when applying stateoftheart 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 BranchandPrice 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.
In the HSTP, the goal is to obtain a timetable for the forthcoming schoolyear. A timetable consists of lectures scheduled to timeslots, 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 MixedInteger Programming (MIP) model is developed, and in both cases are empirical tests performed on a large number of reallife datasets, which show that the MIP model is a challenge to solve for a stateoftheart generic MIPsolver. 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 TwoStage 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 nearoptimal 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 lowlevel 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 timelimit. Given a timelimit of two hours, the matheuristic obtains solutions which are within 15.2% of optimum in average for 100 reallife 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 timeslots. 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 NPhardness 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 reallife 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 timeslots, 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 problemspeci_c constraints are handled by the subproblem of the Column Generation algorithm. This leads to a BranchandPrice algorithm for the GMPP which is independent of these problemspeci_c details, but still applicable to a range of optimization problems. As a testcase for the GMPP, the CTP is used. The BranchandPrice algorithm obtains solutions within 3% of optimum in average on the same set of instances as the ALNS algorithm. The thesis show that realworld high school timetabling problems are a challenge to solve for exact methods, even with the recent advances of generic MIP solvers and when applying stateoftheart 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 BranchandPrice 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.
Original language  English 

Publisher  DTU Management Engineering 

Number of pages  247 
Publication status  Published  2013 
Fingerprint Dive into the research topics of 'Timetabling at High Schools'. Together they form a unique fingerprint.
Projects
 1 Finished

Dynamisk optimering af skemalægning på gymnasielle uddannelser
Sørensen, M., Stidsen, T. J. R., Herold, M. B., Røpke, S., Lübbecke, M. & Kendall, G.
01/12/2010 → 26/05/2014
Project: PhD