PENDEKATAN HYPER HEURISTIC DENGAN KOMBINASI ALGORITMA PADA EXAMINATION TIMETABLING PROBLEM

Vicha Azthanty Supoyo, Ahmad Muklason

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

Refbacks

  • There are currently no refbacks.


Creative Commons License
ILKOM Jurnal Ilmiah work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.