DHPC Technical Report DHPC-045
A Comparison of Annealing Techniques for Academic Course Scheduling
M.A. Saleh Elmohamed, Paul Coddington, and Geoffrey Fox
Archived: 14 April 1998
Published in
Practice and Theory of Automated Timetabling II,
Selected Papers from the 2nd International Conference, PATAT'97,
ed. Edmund Burke and Mike Carter,
Lecture Notes in Computer Science, Springer, 1998.
Abstract
In this study we have tackled the NP-hard problem of academic
class scheduling (or timetabling) at the university level.
We have investigated a variety of approaches based on simulated annealing,
including mean-field annealing, simulated annealing with three different
cooling schedules, and the use of a rule-based preprocessor to provide a
good initial solution for annealing.
The best results were obtained using simulated annealing with
adaptive cooling and reheating as a function of cost,
and a rule-based preprocessor. This approach enabled us to obtain valid
schedules for the timetabling problem for a large university, using a
complex cost function that includes student preferences.
None of the other methods were able to provide a complete valid schedule.
PDF version
PostScript version (gzip compressed)
[
DHPC Adelaide |
DHPC Bangor |
Contacts |
People |
Projects |
Reports
]
webmaster@dhpc.adelaide.edu.au