An Outperforming Hybrid Discrete Particle Swarm Optimization for Solving the Timetabling Problem

摘要

There are various categories of the timetabling problem, and one of them that is quite interesting is the post enrolment based course timetabling problem (PECTP). The PETCP is classified as an NP-complete and a combinatorial optimization problem, which is well known that no algorithm to solve it by spending time in the degree of the polynomial due to its complexity. Furthermore, the solution of the problem is an optimal timetable that has to satisfy all hard constraints and soft constraints as much as possible reflecting its quality. In this paper, we have developed a Hybrid Genetic-based Discrete Particle Swarm Optimization algorithm hybridizing with two different local search algorithms including Local Search and Tabu Search (HGDPSOLTS) to improve the performance of searching solution by using the advantage of their exploitation abilities. In addition, we also have improved the representation of a solution to reduce complexity in computation, resulting in improving performance for solving the discrete function The proposed hybrid approach was tested on a standard benchmark problem in comparison with other approaches from the literature and the experimental results indicated that the proposed hybrid approach was able to find effective solutions for solving the PECTP, and it can outperform all algorithms from the literature.