Solving Multiple Timetabling Problems at Danish High Schools

Planning problems at educational institutions are often time-consuming and complex tasks. Educational planning problems are studied using operational research techniques, which have been used with success and resulting in great improvements on the field. Educational planning problems are often divided into four main categories; University Course Timetabling, High School Timetabling, Examination Timetabling and Student Sectioning.

This Ph.D. thesis addresses some of the planning problems the high schools are struggling with annually, and it is partitioned into three research directions; High School Timetabling, Student Sectioning and the Meeting Planning Problem. The underlying work of this thesis is carried out as an Industrial Ph.D. project in co-operation with the Danish software company MaCom A/S, which delivers administrative software solutions for high schools in Denmark.

Research in High School Timetabling has mainly been concentrated on local problems until recently. By the creation of an XML-format, XHSTT, and applicable wide ranging benchmark instances, it is been possible to solve the more generalized High School Timetabling problem. The first part of this thesis presents two approaches for the High School Timetabling problem of XHSTT; a heuristic method and an exact method.

The heuristic method presented is an Adaptive large Neighborhood Search (ALNS) and was submitted as a contribution to the Third International Timetabling Competition in 2011. The algorithm was one of the finalists, and it achieved a third place. For the exact method a Mixed Integer Programming (MIP) model has been developed, and a two stage method has been used to solve it in a state-of-the-art MIP solver.

Using the exact method has made it possible to generate lower bounds for several instances and to prove optimality of a few. In the second part two different Student Sectioning problems at Danish high schools have been presented with three papers. Firstly the Elective Course Planning problem has been presented, which is the problem of assigning 2nd and 3rd year students to elective courses given their requests.

The problem has been solved using Dantzig-Wolfe decomposition in a Branch-and-Bound framework. The method applied shows that a previously applied method performs poorly and is insufficient. A more comprehensive model has been created, containing the lacking constraints, using the more appropriate name; Elective Course Student Sectioning.

The problem is solved using ALNS and solutions are proven to be close to optimum. The algorithm has been implemented and made available for the majority of the high schools in Denmark. The second Student Sectioning problem presented is the sectioning of each first year student to a cohort, based on his/hers study line request, and two elective courses based on the requests for these.

The High School Student Sectioning problem has been modeled as a bipartite network model and solved using two solution methods, a direct and a sequential method. The results show that by using a sequential method it is possible to gain much better results. The last part of the thesis is concerned the Meeting Planning Problem and presented with two papers.

The Consultation Timetabling Problem is one of the minor, but still time-consuming, planning problems at the Danish high schools. Two types of consultations are presented; the Parental Consultation Timetabling Problem (PCTP) and the Supervisor Consultation Timetabling Problem (SCTP). One mathematical model containing both consultation types has been created and solved using an ALNS approach.

The received solutions are close to optimum. Based on the Consultation Timetabling Problem, a Generalized Meeting Planning Problem (GMPP) has been developed. Column generation with a Branch-and-Price (B&P) algorithm has been applied as solution method for the GMPP, and it has been tested on the PCTP and SCTP problem instances.

The results prove that the B&P algorithm is an efficient method for solving the GMPP, and that the ALSN method performs better than anticipated. The thesis has been aiming at solving the planning problems to optimality, or near optimality, and opening up research within the area of educational timetabling.

It gives a thorough introductions to the domain of educational planning problems and presents several solution methods for High School Timetabling, Student Sectioning and the Meeting Planning Problem. From an industrial point of view, this thesis has been able to formulate different high school planning problems as mathematical models and solve them using operational research techniques.

Two of the models and the suggested solution methods have resulted in implementations in an actual decision support software, and are hence available for the majority of the high schools in Denmark. These implementations can improve the solution process in terms of time and quality.