## PENERAPAN ALGORITMA TABU SEARCH UNTUK PENJADWALAN MATA PELAJARAN DI SMK SWASTA PELITA-2 AEKKANOPAN

## Leo Candra S
Mahasiswa Teknik Informatika STMIK Budi Darma Medan Jl. Sisingamangaraja No 338 Simpang Limun Medan

## ABSTRAK
Penjadwalan  merupakan  proses  untuk  menyusun  jadwal,  penjadwalan  berhubungan  dengan  jadwal  mata pelajaran, baik sekolah, perkuliahan maupun dunia kerja. Proses penjadwalan mata pelajaran Di SMK swasta pelita Aek Kanopan pada saat ini masih dilakukan secara manual. Metode Tabu Search merupakan salah satu metode  pemecahan  permasalahan  optimasi  kombinatorial  yang  tergabung  ke  dalam  local  search  methods. Metode  ini  bertujuan  untuk  mengefektifkan  proses  pencarian  solusi  terbaik  dari  suatu  permasalahan  optimasi kombinatorial yang berskala  besar (bersifat  np-hard). Penerapan merupakan  sebuah tindakan  yang dilakukan baik secara individu maupun kelompok dengan maksud untuk mencapai tujuan yang telah dirumuskan.
Kata Kunci: Penerapan,Tabu Search, Penjadwalan

## I. PENDAHULUAN
Penjadwalan merupakan proses untuk menyusun jadwal, penjadwalan berhubungan dengan jadwal mata pelajaran,  baik  sekolah,  perkuliahan  maupun  dunia kerja.  Proses  penjadwalan  mata  pelajaran  Di  SMK swasta  pelita  Aek  Kanopan  pada  saat  ini  masih dilakukan secara manual.
Dalam penyelenggaraan pendidikan penjadwalan mata  pelajaran  Di  SMK  Swasta  pelita  Aek  Kanopan sangat dibutuhkan untuk dapat menerapkan penjadwalan dengan secara efisien. Proses penjadwalan  mata  pelajaran  merupakan  faktor  yang sangat  penting  dalam  proses  pendidikan  Sekolah Menengah  Kejuruan  (SMK).  SMK  Swasta  Pelita-2 Aek  Kanopan  merupakan  lembaga  pendidikan dikabupaten
Labuhan
Batu
Utara,
dalam melaksanakan  penjadwalan  mata  pelajaran  di  SMK Swasta  Pelita  masih  menggunakan  manual  sehingga pelaksaannya  kurang  optimal  demikian  juga  dalam memberikan  pelayanan  kepada  pihak-pihak  terkait tidak dapat dilakukan dengan maksimal.
Inti  permasalahan  penjadwalan  mata  pelajaran adalah  bagaimana  menjadwalkan sejumlah komponen yang  terdiri  atas  mata  pelajaran,  guru  dan  waktu dengan  sejumlah  batasan  dan  syarat  ( constraint) agar tidak terjadinya bentrokan pada jam yang bersamaan. Adapun  jurnal  sebagai  pendukung  dalam  penulisan karya  ilmiah  tersebut  yang  sudah  diterbitkan  dahulu dengan  judul  “Implementasi  Metode  Tabu  Search Untuk  Penjadwalan  Kelas”  oleh  Iriansyah  BM Sangadji  terdapat  bahwa  metode Tabu  Search merupakan salah satu metode pemecahan permasalahan  optimasi  kombinatorial  yang  tergabung ke dalam local  search methods. Metode ini  bertujuan untuk  mengefektifkan  proses  pencarian  solusi  terbaik dari  suatu  permasalahan  optimasi  kombinatorial  yang berskala besar (bersifat np-hard).

## II. TEORITIS

