Learning assignment order in an ant colony optimiser for the university course timetabling problem

Abstract

Previous studies have employed Ant Colony Optimisation to solve the University Course Timetabling task — which requires the order of lecture assignments to be defined for its construction graph. Various heuristic or random ordering techniques have been proposed in the literature, but uncertainty remains regarding the best approach for this. We investigate the effect that permuting assignment order has on the quality of timetable produced. As part of this we develop a novel MAX-MIN Ant System including dynamic constraint handling and partial function evaluations. We also explore algorithm variants with and without Local Search and employ a form of transfer learning to identify appropriate permutations. We find that between smaller problems in the International Timetabling Competition 2007 benchmark, timetabling performance can be improved using such an approach. However we find that we lose this performance gain when attempting to transfer to considerably larger problems — indicating that similar structures are required when using a ‘learnt’ permutation approach in such a framework.