PENYELESAIAN PERMASALAHAN TRIM LOSS DENGAN MODEL INTEGER LINEAR PROGRAMMING DAN MIXED INTEGER LINEAR PROGRAMMING

PENYELESAIAN PERMASALAHAN TRIM LOSS DENGAN MODEL INTEGER LINEAR PROGRAMMING DAN MIXED INTEGER LINEAR PROGRAMMING Nama Mahasiswa NRP Jurusan Dosen Pembimbing

: Pradina Eka Wardani : 1206 100 024 : Matematika : Dra. Laksmi Prita Wardhani, M.Si

Abstrak Masalah trim loss merupakan masalah kerugian yang timbul dari hasil proses pemotongan yang tidak optimal. Kerugian ini ditimbulkan oleh beberapa faktor, salah satu diantaranya adalah peletakan pola pemotongan yang kurang tepat sehingga mengakibatkan ketidakefisienan penggunaan bahan baku. Pada Tugas Akhir ini, masalah trim loss ditinjau berdasarkan trim loss dari proses pemotongan kayu. Model permasalahan trim loss yang dikembangkan merupakan model dalam bentuk Integer Non Linear Programming (INLP) sebab terdapat beberapa kendala dari model yang bersifat bilinier. Untuk mendapatkan hasil penyelesaian dari model tersebut, maka model tersebut dilinierkan ke dalam bentuk Integer Linear Programming (ILP) dan Mixed Integer Linear Programming (MILP). Proses penyelesaian permasalahan dilakukan dalam dua tahapan. Pertama, model permasalahan trim loss bentuk ILP dan MILP diolah dengan program simulasi sehingga menjadi bentuk model yang siap untuk tahapan selanjutnya. Kedua, model permasalahan trim loss hasil program simulasi diselesaikan dengan menggunakan LINGO 8 sehingga diketahui penyelesaian permasalahannya. Dari beberapa contoh kasus yang dilakukan, dapat ditunjukkan bahwa model permasalahan trim loss bentuk ILP lebih efisien untuk penyelesaian permasalahan jika dibandingkan dengan model permasalahan trim loss bentuk MILP. Kata kunci : trim loss, Integer Linear Programming (ILP), Integer Non Linear Programming (INLP), Mixed Integer Linear Programming (MILP) baku juga menimbulkan biaya kerugian bahan baku yang cukup besar terutama untuk bahan baku yang mahal, sehingga biaya produksi yang diharapkan seminimal mungkin malah menjadi besar. Permasalahan trim loss dalam Tugas Akhir ini dibentuk berdasarkan data proses pemotongan kayu yang diperoleh dari PT. Sinarindo Megantara serta model permasalahan trim loss yang dikembangkan oleh Harjunkoski (1996). Pembahasan trim loss dalam Tugas Akhir ini dilakukan dengan mengabaikan faktor-faktor eksternal seperti kerusakan mesin, tetapi hanya menitikberatkan pada pengaturan pola pemotongan yang optimal. Permasalahan trim loss dibentuk dalam bentuk integer non-linear programming (INLP). Permasalahan ini juga dapat dituliskan dan diperluas dalam bentuk linier sehingga dapat dibentuk sebagai permasalahan integer linear programming (ILP) atau mixed integer linear programming (MILP). Adapun tujuan dari Tugas Akhir ini adalah : 1. Mendapatkan model permasalahan trim loss dalam bentuk INLP.

1.

Pendahuluan Pada proses produksi, khususnya pada proses pemotongan material, sering dihasilkan sisa potongan material yang tidak dapat digunakan lagi. Hal ini tidak dapat dihindari karena bahan baku yang diterima dari pemasok tidak selalu dapat memenuhi ukuran dimensi yang sesuai dengan yang diharapkan pada setiap proses. Masalah ini dikenal sebagai masalah trim loss yang berarti kerugian yang timbul dari hasil proses pemotongan yang tidak optimal. Kerugian ini ditimbulkan oleh beberapa faktor, salah satu diantaranya adalah peletakan pola pemotongan yang kurang tepat sehingga mengakibatkan ketidakefisienan penggunaan bahan baku. Sebenarnya permasalahan trim loss tidak selalu dihadapi oleh setiap industri. Industri yang menggunakan bahan baku yang bisa didaur ulang seperti industri logam dan sebagainya mungkin tidak akan menjadikan masalah trim loss sebagai kendala utama, namun tidak demikian halnya dengan industri yang menggunakan bahan baku yang selain tidak dapat didaur ulang juga mahal dan sukar diperoleh seperti kertas, plastik dan kayu. Masalah trim loss selain mengakibatkan adanya pemborosan dalam penggunaan bahan

