TY - GEN
T1 - Flexible Automated Course Timetabling System with Lecturer Preferences Using Hyper-heuristic Algorithm
AU - Muklason, Ahmad
AU - Nugroho, Bayu Adi
AU - Riksakomara, Edwin
AU - Tyasnurita, Raras
AU - Mahananto, Faizal
AU - Vinarti, Retno A.
AU - Nuriman, Muhammad Arif
N1 - Publisher Copyright:
© 2022 ACM.
PY - 2022/11/22
Y1 - 2022/11/22
N2 - Timetabling is a problem that is often encountered in educational institutions such as universities which have to timetable courses according to the available time and resources, including other constraints, both hard and soft constraints. Based on the complexity of the existing problems, the course timetabling can be categorized as an NP-hard problem (non-deterministic polynomial problem) where to get the most optimal solution it takes a very long time to do the calculations. In addition, the limited availability of lecturer time is also a problem because it is not uncommon for lecturers to have other activities, such as serving in organizational positions at universities or other organizations. Various studies have been carried out with several methods to automate course timetabling so that the process can be carried out more efficiently and faster. One method that is considered to have above-Average performance is hyper-heuristic. In this research, hyper-heuristic development will be carried out by applying the Late Acceptance Hill Climbing (LAHC) algorithm to perform optimization based on the initial solution generated by the Graph Coloring method. The timetabling process will be equipped with an interface in the form of a website to facilitate the process of inputting datasets and constraints that make it flexible to various timetabling conditions because timetabling conditions will vary in each semester, including the preferences of each lecturer's teaching timetable. The results of this research show that the hyper-heuristic-based LAHC Algorithm which was tested on the ITS Information Systems Department course dataset in the odd semester of the 2021-2022 academic year resulted in a more optimal penalty of 103.9 compared to the penalty value generated by Graph Coloring and Hill Climbing Algorithm penalties of 753.84 and 189.59, respectively. Likewise, in the even semester, the LAHC Algorithm results are more optimal with a penalty of 117.46 compared to the Graph Coloring and Hill Climbing Algorithm penalties of 863.52 and 737.41, respectively.
AB - Timetabling is a problem that is often encountered in educational institutions such as universities which have to timetable courses according to the available time and resources, including other constraints, both hard and soft constraints. Based on the complexity of the existing problems, the course timetabling can be categorized as an NP-hard problem (non-deterministic polynomial problem) where to get the most optimal solution it takes a very long time to do the calculations. In addition, the limited availability of lecturer time is also a problem because it is not uncommon for lecturers to have other activities, such as serving in organizational positions at universities or other organizations. Various studies have been carried out with several methods to automate course timetabling so that the process can be carried out more efficiently and faster. One method that is considered to have above-Average performance is hyper-heuristic. In this research, hyper-heuristic development will be carried out by applying the Late Acceptance Hill Climbing (LAHC) algorithm to perform optimization based on the initial solution generated by the Graph Coloring method. The timetabling process will be equipped with an interface in the form of a website to facilitate the process of inputting datasets and constraints that make it flexible to various timetabling conditions because timetabling conditions will vary in each semester, including the preferences of each lecturer's teaching timetable. The results of this research show that the hyper-heuristic-based LAHC Algorithm which was tested on the ITS Information Systems Department course dataset in the odd semester of the 2021-2022 academic year resulted in a more optimal penalty of 103.9 compared to the penalty value generated by Graph Coloring and Hill Climbing Algorithm penalties of 753.84 and 189.59, respectively. Likewise, in the even semester, the LAHC Algorithm results are more optimal with a penalty of 117.46 compared to the Graph Coloring and Hill Climbing Algorithm penalties of 863.52 and 737.41, respectively.
KW - Course Timetabling
KW - Hyper-heuristic
KW - Iterated Local Search
KW - Late Acceptance Hill Climbing Algorithm
UR - http://www.scopus.com/inward/record.url?scp=85146956472&partnerID=8YFLogxK
U2 - 10.1145/3568231.3568273
DO - 10.1145/3568231.3568273
M3 - Conference contribution
AN - SCOPUS:85146956472
T3 - ACM International Conference Proceeding Series
SP - 258
EP - 262
BT - SIET 2022 - Proceedings of 7th International Conference on Sustainable Information Engineering and Technology 2022
PB - Association for Computing Machinery
T2 - 7th International Conference on Sustainable Information Engineering and Technology, SIET 2022
Y2 - 22 November 2022
ER -