Lewis, Rhydian M R (2006) Metaheuristics for university course timetabling. PhD thesis, Napier University, Edinburgh, Scotland.
Download (1098kB) | Preview
The work presented in this thesis concerns the problem of timetabling at universities – particularly course-timetabling, and examines the various ways in which metaheuristic techniques might be applied to these sorts of problems. Using a popular benchmark version of a university course timetabling problem, we examine the implications of using a “twostaged” algorithmic approach, whereby in stage-one only the mandatory constraints are
considered for satisfaction, with stage-two then being concerned with satisfying the remaining constraints but without re-breaking any of the mandatory constraints in the process. Consequently, algorithms for each stage of this approach are proposed and analysed in detail.
For the first stage we examine the applicability of the so-called Grouping Genetic Algorithm (GGA). In our analysis of this algorithm we discover a number of scaling-up
issues surrounding the general GGA approach and discuss various reasons as to why this is so. Two separate ways of enhancing general performance are also explored. Secondly, an Iterated Heuristic Search algorithm is also proposed for the same problem, and in experiments it is shown to outperform the GGA in almost all cases. Similar observations to these are also witnessed in a second set of experiments, where the analogous problem of colouring equipartite graphs is also considered.
Two new metaheuristic algorithms are also proposed for the second stage of the twostaged approach: an evolutionary algorithm (with a number of new specialised evolutionary
operators), and a simulated annealing-based approach. Detailed analyses of both algorithms are presented and reasons for their relative benefits and drawbacks are discussed.
Finally, suggestions are also made as to how our best performing algorithms might be modified in order to deal with further “real-world” constraints. In our analyses of these modified algorithms, as well as witnessing promising behaviour in some cases, we are also able to highlight some of the limitations of the two-stage approach in certain cases.
|Item Type:||Thesis (PhD)|
|Uncontrolled Keywords:||Computer programming; Genetic algorithms; Evolutionary algorithms; Graph colouring; Application; University timetables; Method benchmarking; Soft constraints; Evaluation;|
|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|
000 Computer science, information & general works > 000 Computer science, knowledge & systems > 005 Computer programming, programs & data
|Library of Congress Subjects:||Q Science > QA Mathematics > QA76 Computer software|
|Depositing User:||Users 2 not found.|
|Date Deposited:||08 Jul 2008 12:14|
|Last Modified:||12 Jan 2011 04:49|
Actions (login required)