Title : Enhancement of simulated annealing algorithm for solving university course timetabling problems

​ Simulated Annealing (SA) is a common meta-heuristic algorithm that has been widely used to solve complex optimization problems. This is due to its ease of implementation and capability to escape from local optimum. However, it could still get trapped in local optima and takes longer time to find good quality solution. Thus, the aim of this thesis is to improve the SA performance and overcome the disadvantages. The research work is divided into three phases. Two real world university course timetable datasets, which are the ITC2007-Track3 benchmark and UKM-faculty of engineering datasets, were used in this research. The first phase is to conduct a thorough investigation on three of SA components: the initial temperature, cooling schedule and neighbourhood structure. We observed that the high initial temperature will lead SA to accept any solution (wasting more computational time), whilst the lower value leads SA to quickly trap in local optima.  Based on the findings from this phase, for each component we proposed a technique to overcome their limitations. These are: (i) a dynamic initial temperature mechanism that dynamically chose the suitable initial temperature for each instance problem; (ii) adaptive cooling schedule that will adjust the temperature value during the search; and (iii) a new neighbourhood structure to improve the search ability by minimizing the random selection. In the second phase, we hybridized simulated annealing with memory called (SAM) to enhance the capability of SA in escaping the local optima. Moreover, we also proposed a guided shaking procedure for SA-M that can effectively diverts the search to another promising region, using adaptive soft constraints weights.  In the final phase, we further enhanced the SAM by integrating a tabu list memory (SA-TL-AM) on SAM to avoid cycling. Experimental results showed that the SA-TL-AM has improved the performance of SAM by having more capability in escaping from local optimum and reduces possibility of re-trapping in a recently local optimum.  A new adaptive neighbourhood’s selection (AD-NS) is another technique that we designed to select a neighbourhood with the best improvement strength history. AD-NS enhanced the solution quality by avoiding the disconnected neighbourhood structure. The experimental results showed that the proposed techniques and approaches in all phases have outperformed the SA and comparable to other approaches in the literature (tested on ITC2007-Track3 and UKM-faculty of engineering university course timetabling datasets). Therefore, we can conclude that the research objectives have been achieved

​​