1

2.

Memperoleh model matematis permasalahan trim loss dalam bentuk ILP dan MILP. Mendapatkan hasil penyelesaian permasalahan trim loss, baik dengan menggunakan ILP maupun MILP. Mengetahui hasil penyelesaian permasalahan trim loss yang lebih efisien antara model ILP dan MILP.

3.

4.

Q R Bq Nq Br,min Br,max Zr,max

2.

Trim Loss Tujuan utama CSP adalah untuk meminimalkan trim loss yang biasanya didefinisikan sebagai peminimalan jumlah pola pemotongan. Tetapi pada umumnya trim loss pada setiap pemotongan bisa diformulasikan sebagai: " trim loss = panjang objek - total panjang pemotongan material" Formulasi di atas dapat diaplikasikan baik dalam metode CSP yang berorientasi item maupun berorientasi pola. Dalam kasus proses pemotongan tumpukan kertas (Westerlund, 1998), permasalahan trim loss bisa dikategorikan sebagai permasalahan non convex integer nonlinear programming. Adapun formulasinya adalah sebagai berikut :

mr yr cr f Z ∆q

3.

Proses Pemotongan Kayu Proses pemotongan kayu merupakan sebuah proses membagi potongan kayu yang besar (kayu baku) menjadi potongan-potongan kayu yang lebih kecil (kayu produk). Proses pemotongan kayu dilakukan melalui tiga tahapan yaitu: 1. Pemotongan tebal kayu, kayu baku dipotong pada sisi tebal dengan ukuran yang sesuai dengan tebal kayu produk. 2. Pemotongan panjang kayu, setiap hasil pemotongan tebal kayu baku dipotong pada sisi panjang dengan ukuran yang sesuai dengan panjang kayu produk. 3. Pemotongan lebar kayu, setiap hasil pemotongan panjang kayu baku dipotong pada sisi lebar dengan ukuran yang sesuai dengan lebar kayu produk.

𝑄

𝑅

min

𝑛 𝑞,𝑟 ,𝑚 𝑟 ,𝑦𝑟

nq,r

𝑐𝑟 𝑚𝑟 𝐵𝑟,𝑚𝑎𝑥 − 𝑓 𝑟=1

𝑛𝑞,𝑟 𝐵𝑞

+ 𝑐𝑟 𝑦𝑟

(2.1)

𝑞=1

Dengan kendala : 𝑄

𝑛𝑞,𝑟 𝐵𝑞 − 𝐵𝑟,𝑚𝑎𝑥 ≤ 0

(2.2)

𝑞=1 Q

− Q

nq,r Bq + Br,min ≤ 0

(2.3)

q=1

nq,r − Zr,max ≤ 0 q=1

(2.4)

mr − Z yr ≤ 0 r = 1,2,3, … , R

(2.5)

Nq −

nq,r mr ≤ 0

(2.6)

nq,r mr − Nq − ∆q ≤ 0

(2.7)

: banyak tipe lembaran kertas q= 1,2,3, … , Q : banyak pola pemotongan r= 1,2,3, … , R : lebar dari lembaran kertas ke-q : banyak lembaran kertas ke-q : lebar minimum pola pemotongan ke-r : lebar maksimum pola pemotongan ke-r : maksimum banyaknya pisau untuk pola pemotongan ke-r : jumlah lembaran kertas ke-q untuk pola pemotongan ke-r : banyaknya pola pemotongan ke-r : pola pemotongan ke-r yang akan digunakan atau tidak : koefisien biaya : bobot produk yang disesuaikan dengan permintaan : bilangan positif : banyak produk tambahan ke-q yang dapat dijual

R

R

r=1

(a)

r=1

q = 1,2,3, … , Q nq,r , mr ∈ Z+ yr ∈ {0,1}

