Research Article Open Access

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

Chong-Keat Teoh1, Habibollah Haron2, Antoni Wibowo3 and Mohd. Salihin Ngadiman2
  • 1 Tunku Abdul Rahman University College, Malaysia
  • 2 UniversitiTeknologi Malaysia, Malaysia
  • 3 Bina Nusantara University, Indonesia

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.

Journal of Computer Science
Volume 12 No. 10, 2016, 510-516

DOI: https://doi.org/10.3844/jcssp.2016.510.516

Submitted On: 5 July 2015 Published On: 15 December 2016

How to Cite: Teoh, C., Haron, H., Wibowo, A. & Ngadiman, M. S. (2016). Integrating a Repairing-based Genetic Algorithm-Neighborhood Search Structure in Solving the Course Timetabling Problem. Journal of Computer Science, 12(10), 510-516. https://doi.org/10.3844/jcssp.2016.510.516

  • 1,912 Views
  • 1,401 Downloads
  • 1 Citations

Download

Keywords

  • Genetic Algorithm
  • Neighborhood Search
  • Repair Operator
  • University Course Timetabling Problem