Pemenuhan Strategi pada Penjadwalan Ruangan Kuliah Mahasiswa Kelas Reguler menggunakan Algoritma Heulistik di Universitas Komputer Indonesia
N F Fauziah 1 , Y H Putra 2
12 Program Studi Magister Sistem Informasi, Universitas Komputer Indonesia, Indonesia
Email : nfildafauziah@gmail.com
Abstrak. Penjadwalan  adalah    permasalahan  yang  dipengaruhi  beberapa  faktor,  seperti ketersediaan dosen,  waktu,  matakuliah, ruangan. Salah  satu permasalahan  yang terjadi adalah setiap  stakeholder  yang  terlibat  dalam  penjadwalan  memiliki  strategy  atau  kebutuhan  masing masing  yang  harus  dipenuhi.  Tujuan  penelitian  ini  adalah  untuk  melakukan  perancangan  dan implementasi untuk penyusunan penjadwalan ruangan mahasiswa kelas reguler secara otomatis sekaligus  memberikan  keterbaruan  yaitu  dapat  memenuhi  kebutuhan  dari  setiap  stakeholder yang terlibat dan memberikan nilai bisnis lebih berupa analisis ruangan kosong. Metoda yang digunakan  adalah  Heuristik  yang  berfungsi  untuk  membantu  mempersingkat  waktu  dalam pencarian kombinasi-kombinasi yang harus dicocokan terutama pada kasus yang memiliki data yang  cukup  banyak  maka  algoritma  heuristik  membantu  dalam  mengelompokan  bagian  yang harus diprioritaskan agar persentase tingkat keterjadwalannya lebih baik. Bahasa pemograman yang  digunakan  adalah  PHP  dengan  menggunakan  platform  Windows.  Algoritma  yang digunakan adalah penggabungan dari Algoritma Genetika dan Tabu Search dimana Algoritma Genetika  berfungsi  untuk  mencari  kombinasi  jadwal  dengan  nilai  fitness  tertentu  dan  Tabu Search  digunakan  untuk  mempertahankan  nilai  fitness  tidak  pernah  turun.  Sehingga  dengan menggunakan  Algoritma  Genetika  dan  Tabu  Search  dapat  dibuat  sistem  penjadwalan  dengan nilai fitness yang tinggi dan jumlah iterasi yang sedikit. Telah dilakukan kegiatan berupa 2 kali pengujian,  pertama  dengan  menguji  pengaruh  jumlah  populasi  dan  generasi  terhadap  nilai fitness, pengujian kedua dengan menguji pengaruh jumlah strategy dari setiap stakeholder yang dijadikan  consraint  terhadap  nilai  fitness  yang  terlibat  dimulai  penyusunan  jadwal  dengan jumlah constraint yang sedikit yang dimasukan kedalam penjadwalan kemudian meningkatkan jumlah contraint kedalam penjadwalan hingga semua constraint  masuk kedalam penjadwalan. Hasil  yang  diperoleh  adalah  semakin  banyak  contraint  yang  harus  dipenuhi  maka  semakin banyak jumlah iterasi yang dibutuhkan untuk mencapai nilai fitness terbaik. Dari hasil tersebut dapat  disimpulkan  bahwa  jumlah  contraint  yang  dimasukan  kedalam  penyusunan  jadwal berpengaruh terhadap tingkat akurasi keterjadwalan.
Kata kunci :  Penjadwalan, Heuristik, Algoritma Genetika, Tabu Search.

## 1. Latar Belakang Penelitian
Penjadwalan di universitas adalah hal mengatur ruangan ke waktu tertentu [1]. Penjadwalan yang ada secara  umum  masih  manual,  yang  menimbulkan  waktu  yang  lama  [2].  Algoritma  genetika  adalah algoritma heuristik [3]. Pencarian tabu adalah pendekatan heuristik untuk mengeksplorasi solusi lokal secara optimal [4]. Metode pencarian tabu memberikan solusi yang sangat dekat secara optimal [5]. Penelitian  menggunakan  algoritma  genetika  dan  pencarian  tabu  telah  banyak  dilakukan  untuk mengoptimalkan  penjadwalan  seperti  Alberto  colorni    melakukan  penelitian  menggunakan  algoritma genetika  untuk  menyelesaikan  masalah  penjadwalan,  algoritma  genetika  menghasilkan  jadwal  yang lebih baik tetapi dengan jumlah langkah-langkah yang lebih banyak [6]. Tanzila islam menggunakan pencarian tabu untuk penjadwalan universitas menghasilkan solusi penjadwalan yang lebih pendek [5]. Kemudian, dari masalah itu pada penelitian ini bertujuan untuk menghasilkan penjadwalan yang dapat menjadwalkan  waktu  baik  dan  kurang  dengan  menggabungkan  algoritma  heuristik,  yaitu  algoritma genetika dan penelusuran tabu.

