Perbandingan Metode Branch and Bound dan Enumerasi implisit dalam menyelesaikan masalah Knapsack

Fakhry Asad Agusfrianto; Ramya Rachmawati

doi:10.26877/aks.v13i1.11782

Perbandingan Metode Branch and Bound dan Enumerasi implisit dalam menyelesaikan masalah Knapsack

Fakhry Asad Agusfrianto, Ramya Rachmawati

Abstract

Masalah knapsack merupakan masalah program bilangan bulat yang melibatkan satu kendala saja. Masalah knapsack umumnya diilustrasikan dengan suatu tas dan barang. Masalah yang akan kita selesaikan dalam masalah knapsack adalah memaksimumkan harga barang dengan kapasitas tertentu yang dapat dimuat oleh tas dengan kapasitas tertentu juga. Dalam menyelesaikan masalah knapsack, umumnya dapat dikerjakan secara langsung (penerkaan), menggunakan metode branch and bound, dan enumerasi implisit. Pada paper ini, akan dilakukan perbandingan penyelesaian masalah knapsack dengan metode branch and bound dan enumerasi implisit. Kita juga akan dapat melihat metode mana yang paling efektif untuk menyelesaikan suatu masalah knapsack.

Full Text:

PDF

References

Basriati, Sri. (2018). Integer Linear Programming Dengan Pendekatan Metode Cutting Plane Dan Branch And Bound Untuk Optimasi Produksi Tahu. Jurnal Sains Matematika dan Statistika, 4(2). 95 – 104.

Devita, Riri Nada & Wibawa, Aji Prasetya. (2020). Teknik Teknik Optimasi Knapsack Problem. Sains, Aplikasi, Komputasi dan Teknologi Informasi, 2(1). 35 – 40.

Hiller, F.S & Lieberman, G.J. (2015). Introduction to Operation Research : Tenth Edition. New York, USA : Mc Graw Hill Education.

Lageweg, B.J., Lenstra, J.K., & Rinnooy Kan, H.G. (1977). Job-Shop Scheduling by Implicit Enumeration. Management Science, 24(4). 441 – 450.

Lesmana, Nunung Indra. (2016). Penjadwalan Produksi Untuk Meminimalkan Waktu Produksi Dengan Menggunakan Metode Branch and Bound. Jurnal Teknik Industri, 17(1). 42 – 50.

Ligget, R.S. (1973). The Application of An Impicit Enumeration Algorithm To The School Desegregation Problem. Management Science, 20(2). 159 – 168.

Mazda, Chadziqatun Najilatil & Kurniawati, Dwi Agustina. (2020). Branch and Bound Method to Overcome Delay Delivery Order in Flow Shop Scheduling Problem. Presented at International Conference on Industrial and Manufacturing Engineering, Medan, North Sumatra, Indonesia, September 4, 2020.

Rachmawati, Dian & Candra, Ade. (2013). Implementasi Algoritma Greedy Untuk Menyelesaikan Masalah Knapsack Problem. Jurnal SAINTIKOM, 12(3). 185 – 192.

Sabaruddin, Raja. (2016). Solusi Optimum Minmax 0/1 Knapsack Menggunakan Algoritma Greedy. Jurnal Evolusi, 4(2). 76 – 82.

Winston, W.L. (2004). Operation Research: Application and Algorithms. Belmont, USA: BROOCKS/COLE.

DOI: https://doi.org/10.26877/aks.v13i1.11782