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

Mei Ching, Chen (2023) Improved Variable Neighbourhood Descent (VND) to Solve Universiti Malaysia Sarawak (UNIMAS) Course Timetabling Problem. PhD thesis, Universiti Malaysia Sarawak.

	PDF chen mei ching_dsva.pdf Restricted to Repository staff only Download (428kB) | Request a copy
	PDF Thesis PhD_ Chen Mei Ching - 24 pages.pdf Download (460kB)
	PDF (Please get the password by email to repository@unimas.my , or call ext: 3942 / 3973 / 3933) Thesis PhD_ Chen Mei Ching.ftext.pdf Restricted to Registered users only Download (1MB) | Request a copy

Abstract

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.

Actions (For repository members only: login required)

View Item