## 2. Metodologi Penelitian
Pada  tahap  penjadwalan  yang  dilakukan,  pengujian  akan  menggunakan  tiga  jenis  algoritma penjadwalan  heuristik  yaitu  algoritma  genetika,  penelusuran  tabu,  dan  menggabungkan algoritma genetika dengan tabu search.

## 2.1 Algoritma Genetika
Algoritma  genetika  adalah  pendekatan  komputasi  untuk  memecahkan  masalah  yang dimodelkan  sebagai  proses  evolusi  biologi  [7].  Algoritma  genetika  adalah  metode  pemecahan masalah  berdasarkan  abstraksi  proses  seleksi  alam  [8].  Algoritma  genetika  pada  umumnya terdiri dari tiga operasi yaitu reproduksi, crossover, dan mutasi [11].

## 2.2 Algoritma Tabu Search
Algoritma  pencarian  Tabo  [10,12]  adalah  solusi  heuristik  evolusi  yang  meningkatkan  solusi tunggal.  Ini  dimulai  dari  solusi  acak  dan  secara  berurutan  memindahkannya  ke  salah  satu tetangganya [9].

## 2.3 Algoritma Genetika -Tabu Search
Untuk mendapatkan hasil optimal dalam penjadwalan, yaitu melengkapi setiap kekurangan yang ada pada  masing-masing  metode  dengan  cara  saling  melengkapi  satu  sama  lain  untuk  mendapatkan penjadwalan terbaik dengan jumlah waktu yang sedikit maka diperlukan penggabungan kedua metode algoritma  genetika  dan  tabu.  pencarian.  Dalam  menggabungkan  kedua  metode  ini  dapat  dilihat  pada Gambar 1.

## Algoritma Genetika
Gambar 1 . Algoritma Genetika dan Tabu Search
Dalam  algoritma  genetika  terdapat  proses  pengkodean  untuk  inisialisasi  populasi  awal,  kemudian dilakukan  proses  evaluasi  untuk  mencari  kecocokan  dengan  menentukan  nilai  fitnessnya,  jika  nilai fitness  sudah  sesuai  maka  akan  meghasilkan  solusi  penjadwalan,  namun  apabila  nilai  fitness  belum memenuhi  maka  akan  melakukan  proses  berikutnya  yaitu  seleksi  induk  terbaik  dilanjutkan  dengan proses  crossover  dan  mutasi.  Apabila  nilai  fitness  sudah  memenuhi  maka  akan  menghasilkan  solusi penjadwalan namun apabila nilai fitness belum memenuhi pada proses maka akan dilanjutkan dengan proses  tabu  search  dimana  metode  ini  menggunakan  tabu  list  untuk  menyimpan  sekumpulan  solusi yang  baru  saja  dievaluasi.  Selama  proses  optimasi,  pada  setiap  iterasi,  solusi  yang  akan  dievaluasi dicocokan  terlebih  dahulu  dengan  isi  tabu  list  untuk  melihat  apakah  solusi  tersebut  sudah  ada  pada tabu list. Apabila solusi tersebut sudah ada pada tabu list, maka solusi tersebut tidak akan dievaluasi lagi pada iterasi berikutnya.
Tabu  search  memungkinkan  sebuah  solusi  diterima  kembali  menjadi  current    solution  apabila  nilai pinalty keseluruhan jauh lebih kecil dari pada solusi sebelumnya menurut batasan batasan tertentu agar solusi  yang  sudah  ada  pada  tabu  list  tidak  diperiksa  berulang-ulang.  Tabu  search  digunakan  untuk mempertahankan nilai fitness yang baik dengan jumlah iterasi yang sedikit.

