Journal of Computer Science

Integrating a Repairing-based Genetic Algorithm-Neighborhood Search Structure in Solving the Course Timetabling Problem

Chong-Keat Teoh, Habibollah Haron, Antoni Wibowo and Mohd. Salihin Ngadiman

DOI : 10.3844/jcssp.2016.510.516

Journal of Computer Science

Volume 12, Issue 10

Pages 510-516

Abstract

The course timetabling problem is not a trivial task as it is an NP-hard and NP-complete problem and many solutions have been proposed due to its high complexity search landscape. In essence, the nature of the course timetabling problem is to assign a lecturer-course entity to existing teaching venue and timeslot in an academic institution. In this article, the authors propose a Genetic Algorithm-Neighborhood Search (GANS) to construct a feasible timetable for courses offered by a department in the faculty of a local university in Malaysia. The framework of the solution is as follow: The feasible timetable is first constructed by Genetic Algorithm, which includes are pair operator which attempts to repair infeasible timetables. Upon feasibility, the second phase exploits the initial feasible solution using three neighborhood structures to search for an improved solution and global optimum. The experimental results demonstrate the efficiency and effectiveness of the various neighborhood structures in exploiting the feasible solutions to yield the global optimum.

Copyright

© 2016 Chong-Keat Teoh, Habibollah Haron, Antoni Wibowo and Mohd. Salihin Ngadiman. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.