## A. Penerapan
Menurut  J.S  Badudu  dan  Sutan  Mohammad Zain, penerapan adalah hal, cara atau hasil (Badudu & Zain,  1996:1487).  Adapun  menurut  Lukman  Ali,
penerapan  adalah  mempraktekkan,  memasangkan (Ali,  1995:1044).  Berdasarkan  pengertian  tersebut dapat  disimpulkan  bahwa  penerapan  merupakan sebuah  tindakan  yang  dilakukan  baik  secara  individu maupun  kelompok  dengan  maksud  untuk  mencapai tujuan  yang  telah  dirumuskan.  Adapun  unsur-unsur penerapan meliputi :
1. Adanya program yang dilaksanakan
2. Adanya  kelompok  target,  yaitu  masyarakat  yang menjadi  sasaran  dan  diharapkan  akan  menerima manfaat dari program tersebut.
3. Adanya pelaksanaan, baik organisasi atau perorangan  yang  bertanggung  jawab  dalam pengelolaan,  pelaksanaan  maupun  pengawasan dari proses penerapan tersebut  (Wahab, 1990:45).

## B. Searching
Searching adalah  satu  pekerjaan  yang  paling mendasar  dalam  bidang  perkomputeran.  Searching digunakan  dalam  dalam  setiap  tindakan  yang  perlu untuk mengetahui bila mana sebuah elemen tercantum dalam  daftar  atau  lebih  umum  lagi,  pencarian  ulang dari  file  informasi  yang  berhubungan  dengan  unsur tersebut.

## a. Klasifikasi Searching
Adapun klasifikasi searching yaitu antara lain :
1. Line search
Line  search ini  dibuat  dengan  cara  melakukan pengecekan 1 persatu, yaitu antara data yang dicari dengan  kumpulan  data  yang  dimiliki,  keuntungan metode  ini  adalah  tidak  perlu  mengurutkan  data yang  ada,  bila  mencari  data  pada  kumpulan  data yang  tidak  urut  hanya  terdapat  metode  ini  yang dapat dilakukan. Listing program (open in internet explorer only) .
2. Binnary search Binnary  search ini  hanya  dapat  digunakan  pada kumpulan  data  yang  sudah  diurutkan,  teknik  ini melakukan  pencarian  dengan  mencari  data  pada index  yang  tengah,  apakah  lebih  besar,lebih  kecil atau sama dengan.bila  lebih  kecil  atau  lebih  besar maka akan dibuang setengah data dari yang salah,
dan  mencari dari  indeks  yang tengah dari  sisanya. Demikian  sampai  data  ditemukan  atau  tidak ditemukan. Listing  program  (open  internet explorer only).
3. Fibonanchi search Teknik  ini  hanya dapat digunakan pada kumpulan data yang sudah di  urutkan, teknik ini melakukan pencarian  dengan  mencari  data  melalui  pola bilangan fibonanchi .  Bila  pada binnary  search berbeda  yaitu  :  bilangan fibonachi, yang  bilangan fibonachi nya  terdekat  dengan  jumlah  data  tetapi tidak  lebih  besar  dari  jumlah  data  yang  akan  di proses.

