### 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*