Cover Image

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

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 ta...

Full description

Saved in:
Bibliographic Details
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/
Tags: Add Tag
No Tags, Be the first to tag this record!
id my.unimas.ir.43242
record_format eprints
spelling my.unimas.ir.432422023-11-01T04:40:10Z http://ir.unimas.my/id/eprint/43242/ Improved Variable Neighbourhood Descent (VND) to Solve Universiti Malaysia Sarawak (UNIMAS) Course Timetabling Problem Mei Ching, Chen T Technology (General) 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. Universiti Malaysia Sarawak 2023-10-30 Thesis NonPeerReviewed text en http://ir.unimas.my/id/eprint/43242/3/chen%20mei%20ching_dsva.pdf text en http://ir.unimas.my/id/eprint/43242/4/Thesis%20PhD_%20Chen%20Mei%20Ching%20-%2024%20pages.pdf text en http://ir.unimas.my/id/eprint/43242/5/Thesis%20PhD_%20Chen%20Mei%20Ching.ftext.pdf Mei Ching, Chen (2023) Improved Variable Neighbourhood Descent (VND) to Solve Universiti Malaysia Sarawak (UNIMAS) Course Timetabling Problem. PhD thesis, Universiti Malaysia Sarawak.
institution Universiti Malaysia Sarawak
building Centre for Academic Information Services (CAIS)
collection Institutional Repository
continent Asia
country Malaysia
content_provider Universiti Malaysia Sarawak
content_source UNIMAS Institutional Repository
url_provider http://ir.unimas.my/
language English
English
English
topic T Technology (General)
spellingShingle T Technology (General)
Mei Ching, Chen
Improved Variable Neighbourhood Descent (VND) to Solve Universiti Malaysia Sarawak (UNIMAS) Course Timetabling Problem
description 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.
format Thesis
author Mei Ching, Chen
author_facet Mei Ching, Chen
author_sort Mei Ching, Chen
title Improved Variable Neighbourhood Descent (VND) to Solve Universiti Malaysia Sarawak (UNIMAS) Course Timetabling Problem
title_short Improved Variable Neighbourhood Descent (VND) to Solve Universiti Malaysia Sarawak (UNIMAS) Course Timetabling Problem
title_full Improved Variable Neighbourhood Descent (VND) to Solve Universiti Malaysia Sarawak (UNIMAS) Course Timetabling Problem
title_fullStr Improved Variable Neighbourhood Descent (VND) to Solve Universiti Malaysia Sarawak (UNIMAS) Course Timetabling Problem
title_full_unstemmed Improved Variable Neighbourhood Descent (VND) to Solve Universiti Malaysia Sarawak (UNIMAS) Course Timetabling Problem
title_sort improved variable neighbourhood descent (vnd) to solve universiti malaysia sarawak (unimas) course timetabling problem
publisher Universiti Malaysia Sarawak
publishDate 2023
url 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/
_version_ 1781710404528898048
score 13.211869

Similar Items