Received June1 st June25 th , 2012; Accepted July 10 th , 20 http://jurnal.mdp.ac.id         jatisi@mdp.ac.id

## Optimasi Penjadwalan Mata Kuliah Menggunakan Algoritma Late Acceptence Hill Climbing Berbasis

## Hiper Heuristik
I Gusti Agung Premanananda* 1 , Ahmad Muklason 2 1,2 Jurusan Sistem Informasi Institut Teknologi Sepuluh Nopember e-mail: * igustiagungpremananda@gmail.com

## Abstrak
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.
Kata kunci —Penjadwalan Mata Kuliah, Algoritma LAHC, Hiper Heuristik

## Abstract
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.
Keywords —Course Scheduling, LAHC Algorithm, Hyper Heuristics
E- ISSN 2503-2933   775

## 1. PENDAHULUAN
ermasalahan  penjadwalan  matakuliah  merupakan  permasalahan  untuk  menjadwalkan  mata kuliah terhadap jadwal dan  ruangan  yang  tersedia dengan  memastikan  tidak  ada pelanggaran terhadap hard  constraint dan  meminimalkan soft  constraint [1] . Permasalahan  penjadwalan mata  kuliah  termasuk  ke  dalam  permasalahan NP-Hard karena  tidak  memungkinkan menyelesaikan  permasalahan  ini  dengan  algoritma exact dalam  waktu  yang  wajar.  Sehingga penelitian terkini lebih berfokus mengembangkan algoritma dengan pendekatan heuristik [2].
Beberapa penelitian dalam lima tahun terakhir melakukan  pengembangan algoritma baru dengan  mengembangkan  berbagai  macam  jenis  algoritma.  Studi  yang  dilakukan  Saviniec  [3] menghasilkan  algoritma  baru  dengan  menggabungkan  Iterated  Local  search  dan  Variable Neighborhood  Search.  Studi  lain  dilakukan  oleh  Alzaqebah  [4]  mencoba  menggabungkan algoritma bee colony optimization dengan beberapa algoritma local search . Ada juga studi lain yang  dilakukan  oleh  Skoullis  [1]  dengan  mencoba  algoritma  hybrid  cat  swarm  optimization pada  permasalahan  penjadwalan.  Dari  beberapa  penelitian  tersebut,  penyelesaian  masalah penjadwalan  mata  kuliah  masih  berfokus  terhadap  dataset  lama,  sehingga  hasil  penelitian tersebut kurang relevan jika diterapkan pada studi kasus saat ini.
Salah  satu  organisasi  mengeluarkan  dataset real  world terbaru  mengenai  penjadwalan mata  kuliah  dari  berbagai  universitas  di  dunia  lewat  sebuah  kompetisi  bernama  International Timetabling  Competition  2019  (2019)  [5].  Dataset  pada  ITC  2019  merupakan  dataset  terbaru dengan tingkat kompleksitas yang sangat tinggi. Dataset ini terdiri dari 30 dataset yang terbagi menjadi  tiga  kelompok  dimana  setiap  bagian  berisi  10  dataset.  Tiga  kelompok  tersebut  terdiri dari dataset early, middle dan late.  Secara keseluruhan dataset ini memiliki 19 batasan distribusi seperti  pada  gambar  1  dimana  batasan  ini  dapat  berupa hard  constraint atau  berupa soft constraint . Selain batasan distribusi terdapat juga hirarki dalam setiap mata kuliah seperti pada gambar  2.  Tujuan  utama  dari  kompetisi  ini  adalah  menjadwalkan  mahasiswa  ke  dalam matakuliah  yang  diinginkan  dan  menjadwalkan  kelas  pada  daftar  waktu  dan  ruangan  yang tersedia  tanpa  melanggar hard  constraint yang  ada.  Nilai  penalti  menjadi  penentu  untuk menentukan  kualitas  dari  solusi  yang  dihasilkan.  Solusi  dengan  penalti  terkecil  merupakan solusi yang paling baik.
Dalam  pengembangan  algoritma  dengan  pendekatan  heursitik,  terdapat  beberapa  jenis metode  yaitu  heuristik,  metaheuristic  dan  hiper  heuristik.  Metode  heuristik  mudah  untuk digunkan  namun  sering  menghasilkan  hasil  yang  buruk  pada  beberapa  kasus.  Metode metaheuristik  dapat  menghasilkan  solusi  yang  sangat  baik,  namun  metode  ini  tidak  dapat digunakan pada dunia komersial dan industri karena metode ini membutuhkan biaya yang mahal dan susah untuk diterapkan.  Sedangkan  metode hiper heutistik dapat digunakan dengan cukup mudah, terjangkau , dan lebih mampu menghasilkan solusi yang baik [6].
Berdasarkan  latar  belakang  tersebut  maka  penelitian  ini  mengembangkan  algoritma LAHC  dengan  pendekatan  hiper  heuristik  untuk  menyelesaikan  permasalahan  penjadwalan terbaru  dari  dataset  ITC  2019.  Penelitian  ini  hanya  berfokus  bagian  optimasi  penjadwalan terhadap  10  dataset  pada  bagain  dataset  early.  Karakteristik  dari  10  dataset  yang  digunakan dapat  dilihat  pada  tabel  1.  Dari  penelitian  ini  diharapkan  mampu  digunakan  sebagai  acuan dalam menyelesaikan permasalahan penjadwalan di universitas.
P
776 Jatisi ISSN 2407-4322 Vol. 8, No. 2, Juni 2021, Hal. 774-782 E- ISSN 2503-2933
Gambar 1. Batasan Distribusi ITC 2019
Gambar 2. Hierarki Mata Kuliah Tabel 1. Karakteristik Dataset Early Dataset Kelas  Ruangan  Murid  Batasan Distribusi agh-fis-spr17 1239 80 1641 1220 agh-ggis-spr17 1859 44 2116 2690 bet-fal17 983 62 3018 1251 iku-fal17 2641 214 0 2902 mary-spr17 882 90 3666 3947 muni-fi-spr16 575 35 1543 740 muni-fsps-spr17 561 44 865 400 muni-pdf-spr16c  2526 70 2938 2026 pu-llr-spr17 1001 75 27018 634 tg-fal17 711 15 0 501