## C. Tabu Search
Kata  “ Tabu atau  Taboo” berasal  dari  Tongan, suatu  bahasa  Polinesia  yang  digunakan oleh  suku Aborigin  Pulau  tonga  untuk  mengindikasikan  suatu hal  yang  tidak  boleh  “disentuh”  karena  sakralnya. Menurut  kasus  Webster,  Tabu  berarti  larangan  yang dipaksakan  oleh  kebudayaan  social  sebagai  suatu tindakan  pencegahan  atau  sesuatu  yang  dilarang karena berbahaya. Bahaya yang harus dihindari dalam Tabu Search adalah  penjadwalan  yang  tidak  layak, dan  terjebak  tanpa  ada  jalan  keluar. Dalam  konteks lebih  luas,  larangan  perlindungan  dapat  diganti  jika terjadi tuntutan yang mendadak.
Tabu  Search adalah  sebuah  metode  optimasi yang  berbasis  pada local  search .  Proses  pencarian bergerak dari satu solusi ke solusi berikutnya, dengan cara  memilih  solusi  terbaik neighbourhood solusi sekarang  ( current )  yang  tidak  tergolong  solusi terlarang  ( tabu ). Ide  dasar  dari  algoritma tabu  search adalah  mencegah  proses  pencarian  dari local  search agar  tidak  melakukan  pencarian  ulang  pada  ruang solusi yang  sudah  pernah  ditelusuri,  dengan memanfaatkan  suatu  struktur  memori  yang  mencatat sebagian jejak proses pencarian yang telah dilakukan. (Hindriyanto Dwi Purnomo,2014:92)
Menurut  Fred  Glover,  tabu  search  memiliki tiga hal pokok yaitu :
1. Penggunaan Struktur memori  yang  fleksibel,  yang memungkinkan  evaluasi  criteria  dan  informasi historis  bisa  eksploitasi  lebih  baik  dibandingkan dengan struktur memori yang statis.
2. Penggunaan  mekanisme  control  yang  didasarkan pada  interaksi antara kondisi  yang  membatasi dan kondisi yang mendukung proses pencarian.
3. Penggabungan  fungsi  memori  yang  memiliki rentang  waktu  yang  berbeda,  dari  memori  jangka pendek  sampai  dengan  memori  jangka  panjang, untuk  menerapkan  strategi  intensifikasi  dan diversifikasi.
Didalam menerapkan tabu search, ada beberapa hal yang harus diperhatikan, yaitu : a. Tabu  list :  tujuan  dari  penggunaan tabu  list (memori jangka pendek) adalah untuk menghindari  mengevaluasi kandidat solusi  yang pernah dikunjungi sebelumnya.
b. Aspiration  criteria :  umumnya  diterapkan  jika pergerakan  tabu  tersebut  menghasilkan  kandidat
solusi  yang  memiliki  nilai  yang  lebih  baik  dari pada seolusi terbaik yang telah dihasilkan.
c. Intensifikasi  (memori  jangka  menengah):  memori jangka  menengah  menyimpan  sejumlah  solusi yang  berkualitas  ( elite  solution )  yang  dihasilkan selama proses pencarian. Memori jangaja menengah  ini  bertujuan  untuk  memberikan prioritas  kepada  atribut  dari  solusi  berkualitas tersebut.
d. Diversifikasi  (memori  jangka  panjang):  memori jangka
menyimpan informasi
tentang kandidat solusi yang pernah dikunjungi. ( Hindriyanto Dwi Purnomo,2014:94).
Untuk  mendalami  lagi  prinsip  kerja  metode pencarian  tabu,  dapat  memformulakan  metoda menurun  klasik  ( classical  descent  method) dalam beberapa langkah, yaitu : a. Memilih sebuah solusi awal i dalam S
b. Membangkitkan  subset V* sebagai  solusi  dalam N(i).
c. Mencari j ’terbaik’ dalam V* dan menetapkan i=j d. Jika f(i)=f(i) maka  berhenti,  namun  jika  tidak kembali ke langkah ke-2.
Dalam  metoda  menurun  secara  umum  akan dapat langsung ditetapkan bahwa V*=N(i). Tetapi hal ini  seringkali  membutuhkan  waktu  yang  lama.  Untuk itulah  cara  pemilihan V* yang  tepat  seringkali dijadikan  sebagai  peningkatan  yang  penting  dalam metode  pencarian.  Dalam  metode  menurun  secara umum  akan  dapat  langsung  ditetapkan  bahwa V*=N(i). Tetapi  hal  ini  sering  kali  membutuhkan waktu  yang  lama.  Untuk  itulah  cara  pemilihan V* yang  tepat  seringkali  dijadikan  sebagai  peningkatan yang  penting  dalam  metode  pencarian.  Pada  kasus yang  berlawanan,  akan  ditetapkan  | V*|=1. Hal  ini akan  menurunkan  fase  pemilihan j  ‘ terbaik’.  Solusi j akan  diterima  jika f(i)=f(i), sebaiknya  hal  ini  akan diterima dengan kemungkinan tertentu yang bergantung  pada  nilai-nilai f pada i dan j serta  pada sebuah parameter yang disebut temperatur.
Dengan  perujukan  ini  bisa  dapat  mencoba untuk  melakukan  peningkatan  algoritma  menurun dalam  beberapa  hal  untuk  lebih  mendekatkan  metode ini  ke  prosedur  dalam  metode  pencarian  tabu  secara umum.  Hal  ini  dapat  didefinisikan  dalam  beberapa langkah  (catatan i* adalah  solusi  ‘terbaik’  yang ditemukan dan k adalah penghitung dalam pengulangan):
a. Memilih solusi awal I dalam S. Tetapkan i*=I dan k=0.
b. Tetapkan  nilai k=k+1 dan  membangkitkan  subset V* sebagai solusi dalam N(i,k)
c. Pilih j ‘terbaik’ dalam V* dan tetapkan i=j. d. Jika f(i)<f(i*) maka tetapkan i*=i.
e. Jika  kondisi  berhenti  ditemukan,  maka  proses dihentikan  sedangkan  jika  belum  kembali  ke langkah 2.
Dalam metode pencarian tabu, kondisi berhenti dapat berupa :
a. N(i,k+1)= tidak terdefinisi.
b. k lebih  besar  daripada  bilangan  maksimum  pada pengulangan.
c. Banyaknya  pengulangan  selama  peningkatkan terakhir i* lebih besar dari bilangan tertentu.
d. Pembuktian  dapat  diberikan  daripada  solusi optimum yang telah didapatkan.