(b)

dimana,

2

dengan kendala: 𝐼

𝑑𝑖 −

𝑚𝑖𝑗 𝑁𝑗 ≤ 0 , 𝑖 = 1, … , 𝐼

(5.2)

𝑗=1

𝑁𝑗 − 𝑝 ≤ 0 , 𝑗 = 1, … , 𝐽 𝑁𝑗 ∈ ℤ+

(c) Gambar 3.1 Gambar proses pemotongan kayu. (a) Pemotongan tebal kayu, (b) Pemotongan panjang kayu, dan (c) Pemotongan lebar kayu

6.

Model MILP Permasalahan Trim Loss Sama seperti sebelumnya, untuk mendapatkan model MILP permasalahan trim loss juga dilakukan proses pelinieran. Cara yang digunakan untuk pelinieran adalah mengganti variabel-variabel integer yang menyebabkan model permasalahan trim loss berbentuk nonlinier. Variabel-variabel integer yang dimaksud yaitu variabel 𝑁𝑗 dan 𝑚𝑖𝑗 . Dalam pelinieran, variabel 𝑁𝑗 akan digantikan dengan variabel biner 𝛽𝑗,𝑘 sedangkan

4.

Model INLP Permasalahan Trim Loss Model yang digunakan sebagai landasan dalam pengerjaan Tugas Akhir ini merupakan model optimasi trim loss yang dikembangkan oleh Westerlund (1996). Dalam jurnal ilmiahnya, model optimasi trim loss tersebut digunakan dalam pemotongan kertas (persamaan 2.1 − (2.7)). Permasalahan pemotongan kayu dengan tujuan untuk meminimumkan trim loss dari hasil pemotongan kayu, dapat ditulis sebagai berikut: 𝐽

𝑁 𝑗 ,𝑛 𝑖𝑗

perkalian antara variabel integer 𝑚𝑖𝑗 dengan variable biner 𝛽𝑗,𝑘 akan digantikan oleh variabel 𝑆𝑖,𝑗,𝑘 . Rumus yang digunakan adalah:

𝐼

min

𝑁𝑗 𝑉 − 𝑗 =1

𝑣𝑖 𝑚𝑖𝑗

𝐾

(4.1)

𝑘=1

dengan kendala:

𝛽𝑗,𝑘 𝑚𝑖,𝑗 = 𝑆𝑖,𝑗,𝑘 Model MILP permasalahan trim loss dapat ditulis sebagai berikut:

𝐼

𝑖=1

(4.2)

𝐼

𝐽

𝑑𝑖 −

𝑚𝑖𝑗 𝑁𝑗 ≤ 0 , 𝑖 = 1, … , 𝐼

𝛽𝑗,𝑘 ,𝑆𝑖,𝑗,𝑘

𝑖=1

𝑘=1

Model ILP Permasalahan Trim Loss Untuk mendapatkan model ILP permasalahan trim loss maka dilakukan proses pelinieran pada model INLP permasalahan trim loss. Pelinieran dilakukan dengan menggunakan teknik enumerasi. Teknik enumerasi adalah mengasumsikan salah satu variabel yang menyebabkan munculnya sifat bilinier menjadi sebuah parameter. Variabel yang dijadikan parameter adalah variabel 𝑚𝑖𝑗 . Model ILP permasalahan trim loss dapat ditulis sebagai berikut:

𝐾

(6.1)

𝑖=1 𝑘=1

𝑣𝑖 𝑚𝑖𝑗

(6.2)

𝐾

2𝑘−1 𝑆𝑖,𝑗,𝑘 ≤ 0 , 𝑖 = 1, … , 𝐼

(6.3)

𝑗=1 𝑘=1

2𝑘−1 𝛽𝑗,𝑘 − 𝑝 ≤ 0 , 𝑗 = 1, … , 𝐽

(6.4)

𝑘=1

𝐼

𝑁𝑗 𝑉 −

𝐼

𝑑𝑖 −

5.

𝑗 =1

𝑗=1

2𝑘−1 𝑆𝑖,𝑗,𝑘 𝑣𝑖

𝛽𝑗,𝑘 𝑉 −

𝑣𝑖 𝑚𝑖,𝑗 − 𝑉 ≤ 0

