University Course Timetabling Using a Hybrid Harmony Search Metaheuristic Algorithm

摘要

University course timetabling problem (UCTP) is considered to be a hard combinatorial optimization problem to assign a set of events to a set of rooms and timeslots. Although several methods have been investigated, due to the nature of UCTP, memetic computing techniques have been more effective. A key feature of memetic computing is the hybridization of a population-based global search and the local improvement. Such hybridization is expected to strike a balance between exploration and exploitation of the search space. In this paper, a memetic computing technique that is designed for UCTP, called the hybrid harmony search algorithm (HHSA), is proposed. In HHSA, the harmony search algorithm (HSA), which is a metaheuristic population-based method, has been hybridized by: 1) hill climbing, to improve local exploitation; and 2) a global-best concept of particle swarm optimization to improve convergence. The results were compared against 27 other methods using the 11 datasets of Socha et al. comprising five small, five medium, and one large datasets. The proposed method achieved the optimal solution for the small dataset with comparable results for the medium datasets. Furthermore, in the most complex and large datasets, the proposed method achieved the best results.