Generic University Examination Timetabling System with Steepest-Ascent Hill Climbing Hyper-heuristic Algorithm

Ahmad Muklason*, Ezra Juninho Pratama, I. Gusti Agung Premananda

*Corresponding author for this work

Research output: Contribution to journalConference articlepeer-review

Abstract

A common problem encountered in various educational institutions is the scheduling of exams, which involves allocating resources such as time and space, as well as considering student schedules within defined hard and soft constraints. This scheduling problem falls under the category of NP-Hard Problems, making it challenging to solve perfectly, and manual scheduling becomes even more difficult. One approach commonly used to address this issue is the Hyper-heuristic method, which generally provides above-average solutions. In this study, the Steepest-Ascent Hill Climbing algorithm is employed to optimize the initial solution generated by the Graph Coloring algorithm. The optimization process, using the Steepest-Ascent Hill Climbing algorithm, was tested over data set from Department of Information Systems, ITS University. The results showed improved timetabling compared to the Simple Hill Climbing algorithm, with lower penalty values. After 10,000 iterations, Steepest-Ascent Hill Climbing achieved an average penalty value of 2.783, whereas Simple Hill Climbing resulted in an average penalty value of 3.943.

Original languageEnglish
Pages (from-to)584-591
Number of pages8
JournalProcedia Computer Science
Volume234
DOIs
Publication statusPublished - 2024
Event7th Information Systems International Conference, ISICO 2023 - Washington, United States
Duration: 26 Jul 202328 Jul 2023

Keywords

  • Exam Timetabling
  • Graph Coloring
  • Hyper-heuristics
  • Optimization
  • Steepest-Ascent Hill Climbing

Cite this