## D. Penjadwalan Mata Pelajaran
Pengertian jadwal menurut kamus besar bahasa Indonesia  adalah  pembagian  waktu  berdasarkan rencana  pengaturan  urutan  kerja,  daftar  atau  tabel kegiatan  atau  rencana  kegiatan  dengan  pembagian waktu  pelaksanaan  yang  terperinci.  Sedangkan pengertian penjadwalan adalah proses, cara, perbuatan menjadwalkan atau memasukkan ke dalam jadwal.
Menurut Rosani Ginting (2005:95), bahwa penj adwalan adalah pengalokasi-an  sumber  daya  pada objek-objek  yang  ada  pada  ruang  waktu  dan tergantung  pada  kendala-kendala  yang  sedemikian sehingga  memenuhi  sekumpulan  sasaran  yang diinginkan,  secara  sederhana,  penjadwalan  dapat diartikan  sebagai  pengalokasian  sumber-sumber  daya yang  tersedia  pada  ruang  waktu  yang  ada  sehingga memenuhi kondisi-kondisi  tertentu. Tujuannya adalah untuk  memaksimalkan  suatu  proses  dengan  tetap menjaga agar tidak melanggar constraint yang berlaku pada  proses  yang  bersangkutan,  penjadwalan  sekolah merupakan  salah  satu  masalah  optimasi,  dimana optimasi adalah sarana untuk mengekspresikan model matematika  yang  bertujuan  memecahkan  masalah dengan cara yang tepat.
Didalam  penjadwalan  dikenal  dua  macam constraint (persyaratan)  yaitu Hard  Constraint dan Soft Constraint . Constraint penjadwalan sekolah yang berlaku  tentunya  berbeda  tergantung  dari  aturan  dan tata  cara  sekolah  dari  institusi  yang  bersangkutan. Constraint pada  umumnya  terbagi  menjadi  dua  jenis yaitu Hard Constraint dan Soft Constraint pada kasus penjadwalan sekolah adalah :
1. Mata  pelajaran  yang  berbeda  tidak  boleh dijadwalkan  pada  waktu  dan  tempat  yang  sama, serta  siswa  tidak  boleh  menghadiri  2  mata pelajaran pada waktu yang sama. (Hard Constraint).
2. Dalam  satu  hari  siswa  tidak  boleh  menghadiri lebih 3 x timeslot sekolah berturut-turut, harus ada jeda minimal 1 timeslot ( Soft Constraint). Perhitungan Constraint
𝑆 =                  ∑ 𝑁 𝑗=1 ∑ 𝐶𝑗𝑖 𝑁 𝑖=1
∑(𝑘𝑙𝑠)𝑖 𝑛 𝑖=1
R= S1+ S2 .... Sn
Dimana : Cji  =  nilai cost  constraint ke-j  pada  kelas  mata pelajaran ke i (kls) = jumlah kelas mata pelajaran ke i.
S = Total nilai cost
r = nilai cost total yang dihasilkan.

