A hybrid genetic algorithm with local search and tabu search approaches for solving the post enrolment based course timetabling problem: Outperforming guided search genetic algorithm

摘要

The post enrolment based course timetabling problem (PECTP) is one type of university course timetabling problem which a set of events has to be assigned into time slots and suitable rooms according to students' enrolment data. This problem is classified as a combinatorial optimization problem and it is very hard to solve the problem efficiently because solving the problem is to find an optimal timetable which it must satisfy all hard constraints and should satisfy soft constraints as much as possible. Moreover, this problem is technically complicated and highly time-consuming and it is known to be in the NP-complete class. In this paper we have developed a genetic algorithm hybridized with a local search technique and a tabu search heuristic for solving the PECTP. The algorithm takes advantage of the exploitation ability of a local search technique and a tabu search heuristic to improve the results obtained in the exploration phase of the genetic algorithm. In addition, the proposed hybrid approach was tested on a set of standard benchmark problem in comparison with other methods from the literature, and experimental results show that the proposed hybrid approach was able to find promising solutions for solving the PECTP.