𝑚𝑖𝑗 , 𝑁𝑗 ∈ ℤ+

𝑁𝑗

2

𝐾

𝐼

(4.4)

𝑗 =1

min

𝐼 𝑘−1

dengan kendala:

𝑁𝑗 − 𝑝 ≤ 0

𝐽

𝐾

min

(4.3)

𝑗 =1

𝐽

2𝑘−1 𝛽𝑗,𝑘 , 𝑗 = 1, … , 𝐽

𝑁𝑗 =

𝑖=1

𝑣𝑖 𝑚𝑖,𝑗 − 𝑉 ≤ 0

(5.3)

(5.1)

𝑖=1

3

𝑆𝑖,𝑗,𝑘 − 𝑚𝑖𝑗 ≤ 0 𝑖 = 1, … , 𝐼 , 𝑗 = 1, … , 𝐽 , 𝑘 = 1, … , 𝐾 −𝑆𝑖,𝑗,𝑘 + 𝑚𝑖𝑗 − 𝐿𝑖,𝑗 (1 − 𝛽𝑗,𝑘 ) ≤ 0 𝑖 = 1, … , 𝐼 , 𝑗 = 1, … , 𝐽 , 𝑘 = 1, … , 𝐾 𝑆𝑖,𝑗,𝑘 − 𝐿𝑖,𝑗 𝛽𝑗,𝑘 ≤ 0

(6.5)

𝑆𝑖,𝑗,𝑘 − 𝐿𝑖,𝑗 𝛽𝑗,𝑘 ≤ 0 𝑖 = 1, … , 𝐼 , 𝑗 = 1, … , 𝐽 , 𝑘 = 1, … , 𝐾 𝛽𝑗,𝑘 ∈ 0,1 , 𝑆𝑖,𝑗,𝑘 ∈ ℝ+

(6.8)

(6.6) (6.7)

G12 E7

7.

Penyelesaian Model Permasalahan Untuk mendapatkan hasil penyelesaian dari model permasalahan maka diperlukan dua tahapan. Tahapan yang pertama adalah pengolahan data dengan menggunakan program simulasi. Sedangkan tahapan yang kedua adalah penyelesaian akhir dengan menggunakan software LINGO 8. Program simulasi dibuat untuk menjabarkan model ILP dan MILP dari permasalahan trim loss sesuai dengan data yang menjadi masukan bagi program.

18 18

610 610

35 100

50 50

Hasil dari setiap uji coba adalah sebagai berikut: Tabel 8.2 Hasil penyelesaian kasus 1 Hasil Penyelesaian Uji Coba ILP MILP 8 3 data 2.58077 𝑥 10 2.58077 𝑥 108 5 data 2.01287 𝑥 108 2.01287 𝑥 108 7 data 2.43432 𝑥 108 2.43432 𝑥 108 Kasus 2 Pada kasus 2, ukuran dimensi kayu baku yang digunakan adalah tebal = 32 mm, panjang = 4200 mm, dan lebar = 140 mm. Sedangkan jumlah persediaan dari kayu baku tersebut adalah sebanyak 897 unit. Untuk ukuran dimensi dan jumlah permintaan kayu produk menggunakan data yang disajikan pada Tabel 8.1. Berdasarkan data pada Tabel 8.1, dilakukan tiga kali uji coba, yaitu uji coba dengan menggunakan tiga data permintaan (E10, G10, dan E7), lima data permintaan (E10, E12, G10, B4, dan E7), dan tujuh data permintaan. Hasil dari setiap uji coba adalah sebagai berikut:

Gambar 7.1 Program simulasi 8.

Tabel 8.3 Hasil penyelesaian kasus 2 Hasil Penyelesaian Uji Coba ILP MILP 7 3 data 6.0759 𝑥 10 6.0759 𝑥 107 8 5 data 1.03983 𝑥 10 1.03983 𝑥 108 7 data 1.1894 𝑥 108 1.1894 𝑥 108

Uji Coba dan Hasil

