EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

3022. A hybrid meta-heuristic for the generation of feasible large-scale course timetables using instance decomposition

Contributed abstract in session MA-58: Automated Timetabling, stream Automated Timetabling.

Monday, 8:30-10:00
Room: S07 (building: 101)

Authors (first author is the speaker)

1. João Almeida
CEGIST, University of Lisbon - Instituto Superior Técnico
2. José Rui Figueira
CEG-IST, Instituto Superior Técnico, Universidade de Lisboa
3. Daniel Santos
CEGIST, Instituto Superior Técnico, Universidade de Lisboa

Abstract

We propose a hybrid meta-heuristic for generating feasible course timetables for large-scale problems. A novel instance decomposition technique is introduced. Different types of constraint violations are regarded as objective functions to be minimised. The search targets slots where the most violations are identified. After some iterations without improvements, the most challenging constraint groups are given new weights, guiding the search towards non-dominated solutions, which improve the performance of these objectives, even if the total sum of the violations increases. If this mechanism fails to escape these local optima, a shaking phase is conducted. The decomposition mechanism operates as follows: curricula are iteratively introduced to the problem, and new feasible solutions are found considering the increasing set of lectures. The assignments from each iteration can be modified in subsequent iterations. We tested real-world instances from our university and random sub-divisions. For sub-divisions with 400 curricula, decomposition reduces the solution times to up to 27%. For real-world instances, with 1288 curricula, the reduction is 18%. Clustering curricula with common characteristics when incrementing the instances improved the solution times by 18% more than random increments. Feasible solutions for the real-world instance are found in 21 minutes, whereas the commercial software takes several hours, and can fail to comply with some constraints.

Keywords

Status: accepted

Back to the list of papers