Improved Variable Neighbourhood Descent (VND) to Solve Universiti Malaysia Sarawak (UNIMAS) Course Timetabling Problem

• Main Author: Mei Ching, Chen
• Format: Thesis
• Language: English; English; English
• Published: Universiti Malaysia Sarawak 2023
• Subjects: T Technology (General)
• Online Access: http://ir.unimas.my/id/eprint/43242/3/chen%20mei%20ching_dsva.pdf; http://ir.unimas.my/id/eprint/43242/4/Thesis%20PhD_%20Chen%20Mei%20Ching%20-%2024%20pages.pdf; http://ir.unimas.my/id/eprint/43242/5/Thesis%20PhD_%20Chen%20Mei%20Ching.ftext.pdf; http://ir.unimas.my/id/eprint/43242/

Academic institutions face the timetabling problem every semester. The task of allocating lectures to limited timeslots and venues must fulfil certain constraints unique to each educational institution. This study investigated heuristic orderings and the variable neighbourhood descent approach to tackle the course timetabling problem at the Faculty of Computer Science and Information Technology (FCSIT), Universiti Malaysia Sarawak (UNIMAS) on the basis of the students. The objectives of the study were to formulate a mathematical model and improve a computational bounded heuristics-based solution to solve the course timetabling problem at the faculty. A two-stage heuristic algorithm is proposed. In stage 1, heuristic orderings were utilised to find a feasible solution using 31 timeslots instead of the 48 timeslots in the existing timetabling software. In stage 2, the variable neighbourhood descent approach with new neighbourhood structures was utilised to improve the quality of the solution. The improved algorithm was tested on real-world data instances (in semesters 1 and 2 of 2019/2020) at the FCSIT, UNIMAS. The results show that certain heuristic orderings (the largest degree or the combination of the largest degree and largest enrolment in descending order) are better than others in generating a feasible solution. In stage 2, the proposed algorithm with new neighbourhood structures managed to reduce the soft constraint violations for instances in semesters 1 and 2. Sensitivity analysis was performed on the proposed algorithm. The experimental results demonstrate the flexibility of the proposed algorithm in solving the university course timetabling problem (UCTTP) at the FCSIT.