Application of Heuristic Combinations in Hyper-Heuristic Framework for Exam Scheduling Problems
Aplikasi Kombinasi Heuristik dalam Kerangka Hyper-Heuristic untuk Permasalahan Penjadwalan Ujian
Abstract
Examination Timetabling Problem is one of the optimization and combinatorial problems. It is proved to be a non-deterministic polynomial (NP)-hard problem. On a large scale of data, the examination timetabling problem becomes a complex problem and takes time if it solved manually. Therefore, heuristics exist to provide reasonable enough solutions and meet the constraints of the problem. In this study, a real-world dataset of Examination Timetabling (Toronto dataset) is solved using a Hill-Climbing and Tabu Search algorithm. Different from the approach in the literature, Tabu Search is a meta-heuristic method, but we implemented a Tabu Search within the hyper-heuristic framework. The main objective of this study is to provide a better understanding of the application of Hill-Climbing and Tabu Search in hyper-heuristics to solve timetabling problems. The results of the experiments show that Hill-Climbing and Tabu Search succeeded in automating the timetabling process by reducing the penalty 18-65% from the initial solution. Besides, we tested the algorithms within 10,000-100,000 iterations, and the results were compared with a previous study. Most of the solutions generated from this experiment are better compared to the previous study that also used Tabu Search algorithm.
Downloads
References
I. H. O. Vic J Rayward-Smith, Colin Richard Reeves., 1996. Modern heuristic search methods.
A. Muklason, R. G. Irianti, and A. Marom, 2019. Automated course timetabling optimization using tabu-variable neighborhood search based hyper-heuristic algorithm. In: Procedia Computer Science, The Fifth Information Systems International Conference 2019.Surabaya, 23-24 Juli 2019, Surabaya: Indonesia.
A. Muklason, G. B. Syahrani, and A. Marom, 2019. Great deluge based hyper-heuristics for solving real-world university examination timetabling problem: New data set and approach. In: Procedia Computer Science, The Fifth Information Systems International Conference 2019.Surabaya, 23-24 Juli 2019, Surabaya: Indonesia.
D. Kusumawardani, A. Muklason, and V. A. Supoyo, 2019. Examination timetabling automation and optimization using greedy-simulated annealing hyper-heuristics algorithm.
E. K. Burke and G. Kendall., 2014. Search Methodologies. Second edition. Springer: New York Heidelberg Dordrecht London.
G. L. and S. Y. L. M.W. Carter., 1996. Examination Timetabling : Algorithmic Strategies and Applications. Journal of Operational Research Society , 47(3), pp. 373–383.
R. Qu and E. Burke, 2017. Hybrid Variable Neighborhood HyperHeuristics for Exam Timetabling Problems. The Sixth Metaheuristics International Conference. Vienna, Austria, August 22–26.
A. M. B. Syariza Abdul-Rahman, Sharifah Shuthairah Syed Abdullah, 2017. A Nonlinear Heuristic Modifier for Constructing Examination Timetable. Journal of Theoretical and Applied Information Technology, 95(20), pp. 5642–5653.
Y. Lei and J. Shi, 2017. A NNIA Scheme for Timetabling Problems. Journal of Optimization., 2017(2006), pp. 1–11.
V. A. Supoyo and A. Muklason.,2019. Pendekatan Hyper Heuristic Dengan Kombinasi Algoritma Pada Examination Timetabling Problem. ILKOM Jurnal Ilmiah., 11(1), pp. 34–44.
M. A. Al‑Betar, 2020. A B‑hill climbing optimizer for examination timetabling problem. Journal of Ambient Intelligence and Humanized Computing.
L. Candra., 2016. Penerapan algoritma tabu search untuk penjadwalan mata pelajaran di smk swasta pelita-2 aekkanopan. JURIKOM (Jurnal Riset Komputer), 3(6), pp. 74–79.
R. Qu, E. K. Burke, B. Mccollum, L. T. G. Merlot, and S. Y. Lee., 2006. A survey of search methodologies and automated approaches for examination timetabling. Comput. Sci. Tech. Rep. No . NOTTCS-TR-2006-4, UK, pp. 1–56.
University of Toronto, 1996. University of Toronto Benchmark Data [Online]. Available at : ftp://ftp.mie.utoronto.ca/pub/carter/testprob. [Accessed: April 2020].
E. K. Burke, G. Kendall, and E. Soubeiga., 2003. A Tabu-Search Hyperheuristic for Timetabling and Rostering. Journal of Heuristics, 9(6), pp. 451–470.
P. C. Konstantin Chakhlevitch., 2008. Hyperheuristics: Recent Developments. Springer: Berlin, Heidelberg.
E. Özcan, M. Misir, G. Ochoa, and E. K. Burke., 2019. A Reinforcement Learning - Great-Deluge Hyper-Heuristic for Examination Timetabling. International Journal of Applied Metaheuristic Computing., 1(1), pp. 39–59.
F. G. Laguna., 1998. Tabu Search. Springer: Boston, MA.
R. A. S. Mayang Putri Khairunnisa, Bambang Pramono.,2017. Implementasi Algoritma Tabu Search pada Aplikasi Penjadwalan Mata Pelajaran (Studi Kasus: SMA NEGERI 4 Kendari). InformaticsEngineering Department of Halu Oleo University, 2(2), pp. 31–39.
A. S. Luca Di Gaspero, 2000. Tabu Search Techniques for Examination Timetabling. The 3rd International Conference on the Practice and Theory of Automated Timetabling Programme Committee. Konstanz, August 16-18, Springer: Verlag Berlin Heidelberg.
Copyright (c) 2020 Jurnal RESTI (Rekayasa Sistem dan Teknologi Informasi)
This work is licensed under a Creative Commons Attribution 4.0 International License.
Copyright in each article belongs to the author
- The author acknowledges that the RESTI Journal (System Engineering and Information Technology) is the first publisher to publish with a license Creative Commons Attribution 4.0 International License.
- Authors can enter writing separately, arrange the non-exclusive distribution of manuscripts that have been published in this journal into other versions (eg sent to the author's institutional repository, publication in a book, etc.), by acknowledging that the manuscript has been published for the first time in the RESTI (Rekayasa Sistem dan Teknologi Informasi) journal ;
