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

Title:	Local search algorithms for the practical university course timetabling problem
Authors:	Yang Xiao Fei (P64784)
Supervisor:	Masri Ayob, Prof. Dr.
Keywords:	Universiti Kebangsaan Malaysia -- Dissertations Dissertations, Academic -- Malaysia Timetabling problem Algorithms
Issue Date:	8-Oct-2020
Description:	Building an effective model for a practical university course timetabling problem is an ongoing challenging task. This is due to the emergence of external factors that influencing the universities' goals and policies result in the introducing of many new constraints and features. These new features and constraints highly increase the complexity of practical problems. Thus, in this research, we have proposed a new practical curriculum-based university course timetabling problem for the Faculty of Information Technology and Science (FTSM-UCTP) and modelling this problem using integer programming techniques. The proposed FTSM-UCTP contains some specific constraints and features such as courses configurations, multiple sectioning, elective course, and dynamic element assignment. Additionally, the proposed model applies a new objective function, i.e. the objective function with reward and penalty mechanism to evaluate the solution quality. Next, to find a feasible solution of the FTSM-UCTP, we firstly proposed the least saturation degree with dynamic element heuristic (LSDDEA) to make the conventional least saturation degree heuristic applicable to solve the UCTP with dynamic element Assignment features. Furthermore, to tackle the special constraint highly increase an event's schedule difficulty in FTSM-UCTP, the proposed LSD-DEA heuristic is further improved by integrating it to a hierarchical graph colouring heuristic event selection mechanism. Next, we introduced the Tabu Search based Graph Colouring Heuristic Constructive approach for solving the FTSM-UCTP. This proposed TS-HGCH constructive approach has been tested on two instances of the FTSM-UCTP and 21 instances from the benchmark curriculum-based university course timetabling problem. The experiment results provide sufficient evidence to prove the effectiveness of the LSD-DEA heuristic, HGCH events selection mechanism and the proposed TS-HGCH constructive approach. Furthermore, the Simulated Annealing algorithm (SA) has been applied for solving the university course timetabling problems in many works and produced promising results. Thus, we introduced the Reinforcement Learning Simulated Annealing with Improved Reheating (RL-SAIR) approach to optimise the solution quality for the FTSM-UCTP. The RL-SAIR applies an integrating an intelligent neighbourhood selection strategy based on reinforcement learning technique to select the neighbourhood based on the searching history and current search progress. The new proposed algorithm RL-SAIR has been proved as an effective improvement method for solving the FTSM-UCTP.,Ph.D
Pages:	217
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.