A great deluge algorithm for a real-world examination timetabling problem

Abstract

The examination timetabling problem involves assigning exams to a specific or limited number of timeslots and rooms with the aim of satisfying all hard constraints (without compromise) and satisfying the soft constraints as far as possible. Most of the techniques reported in the literature have been applied to simplified examination benchmark data sets. In this paper, we bridge the gap between research and practice by investigating a problem taken from the real world. This paper introduces a modified and extended great deluge algorithm (GDA) for the examination timetabling problem that uses a single, easy to understand parameter. We investigate different initial solutions, which are used as a starting point for the GDA, as well as altering the number of iterations. In addition, we carry out statistical analyses to compare the results when using these different parameters. The proposed methodology is able to produce good quality solutions when compared with the solution currently produced by the host organisation, generated in our previous work and from the original GDA.

Keywords:

• examination timetabling
• great deluge algorithm
• scheduling

Acknowledgements

The examination/invigilator data set has been provided by the Academic Management Office (AMO), UMP and the research has been supported by the Public Services Department of Malaysia (JPA) and the Universiti Malaysia Pahang (UMP).