A Hybrid of Heuristic Orderings and Variable Neighbourhood Descent for a Real Life University Course Timetabling Problem

Chen, Mei Ching and Sze, San Nah and Goh, Say Leng and Lau, Sei Ping (2021) A Hybrid of Heuristic Orderings and Variable Neighbourhood Descent for a Real Life University Course Timetabling Problem. International Journal of Systematic Innovation, 6 (5). pp. 1-10. ISSN 2077-8767

PDF Sei Ping Lau.pdf Download (127kB)

Abstract

Academic institutions face timetabling problem every semester. Addressing timetabling problem at academic institutions is a challenging combinatorial optimisation task both in theory and practice. This is due to the size of the problem instances as well as the number of constraints that must be satisfied. Over the years, timetabling problem has attracted many researchers in proposing ways to find an optimal solution. In this paper, we investigate a hybrid of heuristic orderings and variable neighbourhood descent approach in tackling course timetabling problem at the Faculty of Computer Science and Information Technology (FCSIT), Universiti Malaysia Sarawak (UNIMAS). At FCSIT, some events of 4 lecture hours are not evenly spread over minimum working days and some events are conducted until 9 pm. The objectives of the study are to shorten the daily lecture hours and evenly distribute events’ lecture. In stage 1, heuristic orderings are utilised to find a feasible solution. In stage 2, a hybrid of heuristic orderings and variable neighbourhood descent approach are utilised to improve the quality of the solution. The proposed algorithm is tested on real-world data instances (semesters 1 and 2 of 2019/2020) of FCSIT, UNIMAS. Results show that certain heuristic ordering (largest degree or the combination of largest degree and largest enrolment) are better than others in generating a feasible solution. In addition, the number of timeslots required by heuristic ordering are less compared to that required by the existing timetabling software. In stage 2, the proposed algorithm manages to achieve soft constraint violations of 0 and 1 for instances for semesters 1 and 2, respectively. However, all HO manage to achieve 0 violation for both instances when the proposed algorithm is executed 30 times. Each neighbourhood structures defined in this study contributes to lowering the soft constraint violations thus ensuring a high-quality timetable. Results show that the order of neighbourhood structures do impact the number of soft constraint (SC1) violations achieved.

Actions (For repository members only: login required)

View Item