## 2. METODE PENELITIAN
Penelitian  ini  akan  melalui  beberapa  tahapan  mulai  dari  praproses,  desain  algoritma, implementasi dan analisis hasil.
E- ISSN 2503-2933   777

## 2.1 Pra Proses Data
Pada  dataset  ITC  2019,  terdapat  beberapa  kandidat  jadwal  yang  tidak  mungkin  dapat digunakan  selama  penjadwalan  kelas  karena  pasti  akan  melanggar hard  constraint yang  ada. Sehingga kandidat jadwal tersebut harus dihapus agar tidak mengganggu dalam proses optimasi jadwal. Penghapusan kandidat jadwal dilakuakan berdasarkan konflik dengan ruangan,  batasan distribusi dan jadwal kelas lainnya [7].

## 2. 2 Desain Algoritma
Pada  desain  algoritma  terbagi  menjadi  dua  bagian  yaitu  desain  LLH  yang  digunakan untuk mengubah solusi dan yang kedua desain dari algoritma yang digunakan untuk pemilihan penerimaan  solusi.  Pada  desain  algoritma  ini  akan  menggunakan  dua  LLH  yaitu  mutasi  dan local search . Sedangkan algoritma yang digunakan adalah algoritma LAHC.

## 2. 2.1 LLH Mutasi
Mutasi  akan  digunakan  saat  menjalankan  algoritma  LAHC  dengan  tujuan  untuk meminimalkan  terjadinya  pelanggaran hard  constraint dengan  hanya  mengubah  jadwal  kelas pada list jadwal yang memungkinkan. Mutasi dilakukan dengan cara mengubah beberapa jadwal kelas terhadap jadwal yang tersedia. Seperti pada gambar 3, jadwal pada kelas ke-1 diubah dari yang awalnya dijadwalkan pada slot  10 diubah ke slot 13. Pada kelas ke-3 dari, yang awalnya dijadwalkan pada slot 23 diubah ke slot 27 dan pada kelas ke-3.
Untuk  memastikan tidak ada pelanggaran setelah terjadi operasi mutasi, perubahan baru akan  terjadi  jika  tidak  terjadi  konflik  dengan  kelas  yang  lain.    Dengan  demikian,  sebelum melakukan perubahan, akan dilakukan tahapan pengecekan hard constraint dan pengecekan slot jadwal terhadap jadwal baru yang akan digunakan.
Gambar 3. Ilustrasi LLH Mutasi