## E. Mata Pelajaran
Menurut  Ana  (2006;6)  Mata  pelajaran  adalah suatu  pelajaran  dimana  pelajaran  tersebut  selalu mempelajari  hal-hal  dalam  kehidupan  sehari-hari sehingga  dengan  memahami  pelajaran  tersebut    dan lebih  berhati-hati dalam  menjalani kehidupan  ini, dan tidak  menganggap  mudah  suatu  masalah  yang  kecil tersebu  dapat  mengakibatkan  hal-hal  yang  besar  atau suatu cabang pengetahuan  yang diajarkan atau diteliti di  jenjang  sekolah.  (Jurnal  Pelita  Informatika  Budi Darma, Volume : V, Nomor: 3, Desember 2013).
Penjadwalan mata pelajaran merupakan kegiatan  yang  sangat  penting  untuk  proses  belajar mengajar.  Proses  belajar  mengajar  dilaksanakan  oleh seluruh  siswa  dan  guru,  sehingga  jadwal  mata pelajaran  yang  disusun  harus  dapat  memfasilitasi kepentingan guru dan siswa-siswi. (sugiarto 2007;90).
Pengertian jadwal menurut kamus besar bahasa Indonesia  adalah  pembagian  waktu  berdasarkan rencana  pengaturan  urutan  kerja,  daftar  atau  tabel kegiatan  atau  rencana  kegiatan  dengan  pembagian waktu  pelaksanaan  yang  terperinci.  Sedangkan pengertian penjadwalan adalah proses, cara, perbuatan menjadwalkan atau memasukkan ke dalam jadwal.
Menurut  Chambers  (1995:22)  menyatakan bahwa  jadwal  didefinisikan  sebagai  sesuatu  yang menjelaskan  di  mana  dan  kapan  orang-orang  dan sumber  daya  berada  pada  suatu  waktu.  Berdasarkan Kamus  Besar  Bahasa  Indonesia,  jadwal  merupakan pembagian  waktu  berdasarkan  rencana  pengaturan urutan kerja. Jadwal  juga didefinisikan  sebagai daftar atau  tabel  kegiatan  atau  rencana  kegiatan  dengan pembagian waktu pelaksanaan yang terperinci.
Kebanyakan  orang  terbiasa  dengan  jadwal pelajaran  yang  disajikan  sebagai  tabel  hari  dalam seminggu  dan  jangka  waktu.  Dapat  dilihat  bahwa setiap  hari  dibagi  ke  dalam  jangka  waktu.  Setiap jangka  waktu  memiliki  daftar  mata  kuliah  yang sedang  diajarkan,  oleh  siapa  dan  di  mana.  Jadwal dapat  dinyatakan  dalam  sejumlah  cara  yang  berbeda, masing-masing  mahasiswa  harus  memiliki  jadwal sendiri  tergantung  pada  mata  pelajaran,  begitu  juga masing-masing  guru  dan  ruang,  semua  ini  adalah perspektif yang berbeda pada jadwal yang sama.
Penjadwalan  juga  didefinisikan  sebagai  proses pengalokasian sumber-sumber atau mesin-mesin yang ada  untuk  menjalankan  sekumpulan  tugas  dalam jangka  waktu  tertentu.  Definisi  yang  diberikan mengandung  dua  arti,  yaitu  (constraint  programming untuk  penjadwalan  job-shop  para  guru,  naskhalim, 2014:93):
a. Penjadwalan  merupakan  fungsi  pengambilan keputusan yaitu menentukan jadwal (nilai praktis).
b. Penjadwalan merupakan suatu teori, yaitu sekumpulan  prinsip-prinsip  dasar,  model-model, teknik-teknik,  dan  kesimpulan-kesimpulan  logis dalam  proses  pengambilan  keputusan  yang
memberikan pengertian dalam fungsi Penjadwalan (nilai konseptual).
Adapun  tujuan  penjadwalan  secara  umumnya adalah sebagai berikut:
c. Meningkatkan  produktifitas  mesin,  yaitu  dengan mengurangi waktu mesin menganggur.
d. Mengurangi  persediaan  barang  setengah  jadi dengan jalan mengurangi jumlah rata-rata pekerjaan  yang  menunggu  dalam  antrian  suatu mesin karena mesin tersebut sibuk.
e. Mengurangi keterlambatan suatu pekerjaan. Setiap pekerjaan  mempunyai  batas  waktu  ( due  date ) penyelesaian,  jika  pekerjaan  tersebut  diselesaikan melewati  batas  waktu  yang  ditentukan  maka pekerjaan  tersebut  dinyatakan  terlambat.  Dengan metoda penjadwalan maka keterlambatan ini dapat dikurangi, baik waktu maupun frekuensi.

