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

Authors

  • Mei Ching Chen Universiti Malaysia Sarawak
  • San Nah Sze Universiti Malaysia Sarawak
  • Say Leng Goh Universiti Malaysia Sabah
  • Sei Ping Lau Universiti Malaysia Sarawak

DOI:

https://doi.org/10.6977.IJoSI.202109_6(5).0001

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.

Downloads

Published

2021-10-03

Issue

Vol. 6 No. 5 (2021): Special Issue on Info. Tech.

Section

Special Issue 2021: Management innovation

License

Copyright in a work is a bundle of rights. IJoSI's, copyright covers what may be done with the work in terms of making copies, making derivative works, abstracting parts of it for citation or quotation elsewhere and so on. IJoSI requires authors to sign over rights when their article is ready for publication so that the publisher from then on owns the work. Until that point, all rights belong to the creator(s) of the work. The format of IJoSI copy right form can be found at the IJoSI web site.
The issues of International Journal of Systematic Innovation (IJoSI) are published in electronic format and in print. Our website, journal papers, and manuscripts etc. are stored on one server. Readers can have free online access to our journal papers. Authors transfer copyright to the publisher as part of a journal publishing agreement, but have the right to:
1.    Share their article for personal use, internal institutional use and scholarly sharing purposes, with a DOI link to the version of record on our server.
2.    Retain patent, trademark and other intellectual property rights (including research data).
3.    Proper attribution and credit for the published work.