Evaluation of Hyper-Heuristic Method Using Simple Random-Step Counting Hill Climbing in the Examination Timetabling Problem

Rusdi Hamidan, Ahmad Mukhlason

Abstract


Exam Timetabling Problem (ETP) is a problem that occurs at the university. Solution to the ETP problem involves computational search methods to get results. In the process, if done manually it will require lot of time to achieve the optimal solution. ETP is basically allocating a schedule into room at particular time. Several previous researchers developed a hyper-heuristic method to obtain solutions that are expected to provide result that are close to optimal. In this study, ITC 2007 dataset will be used to find generic solutions that are near optimal. Simple Random (SR) was chosen as strategy to choose Low Level Heuristic (LLH) and Step Counting Hill Climbing (SCHC) was chosen as move-acceptance strategy for ETP. 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


Examination Timetabling Problem; ITC 2007; Hyper-Heuristic; Hill Climbing; Simple Random

Full Text:

PDF

References


R. Qu, E. K. Burke, B. McCollum, L. T. G. Merlot, and S. Y. Lee, “A survey of search methodologies and automated system development for examination timetabling,” J Sched, vol. 12, no. 1, pp. 55–89, Feb. 2009, doi: 10.1007/s10951-008-0077-5.

E. Burke and W. Erben, Eds., Practice and Theory of Automated Timetabling III: Third International Conference, PATAT 2000 Konstanz, Germany, August 16-18, 2000 Selected Papers. Berlin Heidelberg: Springer-Verlag, 2001.

A. Mukhlason, “Hyper-heuristics and fairness in examination timetabling problems,” Jul. 2017.

A. P. Dornelles, “A matheuristic approach for solving the high school timetabling problem,” 2015.

B. Mccollum, P. McMullan, A. Parkes, E. K. Burke, and R. Qu, “A New Model for Automated Examination Timetabling,” Annals of Operations Research, vol. 194, pp. 291–315, Jan. 2012.

S. Abdullah and M. Alzaqebah, “A hybrid self-adaptive bees algorithm for examination timetabling problems,” Applied Soft Computing, vol. 13, no. 8, pp. 3608–3620, Aug. 2013, doi: 10.1016/j.asoc.2013.04.010.

] E. Burke, M. R. Hyde, G. Kendall, G. Ochoa, and E. Özcan, “A classification of hyper-heuristic approaches,” in International Series in Operations Research and Management Science, 2010, pp. 449–468.

P. Cowling, G. Kendall, and E. Soubeiga, “A Hyperheuristic Approach to Scheduling a Sales Summit,” in Practice and Theory of Automated Timetabling III, Berlin, Heidelberg, 2001, pp. 176–190, doi: 10.1007/3-540-44629-X_11.

A. Ferreira, R. Gonçalves, and A. Pozo, “A Multi-Armed Bandit selection strategy for Hyper-heuristics,” Jun. 2017, pp. 525–532, doi: 10.1109/CEC.2017.7969356.




DOI: http://dx.doi.org/10.12962/j23546026.y2020i6.11103

Refbacks

  • There are currently no refbacks.


View my Stat: Click Here

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