Parallel Scatter Search Algorithms for Exam Timetabling

Introduction

Wren (1999) defined timetabling as “the allocation, subject to constraints, of given resources to objects being placed in space time, in such a way as to satisfy as nearly as possible a set of desirable objectives”. The university timetabling problem is of two types: exam timetabling and course timetabling. In this work, we are concerned with the exam timetabling problem. Exam timetabling consists of allocating periods and rooms to a set of exams, subject to constraints, which can be hard or soft (Qu et al., 2009). An example of hard constraints is room capacity. Examples of soft constraints are number of students having consecutive exams and number of students with multiple exams per day. In our case, we consider a predefined number of periods and a limited number of rooms as resources for allocation. Despite the similarity between exam and course timetabling, they are different; they have different objectives and constraints. For example, in course timetabling, a hard constraint is not to schedule courses taught by the same instructor at the same time, whereas this might be requested by some instructors for exam timetabling and in the same room whose capacity must allow such assignment. In addition, even in exam timetabling alone, different problem versions have been reported and addressed in a variety of ways. Furthermore, it is not possible to schedule exams at the same time as the corresponding course, since courses normally last one hour whereas exams last 2-3 hours. Also, students might take 4 or 5 courses on the same days whereas this is considered unacceptable for exams.

The university timetabling problem is an NP-hard optimization problem (Schaerf, 1999). A number of heuristic algorithms have been developed for finding sub-optimal exam timetabling solutions. Examples of these algorithms and techniques are: case-based reasoning technique in combination with a simple simulated annealing algorithm (Burke et al., 2003); hybridization within a graph based hyperheuristic framework (Qu & Burke, 2009); genetic and evolutionary algorithms (Cheong et al., 2009; Cote et al., 2005); clustering and clique algorithms (Carter & Johnson, 2001; Lotfi & Cerveny, 1991); tabu search (Kendall & Hussin, 2005); simulated annealing approaches (Burke et al., 2004; Mansour et al., 2003; Thompson & Dowsland, 1998); scatter search algorithm (Mansour et al., 2009); hybrid heuristics (Azimi, 2005; Bilgin et al., 2007; Pillay & Banzhaf, 2009); heuristic ordering based method combined with backtracking technique (Carter & Johnson, 2001); great-deluge hyper-heuristic (Ozcan et al., 2010). A recent survey of exam timetabling techniques appears in Qu et al. (2009). Clearly, the exam timetabling literature includes a wide variety of approaches and algorithms and presents a variety of objectives and constraints for the problem (Qu et al., 2009) and, thus, different ways to evaluate solutions. This variety is based on theoretical assumptions as well as diverse requirements found, in reality, among different institutions even within the same country (Burke et al., 1996). Hence, methods that address real-world problems based on real-world data are still needed for bridging the gap between research and practice (McCollum, 2007).