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