## 3. Hasil dan Posisi Keterbaruan Penelitian
Dalam  menyelesaikan  permasalahan  penjadwalan  perkuliahan,  peneliti  sebelumnya sudah  ada  yang  menggunakan  penggabungan  algoritma  genetika  dan  tabu  search.  Pada penelitian  Komang  Setemen  dan  Mauridhi  Hery  Purnomo  target  yang  ingin  dicapainya hanyalah  menghasilkan  jadwal  kuliah  serta  menguji  coba  bagaimana  kinerja  antara penggabungan  algoritma  genetika  dan  tabu  search  dengan  bila  dibandingkan  dengan menggunakan  algoritma  genetika  saja.    Uji  coba  pada  implementasi  perangkat  lunak  yang dikembangkan  pada  penelitian  tersebut  adalah  dengan  menguji  coba  tiga  kelompok  data dengan  jumlah  matakuliah  yang  berbeda.dari  uji  coba  didapatkan  hasil  bahwa  kombinasi algoritma genetika dan tabu search cenderung menghasilkan nilai fitness lebih baik dan jumlah iterasi yang lebih sedikit jika dibandingkan dengan algoritma genetika saja.
Sedangkan  keterbaruan  pada  penelitian  ini    yaitu,  hasil  yang  ingin  dicapai  bukan  hanya menghasilkan jadwal perkuliahan tetapi diupayakan dapat memberikan nilai bisnis lebih untuk pihak kampus seperti:
Diupayakan  dapat  memenuhi  semua  keinginan  yang  menjadi  strategy  dari  setiap  stakholder yang terlibat.
2. Diupayakan  dapat  memberikan  analisis  penggunaan  ruangan  yang  kosong,  sehingga dapat memberikan rekomendasi untuk kegiatan lain yang memerlukan ruangan. Dengan begitu diharapkan penggunaan ruangan menjadi lebih efektif.
Perbedaan  lain  penelitian  yang  sudah  dilakukan  dengan  penelitian  ini  adalah  pengujian  yang akan  diujicoba  pada  implementasi  yang  perangkat  lunak  yang  dibangun  adalah  dengan menggunakan dua kali pengujian yaitu :
1. Menguji bagaimana pengaruh jumlah generasi dan populasi terhadap nilai fitness.
2. Menguji bagaimana pengaruh jumlah strategy yang harus dipenuhi menggunakan jumlah generasi  dan  populasi  yang  sama  sesuai  dengan  jumlah  generasi  dan  populasi  terbaik  saat pengujian pertama.

## 4. Pengujian Akurasi
Prosentase ketepatan / akurasi dari pengujian ini dihitung dengan rumus sebagai berikut:
Akurasinya akan 100% jika nilai fitness yang didapatkan sudah bernilai 1 dari proses iterasi, jika nilai fitness sudah didapatkan 1 artinya tidak ada lagi jadwal yang terlanggar constraintnya dan proses iterasi selesai.

## Pengujian berdasarkan pengaruh jumlah populasi dan generasi

## Tabel 1 Pengujian Berdasarkan Pengaruh Jumlah Populasi dan Generasi
Pengaruh Jumlah populasi dan generasi  terhadap Nilai Fitness Jumlah populasi Jumlah generasi Nilai fitness yang diperoleh 10 50 0,26 20 70 0,29 40 90 0,40 80 110 0,51
Setelah melakukan pengujian berdasarkan pengaruh jumlah populasi dan generasi terhadap nilai fitnes, maka jumlah populasi dan generasi yang menghasilkan nilai fitness terbaik akan
digunakan untuk kebutuhan pengujian selanjutnya yaitu pengujian berdasarkan pemenuhan strategy menggunakan jumlah populasi dan jumlah generasi terbaik yang telah diperoleh pada pengujian ini.

## Pengujian berdasarkan pemenuhan strategy

## Tabel 2 Pengujian berdasarkan pemenuhan strategy
Kemudian  setelah  semua  strategy  dijadikan  contraint  dan  dimasukan  kedalam  penjadwalan maka akan diperoleh output dari hasil pengujian yang menunjukan strategy mana saja yang terpenuhi dan tidak terpenuhi atau harus dikorbankan. Seperti contoh berikut ini :
Tabel 3 Output hasil pengujian strategy Output hasil pengujian pemenuhan strategy Nama Strategy Bobot Stakeholder asal Status A 1 Kaprodi Terpenuhi B 0,5 Dosen Terpenuhi C 0,5 Mahasiswa Tidak terpenuhi D 1 Rektorat Terpenuhi E 1 Dosen Tidak terpenuhi Pengaruh Jumlah Strategy terhadap Nilai Fitness Jumlah populasi Jumlah generasi Jumlah strategy yang digunakan dalam penjadwalan Nilai fitness yang diperoleh X Y 4 1 X Y 8 1 X Y 12 0.92 X Y 18 0,87

