A Hybrid of Heuristic Orderings and Variable Neighbourhood Descent for a Real Life University Course Timetabling Problem
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 sa...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
2021
|
| Subjects: | |
| Online Access: | http://ir.unimas.my/id/eprint/37241/1/Sei%20Ping%20Lau.pdf http://ir.unimas.my/id/eprint/37241/ https://www.ijosi.org/index.php/IJOSI/article/view/459 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Universiti Malaysia Sarawak |
| Language: | English |
| Summary: | 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. |
|---|