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
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.
© 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.