Application of Heuristic Combinations within a Hyper-Heuristic Framework for Exam Timetabling
Examination Timetabling Problem is one of the optimization and combinatorial problems. It is proved to be a non-deterministic polynomial (NP)-hard problem. On a large scale of data, the examination timetabling problem becomes a complex problem and takes time if it solved manually. Therefore, heurist...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Ikatan Ahli Informatika Indonesia
2020-08-01
|
| Series: | Jurnal RESTI (Rekayasa Sistem dan Teknologi Informasi) |
| Subjects: | |
| Online Access: | http://jurnal.iaii.or.id/index.php/RESTI/article/view/2066 |
| _version_ | 1797331865539969024 |
|---|---|
| author | Gabriella Icasia Raras Tyasnurita Etria Sepwardhani Purba |
| author_facet | Gabriella Icasia Raras Tyasnurita Etria Sepwardhani Purba |
| author_sort | Gabriella Icasia |
| collection | DOAJ |
| description | Examination Timetabling Problem is one of the optimization and combinatorial problems. It is proved to be a non-deterministic polynomial (NP)-hard problem. On a large scale of data, the examination timetabling problem becomes a complex problem and takes time if it solved manually. Therefore, heuristics exist to provide reasonable enough solutions and meet the constraints of the problem. In this study, a real-world dataset of Examination Timetabling (Toronto dataset) is solved using a Hill-Climbing and Tabu Search algorithm. Different from the approach in the literature, Tabu Search is a meta-heuristic method, but we implemented a Tabu Search within the hyper-heuristic framework. The main objective of this study is to provide a better understanding of the application of Hill-Climbing and Tabu Search in hyper-heuristics to solve timetabling problems. The results of the experiments show that Hill-Climbing and Tabu Search succeeded in automating the timetabling process by reducing the penalty 18-65% from the initial solution. Besides, we tested the algorithms within 10,000-100,000 iterations, and the results were compared with a previous study. Most of the solutions generated from this experiment are better compared to the previous study that also used Tabu Search algorithm. |
| first_indexed | 2024-03-08T07:41:31Z |
| format | Article |
| id | doaj.art-eb0b176c8cdd467bafd1f9ca504f4712 |
| institution | Directory Open Access Journal |
| issn | 2580-0760 |
| language | English |
| last_indexed | 2024-03-08T07:41:31Z |
| publishDate | 2020-08-01 |
| publisher | Ikatan Ahli Informatika Indonesia |
| record_format | Article |
| series | Jurnal RESTI (Rekayasa Sistem dan Teknologi Informasi) |
| spelling | doaj.art-eb0b176c8cdd467bafd1f9ca504f47122024-02-02T17:22:52ZengIkatan Ahli Informatika IndonesiaJurnal RESTI (Rekayasa Sistem dan Teknologi Informasi)2580-07602020-08-014466467110.29207/resti.v4i4.20662066Application of Heuristic Combinations within a Hyper-Heuristic Framework for Exam TimetablingGabriella Icasia0Raras Tyasnurita1Etria Sepwardhani Purba2Institut Teknologi Sepuluh NopemberInstitut Teknologi Sepuluh NopemberInstitut Teknologi Sepuluh NopemberExamination Timetabling Problem is one of the optimization and combinatorial problems. It is proved to be a non-deterministic polynomial (NP)-hard problem. On a large scale of data, the examination timetabling problem becomes a complex problem and takes time if it solved manually. Therefore, heuristics exist to provide reasonable enough solutions and meet the constraints of the problem. In this study, a real-world dataset of Examination Timetabling (Toronto dataset) is solved using a Hill-Climbing and Tabu Search algorithm. Different from the approach in the literature, Tabu Search is a meta-heuristic method, but we implemented a Tabu Search within the hyper-heuristic framework. The main objective of this study is to provide a better understanding of the application of Hill-Climbing and Tabu Search in hyper-heuristics to solve timetabling problems. The results of the experiments show that Hill-Climbing and Tabu Search succeeded in automating the timetabling process by reducing the penalty 18-65% from the initial solution. Besides, we tested the algorithms within 10,000-100,000 iterations, and the results were compared with a previous study. Most of the solutions generated from this experiment are better compared to the previous study that also used Tabu Search algorithm.http://jurnal.iaii.or.id/index.php/RESTI/article/view/2066: examination timetabling problem, toronto dataset, hill-climbing algorithm, tabu search algorithm, hyper-heuristics |
| spellingShingle | Gabriella Icasia Raras Tyasnurita Etria Sepwardhani Purba Application of Heuristic Combinations within a Hyper-Heuristic Framework for Exam Timetabling Jurnal RESTI (Rekayasa Sistem dan Teknologi Informasi) : examination timetabling problem, toronto dataset, hill-climbing algorithm, tabu search algorithm, hyper-heuristics |
| title | Application of Heuristic Combinations within a Hyper-Heuristic Framework for Exam Timetabling |
| title_full | Application of Heuristic Combinations within a Hyper-Heuristic Framework for Exam Timetabling |
| title_fullStr | Application of Heuristic Combinations within a Hyper-Heuristic Framework for Exam Timetabling |
| title_full_unstemmed | Application of Heuristic Combinations within a Hyper-Heuristic Framework for Exam Timetabling |
| title_short | Application of Heuristic Combinations within a Hyper-Heuristic Framework for Exam Timetabling |
| title_sort | application of heuristic combinations within a hyper heuristic framework for exam timetabling |
| topic | : examination timetabling problem, toronto dataset, hill-climbing algorithm, tabu search algorithm, hyper-heuristics |
| url | http://jurnal.iaii.or.id/index.php/RESTI/article/view/2066 |
| work_keys_str_mv | AT gabriellaicasia applicationofheuristiccombinationswithinahyperheuristicframeworkforexamtimetabling AT rarastyasnurita applicationofheuristiccombinationswithinahyperheuristicframeworkforexamtimetabling AT etriasepwardhanipurba applicationofheuristiccombinationswithinahyperheuristicframeworkforexamtimetabling |