Domain transformation approach to deterministic optimization of examination timetables

Timetabling problems exist in numerous areas including educational timetabling, nurse rostering, transportation timetabling, sports timetabling and so on. Of all the timetabling problems, it was reported that the educational timetabling is one of the most widely studied problems [19]. Examples of educational timetabling include school timetabling, university course timetabling and university examination timetabling. In this study, we focus on the examination timetabling problem.

Exam timetabling represents a challenging computational problem due to the strong inter-dependencies between exams caused by the many-to-many relationship between students and exams. In the exam timetabling problems, the general objective is to generate feasible schedules, which satisfy basic constraints. It is very difficult to define a standard examination timetabling problem due to different constraints present in different academic institutions. Consequently, the

effectiveness of the timetabling methods and algorithms is measured by their performance on a representative set of benchmark problems.

Two types of constraints defined in the timetabling literatures are:

Hard Constraints

These are the constraints that must be fulfilled at all times. The primary hard constraint is that two exams with a common student cannot be scheduled in the same slot. Another hard constraint that needs to be conformed is the room capacity; i.e. there must be enough space in a room to accommodate all students taking a given exam. A timetable which satisfies all hard constraints is called a feasible timetable.

Soft Constraints

Soft Constraints are not absolutely crucial but satisfaction of these constraints is beneficial to students and/or the institution. An example of a soft constraint is a requirement to space out exams taken by individual students as widely as possible across the examination session so that they have adequate revision time between their exams. Normally one cannot satisfy all soft constraints thus there is a need for a performance function measuring the degree of fulfillment of these constraints.

Feasible timetable can have exam orderings which do not satisfy many of the soft constraints. Consequently, a separate optimization process needs to be deployed to obtain better quality schedules. In general, optimization can be seen as a process that maximizes the benefits while minimizing the investment in resources that facilitate these benefits [24]. Optimization can be applied to many areas and disciplines. In the area of the examination scheduling, optimization methods include Constraint Logic Programming [15] and Ant Colony [14] etc, in addition to metaheuristics in recent years [19].

For full text: click here

(Author: Siti Khatijah Nor Abdul Rahim, Andrzej Bargiela, Rong Qu

Published by Sciedu Press)