1. UKM Learning and Research Repository
2. PHD Thesis / Tesis PHD
3. Faculty of Information Science and Technology / Fakulti Teknologi dan Sains Maklumat

Title:	Enhancement Of Simulated Annealing Algorithm For Solving University Course Timetabling Problems
Authors:	Hassan Younis Al-Tarawneh (P46477)
Supervisor:	Masri Ayob, Assoc. Prof. Dr.
Keywords:	Simulated Annealing Algorithm Course Timetabling Problems Annealing Algorithm Heuristic algorithms
Issue Date:	19-Jul-2013
Description:	Simulated Annealing (SA) is a common metaheuristic algorithm that has been widely used to solve complex optimization problems. This is due to its ease of implementation and its capability to escape from the local optimum. However, it could still get trapped in the local optimum and it takes a longer time to find a good quality solution. Thus, the aim of this thesis is to improve the SA performance and overcome the disadvantages. Two real world university course timetable datasets, which are the ITC2007 Track3 benchmark and the UKM-Faculty of Engineering datasets, were used in this research. The first phase involved conducting a thorough investigation into three SA components: the initial temperature, the cooling schedule and the neighbourhood structure. It was observed that a high initial temperature would cause the SA to accept any solution (wasting more computational time), whilst a lower value would cause it to be quickly trapped in local optimum. Based on the findings from this phase, a technique has been proposed for each component to overcome these limitations. These are: (i) a dynamic initial temperature mechanism that dynamically chooses a suitable initial temperature for each instance problem; (ii) an 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, the simulated annealing was hybridized with a memory called (SAM) to enhance the capability of the SA in escaping the local optimum. Moreover, a guided shaking procedure was also proposed for the SAM that can effectively divert the search to another promising region using adaptive soft constraint weights. In the final phase, the SAM was further enhanced by integrating a tabu list memory (SA-TL-AM) onto the SAM to avoid repetition. The experimental results showed that the SA-TL-AM improved the performance of the SAM by increasing its capability to escape from local optimum and reducing the possibility of it being re-trapped in recent local optimum. The new adaptive neighbourhood selection (AD-NS) is another technique that has been designed to select a neighbourhood with the best improvement strength history. The AD-NS enhanced the solution quality by avoiding the disconnected neighbourhood structure. The experimental results showed that the proposed techniques and approaches in all the phases outperformed the SA and were comparable to other approaches in the literature (tested on ITC2007 Track3 and the UKM-Faculty of Engineering's university course timetabling datasets). Therefore, it can be concluded that the research objectives have been achieved.,PhD
Pages:	157
Call Number:	T57.84 .T347 2013 3
Publisher:	UKM, Bangi
Appears in Collections:	Faculty of Information Science and Technology / Fakulti Teknologi dan Sains Maklumat

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.