Pattern Generation Untuk Cutting Stock Problem Tiga Dimensi
Abstract
Cutting Stock Problem (CSP) adalah permasalahan dalam program linier
yang bertujuan untuk menentukan pola pemotongan bahan baku agar hasil yang
diperoleh optimal namun dengan cut loss seminimum mungkin. Bahan baku
dipotong menjadi potongan-potongan yang lebih kecil sesuai ukuran yang diminta
(item). Potongan-potongan tersebut harus memenuhi banyaknya jumlah permintaan
konsumen. Proses pemotongan CSP dapat dilakukan secara guillotine dan non guillotine. Guillotine adalah pemotongan yang dilakukan dengan memotong dari
salah satu sisi bahan baku hingga sisi yang berseberangan, sedangkan pemotongan
non-guillotine tidak. Pemotongan yang hanya memperhatikan satu sisi dari bahan
baku disebut CSP satu dimensi, sedangkan jika kedua sisi bahan baku diperhatikan
untuk dipotong maka disebut CSP dua dimensi.
Kasus CSP tiga dimensi masih jarang dibahas dalam literatur jika
dibandingkan dengan penelitian tentang permasalahan pemotongan satu dimensi
(1DCSP) dan permasalahan pemotongan dua dimensi (2DCSP) . Kami membahas
masalah pemotongan CSP tiga dimensi dengan mengilustrasikan suatu bahan baku
yang berupa balok besar dipotong menjadi sejumlah potongan balok kecil, dengan
ukuran dan permintaan tertentu. Pattern Generation (PG) adalah algoritma yang
telah digunakan untuk menentukan pola pemotongan dalam masalah 1DCSP dan
2DCSP. PG menentukan pola pemotongan dengan memotong bahan baku dari item
yang memiliki panjang atau lebar terbesar. Sisa dari pemotongan awal dipotong
kembali untuk ukuran item selanjutnya sehingga diperoleh pola pemotongan yang
menunjukkan jumlah dari masing-masing item.
Penelitian ini melakukan modifikasi algoritma PG yang telah digunakan
untuk 1DCSP dan 2DCSP agar dapat digunakan dalam masalah CSP tiga dimensi,
serta dapat pula menentukan pola pemotongan dengan cut loss seminimum
mungkin. Bahan baku yang berupa balok besar dipotong berdasarkan sisi panjang,
lebar, dan tinggi dari setiap ukuran item yang diminta. Banyaknya pemotongan
yang dilakukan pada tahap awal menghasilkan pola-pola untuk pemotongan setiap
item, namun ini belum bisa menjadikan pola tersebut optimal karena masih ada cut
loss hasil pemotongan berdasarkan panjang, lebar, dan tinggi yang memungkinkan
dapat dipotong kembali.
Cut loss dari pemotongan setiap sisi tersebut dipotong kembali agar dapat
meminimumkan sisa. Untuk masalah tiga dimensi dilakukan pemotongan dengan
memperbolehkan rotasi orthogonal pada item. Dengan mengizinkan item diputar,
maka dimensinya memiliki enam permutasi. Sehingga cut loss dari setiap
pemotongan akan tetap pada posisi awal, namun hanya item yang dilakukan
perputaran sebanyak enam kali. Ketika semua perputaran telah dilakukan, maka
pola pada pemotongan awal diperbarui dengan menambahkan pola baru hasil dari
pemotongan cut loss berdasarkan panjang, lebar, dan tinggi. Dengan adanya
pemotongan kembali dari cut loss tersebut, maka volume cut loss juga harus
diperbarui.
Pada penelitian ini dilakukan ilustrasi untuk masalah CSP tiga dimensi yang
diselesaikan dengan algoritma PG yang telah dimodifikasi. Hasil perhitungan
dengan menggunakan algoritma PG untuk masalah tiga dimensi adalah diperoleh
261 pola pemotongan. Namun dari 261 pola tersebut ada pola-pola yang
menghasilkan jumlah item yang sama sehingga dengan mengabaikan pola-pola
kembar diperolah 90 pola pemotongan yang berbeda. Untuk mendapatkan cut loss
yang diperoleh minimum, maka pola pemotongan yang disarankan adalah pola ke
5 yang dipotong sebanyak tiga kali. Algoritma PG untuk masalah tiga dimensi
memberikan semua pola-pola pemotongan yang dapat dilakukan namun hasil yang
diperoleh tidak efisien karena dari semua pola yang dihasilkan terdapat pola-pola
yang sama walau dengan perputaran item yang berbeda. The Cutting Stock Problem (CSP) is a problem in a linear program that aims
to determine the cutting pattern of raw materials so that the results obtained are
optimal but with a minimum cut loss. The raw material is cut into smaller pieces
according to the requested size (item). The pieces must meet a large number of
consumer demands. CSP cutting process can be done by guillotine and non guillotine. Guillotine cutting is done by cutting from one side of the raw material to
the opposite side, while non-guillotine cutting does not. Cutting that only pays
attention to one side of the raw material is called one-dimensional CSP, whereas if
both sides of the raw material are considered for cutting, it is called two dimensional CSP.
The case of three-dimensional CSP is still rarely discussed in the literature
compared to research on the one-dimensional cutting stock problem (1DCSP) and
two-dimensional cutting stock problem (2DCSP). We discuss the problem of three dimensional CSP cutting by illustrating a raw material in the form of a large block
cut into several small block pieces, with certain sizes and requests. Pattern
Generation (PG) is an algorithm used to determine the cutting pattern in 1DCSP
and 2DCSP. PG determines the cutting pattern by cutting the raw material from the
item that has the greatest length or width. The remainder of the initial cut is cut back
for the next item size so that a cutting pattern is obtained that shows the number of
each item.
This study modifies the PG algorithm that has been used for 1DCSP and
2DCSP so that it can be used in three-dimensional CSP problems, and can also
determine the cutting pattern with the minimum cut loss. Raw materials in the form
of large blocks are cut based on the length, width, and height of each item size
requested. The number of cuts made in the early stages produces patterns for cutting
each item, but this has not been able to make the pattern optimal because there is
still a cut loss resulting from cutting based on length, width, and height that allows
it to be cut again.
Cut loss from cutting each side is cut back to minimize the rest. For three dimensional problems, cuts are made to allow orthogonal rotation of the item. By
allowing the item to be rotated, the dimensions have six permutations. So the cut
loss of each cut will remain at the initial position, but only for items that are rotated
six times. When all rotations have been made, the pattern on the initial cut is
updated by adding a new pattern resulting from the cut loss cut based on length,
width, and height. With the cut back from the cut loss, the cut loss volume must
also be updated.
In this study, an illustration for a three-dimensional CSP problem is carried
out which is solved by a modified PG algorithm. The results of calculations using
the PG algorithm for three-dimensional problems are obtained in 261 cutting
patterns. However, from the 261 patterns, there are patterns that produce the same
number of items so by ignoring the twin patterns, 90 different cutting patterns are
obtained. To get the minimum cut loss, the recommended cutting pattern is the 5th
pattern which is cut three times. The PG algorithm for three-dimensional problems
provides all the cutting patterns that can be done but the results obtained are not
efficient because all the patterns produced there are the same patterns even with
different item rotations.