Affiliations: Information and Human Centred Computing Group, Research School of Computer Science, Australian National University, Canberra, ACT, Australia
Correspondence:
[*]
Corresponding author: Nandita Sharma, Centre of Information and Human Centred Computing, Research School of Computer Science, Building 108, Australian National University, Canberra, ACT 0200, Australia. Tel.: +61 2 6125 9664; E-mail: [email protected]
Abstract: The examination timetabling problem (ETP) is a NP complete, combinatorial optimization problem. Intuitively, use of properties such as patterns or clusters in the data suggests possible improvements in the performance and quality of timetabling. This paper investigates whether the use of a genetic algorithm (GA) informed by patterns extracted from student timetable data to solve ETPs can produce better quality solutions. The data patterns were captured in clusters, which then were used to generate the initial population and evaluate fitness of individuals. The proposed techniques were compared with a traditional GA and popular techniques on widely used benchmark problems, and a local data set, the Australian National University (ANU) ETP, which was the motivating problem for this work. A formal definition of the ANU ETP is also proposed. Results show techniques using cluster patterns produced better results than the traditional GA with statistical significance of p < 0.01, showing strong evidence. Our techniques either clearly outperformed or performed well compared to the best known techniques in the literature and produced a better timetable than the manually constructed timetable used by ANU, both in terms of quality and execution time. In this work, we also propose clear criteria for specifying the top results in this area.
Keywords: Timetabling, clusters, constraints, data patterns, genetic algorithms
