Metode Non-dominated Sorting pada Algoritma Genetika Multi Objektif dan Multi Solusi untuk Bin Packing Problem

MUHAMMAD BINTANG BAHY, Aina Musdholifah, S.Kom, M.Kom, Ph.D.

2021 | Skripsi | S1 ILMU KOMPUTER

Permasalahan bin packing adalah sebuah permasalahan di mana barang dengan volume dan dimensi berbeda dimasukkan ke dalam sebuah wadah sehingga volume barang yang dimasukkan maksimal. Permasalahan bin packing multi objektif adalah permasalahan yang lebih umum ditemukan di kehidupan sehari-hari, karena yang diperhatikan dalam pengepakan biasanya tidak hanya volume. Pada penelitian ini diajukan sebuah algoritma genetika multi objektif untuk menyelesaikan permasalahan bin packing multi objektif. Algoritma genetika yang diajukan menggunakan metode non-dominated sorting dan crowding distance untuk mendapatkan solusi yang terbaik untuk tiap objektifnya dan menghindari adanya bias. Algoritma kemudian diuji dengan beberapa kelas uji yang menyatakan kombinasi ukuran barang dan wadah yang berbeda. Dari hasil pengujian yang dilakukan didapatkan bahwa algoritma yang diajukan dapat menemukan beberapa solusi yang merupakan kandidat solusi terbaik untuk tiap objektif. Didapatkan juga bagaimana korelasi tiap objektif pada populasi.

The bin packing problem is a problem where goods with different volumes and dimensions are put into a container so that the volume of goods inserted is maximized. The problem of multi-objective bin packing is a problem that is more commonly found in everyday life, because what is considered in packing is usually not only volume. In this research, a multi-objective genetic algorithm is proposed to solve the multi-objective bin packing problem. The proposed genetic algorithm uses non-dominated sorting and crowding distance methods to get the best solution for each objective and to avoid bias. The algorithm is then tested with several test classes that represent different combinations of item and container sizes. From the results of the tests carried out, it was found that the proposed algorithm can find several solutions which are the best candidate solutions for each objective. Also found how the correlation of each objective in the population.

Kata Kunci : Algoritma genetika, bin packing problem, multi objektif, multi solusi, non-dominated sorting