Penyelesaian Masalah Knapsack Dua Dimensi Dengan Algoritma Aproksimasi

Efisiensi sangat diperlukan dalam setiap bidang, karena dengan efisiensi ini akan didapatkan suatu penghemata~ sumber daya. Di bidang permasalahan knapsack dua dimensi untuk pemotongan bahan, efisiensi penggunaan bahan sangat diperlukan untuk memaksimalkan profit ini akan diperoleh dari kombinasil pola pemotongan optimal dengan meminimalkan sisa bahan. · Dalam tugas akhir ini permasalahan knapsack dua dimensi diselesaikan dengan sebuah teknik heuristik Dari analisa struktural knapsack dua dimensi diturunkan algoritma aproksimasi. Algoritma ini menggunakan permasalahan knapsack satu dimensi untuk menyelesaikan pemotongan bahan. Algoritma menggunakan pola-pola untuk menghasilkan sekumpulan strip-strip terbaik dan mengisikannya ke dalam lembaran baJI,tm sehingga diperoleh kombinasi strip optimal. Algoritma ini dinamakan dentf.m algoritma Best Strip Cutting (BSC). Dengan menggunakan metode program dinamis, jumlah knapsack yang terlibat dapat dikurangi. Karena profit dari po~a adalah luasan dari pola itu sendiri maka fungsi tujuan adalah meminimal~n sisa bahan yang tidak terpakai. Algoritma Best Strip Cutting inil memberikan persentase solusi optimal 97%. Hasil uji coba terhadap data u~uran bahan yang besar menunjukkan efisiensi dari a/goritma ini sehingga !dapat digunakan untuk penyelesaian permasalahan di dunia nyata. Di bidang usaha industri yang berhubungan dengan permasalahan pemotongan ba~an seperti kertas, kaca, plasik , plat logam dapat memanjaatkan penyelesaian ini dalam usaha mendapatkan profit maksimal dengan sisa bahan seminimal mungkin