Peter Ross (Artificial Intelligence, University of Edinburgh)

Exam timetabling by genetic algorithms: a cautionary tale
Wednesday 18 February 1998 at 15.30, JCMB 6324

Abstract

Over the past several years we have done considerable research into solving exam timetabling problems by genetic algorithms. The simplest approach to such problems is based on graph-colouring, but extra constraints such as seating capacity and the desire to spread out each student's exams complicate the picture. A conventional GA-based approach appears to work: we use it in earnest for timetabling the modular MSc exams across several departments, and various other universities have used our software to solve their own large problems.

Nevertheless, there are surprises. It is possible to construct simple examples which the GA cannot hope to solve. It is also possible to construct small and solvable problems P1, P2 and P3 such that the GA cannot reliably solve P2, it can reliably solve P1 and P3, and yet P1 is contained within P2 which is contained within P3. Moreover, a number of more classical methods fail in the same way on these problems.

A more promising way forward seems to be to get a GA to configure a much simpler Brelaz-like algorithm. This has handled real-world problems involving thousands of exams.

Seminars by year

Current 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996