Time tabling is a complex optimisation problem given its large number of constraints (e.g., no overlap between core modules for a particular year) or cost functions (e.g., minimise the distance between any two consecutive lectures/TA/labs).
Many techniques have been used to address various versions of the problem, such as, Constraint-based methods or Meta-heuristics methods, but the problem is still largely open. A conference (PATAT, the International Conference on the Practice and Theory of Automated Timetabling), is held every two years to present new techniques to address the problem. [the student(s) will find plenty of ideas in the proceedings of the previous editions]
The objective of this project is to study the timetabling problem, to evaluate classical optimisation techniques and to develop a novel method (a 3 step meta-heuristic). The students will study various classical and less classical optimisation techniques, and will apply them on (relatively) large scale problems.
Possible objectives:
- Design and implementation of simple (greedy, local search, genetic) algorithms for the (mono-objective) time tabling problem
- Evaluation of these techniques on a benchmark
- Design and implementation of a 3 step metaheuristic
Reading:
- https://www.utwente.nl/ctit/hstt/archives/XHSTT-2014/ (data set of instances of the time tabling problem)
- http://www.patatconference.org/ (the home page of the PATAT series of conferences)
- Burke, Edmund Kieran, and Sanja Petrovic. “Recent research directions in automated timetabling.” European Journal of Operational Research 140.2 (2002): 266-280.
- Schaerf, Andrea. “A survey of automated timetabling.” Artificial intelligence review 13.2 (1999): 87-127.