Hybridizing harmony search with local search based metaheuristic for solving curriculum based university course timetabling / Juliana Wahid

Harmony search algorithm (HSA) is a population-based metaheuristic optimization algorithm that imitates the music improvisation process where musicians improvise their instruments’ pitch by searching for a perfect state of harmony. Previous studies have shown that HSA has been successfully adapted for solving combinatorial optimization problems such as university course timetabling problem (UCTP). However, HSA encountered a setback in which the convergence rate and accuracy of the obtained results are reduced because of the solutions in the population are eventually about the same during the final iterations. Thus, this thesis proposed hybrid algorithms between HSA and local search based methods (simulated annealing (SA) and/or great deluge (GD)) to enhance the HSA performance for solving curriculum-based course timetabling (CBCTT) problem which is the variant of UCTP. SA is chosen to be hybridize with HSA for solving CBCTT because in literature, SA was successfully hybridize with HSA to solve other domain of problems. GD is chosen to be hybridize with HSA for solving CBCTT because GD has the related procedure with SA. The result of this approach was compared to other approaches in the literature applied to the same domain and best known solution available in the CBCTT website. The approach produced solutions that are at par quality with the previous published results. Moreover, this approach is able to obtain optimal penalty cost for two problem instances. In this thesis, a CBCTT problem from College of Art and Sciences, Universiti Utara Malaysia (UUM CAS) is also introduced and solved. The real data of UUM CAS timetable was analyzed and processed using the proposed algorithms. The result shows that the quality cost of UUM CAS course timetabling produced by the proposed algorithms is better compared to the course timetable produced by the ready-made software package. The main contributions of this thesis are: a well-defined lecture assignment procedures, with comprehensive comparison of heuristic orderings (with single or combinations) that are able to produce a diverse population of feasible solutions for all problem instances, a comprehensive hybridization settings between population and local search based framework, as well as the formulation and solution of a new curriculum based course timetabling dataset.