Local search algorithms for the practical university course timetabling problem

Yang Xiao Fei (P64784)

Please use this identifier to cite or link to this item: https://ptsldigital.ukm.my/jspui/handle/123456789/513424

Full metadata record

DC Field	Value	Language
dc.contributor.advisor	Masri Ayob, Prof. Dr.
dc.contributor.author	Yang Xiao Fei (P64784)
dc.date.accessioned	2023-10-16T04:36:31Z	-
dc.date.available	2023-10-16T04:36:31Z	-
dc.date.issued	2020-10-08
dc.identifier.other	ukmvital:130611
dc.identifier.uri	https://ptsldigital.ukm.my/jspui/handle/123456789/513424	-
dc.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
dc.language.iso	eng
dc.publisher	UKM, Bangi
dc.relation	Faculty of Information Science and Technology / Fakulti Teknologi dan Sains Maklumat
dc.rights	UKM
dc.subject	Universiti Kebangsaan Malaysia -- Dissertations
dc.subject	Dissertations, Academic -- Malaysia
dc.subject	Timetabling problem
dc.subject	Algorithms
dc.title	Local search algorithms for the practical university course timetabling problem
dc.type	Theses
dc.format.pages	217
dc.identifier.barcode	005882(2021)(PL2)
Appears in Collections:	Faculty of Information Science and Technology / Fakulti Teknologi dan Sains Maklumat

Files in This Item:

File	Description	Size	Format
ukmvital_130611+Source01+Source010.PDF Restricted Access		3.19 MB	Adobe PDF	View/Open

Show simple item record Recommend this item