INSPIRING FUTURES

Some observations about GA based timetabling.

Ross, Peter, Hart, Emma and Corne, Dave (1997) Some observations about GA based timetabling. In: Proceedings of Practical Applications of Automated Timetabling. Lecture Notes in Computer Science, 1408/1 . Springer Berlin, pp. 115-129. ISBN 978-3-540-64979-3

[img] PDF
Restricted to Registered users only
Available under License Creative Commons Attribution Non-commercial.

Download (812kB) | Request a copy

    Abstract/Description

    Although many people have tried using genetic algorithms (GAs) for exam timetabling, far fewer have done systematic investigations to try to determine whether a GA is a good choice of method or not. We have extensively studied GAs that use one particular kind of direct encoding for exam timetabling. Perhaps not surprisingly, it emerges that this approach is not very good, but it is instructive to see why. In the course of this investigation we discovered a class of solvable problems with interesting properties: our GAs would sometimes fail to solve some of the moderately-constrained problems, but could solve all of the lightly-constrained ones and all of the highly-constrained ones. This is despite the fact that they form a hierarchy: those erratically-solved problems are subproblems of the easily-solved but highly-constrained ones. Moreover, some other non-evolutionary approaches also failed on precisely the same sets. This, together with some observations about much simpler graph-colouring methods based on the Brelaz algorithm, suggest some future directions for GA-based methods.

    Item Type: Book Section
    ISBN: 978-3-540-64979-3
    Uncontrolled Keywords: genetic algorithms; exam timetabling; direct encoding; moderately-constrained problems; lightly-constrained; highly-constrained;
    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 > 004 Data processing & computer science
    Library of Congress Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
    Item ID: 3221
    Depositing User: Computing Research
    Date Deposited: 28 Jul 2010 11:38
    Last Modified: 12 Jan 2011 04:52
    URI: http://researchrepository.napier.ac.uk/id/eprint/3221

    Actions (login required)

    View Item

    Document Downloads

    More statistics for this item...

    Edinburgh Napier University is a registered Scottish charity. Registration number SC018373