Application of Heuristic Combinations in Hyper-Heuristic Framework for Exam Scheduling Problems
| Main Authors: | Icasia, Gabriella, Tyasnurita, Raras, Purba, Etria Sepwardhani |
|---|---|
| Format: | Article info application/pdf Journal |
| Bahasa: | eng |
| Terbitan: |
Ikatan Ahli Informatika Indonesia (IAII)
, 2020
|
| Subjects: | |
| Online Access: |
http://jurnal.iaii.or.id/index.php/RESTI/article/view/2066 http://jurnal.iaii.or.id/index.php/RESTI/article/view/2066/276 |
Daftar Isi:
- 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.
- Examination Timetabling Problem yang merupakan salah satu permasalahan optimasi dan kombinatorial terbukti sebagai non-deterministic polynomial (NP)-hard problem. Dalam skala data yang besar, examination timetabling problem menjadi permasalahan yang kompleks dan membutuhkan waktu lebih lama jika harus diselesaikan dengan cara manual. Maka dari itu heuristik hadir untuk memberikan solusi penjadwalan yang mendekati optimal dan juga memenuhi batasan dari permasalahan. Dalam penelitian ini, dilakukan pengujian terhadap permasalahan terkait penjadwalan yang terjadi di kehidupan nyata (dataset Toronto) dengan menggunakan algoritma Hill-Climbing dan Tabu Search. Berbeda dari pendekatan yang ada pada literatur, Tabu Search merupakan metode meta-heuristic, namun pada penelitian ini Tabu Search diimplementasikan dalam kerangka hyper-heuristic. Tujuan utama dari penelitian adalah untuk memberikan pemahaman yang lebih baik pada penerapan Hill-Climbing dan Tabu Search yang diimplementasikan pada kerangka hyper-heuristic untuk menyelesaikan permasalahan penjadwalan. Hasil dari eksperimen menunjukkan bahwa Hill-Climbing dan Tabu Search berhasil mengotomasi proses penjadwalan dengan menurunkan penalti 18-65% dari solusi awal. Selain itu, dilakukan pengujian terhadap algoritma dengan menggunakan 10,000-100,000 iterasi yang kemudian hasilnya dibandingkan dengan penelitian yang sudah dilakukan sebelumnya. Hasil pengujian dari penelitian ini mendominasi perolehan solusi yang lebih baik dibandingkan penelitian yang dilakukan sebelumnya yang juga menggunakan algoritma Tabu Search.