Optimization of Course Scheduling Using Late Acceptance Hill Climbing Algorithms based on Hyper Heuristics ; Optimasi Penjadwalan Mata Kuliah Menggunakan Algoritma Late Acceptence Hill Climbing Berbasis Hiper Heuristik

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. ; Penjadwalan mata kuliah merupakan salah satu bidang dari riset operasi. Permasalahan ini menjadwalkan sebuah kelas dengan tidak melanggar satu batasan yang ada. Pada saat ini permasalahan penjadwalan mata kuliah menjadi semakin kompleks dengan banyaknya batasan yang ada. Salah satunya terdapat pada kompetisi International Timetabling Competition 2019 (ITC 2019) yang menggeluarkan dataset real world terbaru. Penelitian ini berfokus terhadap optimasi kualitas penjadwalan mata kuliah untuk menurunkan nilai penalti pada solusi akhir dari penjadwalan mata kuliah. Algoritma yang digunakan adalah Late Acceptence Hill Climbing(LAHC) dengan pendekatan hiper-heuristik dengan menggunakan Low Level Heuristik(LLH) mutasi dan local search. Algoritma diterapkan terhadap 30 dataset ITC 2019 dengan 100.000 iterasi dalam 5 kali percobaan. Hasilnya penerapan algoritma ini mampu mengoptimasi dengan rata-rata 52% dari solusi awal. Selain itu algoritma ini menghasilkann solusi yang konsisten selama 10 kali percobaan di setiap datasetnya.