## 2. 2.2 LLH Local Search
Konsep  dari local  search adalah  mencari  satu  kandidat  jadwal  terbaik  saat  LLH  ini digunakan sehingga tahapan ini akan mencoba semua kandidat pada satu kelas dan menghitung jumlah  penalti  yang  dihasilkan.  Setelah  itu,  akan  dicari  satu  kandidat  dengan  jumlah  penalti terkecil. LLH ini mampu menurunkan jumlah penalti dengan baik, namun cukup menghabiskan waktu  karena  harus  mengecek  semua  kemungkinan  jadwal  yang  ada.  Untuk  mengatasi  hal tersebut,  dilakukan  pembatasan.  LLH  ini  akan  digunakan  jika  kandidat  dari  waktu  dikali kandidat ruangan tidak lebih dari 500.
778 Jatisi ISSN 2407-4322 Vol. 8, No. 2, Juni 2021, Hal. 774-782 E- ISSN 2503-2933

## 2. 2.3 Algoritma LAHC
Kerangka  algoritma  LAHC  yang  digunakan  mengikuti  dari  algoritma  aslinya. Perubahan dilakukan pada bagian perubahan solusi dengan  memasukan LLH  mutasi dan local search .  Pemilihan  kedua  LLH  dilakukan  secara  acak.  Gambar  4  menunjukan  bagaimana  alur algoritma LAHC bekerja.
Pada algoritma LAHC, terdapat satu parameter, yaitu panjang list yang digunakan oleh algoritma  LAHC  sebagai  penentu  apakah  solusi  akan  digunakan  atau  tidak.    Berdasarkan penelitian yang dilakukan oleh Burke [8], semakin panjang list, solusi yang ditemukan semakin baik.  Namun,  hal  tersebut  membutuhkan  waktu  yang  lebih  lama.  Jika  panjang  list  semakin pendek, penurunan solusi akan lebih cepat daripada list yang panjang. Namun, itu akan rentan terjebak  dalam  local  optima.  Penelitian  lain  yang  dilakukan  oleh  Fonseca  [9]  yang  juga berkaitan dengan penjadwalan pada bidang pendidikan, menemukan nilai parameter panjang list terbaik sebesar 500. Angka ini menghasilkan performa yang baik untuk dataset kecil dan dataset besar. Dengan demikian, penelitian ini akan menggunakan nilai 500 sebagai parameter panjang list pada algoritma LAHC.
Gambar 4. Algoritma LAHC
E- ISSN 2503-2933   779

## 2. 3 Implementasi Algoritma
Pada  bagian  ini  algoritma  yang  telah  dihasilkan,  diimplementasikan  dalam  bahasa pemrograman java melalui program intelij. 10 dataset tersebut akan dijalankan sebanyak 10 kali disetiap  datasetnya  dengan  jumlah iterasi  100.000  dan  waktu  maksimal  disetiap  dataset  dalam satu kali iterasi adalah 30 menit.

## 2. 4 Analisis Hasil
Dari  hasil  implementasi  pada  tahapan  sebelumnya  dilakukan  hasil  analisis  terhadap persentase  optimasi  yang  berhasil  dilakukan  dengan  membandingkan  dari  nilai  penalti  solusi sebelum di optimasi dan sesudah di optimasi. Selain itu persebaran hasil dari 10 kali percobaan akan  dilihat  dalam  grafik  box  plot  untuk  melihat  seberapa  konsisten  algoritma  ini  dalam mengoptimasi solusi.

