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

Jurnal Riset Komputer (JURIKOM), Vol. 3 No. 6, Desember 2016 ISSN 2407-389X (Media Cetak) Hal : 74-79

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 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).

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).

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,

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, 74


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 fibonachinya terdekat dengan jumlah data tetapi tidak lebih besar dari jumlah data yang akan di proses.

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)
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 75


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.

S r

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).

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 𝑁

𝑆=

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

𝑁

∑

∑ 𝐶𝑗𝑖

𝑗=1 𝑛

𝑖=1

= Total nilai cost = nilai cost total yang dihasilkan.

∑(𝑘𝑙𝑠)𝑖 𝑖=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. 76


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.

13 14 15 16 17 18

No 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

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.

No 1 2 3

No 1 2 3 4 5 6 7 8 9 10 11 12

Penjas B. Indonesia Kejuruan Keahlian Administrasi Perkantoran (KK.AP) Kejuruan Keahlian Teknik Jaringan (KK.TKJ) Kimia Fisika

Tabel 1: Daftar Kelas Kelas Nama Jurusan X AK,AP,Tkj XI AK,AP,TKJ XII AK 1,AK2,TKJ 1,TKJ 2,AP

Tabel 3: Daftar Nama Guru Nama Guru Kode Abdul Rasyid RD Mahyudiana MY Amir Hamzah AH Nimrod Padang NP Agung Prasetyo AG Haposan HP Misfaujiah MF Irma Suryani IR Elfrida Siahaan ES Marnaek Albedo MA Hotmaida Sitanggang HM Ruth Damayanti RT Friska FR Fernando. S FS Ria Angelina RA Charles Tampubolon CH Berkat Siringo-ringo BA Siti Nurhayati SN Minisere Pasaribu MP Hotmaida Sirait HS Aston Simarmata AS Suhendra HD Sukirmanto SK Lasma Tampubolon LT Rondang Hasibuan RH Monang Deliany MD Gusar Siringo-ringo GS 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.

Tabel 2: Mata Pelajaran Mata Pelajaran Kejuruan Keahlian Akutansi (KK.AK) Ipa B.inggris Keselamatan Kesehatan Kerja dan Lingkungan Hidup (K3LH) Ips Keterampilan Komputer dan Pengelolaan Informasi (KKPI) Pkn Agama Kewirausahaan (KWH) Matematika Seni Budaya (SBY) Conversation

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 77


setiap kelas harus mengambil mata pelajaran sesuai jenjang kelas tersebut.

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 4: Komponen penjadwalan Mata pelajaran No Mata Pelajaran Kode Guru 1 Kejuruan Keahlian MP,HS,SN,AS Akutansi (KK.AK) 2 Ipa HM 3 B.inggris IR,MF,FS 4 Keselamatan Kesehatan HS,LT,RD Kerja dan Lingkungan Hidup (K3LH) 5 Ips NP,HM, 6 Keterampilan Komputer SH,SK,RD,SN dan Pengelolaan Informasi (KKPI) 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 RT,MD,RH,LT Administrasi Perkantoran (KK.AP) 16 Kejuruan Keahlian RD,SK,HD Teknik Jaringan (KK.TKJ) 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

No 1 2 3 4 5 6 7 8 9 10 Jumlah Ratarata

Tabel 5: Hasil Pengujian Algoritma Tabu Search Dalam Penjadwalan Mata Pelajaran HG HK HMP SG SK SMP Total Hard Total Soft Total Cost 0 0 0 0,005 0,015 0,009 0 0,029 0,029 0 0 0 0,011 0,030 0,019 0 0,06 0,06 0 0 0 0,065 0,045 0,029 0 0,139 0,139 0 0 0 0,095 0,090 0,039 0 0,224 0,224 0 0 0 0,101 0,106 0,049 0 0,256 0,256 0 0 0 0,107 0,060 0,107 0 0,274 0,274 0 0 0 0,113 0,121 0,117 0 0,351 0,351 0 0 0 0,089 0,166 0,127 0 0,382 0,382 0 0 0 0,119 0,136 0,156 0 0,411 0,411 0 0 0 0,130 0,151 0,176 0 0,457 0,457 0 0 0 0,835 0,92 0,828 0 2,583 2,583 0 0 0 0,0008 0,092 0,0828 0 2,0583 2,0583 35

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.

d.

78

Hmp adalah besarnya nilai pinalti (pelanggaran) Hard Constraint mata pelajaran. 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. 2. 3. 4. 5. 6. 7. 8.

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

79

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

Recommend Documents