## III. ANALISA DAN PEMBAHASAN
Mata  pelajaran  merupakan  salah  satu  hal terpenting  bagi  siswa siswi  pendidikan  SMK  Swasta Pelita 2 Aekkanopan menambahkan ilmu pengetahuan yang  ditetapkan  oleh  dinas  pendidikan.  Kegiatan belajar mengajar dilaksanakan pada hari senin sampai sabtu, mulai pukul 07.30 sampai 14.00.
Proses penyusunan penjadwalan  mata pelajaran di awali  dengan  rapat  mata  pelajaran  pada  tiap  selesai ujian  semester.  Kemudian  masing-masing  mata pelajaran ditugaskan kepada guru yang kompeten pada mata  pelajaran  masing-masing  tersebut.  Selanjutnya, mata  pelajaran  dijadwalkan  pada  hari,  jam  dan ruangan  yang  tersedia.  Dengan  mempertimbangkan kesediaan  waktu  mengajar  guru-guru  tersebut.  Hasil akhir  dan  penyusunan  penjadwalan  mata  pelajaran selama satu semester yang disusun berdasarkan ruang kelas, dan mata pelajaran.
Tabel 1: Daftar Kelas No Kelas Nama Jurusan 1 X AK,AP,Tkj 2 XI AK,AP,TKJ 3 XII AK 1,AK2,TKJ 1,TKJ 2,AP Tabel 2: Mata Pelajaran No Mata Pelajaran 1 Kejuruan Keahlian Akutansi (KK.AK) 2 Ipa 3 B.inggris 4 Keselamatan Kesehatan Kerja dan Lingkungan Hidup (K3LH) 5 Ips 6 Keterampilan  Komputer  dan  Pengelolaan Informasi (KKPI) 7 Pkn 8 Agama 9 Kewirausahaan (KWH) 10 Matematika 11 Seni Budaya (SBY) 12 Conversation
13 Penjas 14 B. Indonesia 15 Kejuruan Keahlian Administrasi Perkantoran (KK.AP) 16 Kejuruan Keahlian Teknik Jaringan (KK.TKJ) 17 Kimia 18 Fisika Tabel 3: Daftar Nama Guru No Nama Guru Kode 1 Abdul Rasyid RD 2 Mahyudiana MY 3 Amir Hamzah AH 4 Nimrod Padang NP 5 Agung Prasetyo AG 6 Haposan HP 7 Misfaujiah MF 8 Irma Suryani IR 9 Elfrida Siahaan ES 10 Marnaek Albedo MA 11 Hotmaida Sitanggang HM 12 Ruth Damayanti RT 13 Friska FR 14 Fernando. S FS 15 Ria Angelina RA 16 Charles Tampubolon CH 17 Berkat Siringo-ringo BA 18 Siti Nurhayati SN 19 Minisere Pasaribu MP 20 Hotmaida Sirait HS 21 Aston Simarmata AS 22 Suhendra HD 23 Sukirmanto SK 24 Lasma Tampubolon LT 25 Rondang Hasibuan RH 26 Monang Deliany MD 27 Gusar Siringo-ringo GS 28 Ridwan Siahaan RS
Pada  dasarnya  untuk  membuat  aplikasi penjadwalan  yang  nantinya  akan  digunakan  untuk membantu proses penjadwalan mata pelajaran. Hal ini karenakan  aplikasi  penjadwalan  yang  sudah  ada  dan belum  ada  algoritma  penjadwalan  di  dalamnya, sehingga dalam penyusunannya masih bersifat manual dan membutuhkan waktu yang lama sehingga menjadi efektif dan efisien.

