PENDEKATAN HYPER HEURISTIC DENGAN KOMBINASI ALGORITMA PADA EXAMINATION TIMETABLING PROBLEM


Vicha Azthanty Supoyo(1*); Ahmad Muklason(2);

(1) Institut Teknologi Sepuluh Nopember Surabaya
(2) Institut Teknologi Sepuluh Nopember Surabaya
(*) Corresponding Author

Abstract


Generally, exam scheduling is still done manually and definitely will take a long time. Many researches have developed various studies to find a more appropriate strategy. Hyperheuristic was proposed in this study. In Hyperheuristic, Simple Random is used as a strategy for selecting low-level-heuristic while Hill Climbing and Simulation Annealing as move acceptance strategy. The Carter dataset is used as a test for the algorithms. We proposed testing datasets with a time limit of 15 minutes up to 1 hour and the results were compared with the research conducted by Carter et al (1996) as an initial study using that dataset. In addition, dataset, the number of iterations, and the time limit are as same as one of the literatures which will then be compared. The results obtained show that one pair of algorithms proposed in this study is better than the literature while other algorithms also provide significant results.


Keywords


Hyperheuristic; Carter (Toronto) Datasets; Simple Random Algorithm; Hill Climbing Algorithm; Simulated Annealing Algorithm

Full Text:

PDF

References


E. Burke, Y. Bykov, J. Newall, and S. Petrovic, “A time-predefined local search approach to exam timetabling problems,” IIE Trans., vol. 36, no. 6, pp. 509–528, 2004.

C. Weng, H. Asmuni, B. Mccollum, and P. Mcmullan, “A new hybrid imperialist swarm-based optimization algorithm for university timetabling problems,” Inf. Sci. (Ny)., vol. 283, pp. 1–21, 2014.

P. Demeester, B. Bilgin, P. De Causmaecker, and G. Vanden, “A hyperheuristic approach to examination timetabling problems : benchmarks and a new problem from practice,” pp. 83–103, 2012.

B. Bilgin, E. Ozcan, and E. E. Korkmaz, “An Experimental Study on Hyper-heuristics and Exam Timetabling,” in Practice and Theory of Automated Timetabling VI, E. Burke and H. Rudová, Eds. 2007, pp. 394–412.

M. Kalender, A. Kheiri, E. Özcan, and E. K. Burke, “A greedy gradient-simulated annealing selection hyper-heuristic,” Soft Comput., vol. 17, no. 12, pp. 2279–2292, 2013.

Y. Lei, M. Gong, L. Jiao, and Z. Yi, “A memetic algorithm based on hyper-heuristics for examination timetabling problems,” Int. J. Intell. Comput. Cybern., vol. 8, no. 2, pp. 139–151, 2015.

A. Muklason, A. J. Parkes, E. Özcan, B. McCollumb, and P. McMullan, “Fairness in examination timetabling: Student preferences and extended formulations,” Appl. Soft Comput., vol. 55, pp. 302–318, 2017.

E. K. Burke, “Hybrid variable neighbourhood hyper-heuristics for exam timetabling problems Hybrid Variable Neighborhood HyperHeuristics for Exam Timetabling Problems,” no. July, 2017.

E. Özcan, M. Misir, G. Ochoa, and E. K. Burke, “A Reinforcement Learning - Great-Deluge Hyper-Heuristic for Examination Timetabling,” Int. J. Appl. Metaheuristic Comput., vol. 1, no. 1, pp. 39–59, 2010.

E. K. Burke, T. Curtois, M. Hyde, G. Ochoa, and J. a Vazquez-Rodriguez, “HyFlex: A Benchmark Framework for Cross-domain Heuristic Search,” Arxiv Prepr. arXiv11075462, vol. abs/1107.5, p. 28, 2011.

Y. Lei, M. Gong, L. Jiao, and Y. Zuo, “A memetic algorithm based on hyper-heuristics for examination timetabling problems,” Int. J. Intell. Comput. Cybern., vol. 8, no. 2, pp. 139–151, 2015.

E. Özcan, Y. Bykov, M. Birben, and E. K. Burke, “Examination Timetabling Using Late Acceptance Hyper-heuristics,” University of Nottingham, 2009.

P. Ross, D. Corne, and H. Fang, “Improving Evolutionary Timetabling with Delta Evaluation and Directed Mutation.”

R. Bai and G. Kendall, “An Investigation Of Automated Planograms Using A Simulated Annealing Based Hyper-Heuristic,” no. June 2015, pp. 0–22, 2005.

E. Soubeiga, “Development and Application of Hyper Huristics to Personnel Scheduling,” 2003.

M. W. Carter, G. Laporte, and S. Y. Lee, “Examination Timetabling: Algorithmic Strategies and Applications,” J. Oper. Res. Soc., pp. 373–383, 1996.




DOI: https://doi.org/10.33096/ilkom.v11i1.420.34-44

Article Metrics

Abstract view: 134 times
PDF view: 101 times

Refbacks

  • There are currently no refbacks.


Copyright (c) 2019 Vicha Azthanty Supoyo, Ahmad Muklason

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

 ILKOM Jurnal Ilmiah indexed by

doaj_logoCROSSREF_logoROAD_logoPKP_Index_logoGoogle_Scholar_logosinta_logogaruda_logoonesearch_logoBASE_logoWordcat_logo

___________________________________________________________
ILKOM Jurnal Ilmiah
ISSN 2548-7779
Published by Teknik Informatika Fakultas Ilmu Komputer Universitas Muslim Indonesia
W : https://fikom.umi.ac.id/
E : jurnal.ilkom@umi.ac.id

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0