Generalized Assignment Problem (GAP) merupakan suatu bentuk masalah penugasan dari sehimpunan berhingga tugas ke sejumlah berhingga agen. Setiap agen dapat mengerjakan lebih dari satu tugas, namun suatu tugas hanya dapat dikerjakan oleh satu agen. Setiap tugas memiliki beban pengerjaan, sedangkan setiap agen memiliki keterbatasan kapasitas untuk mengerjakan tugas-tugas yang ada. Pada skripsi ini akan dilihat kinerja tabu search untuk menyelesaikan GAP, yang diukur berdasarkan kedekatan solusi yang didapat dengan Best Known Solution (BKS). Tabu search adalah suatu metode pencarian heuristik yang merupakan pengembangan dari metode pencarian local search. Untuk pengujian, digunakan beberapa data permasalahan yang diperoleh dari OR-Library. Berdasarkan simulasi disimpulkan bahwa kinerja metode tabu search cukup baik dalam menyelesaikan GAP, yaitu dengan kesalahan relatif tidak lebih dari 0,0018 untuk GAP dengan tujuan memaksimumkan.
Penerapan Tabu Search Dalam Menyelesaikan Generalized Assignment Problem
ABSTRAK
Generalized Assignment Problem (GAP) merupakan suatu bentuk masalah penugasan dari sehimpunan berhingga tugas ke sejumlah berhingga agen. Setiap agen dapat mengerjakan lebih dari satu tugas, namun suatu tugas hanya dapat dikerjakan oleh satu agen. Setiap tugas memiliki beban pengerjaan, sedangkan setiap agen memiliki keterbatasan kapasitas untuk mengerjakan tugas-tugas yang ada. Pada skripsi ini akan dilihat kinerja tabu search untuk menyelesaikan GAP, yang diukur berdasarkan kedekatan solusi yang didapat dengan Best Known Solution (BKS). Tabu search adalah suatu metode pencarian heuristik yang merupakan pengembangan dari metode pencarian local search. Untuk pengujian, digunakan beberapa data permasalahan yang diperoleh dari OR-Library. Berdasarkan simulasi disimpulkan bahwa kinerja metode tabu search cukup baik dalam menyelesaikan GAP, yaitu dengan kesalahan relatif tidak lebih dari 0,0018 untuk GAP dengan tujuan memaksimumkan.
Generalized Assignment Problem (GAP) merupakan suatu bentuk masalah penugasan dari sehimpunan berhingga tugas ke sejumlah berhingga agen. Setiap agen dapat mengerjakan lebih dari satu tugas, namun suatu tugas hanya dapat dikerjakan oleh satu agen. Setiap tugas memiliki beban pengerjaan, sedangkan setiap agen memiliki keterbatasan kapasitas untuk mengerjakan tugas-tugas yang ada. Pada skripsi ini akan dilihat kinerja tabu search untuk menyelesaikan GAP, yang diukur berdasarkan kedekatan solusi yang didapat dengan Best Known Solution (BKS). Tabu search adalah suatu metode pencarian heuristik yang merupakan pengembangan dari metode pencarian local search. Untuk pengujian, digunakan beberapa data permasalahan yang diperoleh dari OR-Library. Berdasarkan simulasi disimpulkan bahwa kinerja metode tabu search cukup baik dalam menyelesaikan GAP, yaitu dengan kesalahan relatif tidak lebih dari 0,0018 untuk GAP dengan tujuan memaksimumkan.