## Komponen Penjadwalan Mata Pelajaran
Untuk  memahami  aturan-aturan  yang  akan  di gunakan, pada bagian ini akan di jelaskan karakteristik dari masing-masing variabel yang merupakan komponen utama dari setiap penjadwalan. Komponen pertama  adalah  guru  dan  mata  pelajaran.  Pemberian tugas  mengajar  suatu  mata  pelajaran  kepada  seorang guru dilakukan di penjadwalan. Komponen berikutnya adalah kelas atau siswa, sebagai mata pelajaran. Untuk
setiap  kelas  harus  mengambil  mata  pelajaran  sesuai jenjang kelas tersebut.
Tabel 4: Komponen penjadwalan Mata pelajaran No Mata Pelajaran Kode Guru 1 Kejuruan Keahlian Akutansi (KK.AK) MP,HS,SN,AS 2 Ipa HM 3 B.inggris IR,MF,FS 4 Keselamatan  Kesehatan Kerja  dan  Lingkungan Hidup (K3LH) HS,LT,RD 5 Ips NP,HM, 6 Keterampilan  Komputer dan Pengelolaan Informasi (KKPI) SH,SK,RD,SN 7 Pkn AH,NP 8 Agama MY 9 Kewirausahaan (KWH) RT,HM, 10 Matematika ES,MA 11 Seni Budaya (SBY) FR,RH,FR,FS, 12 Conversation FR 13 Penjas AG,HP, 14 B. Indonesia RA,CH,BS 15 Kejuruan Keahlian Administrasi Perkantoran (KK.AP) RT,MD,RH,LT 16 Kejuruan Keahlian Teknik Jaringan (KK.TKJ) RD,SK,HD 17 Kimia RA 18 Fisika NP, FS Perhitungan cost dalam tabu  search adalah suatu proses yang sangat penting. Melalui perhitungan cost ini tabu  search dapat  mendeteksi  pelanggaran
constraint pada  masing-masing  kelas.  Pendeteksian pelanggaran  ini  dilakukan  untuk  menentukan  kelas mana  yang  harus  diperbaiki,  kemudian  memilih  guru dan  jam  pelajaran  yang  harus  di  pilih  untuk memperbaiki  jadwal  kelas  tersebut.  Dapat  dikatakan keberhasilan tabu  search dalam  menentukan  solusi yang  mempunyai  tingkat  kebenaran  yang  tinggi tergantung dari cara yang digunakan untuk menentukan cost dari suatu kelas.
Constraint yang berlaku :
1. Proses pembuatan jadwal mata pelajaran mengenai penetapan  waktu,  mata  pelajaran  dan  guru  yang mengajar  di  lakukan  oleh  sekretaris  jurusan sedangkan  penetapan  dilakukan  oleh  staf  tata usaha jurusan.
2. Pengaturan  jadwal  sekolah  dilakukan  setiap  tahun sebanyak dua periode, yaitu:
a. Semester  ganjil  :  awal  bulan  juli  sampai  akhir desember tahun berikutnya.
b. Semester  genap  :  awal  januari  sampai  akhir juni tahun yang sama.
3. Data  yang  digunakan  adalah  nama  guru,  nama mata  pelajaran,  waktu  yang  kesediaan  guru mengajar, jumlah kelas dan ruangan yang tersedia. a. Jumlah guru berjumlah 28 orang.
b. Jumlah  mata  pelajaran  adalah  17  mata pelajaran.
c. Waktu  sekolah  yang  diperbolehkan  adalah senin-sabtu pukul 07.30 – 14.00 Wib.
4. Program  sekolah  satu  Les  setara  dengan  45  menit kegiatan tatap muka terjadwal, merupakan sekolah dimana guru memberikan bahan pelajaran di kelas untuk dipahami dan dimengerti.
Tabel 5: Hasil Pengujian Algoritma Tabu Search Dalam Penjadwalan Mata Pelajaran No HG HK HMP SG SK SMP Total Hard Total Soft Total Cost 1 0 0 0 0,005 0,015 0,009 0 0,029 0,029 2 0 0 0 0,011 0,030 0,019 0 0,06 0,06 3 0 0 0 0,065 0,045 0,029 0 0,139 0,139 4 0 0 0 0,095 0,090 0,039 0 0,224 0,224 5 0 0 0 0,101 0,106 0,049 0 0,256 0,256 6 0 0 0 0,107 0,060 0,107 0 0,274 0,274 7 0 0 0 0,113 0,121 0,117 0 0,351 0,351 8 0 0 0 0,089 0,166 0,127 0 0,382 0,382 9 0 0 0 0,119 0,136 0,156 0 0,411 0,411 10 0 0 0 0,130 0,151 0,176 0 0,457 0,457 Jumlah 0 0 0 0,835 0,92 0,828 0 2,583 2,583 Rata- rata 0 0 0 0,0008 35 0,092 0,0828 0 2,0583 2,0583
keterangan  nilai  pinalti  pada  tabel  diatas  adalah sebagai berikut:
a. Hg adalah besarnya nilai pinalti
(pelanggaran) Hard Constraint guru.
b. Hk adalah besarnya nilai pinalti (pelanggaran) Hard Constraint kelas. c. Hmp adalah besarnya nilai pinalti (pelanggaran) Hard Constraint mata pelajaran.
d. Sg adalah besarnya nilai pinalti
(pelanggaran) Soft  Constraint guru  (dalam himpunan fuzzy ).
e. Sk adalah besarnya nilai pinalti
(pelanggaran) Soft  Constraint kelas  (dalam himpunan fuzzy ). Hard Constraint dan total pelanggaran Hard (Hard constraint
guru,kelas,mata pelajaran). Dari  10  kali  percobaan  pada tabel  diatas,  tidak  ada  satupun  pelanggaran pada hard constraint guru,kelas,mata pelajaran  semuanya  bernilai  0.  Nilai Cost tergantung  dari  solusi  awal  yang  dihasilkan yang  dilakukan  secara  random  dan  metoda pencarian move dan swap.

