PERBANDINGAN ALGORITMA BRANCH AND BOUND DAN GILMORE- GOMORY UNTUK OPTIMASI CUTTING - STOCK PROBLEM PADA INDUSTRI PEMOTONGAN KERTAS
Abstract
Permasalahan cutting stock adalah salah satu dari permasalahan optimasi
program linear yang pada dasarnya direduksi ke dalam permasalahan program
linear dengan nilai integer. Dengan kata lain, permasalahan cutting stock
merupakan permasalahan optimasi dalam integer linear programming (ILP).
Permasalahan ini banyak terjadi dalam berbagai aplikasi matematika di bidang
perindustrian seperti industri kertas, industri baja, kayu, dan fiber. Masalah cutting
stock dalam industri kertas adalah masalah yang terjadi ketika sebuah industri
kertas memiliki sejumlah gulungan kertas (stock roll), dengan lebar yang
bervariasi. Pemotongan gulungan kertas dilakukan sesuai dengan permintaan
konsumen. Dalam hal ini, diarahkan untuk memotong gulungan kertas yang
sisanya seminimal mungkin sesuai dengan permintaan.
Metode yang digunakan untuk menyelesesaikan permasalahan cutting
stock tersebut, diantaranya adalah metode Branch and Bound dan metode
Gilmore-Gomory. Oleh karena itu penulis tertarik untuk menerapkan metode
tersebut untuk menyelesaikan permasalahan cutting stock serta mencari nilai
minimum sisa pemotongan kertas. Kompleksitas waktu dari kedua metode
tersebut juga akan menjadi bahan pertimbangan ketika menentukan algoritma
mana yang lebih baik untuk diterapkan pada Cutting Stock Problem.
Pada penelitian ini dilakukan simulasi data permintaan untuk beberapa
ukuran kertas. Data tersebut kemudian diolah menggunakan algoritma Branch and
Bound dan Gilmore-Gomory dengan bantuan software matematika yaitu
MATLAB. Dari hasil penelitian dengan bantuan program menunjukkan: (1) Luas kertas sisa minimum yang dihasilkan menggunakan algoritma Branch and Bound
adalah sebesar 1069691.1 dengan jumlah kertas master yang dibutuhkan 7808
lembar dan waktu komputasi 0,541491 detik. (2) Luas kertas sisa minimum yang
dihasilkan menggunakan algoritma Branch and Bound adalah sebesar 595023,036
dengan jumlah kertas master yang dibutuhkan 7650 lembar dan waktu komputasi
0,3556874 detik.
Dari hasil diatas dapat disimpulkan bahwa algoritma Gilmore-Gomory
lebih optimal untuk mencari sisa pemotongan kertas yang minimum daripada
algoritma Branch and Bound. Serta waktu komputasi yang dibutuhkan juga lebih
efisien. Karena algoritma Gilmore-Gomory bersifat global dan memiliki beberapa
tahapan untuk melakukan pencarian solusinya berbeda dengan algoritma Branch
and Bound pencarian solusinya bersifat lokal