Optimizing heuristic timetabling solvers using graph neural networks

Abstract

This thesis investigates the integration of graph neural networks (GNNs) into heuristic solvers for university course timetabling. The aim is to explore whether learned structural information can guide the solver toward better solutions. The proposed method replaces the solver’s uniform random selection in its mutation step with a weighted sampling strategy derived from a GNN-generated similarity matrix between classes and feasible room–time pairs. The approach is evaluated by comparing the GNN-guided solver with the baseline solver across multiple runs, random seeds, and hyperparameter settings. Evaluation metrics include final hard and soft constraint violations, violation trends over time to analyze search behavior, and robustness to changes in solver parameters. To study the effect of training quality, multiple GNN models trained for different durations are tested. The results show that guidance from a sufficiently trained GNN can achieve small but consistent improvements in soft-constraint satisfaction. However, the baseline solver with uniform random sampling remains more reliable for reaching feasibility and maintaining low hard-penalty scores. Blending uniform and similarity-based sampling did not provide a clear advantage, and guided runs were more sensitive to solver hyperparameters. Overall, the benefits of neural guidance were modest compared to the additional training cost, suggesting that while the approach has potential, it is not yet practically viable for the tested instance.

Date of Award	2025
Original language	English
Supervisor	Stefan Wagner (Supervisor)