EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
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:00Room: 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
- Metaheuristics
- Timetabling
Status: accepted
Back to the list of papers