BAB II LANDASAN TEORI
2.1. Deskripsi Cutting dan Packing Skripsi ini membahas masalah stock cutting, yaitu satu atau banyak potongan besar disebut material (bin, bins) dipetakan dan kemudian dipotong-potong menjadi bagian yang lebih kecil. Dalam landasan teori ini istilah bin packing akan dibahas juga. Alasannya adalah masalah cutting dan packing secara esensial mempunyai struktur logika yang sama. Keduanya mencari hasil yang efisien dari ruang atau objek yang lebih besar yang harus dimasukkan banyak benda yang berlainan ukuran atau pun potongan-potongan yang lebih kecil. Keduanya merupakan keluarga dari natural combinatorial problems, yang banyak dijumpai dalam berbagai bidang seperti computer science, teknik industri, logistik, perindustrian, dan lain-lain. Dalam penerapan dalam dunia industri, masalah cutting dan packing berbeda, walaupun dalam lingkup matematika pun cutting problem dan packing problem sering disamakan. Dyckhoff dan Finke (1992) menterjemahkan dualitas dari masalah cutting dan packing. Masalah packing adalah objek yang lebih besar, kosong, dan harus diisi oleh benda yang lebih kecil. Sedangkan untuk cutting (CSP-Cutting Stock Problems), objek yang besar dibagi menjadi potongan-potongan. Satu, dua, atau tiga dimensi dari masalah cutting dan packing secara esensial mempunyai tujuan dan struktur batasan yang sama. Tidak boleh ada potongan atau benda yang menumpuk dalam satu ruang dan keseluruhan dari potongan harus merupakan
6
bagian dari keseluruhan objek (material bahan). Kedua hal ini adalah masalah utama dalam masalah cutting dan packing. Dyckhoff dan Finke (1992) mengklasifikasi masalah cutting dan packing menjadi lima karakteristik. Dimensi, yaitu jumlah minimum dimensi yang dibutuhkan untuk mendiskripsikan geometri untuk mendapat solusi yang memungkinkan. Batasan, yaitu ada tidaknya ketentuan dan batasan yang dipakai dalam menyelesaikan masalah. Karakteristik, yaitu karakteristik dari objek yang akan dihitung, baik material bahan atau pun karakteristik potongan. Pembatasan pola, yaitu kondisi dari batasan dan juga pengaturan potongan. Yang terakhir adalah objektif, yaitu cara yang dipakai untuk menghasilkan susunan yang berkualitas. Topologi dari masalah cutting dan packing oleh H.Dyckhoff pada Gambar 2.01. Masalah cutting dan packing banyak diminati oleh para peneliti dan praktisi karena penerapannya dalam dunia riil sangat banyak, seperti Puchinger dan Raidl (2005); Vanderbeck(2001); Vassiliadis(2005); Cui, Yang, Cheng, dan Song (2006).
7
Gambar 2.01 Fenomena Cutting dan Packing Sumber:G.Belov,2003,p.2
8
2.2. Klasifikasi Bentuk Salah satu jenis dari cutting stock problem (CSP) adalah two-dimensional cutting-stock problem (2DCSP). Jenis ini umumnya banyak dipakai untuk suatu kumpulan bahan yang akan dipotong dari bentuk rectangular besar yang ukurannya sudah ditetapkan, atau pun berasal dari gulungan bahan, dengan tujuan untuk meminimalkan total biaya, termasuk di dalamnya biaya bahan baku. Two-dimensional cutting-stock problem dapat diklasifikasikan menjadi pemotongan bentuk regular dan irregular (Gambar 2.03 dan Gambar 2.04). Bentuk irregular merupakan bentuk yang tidak beraturan; bahan dipotong dengan bentuk apapun seperti yang terjadi dalam industri baju, sepatu kulit, furnitur(bentuk khusus), mobil, dan bahkan industri pesawat terbang. Pemotongan bentuk regular berbentuk rectangular atau bentuk geometri lain banyak dipakai dalam industri pemotongan kertas, lembaran metal, dan industri kayu. Bentuk pemotongan regular rectangular dapat menggunakan teknik guillotine, yaitu memotong dari ujung ke ujung dari bentuk rectangle tersebut, atau pun dengan teknik non-guillotine. Pemotongan rectangular kemudian dapat diklasifikasikan menjadi pemotongan oriented, di mana panjang dari bentuk yang akan dipotong, disejajarkan paralel sesuai dengan panjang bahan utama (Cheng, 1994, p.291.305). Dengan kata lain dalam oriented tidak dilakukan perputaran (rotation) potongan sama sekali. Klasifikasi ini dapat diilustrasikan dalam Gambar 2.02.
9
Gambar 2.02 Klasifikasi 2DCSP Sumber:S.M.A.Suliman,2006,p.178
Gambar 2.03 Bentuk regular
Gambar 2.04 Bentuk irregular
10
Non-oriented guillotine
Oriented guillotine
Oriented nonguillotine
Non-oriented non-guillotine
Gambar 2.05 Guillotine dan non-guillotine serta oriented dan non-oriented Sumber:S.M.A.Suliman,2006,p.179
2.3. Tingkat (Stage) Pemotongan Dalam perkembangan algoritma untuk 2DCSP, muncul istilah “stage”. Stage dalam 2DCSP adalah berapa kali pemotongan horisontal dan vertikal harus dilakukan. Tiga jenis pola yang lazim digunakan sampai saat ini adalah 2-stage, 3stage, dan n-stage.
Pola 2-stage
Gambar 2.06 Pola 2-stage Sumber:A.A.Farley,1988,p.115 Pola ini hanya terjadi jika potongan yang diinginkan mempunyai ukuran tinggi yang sama. Disebut 2-stage (dua tingkat) karena dalam pola ini terjadi 2 kali tahap potong, pertama memotong horisontal, kedua memotong vertikal.
11
Pola 3-stage
Gambar 2.07 Pola 3-stage Sumber:A.A.Farley,1988,p.115 Pola ini adalah pola yang sering dipakai karena memudahkan peletakan dan memudahkan perhitungan. Potongan-potongan yang diinginkan dalam pola ini mempunyai ukuran yang bervariatif. Disebut 3-stage (tiga tingkat) karena dalam pola ini terjadi 3 kali tahap potong, pertama memotong horisontal, kedua vertikal, yang terakhir adalam memotong waste (sisa potong) yang terbentuk.
Pola n-stage
Gambar 2.08 Pola n-stage Sumber:A.A.Farley,1988,p.115
12
Pola ini adalah hasil dari algoritma yang kompleks, karena benar-benar memampatkan potongan sehingga diperoleh sisa potong yang minimal. Potonganpotongan yang diinginkan dalam pola ini mempunyai ukuran yang bervariatif juga. Disebut n-stage (n tingkat) karena kerumitan pemotongan dari pola yang terbentuk. Dalam kenyataannya, sering ada batasan atau permintaan khusus dalam tiap masalah yang terjadi. Dalam skripsi ini akan dibahas adalah pemotongan secara guillotine orthogonal, yaitu potongan-potongan berbentuk rectangular dan hanya dapat dipotong horisontal atau vertikal dari satu sisi ke sisi lain. Jika dalam industri pemotongan digunakan mesin, maka perlu diperhatikan jumlah stage dalam lembaran material. Dalam setiap stage, pemotongan horisontal dan vertikal dapat dilakukan, tetapi tidak secara bersamaan. Potongan yang sudah melalui satu stage tidak dapat dikembalikan ke stage sebelumnya. Kondisi ini membatasi pemotongan horisontal dan vertikal, dan tinggi maksimum dari tingkatan pemotongan dalam tiap lembar bahan baku. Contoh pada pola three-stage, di mana stage pertama hanya dapat memotong horisontal, stage kedua vertikal, dan stage terkahir horisontal lagi. Pola 3-stage ini banyak dipakai dalam industri kayu dan kaca.
2.4. Logika Dasar Pencetus pemodelan matematika untuk masalah 2DCSP adalah GilmoreGomory. Dalam artikelnya yang pertama (P.C.Gilmore dan R.E.Gomory,1961), Gilmore dan Gomory mencoba membahas dan menyelesaikan masalah 1DCSP (one-dimension cutting stock problem).
13
h(tinggi)
1 (satu) strip W (panjang)
Gambar 2.09 Gilmore-Gomory 1D Tahap 1 Sumber: P.C.Gilmore dan R.E.Gomory,1961,p.849-859 Dari suatu bentuk satu dimensi dipotong menjadi potongan-potongan sesuai ukuran yang diinginkan. Kemudian
Gilmore-Gomory
(P.C.Gilmore
dan
R.E.Gomory,1963)
mengembangkan menjadi bentuk dua dimensi. Bentuk satu dimensi seperti gambar di atas, setelah ditambah satu strip akan menjadi bentuk 2 dimensi
h(tinggi)
W (panjang) 2 (dua) strip
Gambar 2.10 Gilmore-Gomory 1D Tahap 2 Sumber: P.C.Gilmore dan R.E.Gomory,1961,p.849-859 Logika dasar untuk menyelesaikan masalah 2DCSP adalah mengurutkan sesuai tinggi masing-masing potongan secara decending. Kemudian dimasukkan potongan dengan tinggi paling besar ke kiri atas material, tinggi dari potongan pertama yang dimasukkan adalah menjadi tinggi strip pertama.
14
strip 1
Gambar 2.11 Gilmore Gomory 2D Tahap 1 Sumber: P.C.Gilmore dan R.E.Gomory,1963,p.863-888 Setelah potongan pertama dimasukkan segera diikuti oleh potongan berikutnya sesuai urutan tinggi strip 1
Gambar 2.12 Gilmore Gomory 2D Tahap 2 Sumber: P.C.Gilmore dan R.E.Gomory,1963,p.863-888 Apabila potongan berikut tidak muat dalam strip, tinggi potongan berikut menjadi tinggi strip baru. strip 1
strip 2
Gambar 2.13 Gilmore Gomory 2D Tahap 3 Sumber: P.C.Gilmore dan R.E.Gomory,1963,p.863-888
15
2.5. Perkembangan Teori Masalah 2DCS menjadi penting dan banyak aplikasinya terjadi dalam dunia industri secara nyata, seperti industri kaca, kertas, pemotongan kayu, dan juga furnitur. Satu kumpulan bentuk dua dimensi yang berbeda ukuran diberikan untuk dipotong dari lembaran-lembaran material bahan dasar yang mempunyai ukuran tetap. Tujuannya adalah untuk meminimalkan jumlah lembar material yang dipakai dan meminimalkan sisa. Variasi masalah untuk 2DCS sangat banyak. Maksudnya adalah satu macam masalah dengan pembatasan masing-masing tentu saja mempunyai variabel, pemodelan, algoritma, dan penyelesaian yang berbeda. Sebagai contoh, dalam industri kaca, potongan-potongan dapat di rotate. Sedangkan di industri kayu, pemotongan umumnya dilakukan tanpa melakukan rotate. Hal yang dititikberatkan dalam skripsi ini
Potongan-potongan rectangle
Material berbentuk finite rectangle Material atau bins yang mempunyai panjang dan lebar yang terbatas disebut finite bin.
Potongan oriented (non-rotateable) guillotine Hal-hal ini dilakukan untuk membatasi skripsi agar relevan dengan kasus yang dihadapi seperti yang dibahas dalam Bab 3. Pada subbab berikut akan dijelaskan berbagai perkembangan teori dari sudut
pandang matematis berdasarkan titik berat di atas.
16 2.6. Solusi Eksak Solusi eksak untuk 2DCSP dibahas oleh Martello (S.Martello and D.Vigo,1998,p.388-399). Metode ini menggunakan kombinasi dari algortima branch and bound dan algoritma heuristik untuk mendapatkan solusi eksak dari masalah 2DCS. Algoritma ini mengadopsi skema nested branching. Tree keputusan dibagi menjadi dua bagian, yaitu outer branch decision tree dan inner branch decision tree. 2.6.1. Outer Branch Decision Tree Dalam tree ini, dalam setiap decision-node potongan k akan dimasukkan ke dalam bin. Hasil dari tahap ini didapat dengan memperkirakan Lower Bound ‘L’ dari kejadian saat ini. Jika L < 1 maka tahap ini tidak memungkinkan, maka perulangan dilakukan. Setiap algoritma heuristik seperti Finite First Fit (FFF) atau Finite Best-Fit (FBF) diaplikasikan untuk kejadian tersebut. Ketika hasil yang memungkinkan tidak ditemukan, maka looping berlanjut ke Inner Branch Decision Tree 2.6.2. Inner Branch Decision Tree Hasil yang tidak memungkinkan dari Outer Branch Decision Tree akan dicek akan kemungkinan lainnya oleh Inner Branch Decision Tree. Jika hasilnya ‘ya’ maka proses pencarian akan kembali pada Outer Branch Decision Tree, jika tidak, dilakukan backtracking. Hasil penelitian dari Nagarajan (R.P. Nagarajan,2002,p.7) solusi eksak membutuhkan waktu proses yang sangat lama jika potongan-potongan yang akan disusun berjumlah banyak.
17 2.7. Teknik Heuristik Banyak algoritma heuristik yang ditemukan dan dikembangkan untuk memecahkan masalah 2DCSP (J.O.Berkey and P.Y.Wang, 1987, 423-429). Kebanyakan metode heuristik yang dipakai adalah metode konstraktif dan mengolah masalah dengan mengasumsikan bin-bin dengan kapasitas yang terbatas (finite). Setiap algoritma yang akan dibahas menggunakan pemisalan sekumpulan potongan rectangle P = {P1, P2, …, Pn} dimasukkan ke dalam bin-bin berbentuk rectangle B1, B2, …, Bm yang berdimensi terbatas. Semua algoritma yang dideskripsikan di bawah menggunakan level-oriented packing approach, di mana potongan-potongan yang berbentuk rectangular dimasukkan secara bottom-left (bawah-kiri) dari tiap level. Level pertama adalah bagian paling bawah dari sebuah bin. Level berikut dihitung dari tinggi maksimum dari semua potongan dalam level sebelumnya. Tinggi dari tiap level adalah jarak level tersebut dari dasar bin. Dalam bahasa sehari-hari istilah dimensi untuk bentuk rectangle adalah panjang dan lebar, tetapi dalam algoritma yang akan dideskripsikan di bawah menggunakan istilah yang berbeda. Dalam semua litelatur pembahasan 2DCP, ‘lebar’ mewakili panjang dalam bahasa sehari-hari, sedangkan ‘tinggi’ mewakili lebar. Penggunaan istilah ini sesuai dengan algoritma yang ditulis J.O.Berkey dan P.Y.Wang (J.O.Berkey and P.Y.Wang, 1987, 423-429) dan Nagarajan (R.P. Nagarajan,2002,p.7).
18 2.7.1. Pemodelan Matematika Fungsi objektif dari masalah ini adalah meminimalkan jumlah bin. Kendala umum dari tiap potongan adalah: 1.
tiap potong i
P = {1,…,n}
2.
tinggi dari tiap potong didefinisikan sebagai hi ≤ tinggi dari material H
3.
lebar dari tiap potong didefinisikan sebagai wi ≤ lebar dari material W
4.
h tidak boleh nol ataupun negatif, hi > 0
5.
w tidak boleh nol ataupun negatif, wi > 0
6.
H tidak boleh nol ataupun negatif, H > 0
7.
W tidak boleh nol ataupun negatif, W > 0
Pemodelan matematika yang paling relevan dengan batasan masalah adalah pemodelan yang dirumuskan oleh Jacob Puchinger (Puchinger, 2005). Pemodelan matematika untuk 2DCSP berdasarkan Puchinger adalah sebagai berikut: •
{0,1}, j = 1,…,n, i=j,…,n : Nilai 1 jika dan hanya jika i terdapat dalam stack j
•
{0,1}, k = 1,…,n, j=k,…,n : Nilai 1 jika dan hanya jika j terdapat dalam stripe k
•
{0,1}, l = 1,…,n, k=l,…,n Nilai 1 jika dan hanya jika k terdapat dalam bin l
19
Minimalkan
(1) = 1, i = 1, … ,n
Dengan = 0,
j
= 1,…,n-1,
=
> j | wi ≠ wj
, j = 1,…,n ≤
, k = 1,…,n-1
, k = 1,…,n ≤H
, l = 1,…,n-1
hi + hj > H
(3) (4)
, j = 1,…,n-1
≤W =
i
(2)
(5) (6) (7) (8)
{0,1}, j = 1,…,n, i=j,…,n
(9)
{0,1}, k = 1,…,n, j=k,…,n
(10)
{0,1}, l = 1,…,n, k=l,…,n
(11)
Tujuan fungsi 1 (1) adalah untuk meminimalkan jumlah bin yang dipakai. Bin l dipakai jika dan hanya jika
= 1. Fungsi (2) memastikan setiap item i
dipakai hanya 1 kali Prinsipnya, item-item yang ada dalam stack yang sama harus mempunyai lebar w yang identik (sama persis) dan mempunyai total h dari stack tersebut yang tidak melebihi H (3). Dalam inplementasinya, hanya perlu diperhatikan variabel
, dimana wi = wj dan hi + hj ≤ H. Di sini, bagaimanapun
juga variabel-variabel dibuat seperti ini semata-mata untuk kejelasan. Setiap stack j yang ada, sebagai contoh stack j mengandung item j dimana
= 1 artinya :
dimasukkan tepat hanya sekali ke dalam stripe k sesuai persamaan (4). Batasan (5) memastikan tinggi setiap stack j, yaitu total tinggi dari semua item yang terkandung dalam stack j tidak melebihi tinggi dari stripe k tempat stack tersebut, yang identik dengan tinggi item k. Batasan (4) dan (5) keduanya menyatakan
20 bahwa tidak ada item yang dimasukkan ke dalam stack yang tidak dipakai. Persamaan(6) menjamin bahwa lebar W dari bin tidak akan dilewati oleh semua stripe k dan tidak ada stack yang dimasukkan ke dalam stripe yang tidak terpakai ,= 0. Persamaan (7) memaksa setiap stripe k yang dipakai dimasukkan tepat dalam satu bin. Yang terakhir, persamaan (8), menjamin tinggi H setiap bin Kendala yang sesuai dengan batasan masalah diambil dari pemodelan di atas adalah: {0,1}, j = 1,…,n, i=j,…,n :
{0,1}, k = 1,…,n, j=k,…,n :
Minimalkan: Dengan kendala:
= 1,
i
= 1, … ,n
≤W
,
j
≤H
,
k
= 1,…,n-1 = 1,…,n-1
{0,1}, j = 1,…,n, i=j,…,n {0,1}, k = 1,…,n, j=k,…,n
2.7.2. Finite Next-Fit Heuristic (FNF) Dalam teknik next-fit yang asli, hanya satu bin yang ada dalam current-bin list. Ketika potongan berikut yang akan dimasukkan tidak termuat dalam satu bin dalam current-bin list maka bin tersebut akan dihilangkan dari daftar dan sebuah bin yang kosong ditambahkan. Bin yang baru menjadi bin yang sekarang.
21 Algoritma finite-next fit menggunakan metode ini dan pendekatan level oriented. Sebuah potongan diletakkan pada level saat ini dari bin saat ini apabila memungkinkan. Jika tidak, sebuah usaha akan dilakukan untuk membuat level baru dalam bin saat ini. Jika tinggi dari potongan kurang dari atau sama dengan tinggi bin dikurangi tinggi level saat ini, maka level saat ini ditutup dan potongan dimasukkan ke dalam level baru. Ketika potongan berikut tidak dapat dimasukkan ke dalam level baru di bin saat ini, maka dilakukan update pada current-bin list untuk membuat bin baru. Dalam Gambar 2.14, potongan P dengan panjang dan lebar P = {Pi} dengan n = 7 dan P1 = (5x6), P2 = (8x5), P3 = (5x4), P4 = (4x3), P5 = (9x3), P6= (1x2), P7 = (4x1). Dimensi dari bin yang dipakai adalah 10x10
Gambar 2.14 Finite Next-Fit Heuristic Sumber:J.OBerkey and P.Y.Wang,1987,p.424 Cara ini sudah dibuktikan mempunyai waktu proses yang paling cepat 0(n) dibanding heuristik lain, tetapi kualitas solusi sangat buruk. Teknik Finite Next-Fit Heuristic secara singkat adalah:
semua potongan diurutkan menurun sesuai tinggi.
potongan-potongan disusun dengan pendekatan bottom-left.
jika potongan tidak termuat maka bin ditutup dan bin baru dibuat.
22
pada setiap saat hanya ada satu bin dalam bin-list.
2.7.3. Finite First-Fit Heuristic (FFF) Dalam teknik first-fit, semua bin yang sudah dibuat disimpan dalam daftar current-bin. Algoritma ini dimulai dari bin pertama yang dibuat dan dicek setiap level dari dasar bin ke atas untuk melihat apakah potongan dapat dimasukkan ke tempat tersebut. Jika potongan tidak dapat dimasukkan ke dalam level manapun dalam bin ini, bin selanjutnya akan diperiksa atau membuat bin baru jika tidak ada lagi bin dalam daftar current-bin. Setiap potongan akan dimasukkan ke level paling bawah dari bin pertama di mana potongan tersebut dapat dimasukkan. Daftar current-bin memakai struktur data linked-list sehingga pencarian secara berurutan dapat dengan mudah dilakukan. Hasil dari pemisalan P sehingga digambarkan seperti di Gambar 2.15
Gambar 2.15 Finite First-Fit Heuristic Sumber:J.OBerkey and P.Y.Wang,1987,p.425 Cara ini adalah modifikasi dari Finite Next-Fit Heuristic. Waktu proses adalah 0(n²). Dalam teknik ini, semua bin yang dibuat disimpan dalam bin-list. Cara kerja Finite Next-Fit Heuristic secara singkat adalah:
23
semua potongan diurutkan menurun sesuai tinggi.
setiap potongan yang akan dimasukkan dicek mulai dari bin pertama yang dibuat, pengecekan tiap bin dari dasar sampai atas, mencari apakah masih ada ruang untuk potongan tersebut.
pengecekan dilakukan untuk setiap bin dalam bin-list.
teknik ini selesai jika semua potongan sudah dimasukkan. Jika tidak, lakukan pengecekan sampai bin-list habis. Potongan tersebut kemudian dimasukkan dalam bin baru.
2.7.4. Finite Bottom-Left Heuristic (FBL) Untuk masalah yang sederhana, FBS lebih lambat dari algoritma yang lain, tetapi dalam masalah yang besar algoritma ini efektif.
Gambar 2.16 Finite Bottom-Left Heuristic Sumber:J.OBerkey and P.Y.Wang,1987,p.426 Cara ini menggunakan metode yang sama, yaitu pendekatan bottom-left.
semua potongan diurutkan menurun sesuai tinggi.
sebuah potongan yang akan dimasukkan ke posisi paling bawah-kiri dari sebuah bin.
24
jika tidak ada ruang maka bin baru dibuat.
area yang tidak terpakai yang tertutup oleh potongan-potongan pada keempat sisinya disebut sub-hole dari sebuah bin. Pencarian tempat yang memungkinkan bagi sebuah potongan termasuk
dilakukan di sub-hole. Waktu yang terpakai untuk mencari di seluruh sub-hole, diperkirakan 0(n²). 2.7.5. Finite Best-Strip Heuristic (FBS) Algoritma Finite Best-Strip mengolah daftar pertama P dalam sebuah strip yang terbuka (tidak terbatas), menggunakan pendekatan best-fit untuk memilih level untuk potongan berikut. Strip dibagi menjadi blok-blok, di mana lebar dari tiap blok adalah lebar dari strip, dan tinggi dari blok adalah tinggi level tertinggi dalam blok. Blok-blok hasil kemudian dimasukkan dalam bin-bin yang terbatas, sekali lagi menggunakan heuristik best-fit. Dalam pendekatan finite best-strip, level yang dipilih untuk potongan berikut adalah level yang menghasilkan sisa minimal dari area horisontal. Dengan ini, sebuah usaha dibuat dengan tujuan memaksimalkan penggunaan sisa ruang. Blok-blok yang dibuat dari tahap pertama dari prosedur disimpan dalam sebuah struktur data binary search-tree.
25
Gambar 2.17 Finite Best-Strip Heuristic Sumber:J.OBerkey and P.Y.Wang,1987,p.426 Cara ini paling banyak dipakai dalam penyelesaian 2DCSP. Algoritma ini ketika dicoba memakai binary search-tree data structure, membutuhkan waktu dengan estimasi 0(n log n). Untuk masalah yang sederhana, FBS lebih lambat dari algortima yang lain, tetapi dalam masalah yang besar algoritma ini efektif.
Tahap dari algoritma ini adalah:
semua potongan diurutkan menurun sesuai tinggi.
potongan pertama diletakkan ke posisi paling bawah-kiri dari bin. Kemudian bin dimisalkan sebagai sebuah strip dengan tinggi terbuka (tidak terbatas)
strip berikut yang dipilih adalah strip yang mempunyai area sisa horisontal yang minimal. Hal ini dikenal dengan istilah best-fit approach.
tinggi dari setiap level didefinisikan sebagai tinggi maksimal dari potongan dalam level itu.
26
strip hasil kemudian dibagi menjadi bin-bin yang terbatas (finite) menggunakan best-fit approach.
2.8. Perbandingan FNF, FFF, FBL, FBS Hasil uji perbandingan keempat algoritma di atas menurut Berkey dan Wang seperti pada Tabel 2.01 Tabel 2.01 Tabel Hasil Pengujian Algoritma Sumber:J.O.Berkey and P.Y.Wang, 1987, p.428
Algoritma Finite next-fit Finite first-fit Finite best-strip Finite bottom left
Jumlah rata-rata potongan dapat masuk per bin 2.23 3.45 3.53 3.03
Jumlah rata-rata pemakaian bin N* 1.700 1.064 1.040 1.333
Hasil ini didapat dengan memakai jumlah potongan n = 1000 sampai n = 5000, di mana jumlah potongan bertambah bertahap. Dapat dilihat di Tabel 2.01, kolom kedua menunjukkan jumlah rata-rata potongan yang dapat dimasukkan per bin. Semakin besar angka didapat maka semakin optimal algoritma tersebut. Demikian juga pada kolom berikutnya, semakin kecil angka yang didapat semakin sedikit jumlah bin yang dipakai. Pada artikel tersebut disimpulkan bahwa algoritma finite best-strip paling optimal dan efisien. Masih banyak peneliti dan ahli matematika lain yang mengembangkan metode untuk menyelesaikan masalah 2DCSP. Perkembangan itu sejalan dengan batasan dan jenis masalah yang akan dipecahkan. Dengan kata lain perkembangan itu mengarah masalah yang semakin spesifik.
