Algoritma Heuristik Berbasis Pewarnaan Graf Untuk Masalah Bin Packing dengan Konflik

DWI ARUM MENTARI, Dr. Irwan Endrayanto A., S.Si., M.Sc.

2021 | Skripsi | S1 MATEMATIKA

Pada skripsi ini, akan dibahas Masalah Bin Packing dengan Konflik (BPK). BPK adalah masalah penempatan sekumpulan barang dengan ukuran tertentu ke dalam bin (wadah) dengan kapasitas tertentu, dengan memperhatikan beberapa kendala, yaitu setiap item harus ditempatkan ke dalam bin, jumlah total ukuran item yang ditempatkan di setiap bin tidak melebihi kapasitas bin, dan ada beberapa barang yang berkonflik yang tidak boleh ditempatkan dalam bin yang sama. Tujuan dari BPK adalah meminimumkan jumlah bin yang digunakan untuk mengemas item-item yang ada. Pada skripsi ini, BPK akan dimodelkan menggunakan program linear bilangan bulat. Lebih lanjut, BPK akan diasosiasikan dengan graf konflik dan akan diselesaikan dengan algoritma heuristik berbasis pewarnaan graf. Konsep pewarnaan graf yang diadaptasi dalam algoritma ini adalah konsep pewarnaan titik graf. Selain itu, akan disajikan juga prosedur pencarian batas bawah dari BPK dengan menggunakan konsep klik terbesar graf dari graf konflik. Dari hasil yang diperoleh, algoritma heuristik ini dapat menghasilkan solusi yang baik (mendekati optimal) dari masalah BPK, yaitu berupa pengemasan item-item ke dalam bin yang tidak mengandung item yang berkonflik, serta batas bawah yang dihasilkan dapat menjamin solusi tersebut.

In this thesis, the Bin Packing Problem with Conflicts (BPC) will be studied. BPC is a problem of placing a set of items with different size into bins with a certain capacity, with several constraints, i.e. each item must be placed in a bin, the total number of items placed in each bin does not exceed the capacity of bin, and there are some conflicting items that should not be placed in the same bin. The purpose of BPC is to minimize the number of bins used to package existing items. In this thesis, BPC will be modeled using linear integer programming. Furthermore, BPC will be associated with conflict graphs and will be solved by a heuristic algorithm based on graph coloring. The concept of graph coloring adapted in this algorithm is the vertex coloring. In addition, the procedure finding the lower bound of BPC will also be presented using the concept of the maximum-clique of the conflict graph. The result shows that this heuristic algorithm can produce a good solution (near optimal) for BPC, that is packing items into bins that do not contain conflicting items, and the result of the lower bound can guarantee this solution.

Kata Kunci : Bin Packing, Heuristik, Konflik