Optimization of Course Scheduling Using Late Acceptance Hill Climbing Algorithms based on Hyper Heuristics

  • I Gusti Agung Premananda Institut teknologi sepuluh nopember
  • Ahmad Muklason Institut Teknologi Sepuluh Nopember
Keywords: Course Scheduling, LAHC Algorithm, Hyper Heuristics

Abstract

Course scheduling is one area of ​​operations research. This problem schedules a class without violating an existing constraint. At this time the problem of scheduling courses is becoming increasingly complex with existing limitations One of them is in International Timetabling Competition 2019 (ITC 2019) which released the latest real world dataset.

This study focuses on optimizing the quality of course scheduling in order to reduce the value of the final solution of course scheduling. The algorithm used is Late Acceptance Hill Climbing (LAHC) with a hyper-heuristic approach using mutation Low Level Heuristics (LLH) and local search. The algorithm was applied to 30 ITC 2019 data sets with 100,000 iterations in 5 trials.

The result is that the application of this algorithm is able to optimize with an average of 52% of the initial solution. In addition, this algorithm produces a consistent solution for 10 attempts on each dataset.

References

V. I. Skoullis, . I. X. Tassopoulos dan G. N. Beligiannis, “Solving the high school timetabling problem using a hybrid cat swarm optimization based algorithm,” Applied Soft Computing, vol. 52, pp. 277-289, 2017.
T. Song, S. Liu, X. Tang, X. Peng dan M. Chen, “ An iterated local search algorithm for the University Course Timetabling Problem,” Applied Soft Computing, vol. 68, pp. 597-608, 2018.
L. Saviniec dan A. A. Constantino, “Effective local search algorithms for high school timetabling problems,” Applied Soft Computing, vol. 60, pp. 363-373, 2017.
M. Alzaqebah dan S. Abdullah, “Hybrid bee colony optimization for examination timetabling problems,” Computers & Operations Research, vol. 54, pp. 142-154, 2015.
T. M¨uller , ·. H. Rudov´a dan Z. M¨ullerov´a, “University course timetabling and International Timetabling Competition 2019,” Proceedings of the 12th International Conference on the Practice and Theory of Automated Timetabling (PATAT-2018), pp. 5-31, 2018.
E. Burke,, . G. Kendall, . J. Newall dan E. Har, “Hyper-heuristics: An emerging direction in modern search technology,” dalam Handbook of metaheuristics, Springer, Boston, MA, 2003, pp. 457-474.
I. G. A. Premananda, “Penjadwalan Mata Kuliah Otomatis Menggunakan Algoritma Whale Optimization dan Late Acceptence Hill Climbing,” Institut Teknologi Sepuluh Nopember, pp. 1-122, 2021.
E. K. Burke dan Y. Bykov, “The late acceptance Hill-Climbing heuristic,” European Journal of Operational Research, vol. 258, no. 1, pp. 70-78, 2017.
G. H. G. Fonseca, H. G. Santos dan E. G. Carrano , “Late acceptance hill-climbing for high school timetabling,” Journal of Scheduling, p. 453–465, 2016.
Published
2021-06-17