Solving a highly constrained Dutch School Timetabling Problem

Abstract

Constructing a timetable for high schools in the Netherlands comes with many problems. One of the most prominent problems is how to assign students to classes, specifically for students that are in their second half of their education. Commonly, class assignments are made during the creation of cluster schemes. We investigate a local search method to create cluster schemes and compare this against the existing heuristic. Additionally, we create a new method to create the class assignments, which focuses on maximizing the number of classes that can be scheduled together. We make comparisons between the class assignments produced by this method and the class assignments gained from creating cluster schemes. This comparison is made by creating initial schedules using the class assignments and improving them with use of local search.