## 5. Perancangan Antarmuka

## 1. Perancangan input pemenuhan strategy

## Gambar 2  Perancangan input pemenuhan strategy
4. Perancangan output pemenuhan strategy
Gambar 3 Perancangan output pemenuhan strategy

## 6. Implementasi dan Hasil
1. Output penjadwalan

## Gambar 4 Output Penjadwalan

## 2. Analisis Pemenuhan strategy

## 3. Analisis Ruangan Kosong

## Gambar 6 Analisis Ruangan Kosong

## 4. Analisis Ruangan Kosong
Gambar 7 Analisis Ruangan Kosong

## 7. Kesimpulan dan Saran
1. Kesimpulan
Dari  hasil  penelitian  penjadwalan  matakuliah  berdasarkan  pemenuhan  startegy menggunakan algoritma heuristik diperoleh kesimpulan sebagai berikut :
1) Berdasarkan  karakteristik  universitas  tempat  penelitian  setiap  stakeholder memiliki strategy yang menjadi penentu skala prioritas constraint.
2) Berdasarkan  pengujian  yang  telah  dilakukan  diperoleh  hasil  bahwa  jumlah populasi  dan  generasi  berpengaruh  terhadap  akurasi  penjadwalan.  Semakin banyak jumlah populasi dan generasi maka akan semakin tinggi tingkat akurasi keterjadwalan  dikarenakan  kemungkinan  solusi  terbaik  yang  akan  diperoleh semakin banyak.
3) Jumlah  populasi  dan  generasi  harus  dibatasi  karena  semakin  banyak  jumlah populasi  dan  generasi  maka  akan  membutuhkan  lebih  banyak  sumber  daya waktu dan penyimpanan.
4) Jumlah constraint berpengaruh terhadap nilai fitness, semakin banyak strategy dari setiap stakeholder yang ingin dipenuhi maka semakin banyak kemungkinan constraint yang harus dikorbankan atau terlanggar.
2. Saran
Dari hasil penelitian penjadwalan kelas menggunakan metode heuristik dalam memenuhi strategy dari setiap stakeholder masih ada strategy strategy yang dikorbankan untuk memenuhi strategy yang lainnya. Saran untuk pengembangan penelitian selanjutnya yaitu:
Algoritma yang digunakan dalam penelitian ini belum dapat memenuhi semua strategy yang dari semua stakeholder.