## IV. KESIMPULAN
Berdasarkan hasil pembahasan tentang
penerapan algoritma Tabu Search untuk penjadwalan  mata pelajaran di SMK Swasta Pelita-2 Aekkanopan,  dapat  di  buat  kesimpulan  sebagai berikut :
1. Penerapan  algoritma Tabu  Search untuk
penjadwalan  mata  pelajaran  di  SMK  Swasta
Pelita-2  Aekkanopan  dilakukan  dengan  cara pemecahan permasalahan
optimasi kombinatorial  yang  tergabung  ke  dalam  local search  methods.  Metode  ini  bertujuan  untuk mengefektifkan  proses  pencarian  solusi  terbaik dari suatu permasalahan optimasi kombinatorial yang berskala besar (bersifat np-hard).
2. Jadwal  yang dihasilkan dalam  setiap percobaan adalah  berbeda,  maka  hasil  yang  didapatkan akan bervariasi setiap run-time , karena inisialisasi  awal  selalu  diawali  dengan  jadwal yang di generate secara random. Kualitas solusi yang  didapatkan  juga  bervariasi,  maka Soft constraint pada  kasus  ini  sulit  mendapatkan jadwal  yang  valid  dengan  menghasilkan  nilai pelanggaaran 0.

## V. DAFTAR PUSTAKA
1. Hindriyanto  Dwi  Purnomo  2014.  Cara  Mudah  Untuk  Belajar Optimasi Matheriustik. Yogyakarta: Andi.
2. Yuni  Sugiarti,  2013.  Analisis  &  Perancangan  UML  ( Unified Modeling Language), Yogyakarta; Graha Ilmu.
3. Primanda  Arif  Aditya,  2013.  Pemograman  Aplikasi  Database Dengan Microsoft Visual Basic.Net 2008; Informatika.
4. Glover,F,   1990,   “Tabu   Search, Computing, Vol 2 No 1 pp 4 –32
5. Glover,F,  1989,”  Candidate  Li  search”,  CAAI  Research report, Boulder.
6. Glover,F, and greenberg   HJ,   1989,   “New Heuristic Search. A bilateral link-age with Artificial
7. Intelligence,  European  Journal  Of  Operational  Research,  Vol 39 No 2 p 119 –130.
8. Hertz    A    and    de    Werra,D.,    1987 Techniques for graph coloring”, Computing,– Vol 2 351.