Exploring data-driven selection hyper-heuristic approaches for the curriculum-based course timetabling

Abstract

The curriculum-based timetabling problem (CB-CTT) represents a challenging field of study within educational timetabling, with real-world applications that stress its importance. Solving a CB-CTT problem requires allocating a set of courses using limited resources, subject to a set of hard constraints that must be satisfied. The goal then is to find a feasible assignment for every lecture that constitutes the courses to the positions in the timetable formed by a combination of day, period, and room; all while minimizing an objective function as specified by the constraints in the problem.

Designing the timetable for the courses in the incoming term is a problem faced by universities each academic period. Given the complexity of manually designing timetables, automated methods have attracted the attention of many researchers for solving this problem. The design of timetables remains an open problem to this day. According to the no free lunch theorem, different heuristics are effective on different problem instances, stressing the importance of finding automated methods for designing timetables. This dissertation explores novel hyper-heuristic models that rely on various machine learning techniques, such as boosting, clustering and principal component analysis. In total, two models were designed and implemented as results of this work.

The first model relies on gradient boosting algorithms to generate a selection hyper-heuristic. The general idea is that different instances of the CB-CTT are best solved by different heuristics. Hence, the aim is to create a model that learns from the features that describe problem instances and predicts which would be the most suitable heuristic to apply. While the classification model produces promising results in terms of accuracy, the quality of the generated solutions is bounded by the best-known single heuristic.

The second model aims to remove the bounds set by the use of a single heuristic by exploring ways of combining heuristics during the timetable construction process. The selection hyper-heuristic approach is powered by principal component analysis and k-means. The model starts by identifying similar regions in the instance space and keeping track of the performance of each heuristic for those regions. Then, when constructing new timetables, the model determines the most suitable heuristic for a given region of the instance space. The method was able to outperform the synthetic oracle created by taking the result of the best isolated heuristic in several instances.

This dissertation is submitted to the Graduate Programs in Engineering and Information Technologies in partial fulfillment of the requirements for the degree of Master of Science in Computer Sciences with a major in Intelligent Systems.