Perbandingan Algoritma Heuristic Selection untuk Penjadwalan Ujian Menggunakan Kerangka Kerja Hyper-Heuristics

Heuristic Selection Algorithms Comparison for Examination Timetabling Using Hyper-Heuristics Framework

Abstract

Abstract — Examination timetabling is an example of a problem in operations research and an exciting issue in higher education. For example, the problems that occur in an institution are the limited number and capacity of rooms, few exam supervisors, and limited exam time. So far, exam scheduling is done manually, so it is pretty time-consuming. Until now, no algorithm can solve this problem in polynomial time. So that in the optimization world, the problem of scheduling exams is an NP-Hard problem. Solving this problem can be done using a heuristic algorithm to produce a reasonably good solution fairly quickly. Currently, the algorithm has been developed in various ways with a hyper-heuristic approach. This study will discuss the scheduling of exams using carter benchmark datasets. The charter dataset is a dataset of real-world exam scheduling problems. The trials carried out in this study were to apply hyper-heuristics by combining a move acceptance algorithm, namely late acceptance hill climbing, with several heuristic selection algorithms to get the heuristic selection algorithm with the best performance to be combined. The result is the combination of Reinforcement Learning with Late Acceptance Hill Climbing can outperform the results of the comparison algorithm in most of the datasets.

Key words — Carter Datasets; Examination Timetabling; Hyper-Heuristics; Late Acceptance Hill Climbing; Reinforcement Learning; Tabu Search

Abstrak — Penjadwalan ujian merupakan salah satu contoh permasalahan dalam riset operasi serta permasalahan yang menarik untuk dihadapi di pergurugan tinggi. Sebagai contoh, permasalahan yang terjadi di sebuah perguruan tinggi yaitu terbatasnya jumlah dan kapasitas ruangan, terbatasnya pengawas ujian, serta terbatasnya waktu ujian. Selama ini, penjadwalan ujian dilakukan secara manual sehingga cukup memakan waktu.  Hingga saat ini belum ada algoritma yang dapat menyelesaikan permasalahan tersebut dalam waktu polinomial. Sehingga dalam dunia optimasi, permasalahan penjadwalan ujian merupakan NP-Hard problem. Penyelesaian permasalahan ini dapat dilakukan dengan menggunakan algoritma heuristic untuk menghasilkan solusi yang cukup baik dengan waktu yang cukup singkat. Saat ini algoritma telah berkembang secara variatif dengan pendekatan hyper-heuristics. Penelitian ini akan membahas penjadwalan ujian menggunakan benchmark dataset carter. Dataset carter merupakan dataset permasalahan penjadwalan ujian real-world. Uji coba yang dilakukan pada penelitian ini yaitu menerapkan hyper-heuristics dengan mengombinasikan sebuah algoritma move acceptance yaitu late acceptance hill climbing dengan beberapa algoritma heuristic selection untuk mendapatkan algoritma heuristic selection dengan performa terbaik untuk dikombinasikan. Hasilnya yaitu kombinasi Reinforcement Learning dengan Late Acceptance Hill Climbing mampu mengungguli hasil algoritma pembanding dalam sebagian besar dataset.

Kata kunci — Dataset Carter; Hyper-Heuristics; Late Acceptance Hill Climbing; Penjadwalan Ujian; Reinforcement Learning; Tabu Search