Kasus 1 Pada kasus 1, ukuran dimensi kayu baku yang digunakan adalah tebal = 32 mm, panjang = 4200 mm, dan lebar = 130 mm. Sedangkan jumlah persediaan dari kayu baku tersebut adalah sebanyak 398 unit. Untuk ukuran dimensi dan jumlah permintaan kayu produk disajikan pada Tabel 8.1. Berdasarkan data pada Tabel 8.1, dilakukan tiga kali uji coba, yaitu uji coba dengan menggunakan tiga data permintaan (E10, G10, dan E7), lima data permintaan (E10, E12, G10, B4, dan E7), dan tujuh data permintaan.

Kasus 3 Pada kasus 3, ukuran dimensi kayu baku yang digunakan adalah tebal = 32 mm, panjang = 4200 mm, dan lebar = 160 mm. Sedangkan jumlah persediaan dari kayu baku tersebut adalah sebanyak 322 unit. Untuk ukuran dimensi dan jumlah permintaan kayu produk menggunakan data yang disajikan pada Tabel 8.1. Berdasarkan data pada Tabel 8.1, dilakukan tiga kali uji coba, yaitu uji coba dengan menggunakan tiga data permintaan (E10, G10, dan E7), lima data permintaan (E10, E12, G10, B4, dan E7), dan tujuh data permintaan. Hasil dari setiap uji coba adalah sebagai berikut:

Tabel 8.1 Data kayu produk permintaan No. Komponen E10 E12 G10 G11 B4

Tebal (mm) 12 12 18 18 18

Panjang (mm) 530 610 455 455 530

Lebar (mm) 35 62 35 50 43

Demand (unit) 150 50 100 150 50

4

Tabel 8.4 Hasil penyelesaian kasus 3 Hasil Penyelesaian Uji Coba ILP MILP 3 data 1.81710 𝑥 108 1.81710 𝑥 108 5 data 1.77339 𝑥 108 1.77339 𝑥 108 7 data 1.49284 𝑥 108 1.49284 𝑥 108

Iterasi Waktu

Pembanding Fungsi objektif (𝑚𝑚3 ) Variabel Fungsi pembatas Percabangan Iterasi Waktu

Pembandingan Hasil Penyelesaian Pembandingan hasil penyelesaian dari masing-masing uji coba pada kasus 1, 2, dan 3 disajikan dalam Tabel 9.1 s.d Tabel 9.9 berikut ini.

Fungsi objektif (𝑚𝑚3 ) Variabel Fungsi pembatas Percabangan Iterasi Waktu

Model MILP

2.58077 𝑥 108 4 14 0 2 00:00:00

2.58077 𝑥 108 365 1358 43 1455 00:00:00



Model ILP

MILP

6.0759 𝑥 107 6 14 109 161 00:00:00

6.0759 𝑥 107 546 2030 318 4160 00:00:01



Model ILP

MILP

1.81710 𝑥 108 4 14 120 181 00:00:00

1.81710 𝑥 108 364 1358 899 8821 00:00:02


Fungsi objektif (𝑚𝑚3 ) Variabel Fungsi pembatas Percabangan

Model ILP

MILP

2.01287 𝑥 108 14 26 0

2.01287 𝑥 108 2450 9434 460

Model ILP

MILP

1.77339 𝑥 108 20 26 53 111 00:00:00

1.77339 𝑥 108 3500 13466 25746 195324 00:06:51

Model ILP

MILP

2.43432 𝑥 108 23 32 0 13 00:00:00

2.43432 𝑥 108 5704 22112 11473 230523 00:05:04

Model ILP

MILP

1.1894 𝑥 108 30 32 176 470 00:00:00

1.1894 𝑥 108 7440 28832 10120 77759 00:06:04

Tabel 9.9 Pembandingan kasus 3 dengan 7 data permintaan

Tabel 9.4 Pembandingan kasus 1 dengan 5 data permintaan Pembanding

1.03983 𝑥 108 3500 13466 6213 143477 00:01:35



MILP

1.03983 𝑥 108 20 26 75 186 00:00:00



Model ILP


Tabel 9.1 Pembandingan kasus 1 dengan 3 data permintaan ILP

5476 00:00:03


9.

Pembanding

21 00:00:00

Pembanding Fungsi objektif (𝑚𝑚3 ) Variabel Fungsi pembatas Percabangan

5

Model ILP

MILP

1.49284 𝑥 108 31 32 124

