Academic journal article Journal of Digital Information Management

Improving Exam Time Tabling Solution Using Tabu Search

Academic journal article Journal of Digital Information Management

Improving Exam Time Tabling Solution Using Tabu Search

Article excerpt

ABSTRACT; A feasible exam timetable is generated using a method based on constraint satisfaction and heuristics. We investigate the usage of tabu search to further improve the quality of the exam timetable. Different length of short term tabu list and the long term tabu list is examined. Short term tabu list without long term tabu list and vice versa is also tested. Different search iteration based on maximum null iteration and maximum tabu relaxation is also considered. Experiments are carried out on an actual dataset from Universiti Sains Malaysia. Results from these experiments show the relative significance of long term tabu list relative to short term tabu list for this dataset.

Categories and Subject Descriptors

D.3.2[Language Classifications]: H.2 [Database Management]

General Terms

Database, Data Processing

Keywords: : Exam timetabling, Tabu search, Meta heuristics

1 Introduction

A feasible solution for an exam timetabling problem is a solution that satisfies all the hard constraints while trying to maximize the satisfaction of the soft constraints. Given a feasible exam timetabling solution we look for ways to improve the quality of the solution. In other words, we like to increase the satisfaction of soft constraints while maintaining the satisfaction of hard constraints.

Recent research work based on the tabu search technique shows it capabilities to produce an optimal solution with the usage of the structured memory by A.Scharef & L. Di Gaspero [1], George M. White and Bill S. Xie [2], and L. Paquete and T. Stiatzle [3].

In this paper, we present our work in repairing a feasible exam timetabling solution using Tabu Search. We focus on the usage of memory structure to improve the quality of the solution. The memory structure we use includes recency-based short term memory and frequency-based long term memory. The formation of parameter used to tune the memory structure is very important to the success of tabu search technique application as suggested in Michel Gendreau [4].

Hence, experiments are conducted to investigate the effect of memory structure over the quality of solution produced. We investigated the usage of tabu search to improve the quality of the solution. Attempts were made using a combination of different length short term tabu list with different length long term tabu list. The search was also varied by using several different combinations of maximum null iteration and maximum tabu relaxation.

2 Exam Time Tabling

The exam timetabling problem is the assignment of exams to timeslots while satisfying a set of constraints. Improving a feasible exam timetabling is by further trying to minimize the violation of soft constraints while maintaining the hard constraints are being satisfied. In an optimal case, the solution will have both hard and soft constraints satisfied.

Hard constraints are constraints that must be satisfied in order to create a feasible solution. The hard constraints that we take into consideration for our problem includes:

No clashing--not to have more than one exam at one timeslot for a same student. (i.e. a student should not take more than one exam at one particular timeslot.)

Exam availability--some exams must happen together at the same time. Due to the nature of the subjects, certain exams are required to be held at one same timeslot. (i.e. exams with more than one subject codes, exams with different group of students, the lecturer likes the exams to be held at the same time). These exams that have to be scheduled in the same time slot are referred to as concurrent exams in this paper.

Room capacity--Numbers of students sitting for all exams in one particular timeslot must not exceed the capacity at that timeslot. Timeslot constraint--some exams are not allow to be held on a predefine range of timeslots.

In this research, the soft constraints that we wish to satisfy includes:

No consecutive exams--For each student, one exam in a day is always preferred. …

Search by... Author
Show... All Results Primary Sources Peer-reviewed

Oops!

An unknown error has occurred. Please click the button below to reload the page. If the problem persists, please try again in a little while.