Ross, Peter, Hart, Emma and Corne, Dave (2003) Genetic algorithms and timetabling. In: Advances in Evolutionary Optimisation. Springer-Verlag.Full text not available from this repository. (Request a copy)
Genetic algorithms can be used to search very large spaces, and it would seem natural to use them for tackling the nastier kinds of timetabling problem. We completed an EPSRC-funded project on this last year, and distribute a free package that handles a good range of lecture and exam timetabling problems, including some whole-universty-sized ones; constraints it caters for include room capacities, ordering constraints, spread-'em-out constraints and inter-site travel times. The Department of AI has used this approach for years to handle the timetabling of MSc exams, whose pattern varies considerably from year to year.
You might be inclined to ask yourself either "why should it work?" or "why shouldn't it work?". This talk might answer both questions for you. For problems with only binary constraints, graph-colouring methods are often much more effective; for others a GA may be the only game in town. But even in the realm of graph-colouring problems, there are some surprises. In studying a parameterised space of guaranteed-solvable timetabling-like problems, our GA can solve all highly-constrained problems quickly but may fail to solve some very lightly constrained ones. It turns out that some well-regarded non-evolutionary algorithms exhibit the same weaknesses. Some close study hints at why.
|Item Type:||Book Section|
|Uncontrolled Keywords:||Genetic algorithms; timetabling;|
|University Divisions/Research Centres:||Faculty of Engineering, Computing and Creative Industries > School of Computing|
|Dewey Decimal Subjects:||000 Computer science, information & general works > 000 Computer science, knowledge & systems > 006 Special Computer Methods > 006.3 Artificial intelligence|
|Library of Congress Subjects:||Q Science > QA Mathematics > QA75 Electronic computers. Computer science|
|Depositing User:||Computing Research|
|Date Deposited:||11 Mar 2010 16:26|
|Last Modified:||15 Feb 2011 12:31|
Actions (login required)