TY - GEN
T1 - Automated Examination Timetabling Optimization Using Greedy-Late Acceptance-Hyperheuristic Algorithm
AU - Muklason, Ahmad
AU - Bwananesia, Putri C.
AU - Sasmi Hidayatul, Y. T.
AU - Angresti, Nisa D.
AU - Supoyo, Vicha Azthanty
N1 - Publisher Copyright:
© 2018 IEEE.
PY - 2019/1/7
Y1 - 2019/1/7
N2 - Due to its non-deterministic polinomial (NP)-hard nature, exam timetabling problem is one of challenging combinatorial optimisation problems. Therefore, it attracts researchers especially in operation research and artificial intelligence fields for decades. Since the problem is very complex, exam timetable in many universities is developed manually which is very time consuming. This paper presents a new hybrid algorithm, i.e. greedy-late acceptance within hyper-heuristic framework to generate and optimise exam timetable automatically. Greedy algorithm is used to generate initial solution, whereas late acceptance is used as move acceptance strategy. The algorithm is simple but proven powerfull. The algorithm is tested over two datasets from real-world exam timetabling problem from Information Systems Department, Institut Teknologi Sepuluh Nopember (ITS). Over 11 different scenarios, the experimental results show that in addition to its ability to generate feasible solution, the algorithm also could produce more optimal solutions compared to the timetables generated manually.
AB - Due to its non-deterministic polinomial (NP)-hard nature, exam timetabling problem is one of challenging combinatorial optimisation problems. Therefore, it attracts researchers especially in operation research and artificial intelligence fields for decades. Since the problem is very complex, exam timetable in many universities is developed manually which is very time consuming. This paper presents a new hybrid algorithm, i.e. greedy-late acceptance within hyper-heuristic framework to generate and optimise exam timetable automatically. Greedy algorithm is used to generate initial solution, whereas late acceptance is used as move acceptance strategy. The algorithm is simple but proven powerfull. The algorithm is tested over two datasets from real-world exam timetabling problem from Information Systems Department, Institut Teknologi Sepuluh Nopember (ITS). Over 11 different scenarios, the experimental results show that in addition to its ability to generate feasible solution, the algorithm also could produce more optimal solutions compared to the timetables generated manually.
KW - automated timetabling
KW - exam timetabling
KW - greedy algorithm
KW - hyper-heuristic
KW - late acceptance
UR - http://www.scopus.com/inward/record.url?scp=85061901926&partnerID=8YFLogxK
U2 - 10.1109/ICECOS.2018.8605194
DO - 10.1109/ICECOS.2018.8605194
M3 - Conference contribution
AN - SCOPUS:85061901926
T3 - Proceedings of 2018 International Conference on Electrical Engineering and Computer Science, ICECOS 2018
SP - 201
EP - 206
BT - Proceedings of 2018 International Conference on Electrical Engineering and Computer Science, ICECOS 2018
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2018 International Conference on Electrical Engineering and Computer Science, ICECOS 2018
Y2 - 2 October 2018 through 4 October 2018
ER -