Resume Paper 1 Skripsi Informatika

Aplikasi Penjadwalan Mata Pelajaran Menggunakan Algoritma Tabu Search Studi Kasus SMK Negeri 5 Malang

oleh Ali Fitri Wardani

Penjadwalan merupakan proses untuk menyusun suatu jadwal. Permsalahan penjadwalan biasanya berhubungan dengan penjadwalan kelas dalam sekolah atau perkuliahan dan juga dalam lingkup yang tidak jauh berbeda seperti penjadwalan pelajaran sekolah, penjadwalan ujian, atau bias juga penjadwalan karyawan, baik dalam suatu perusahaan ataupun dalam rumah sakit. Dalam proses pembuatan jadwal mata pelajaran untuk jenjang sekolah menengah kejuruan (SMK) atau jenjang lainnya dengan jumlah guru dan kelas yng banyak sangat rumit dilakukan secara manual. Hal tersebut terjadi karena banyaknya criteria yang harus dipenuhi untuk menghasilkan jadwal yang bias diterima oleh semua pihak.

Algoritma tabu search merupakan algoritma salah satu prosedur metaheuristik untuk permasalahan optimasi kombinatorial. Algoritma ini dipakai karena memiliki daerah pencarian yang lebih luas dan mencegah adanya penggulangan move sebelumnya. Algoritma tabu search tidak akan menghilangkan peran dalam penyusunan jadwal, tetapi membantu dalam pengambilan keputusan. Dengan  adanya algoritma tabu search ini dapat membantu dalam proses pembuatan jadwal mata pelajaran terutama dalam hal membuat jadwal mata pelajaran dengan nilai konfilk minimum atau  tidak adanya konflik baik konflik mata pelajaran, guru, dan ruangan dalam satu waktu. Dengan menggunakan aplikasi ini diharapkan bias mempermudahkan dalam pembuatan jadwal mata pelajaran.

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 yang  (current) yang tidak tergolong dalam solusi terlarang. Ide dasar dari algoritma tabu search adalah mencegah proses pencarian ulang pada ruang solusi yang sudah pernah di telusuri, dengan memanfaatkan suatu struktur memori yang mencatat sebagaian jejak proses pencarian yang telah dilakukan.

Struktur memori fundamental dalam algoritma tabu search dinamakan tabu list. Tabu list menyimpan atribut dari sebagian move (transisi solusi) yang telah diterapkan pada iterasi-iterasi sebalumnya. Tabu search menggunakan tabu list untuk menolak solusi yang memenuhi  atribut tertentu guna mencegah proses pencarian mengalami cycling pada penelusuran daerah yang sama, dan menentukan proses daerah yang sudah dikunjungi. Tanpa menggunakan strategi ini local search yang sudah menemukan solusi optimum local dapat terjebak pada daerah solusi optimum local tersebut pada iterasii berikutnya.

Struktur tabu search menggunakan 4 dimensi terdiri dari :

  • Recency
  • Frequency
  • Quality
  • Influence

Recency-based dan frequency-based memory saling melengkapi satu sama lain. Dimensi quality  berhubungan dengan kemampuan membedakan manfaat solusi yang diperoleh selama proses pencarian. Perekaman solusi secara lengkap dalam sebuah forbidden list dan pengecekan solusi tercatat dalam list tersebut merupakan cara yang mahal, baik dari segi kebutuhan memori maupun kebutuhan waktu komputerisasi. Jadi tabu list hanya menyimpan langkah transisi (move) yang merupakan lawn atau kebalikan dari langkah uang telah digunakan dalam ietrasi sebalumnya untuk bergerak dari satu solusi ke solusi berikutnya. Dengan kata lain tebu search list berisi langkah-langkah yang mengembalikan solusi yang ke solusi yang lama.

Pada tiap iterasi, dipilih solusi baru yang merupakan solusi terbaik dalam neighbourhood dan tidak tergolong sebagai tabu. Sebagai tambahan dari tabu list, dikenal adanya kriteria aspirasi yakni suatu penanganan khusus terhadap move yng nilai dapat menghasilkan solusi yang baik namun move tersebut berstatus tabu. Dalam hal ini, jika move memenuhi criteria aspirasi yang telah dapat digunakan untuk membentuk solusi berikutnya (status tabunya dibatalkan).

Pemilihan kandidat terbaik didasarkan nilai fungsi tujuan. Pemeriksaan nilai fungsi tujuan lebih didahulukan sebelum periksaan status tabu. Apabila nilai fungsi tujuan sebuah kandidat lebih baik dari yang lain, maka kandidat tersebut lebih berpotensi untuk diterima sehingga perlu diperiksa status tabunya. Pemilihan kandidat soluisi terbaik yang dilakukan oleh tabu search menggunakan prinsip global best strategy bukan first best strategy. Global best strategy adalah strategi dimana algoritma akan mengganti solusi terbaik saat ini dengan solusi terbaik yang ada pada neighbourhood. Adapun first best strategy adalah strategy dimana algoritma yang akan mengganti solusi terbaik saat ini secara langsung jika solusi yang lebih baik ditemukan.

Algoritma tabu search memiliki kemampuan untuk keluar dari solusi optimum local, tetapi tabu search tidak dapat menentukan optimum global. Tabu search harus memiliki  batasan maksimum jumlah iterasi dan ukuran tabu list yang ditentukan sendiri oleh programmer. Jumlah iterasi yaitu banyaknya iterasi yang akan dilakukan untuk mengekplorasi berbagai space search area.  Semakin besar jumlah maksimum iterasi, maka semakin besar pula peluang untuk mementukan solusi optimal secara global, namun memerlukan waktu perhitungan yang lama.

One thought on “Resume Paper 1 Skripsi Informatika

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s