A hybrid evolutionary approach to the university course timetabling problem
Authors:
- 1 September 2007
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 1089778X,p. 1764-1768
Abstract
Combinations of evolutionary based approaches with local search have provided very good results for a variety of scheduling problems. This paper describes the development of such an algorithm for university course timetabling. This problem is concerned with the assignment of lectures to specific timeslots and rooms. For a solution to be feasible, a number of hard constraints must be satisfied. The quality of the solution is measured in terms of a penalty value which represents the degree to which various soft constraints are satisfied. This hybrid evolutionary approach is tested over established datasets and compared against state-of-the-art techniques from the literature. The results obtained confirm that the approach is able to produce solutions to the course timetabling problem which exhibit some of the lowest penalty values in the literature on these benchmark problems. It is therefore concluded that the hybrid evolutionary approach represents a particularly effective methodology for producing high quality solutions to the university course timetabling problem.Keywords
This publication has 9 references indexed in Scilit:
- A graph-based hyper-heuristic for educational timetabling problemsEuropean Journal of Operational Research, 2007
- The Design of Memetic Algorithms for Scheduling and Timetabling Problems2006
- A Tutorial for Competent Memetic Algorithms: Model, Taxonomy, and Design IssuesIEEE Transactions on Evolutionary Computation, 2005
- A time-predefined local search approach to exam timetabling problemsIIE Transactions, 2004
- A Tabu-Search Hyperheuristic for Timetabling and RosteringJournal of Heuristics, 2003
- A Grouping Genetic Algorithm for Graph Colouring and Exam TimetablingLecture Notes in Computer Science, 2001
- A robust simulated annealing based examination timetabling systemComputers & Operations Research, 1998
- Extensions to a memetic timetabling system1996
- A memetic algorithm for university exam timetabling1996