Enhancing Examination Timetables with Advanced Tabu Search

*Duong TuanAnh
Faculty of Computer Science and Engineering, HoChiMinh City

Nguyen Minh Luan
Faculty of Computer Science and Engineering, HoChiMinh City University of Technology

Tran Quoc Trung
Faculty of Computer Science and Engineering, HoChiMinh City University of Technology

Abstract
In this paper, we present a solving method for the university examination timetabling problem consisting of two phases: the first phase to provide an initial solution that satisfies all hard constraints and the second phase to apply a local search on the initial solution to obtain high quality solution, taking the soft constraints into account. The local search in the second phase is an advanced Tabu Search, ATABU, that uses both recency-based short-term tabu list and a frequency-based longer-term tabu list. We perform preliminary experiments of the method on real data sets and the results are quite encouraging.