Automated course timetabling optimization using tabu-variable neighborhood search based hyper-heuristic algorithm

Ahmad Muklason*, Redian Galih Irianti, Ahsanul Marom

*Corresponding author for this work

Research output: Contribution to journalConference articlepeer-review

19 Citations (Scopus)

Abstract

Course timetabling problems are challenging, laborious and repetitive work in the universities. However, in many universities this repetitive works was still carried out manually. It is because there are so many constraints that must be considered either from the students and lecturers' requirement or the infrastructure such as room availability. Therefore, to automate the process of timetabling is hard problem. Scientifically, in the literature, course timetabling optimization is one of non-deterministic polynomial problems, usually abbreviated as NP-hard problem. For NP-hard problem, there is not any exact algorithm known could solve the problem within polynomial-time. The state-of-the-art methods for solving the problem are approximation algorithms that are mainly meta-heuristics. This paper presents a new approach, namely, hyper-heuristics as opposed to meta-heuristics, to cope with the need of intensive problem specific parameter tuning in meta-heuristics approach. The algorithms employed within hyper-heuristic approach presented in this paper are tabu search hybridize with variable neighborhood search. Tested over two real-world course timetabling problem datasets, the computational results from the experiments showed that the proposed algorithm could automate the process of timetabling. Furthermore, compared to the timetable produced manually, in term of soft constraint violation penalties, the proposed algorithm could improve by 1855 and 1110 respectively. In addition to new approach, the main contribution of this paper is two real-world course timetabling problems available for public to encourage further research as future works.

Original languageEnglish
Pages (from-to)656-664
Number of pages9
JournalProcedia Computer Science
Volume161
DOIs
Publication statusPublished - 2019
Event5th Information Systems International Conference, ISICO 2019 - Surabaya, Indonesia
Duration: 23 Jul 201924 Jul 2019

Keywords

  • Course timetabling
  • Hyper-heuristic algorithm
  • Tabu search algorithm
  • Variable neighborhood search algorithm

Fingerprint

Dive into the research topics of 'Automated course timetabling optimization using tabu-variable neighborhood search based hyper-heuristic algorithm'. Together they form a unique fingerprint.

Cite this