Penerapan metode greedy randomized adaptive search procedure dalam menyelesaikan generalized assignment problem
| Format: | Bachelors |
|---|---|
| Terbitan: |
Universitas Indonesia. Fakultas Matematika dan Ilmu Pengetahuan Alam
, 2006
|
| Subjects: | |
| Online Access: |
http://lib.ui.ac.id/file?file=digital/20180871-S27630-Christina Trias Wulandari.pdf |
Daftar Isi:
- Generalized Assignment Problem (GAP) adalah masalah penugasan sehimpunan berhingga agen ke sehimpunan berhingga pekerjaan. Setiap pekerjaan mempunyai bobot dan setiap agen mempunyai kapasitas, sehingga setiap agen tidak dapat mengerjakan seluruh pekerjaan, tergantung kepada kapasitas yang dimiliki. Ada biaya yang harus dikeluarkan jika agen mengerjakan suatu pekerjaan. Pada skripsi ini akan dilihat kinerja dari algoritma Greedy Randomized Adaptive Search Procedure (GRASP) dalam menyelesaikan GAP. Algoritma GRASP terdiri dari 2 fase, yaitu fase konstruksi solusi awal dengan algoritma Greedy Randomized Adaptive Heuristics (GRAH) dan fase perbaikan dengan metode local search. Kinerja dari algoritma GRASP akan diukur berdasarkan kedekatan solusi yang diperoleh dengan Best Known Solution (BKS). Data masalah untuk menguji diambil dari OR Library. Berdasarkan hasil percobaan, dapat disimpulkan bahwa kinerja Algoritma GRASP dalam menyelesaikan GAP cukup baik untuk masalah GAP berukuran kecil, yaitu berukuran 5 x 15, 5 x 20, 5 x 25, 5 x 30, 8 x 24, 8 x 32 .