## 3. HASIL DAN PEMBAHASAN
Setelah dilakukan percobaan terhadap 10 dataset early ITC 2019 pada algoritma LAHC menggunakan  pendekatan  hiper  heuristik  dengan  10  kali  percobaan  pada  setiap  dataset, menghasilkan hasil berupa rata-rata nilai penalti, nilai penalti terbesar dan nilai penalti terkecil seperti pada tabel 2.
Tabel 2. Hasil Uji Coba Dataset Early ITC 2019 Dataset Rata-Rata Penalti  Penalti Terkecil  Penalti Terbesar agh-fis-spr17 9304,167 8851 9768 agh-ggis-spr17 154064,7 147981 160293 bet-fal17 358455,4 355526 361711 iku-fal17 96417,67 94673 98282 mary-spr17 27691,25 26775 28551 muni-fi-spr16 10420,92 10229 10551 muni-fsps-spr17 19308,25 17561 21464 muni-pdf-spr16c 415951,4 399794 443540 pu-llr-spr17 65576,83 59931 72954 tg-fal17 12612,08 11689 13412
Dari  hasil  percobaan  algoritma  LAHC  dengan  pendekatan  hiper  heuristik  mampu mengurangi  penalti  dengan  rata-rata  sebesar  52%  dari  nilai  penalti  pada  solusi  awal.  Pada dataset  Muni-fsps-spr17  didapatkan  pengurangan  penalti  terbesar  yaitu  dengan  mengurangi penalti sebesar 93% dari solusi awal. Sedangkan pengurangan penalti terkecil ada pada dataset Bet-fal17  dengan  pengurangan  penalti  sebesar  13%.  Hal  ini  terjadi  karena  dataset  Bet-fal17, solusi teroptimal yang pernah ditemukan oleh finalis pada kompetisi ITC 2019 yaitu 27% lebih kecil  dari  solusi  awal  atau  berbeda  14%  dari  solusi  akhir  pada  penelitian  ini.  Perbandingan pengurangan penalti pada solusi awal dan solusi akhir dapat dilihat pada tabel  3 dan gambar 5.
Algoritma  LAHC  dengan  pendekatan  hiper  heuristik  melakukan  penurunan  penalti dengan  cepat  pada  awal  iterasi.  Setelah  itu  algoritma  ini  mampu  mengurangi  penalti  secara perlahan sampai iterasi berakhir. Gambar 6 mengilustrasikan penurunan penalti dari iterasi ke 0 hingga  iterasi  ke  100.000.  Dari  sini  dapat  dilihat  bahwa  algoritma  LAHC  mampu  bekerja dengan  baik  dengan  tidak  terjadi  local  optima  selama  iterasi  berlangsung  dibuktikan  dengan mampu mengurangi nilai penalti sampai akhir iterasi.
780 Jatisi ISSN 2407-4322 Vol. 8, No. 2, Juni 2021, Hal. 774-782 E- ISSN 2503-2933
Tabel 3. Perbandingan Solusi Awal  dan Solusi Akhir B Dataset Solusi Awal  Solusi Akhir Persentase Pengurangan agh-fis-spr17 39088 8851 77% agh-ggis-spr17 194901 147981 24% bet-fal17 410985 355526 13% iku-fal17 161686 94673 41% mary-spr17 75290 26775 64% muni-fi-spr16 25414 10229 60% muni-fsps-spr17 242614 17561 93% muni-pdf-spr16c 601148 399794 33% pu-llr-spr17 136001 59931 56% tg-fal17 25217 11689 54%
Gambar 5. Perbandingan Solusi Awal dan Solusi Akhir
Gambar 6. Ilustrasi Penurunan Penalti pada Dataset Mary-spr17
E- ISSN 2503-2933   781
Pada persebaran hasil solusi dari 10 kali percobaan, didapatkan algoritma LAHC dengan pendekatan  hiper  heuristik  menghasilkan  hasil  solusi  yang  cukup  konsistent.  Hal  ini  dapat dilihat  pada  grafik  box-plot  pada  gambar  7  dan  8  dimana  terlihat  ukuran  candle  yang  cukup kecil  menandakan  persebaran  solusi  yang  dihasilkan rapat  atau  tidak  ada  perbedaan signifikan antara solusi yang dihasilkan.
Gambar 7. Grafik Box Plot dari Solusi Akhir
Gambar 8. Grafik Box Plot dari Solusi Akhir