## Daftar Pustaka
[1] E. Herjanto, Manajemen Operasi (Edisi 3). Grasindo, 2007..
[2] “Rinaldi  Teori  P,  NP,  dan  NP-Completeness  -  Penelusuran  Google.”  [Online].  Available: https://www.google.co.id/search?hl=id&q=Rinaldi+Teori+P,+NP,+dan+NP-Completeness. [Accessed: 18-Jul-2018].
[3] W.  Fatmawati,  I.  Sukendar,  and  P.  S.  Suprobo,  “PENJADWALAN  KERJA  DENGAN METODE ALGORITMA ACTIVE SCHEDULE DAN HEURISTIC SCHEDULE UNTUK MINIMISASI WAKTU PENYELESAIAN,” 2009.
[4] B. Wilkinson and M. Allen, Parallel Programming-Teknik dan Aplikasi Menggunakan Jaringan Workstation & Komputer Paralel. Penerbit Andi, 2010.
[5] Z. Zukhri, “Algoritma Genetika: Metode Komputasi Evolusioner untuk Menyelesaikan Masalah Optimasi,” Yogyakarta: Penerbit Andi, 2014.
[6] M. Gen and R. Cheng, Genetic algorithms and engineering optimization, vol. 7. John Wiley & Sons, 2000.
[1] E. Herjanto, Manajemen Operasi (Edisi 3). Grasindo, 2007.
[2] “Rinaldi  Teori  P,  NP,  dan  NP-Completeness  -  Penelusuran  Google.”  [Online].  Available: https://www.google.co.id/search?hl=id&q=Rinaldi+Teori+P,+NP,+dan+NP-Completeness. [Accessed: 18-Jul-2018].
[3] W.  Fatmawati,  I.  Sukendar,  and  P.  S.  Suprobo,  “PENJADWALAN  KERJA  DENGAN METODE ALGORITMA ACTIVE SCHEDULE DAN HEURISTIC SCHEDULE UNTUK MINIMISASI WAKTU PENYELESAIAN,” 2009.
[4] B. Wilkinson and M. Allen, Parallel Programming-Teknik dan Aplikasi Menggunakan Jaringan Workstation & Komputer Paralel. Penerbit Andi, 2010.
[5] Z. Zukhri, “Algoritma Genetika: Metode Komputasi Evolusioner untuk Menyelesaikan Masalah Optimasi,” Yogyakarta: Penerbit Andi, 2014.
[6] M. Gen and R. Cheng, Genetic algorithms and engineering optimization, vol. 7. John Wiley & Sons, 2000.
[7] A. G. D. M. Suyanto, “Jogjakarta: Penerbit Andi,” 2005.
[8] V.  Witary,  N.  Rachmat,  and  I.  Inayatullah,  “Optimasi  Penjadwalan  Perkuliahan  dengan Menggunakan  Algoritma Genetika  (Studi Kasus:  AMIK  MDP,  STMIK  GI  MDP  dan  STIE MDP),” 2013.
[9] T.  Siswono,  “Analisa  Kombinasi  Algoritma  Genetika  Dengan  Algoritma  Palgunadi  Untuk Penjadwalan Mata Kuliah Di Universitas Sebelas Maret,” 2014.
[10]  N.  Lubis  and  G.  Ginting,  “PERANCANGAN  APLIKASI  PENJADWALAN  KERETA  API DENGAN  MENGGUNAKAN  ALGORITMA  GENETIKA  (Studi  Kasus:  Stasiun  Kereta Api Bandar Khalipah Medan),” JURIKOM (Jurnal Riset Komputer), vol. 3, no. 6, 2016.
[11]  D.  C.  P.  B.-S.  Nusa,  “Optimasi  Algoritma  Naïve  Bayes  dengan  Menggunakan  Algoritma Genetika  untuk  Prediksi  Kesuburan  (Fertility),”  EVOLUSI-Jurnal  Sains  dan  Manajemen AMIK BSI Purwokerto, vol. 4, no. 1, 2016.
[12]  Y. Indrianingsih, “Algoritma genetika untuk menyelesaikan masalah optimasi fungsi berkendala dengan pengkodean bilangan bulat,” Jurnal Angkasa, vol. 2, 2010.
[13]  A. Basuki, “Strategi menggunakan algoritma genetika,” 2003, 2003.
[14]  W. A. Puspaningrum, A. Djunaidy, and R. A. Vinarti, “Penjadwalan Mata Kuliah Menggunakan Algoritma Genetika di Jurusan Sistem Informasi ITS,” Jurnal Teknik ITS, vol. 2, no. 1, pp. A127–A131, 2013.
[15]  R.  E.  Indrajit,  Skala  Prioritas  Sistem  Informasi.  Online),  https://www.  academia. edu/14337525/Skala_Prioritas_Sistem_Informasi, diakses pada, 2012.
[16]  D.  D.  P.  Sari,  W.  F.  Mahmudy,  and  D.  E.  Ratnawati,  “Optimasi  penjadwalan  mata  pelajaran menggunakan  algoritma  genetika  (studi  kasus:  SMPN  1  Gondang  Mojokerto)’,”  DORO: Repository Jurnal Mahasiswa PTIIK Universitas Brawijaya, vol. 5, no. 13, 2015.
[17]  R. K. Budhi, “Aplikasi Algoritma Genetik untuk Optimasi Penjadwalan Kegiatan Perkuliahan,” Jurnal Transformatika, vol. 6, no. 1, pp. 1–9, 2008.
[18]  I.  Nugraha,  “Aplikasi  Algoritma  Genetik  Untuk  Optimasi  Penjadwalan  Kegiatan  Belajar Mengajar,” Bandung: Institut Teknologi Bandung, 2008.
[19]  E.  Yulianti,  E.  C.  Djamal,  and  A.  Komarudin,  “Optimalisasi  Penjadwalan  Perkuliahan  Di Fakultas  MIPA  Unjani  Menggunakan  Algoritma  Genetik  dan  Tabu  Search,”  in  Seminar Nasional Informatika dan Aplikasinya, 2013, pp. 154–159.
[20]  D.  P.  Siregar,  “Optimasi  Penjadwalan  Kuliah  Dengan  Metode  Tabu  Search,”  Optimasi Penjadwalan Kuliah Dengan Metode Tabu Search, 2010.