Kumpulan skripsi dari berbagai jurusan: PENERAPAN TABU SEARCH DALAM MENYELESAIKAN GENERALIZED ASSIGNMENT PROBLEM

BAB I
PENDAHULUAN

1.1 Latar Belakang Masalah

Penugasan merupakan suatu cara untuk memasangkan suatu tugas dengan suatu agen. Agen adalah sesuatu/seseorang yang mengerjakan tugas. Penugasan merupakan salah satu bentuk masalah penting yang sering ditemukan aplikasinya dalam berbagai bidang kehidupan seperti desain jaringan komunikasi, proses produksi, dan penjadwalan sumber daya.

Misalkan terdapat sehimpunan berhingga agen dan sehimpunan berhingga tugas. Banyaknya agen dan tugas diasumsikan sama, sebab satu agen hanya boleh mengerjakan sebuah tugas dan sebuah tugas hanya boleh dikerjakan oleh satu agen. Dalam mengerjakan sebuah tugas terdapat biaya yang besarnya bergantung pada agen mana yang mengerjakan tugas tersebut, sehingga meminimalkan total biaya yang akan dikeluarkan adalah tujuan dari penugasan, dengan mencari agen yang tepat untuk suatu tugas.

Salah satu bentuk umum dari masalah penugasan adalah Generalized Assignment Problem (GAP). Pada GAP, suatu agen dapat mengerjakan lebih dari satu tugas. Sehingga banyaknya agen tidak harus sama dengan banyaknya tugas.

1
GAP dapat diselesaikan dengan menggunakan metode eksak seperti integer programming, mixed integer programming, dan dynamic programming. Tetapi untuk penyelesaian permasalahan dengan ukuran yang besar, dari metode eksak tidak dapat dibangun suatu algoritma yang cukup efisien, oleh karena itu penggunaan metode heuristik mulai diterapkan untuk menyelesaikan GAP, di antaranya adalah local search, genetic algorithm, simulated annealing, tabu search, ant colony optimization, dan hybrids.

Local search merupakan suatu metode pencarian iteratif, dimana pada setiap iterasi dilakukan pencarian pada lingkungan dari solusi sekarang. Pencarian akan terus dilanjutkan melangkah pada lingkungan jika diperoleh solusi yang lebih baik dari solusi sekarang, sehingga pencarian akan berhenti pada solusi yang bersifat optimal lokal.

Tabu search merupakan pengembangan dari local search. Tabu search ditemukan oleh Fred Glover pada tahun 1986. Tidak seperti local search, tabu search mengizinkan pencarian dilakukan pada lingkungan dari solusi berikutnya, meskipun solusi tersebut tidak lebih baik dari solusi sebelumnya. Pada skripsi ini, pendekatan heuristik yang digunakan untuk menyelesaikan GAP adalah metode tabu search, dengan permasalahan yang diambil dari [OR], yaitu kumpulan permasalahan untuk menguji kinerja suatu metode berdasarkan hasil terbaik yang diberikan.

1.2 Perumusan Masalah

Apakah penggunaan metode tabu search cukup baik untuk menyelesaikan Generalized Assignment Problem ?

1.3 Tujuan Penulisan

Tujuan dari penulisan skripsi ini adalah untuk mengetahui kinerja metode tabu search dalam menyelesaikan GAP. Hal yang menjadi pertimbangan kemampuan metode tersebut adalah seberapa dekat solusi yang didapat dengan Best Known Solution (BKS) dari masalah penguji yang diambil dari [OR]. Untuk mencapai tujuan tersebut, akan dilakukan implementasi dan simulasi algoritma tabu search untuk menyelesaikan GAP dengan menggunakan MATLAB 7.

1.4 Pembatasan Pembahasan

Pembahasan skripsi ini dibatasi pada GAP dengan tujuan memini-mumkan biaya pengerjaan keseluruhan tugas. Namun dalam implementasi masalah akan digunakan masalah penguji dengan tujuan memaksimumkan biaya.

1.5 Sistematika Penulisan

Sistematika penulisan skripsi ini dibagi menjadi lima bab. Bab II merupakan landasan teori yang membahas tentang penugasan, GAP, local search, dan tabu search. Bab III berisi pembahasan tentang metode tabu search dalam menyelesaikan GAP. Bab IV berisi implementasi dan beberapa hasil percobaan. Terakhir, Bab V berisi kesimpulan.