## 4. KESIMPULAN
Berdasarkan  hasil  penelitian  dan  pembahasan  pada  bab  sebelumnya,  penelitian  ini menghasilkan  metode  baru  dengan  menghasilkan  algoritma  LAHC  menggunakan  pendekatan hiper  heuristik  dengan  menggunakan  LLH  mutasi  dan local  search .  Algoritma  ini  mampu mengurangi  penalti  dari  solusi  awal  dengan  rata-rata  sebesar  52%  pada  10  dataset  early  ITC
782 Jatisi ISSN 2407-4322 Vol. 8, No. 2, Juni 2021, Hal. 774-782 E- ISSN 2503-2933
2019. Selain itu solusi yang dihasilkan cukup konsisten dibuktikan dengan ukuran candle yang kecil saat dipetakan pada grafik box-plot.

## 5. SARAN
Dalam  penelitian  ini  belum  melakukan  percobaan  terhadap  kombinasi  LLH  lain.  Pada penelitian selanjutnya dapat menambahkan atau mengganti LLH yang telah digunakan dengan LLH  lainnya  seperti  swap  dan  crossover.  Dengan  mencoba  berbagai  jenis  LLH  diharapkan mampu menghasilkan solusi yang lebih baik.

## DAFTAR PUSTAKA
[1] V. I. Skoullis, . I. X. Tassopoulos dan G. N. Beligiannis. 2017, “Solving The High School Timetabling  Problem  Using  A  Hybrid  Cat  Swarm  Optimization  Based  Algorithm,” Applied Soft Computing, Vol. 52, pp. 277-289.
[2] T.  Song,  S.  Liu,  X.  Tang,  X.  Peng  dan  M.  Chen.  2018, “  An  Iterated  Local  Search Algorithm  for  The  University  Course  Timetabling  Problem,” Applied  Soft  Computing, vol. 68, pp. 597-608
[3] L.  Saviniec  dan  A.  A.  Constantino.  2017, “Effective  Local  Search  Algorithms  for  High School Timetabling Problems,” Applied Soft Computing, Vol. 60, pp. 363-373.
[4] M. Alzaqebah dan S. Abdullah. 2015, “Hybrid Bee Colony Optimization for Examination Timetabling Problems,” Computers & Operations Research, Vol. 54, pp. 142-154.
[5] T. M¨uller, H. Rudov´a dan Z. M¨ullerov´a., 2018, “University Course Timetabling and International  Timetabling  Competition  2019, ” Proceedings  of  The  12th  International Conference on The Practice and Theory of Automated Timetabling (PATAT-2018), pp. 5- 31.
[6] E. Burke,, . G. Kendall, . J. Newall dan E. Har,  2003, “Hyper-Heuristics: An Emerging Direction In Modern Search Technology,” Dalam Handbook of Metaheuristics , Springer, Boston, MA, pp. 457-474.
[7] I.  G.  A.  Premananda.  2021, “Penjadwalan  Mata  Kuliah  Otomatis  Menggunakan Algoritma  Whale  Optimization  dan  Late  Acceptence  Hill  Climbing,” Institut  Teknologi Sepuluh Nopember, pp. 1-122,
[8] E.  K.  Burke  dan  Y.  Bykov.  2017, “The  Late  Acceptance  Hill-Climbing  Heuristic,” European Journal of Operational Research, Vol. 258, No. 1, pp. 70-78.
[9] G.  H.  G.  Fonseca,  H.  G.  Santos  dan  E.  G.  Carrano.  2016, “Late  Acceptance  Hill- Climbing for High School Timetabling,” Journal of Scheduling, p. 453–465,