bab ii landasan teori 2.1. deskripsi cutting dan...

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

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, 3-

stage, 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.

Non-oriented guillotine

Oriented guillotine

Oriented non-guillotine

Non-oriented non-guillotine

11

Pola 3-stage

Gambar 2.07 Pola 3-stage


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


12

Pola ini adalah hasil dari algoritma yang kompleks, karena benar-benar

memampatkan potongan sehingga diperoleh sisa potong yang minimal. Potongan-

potongan 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 Gilmore-

Gomory. 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

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

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.

h(tinggi)

W (panjang) 2 (dua) strip

W (panjang)

h(tinggi)

1 (satu) strip

14

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


Apabila potongan berikut tidak muat dalam strip, tinggi potongan berikut

menjadi tinggi strip baru.


strip 1

strip 1

strip 1

strip 2

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) Dengan = 1, i = 1, … ,n (2)

= 0, j = 1,…,n-1, i > j | wi ≠ wj hi + hj > H (3)

= , j = 1,…,n (4)

≤ , j = 1,…,n-1 (5)

≤ W , k = 1,…,n-1 (6)

= , k = 1,…,n (7) ≤ H , l = 1,…,n-1 (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 = 1,…,n-1

≤ H , k = 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


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


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


Cara ini menggunakan metode yang sama, yaitu pendekatan bottom-left.


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 ke-

empat 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


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:


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

Jumlah rata-rata potongan dapat masuk

per bin

Jumlah rata-rata pemakaian bin

N* Finite next-fit 2.23 1.700 Finite first-fit 3.45 1.064 Finite best-strip 3.53 1.040 Finite bottom left 3.03 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.

bab ii landasan teori 2.1. deskripsi cutting dan...

Documents