1.49284 𝑥 108 7688 29792 5675

Iterasi Waktu

459 00:00:00

4.

65698 00:02:07

Berdasarkan pembandingan diperoleh beberapa kesimpulan sebagai berikut: 1. Fungsi objektif diperoleh nilai yang sama sebab kedua model memiliki permasalahan yang sama hanya saja terdapat perbedaan pada penulisan fungsi objektifnya. 2. Variabel diperoleh nilai yang berbeda sebab variabel pada model ILP (𝑁𝑗 ) diperluas menjadi variabel biner (𝛽𝑗,𝑘 ) pada model MILP. 3. Fungsi pembatas diperoleh nilai yang berbeda sebab fungsi pembatas pada model MILP memiliki jumlah yang lebih banyak daripada model ILP. 4. Percabangan diperoleh nilai yang berbeda sebab variabel yang digunakan pada model MILP lebih banyak daripada model ILP. 5. Iterasi diperoleh nilai yang berbeda sebab jumlah percabangan yang digunakan pada model MILP lebih banyak daripada model ILP. 6. Waktu diperoleh nilai yang berbeda sebab jumlah iterasi yang digunakan pada model MILP lebih banyak daripada model ILP.

Hasil pembandingan menunjukkan bahwa model ILP lebih efisien untuk penyelesaian permasalahan trim loss daripada model MILP dalam segi jumlah variabel, fungsi pembatas, percabangan, iterasi, dan lama waktu.

11. Daftar Pustaka [1]. Javanshir, H. dan Shadalooee, M., April 2007. "The trim loss concentration in onedimensional cutting stock problem (1DCSP) by defining a virtual cost". Journal of Industrial Engineering Internasional 2007, Vol. 3, No. 4, 51-58 [2]. Karelahti, J. 25 Nov 2002. ”Solving the Cutting Stock Problem in the Steel Industry”. Master’s Thesis Submitted in Partial Fulfillment of the Requirements for the Degree of Master of Science in Technology. [3]. Siringoringo, Hotniar. 2005. Seri Teknik Riset Operasional. Pemrograman Linear. Penerbit Graha Ilmu. Yogyakarta. [4]. Lasserre, J. B. 2009. Linear and Integer Programming vs Linear Integration and Counting. Springer Science + Business Media, LLC. [5]. Westerlund, T., Isaksson, J., dan Harjunkoski, I. 24 Okt 1996. "Solving a two-dimentional trim-loss problem with MILP". European Journal of Operation Research 104 (1998) 572-581. [6]. Westerlund, T., Isaksson, J., Harjunkoski, I., dan Skrifvars, H. 1996. "Different Formulations for Solving Trim Loss Problems in A Paper-Converting Mill with ILP". Computers chem. Engng Vol. 20, Suppl., pp. S121-S126. [7]. Williams, H. P. 2009. Logic and Integer Programming. Springer Science + Business Media, LLC.

10. Kesimpulan 1. Model permasalahan trim loss dalam bentuk INLP adalah persamaan (4.1) – (4.4). 2. Model permasalahan trim loss dalam bentuk ILP diperoleh dari hasil pelinieran model permasalahan trim loss bentuk INLP dengan menggunakan teknik enumerasi, sedangkan model penyelesaian permasalahan trim loss dalam MILP diperoleh dari hasil pelinieran model permasalahan trim loss bentuk INLP dengan cara mengganti variabel 𝑁𝑗 dan 𝑚𝑖,𝑗 . Model ILP ditulis pada persamaan (5.1) – (5.3). Sedangkan model MILP ditulis pada persamaan (6.1) – (6.8). 3. Penyelesaian permasalahan trim loss dilakukan dalam dua tahapan. Tahapan pertama adalah tahap pengolahan data dengan menggunakan program simulasi. Tahapan kedua merupakan penyelesaian akhir, yaitu hasil yang diperoleh dari program simulasi dijadikan sebagai input dan diselesaikan dengan menggunakan LINGO 8.

6

PENYELESAIAN PERMASALAHAN TRIM LOSS DENGAN MODEL INTEGER LINEAR PROGRAMMING DAN MIXED INTEGER LINEAR PROGRAMMING

Recommend Documents