BAB III ANALISIS MASALAH
Bab ini berisi analisis perbandingan performansi dan hasil akhir penyelesaian masalah pemotongan bar steel dengan algoritma brute force, algoritma greedy, dan algoritma program dinamis. Pada bab ini dapat terlihat jelas perbedaan ketiga algoritma tersebut dalam menyelesaikan masalah yang sama.
3.1 Latar Belakang Masalah Jenis stok material, terutama bar steel, dalam bentuk rol yang dihasilkan dari industri bahan bangunan umumnya mempunyai ukuran panjang terbatas karena adanya keterbatasan kemampuan mesin yang digunakan. Ukuran rol bar steel yang dihasilkan ini jarang sesuai dengan ukuran yang diinginkan oleh konsumen yang membutuhkan ukuran yang beraneka ragam.
Adanya keterbatasan mesin penghasil bar steel dan bermacam- macamnya ukuran bar steel yang diinginkan oleh konsumen menimbulkan beberapa permasalahan dalam menangani keterbatasan mesin produksi bar steel pada pabrik produsen bar steel. Masalah pertama adalah assortment problem, yaitu permasalahan untuk menentukan ukuran- ukuran rol bar steel yang harus diproduksi yang paling mendekati pemenuhan terhadap kebutuhan konsumen sehingga stok yang terpakai minimal. Masalah yang kedua adalah permasalahan untuk menemukan pola terhadap rol bar steel yang dihasilkan pabrik menjadi potongan-potongan yang lebih kecil umtuk memenuhi kebutuhan konsumen. Kedua masalah ini jika diteliti dapat diselesaikan dengan algoritma-algoritma yang telah ada, namun lebih baik lagi jika diteliti lagi untuk mencari algoritma lain yang lebih baik yang dibuat dari hasil modifikasi algoritma yang telah ada. Oleh karena itu diperlukan sebuah anilisis perbandingan penyelesaian masalah pemotongan bar steel dengan berbagai algoritma optimasi untuk dilihat kelebihan dan kelemahan dari masing- masing algoritma optimasi tersebut dalam menyelesaikan masalah pemotongan bar steel. Jika memungkinkan akan dilakukan modifikasi untuk memperbaiki kelemahan algoritma yang tela h ada. III-1
Pada bab ini akan dilakukan perbandingan beberapa algoritma optimasi untuk mendapatkan algoritma optimasi yang mampu menghasilkan pola pemotongan bar steel agar sisa bar steel yang terbuang minimal. Algoritma optimasi yang diikutsertakan dalam penelitian ini adalah algoritma greedy, program dinamis, dan metode pencarian brute force sebagai pengukur seberapa optimal suatu algoritma optimasi dalam menyelesaikan masalah.
3.2 Pola Pemotongan Pola adalah bentuk atau model (atau, lebih abstrak, suatu set peraturan) yang bisa dipakai untuk membuat atau untuk menghasilkan suatu atau bagian dari sesuatu, khususnya jika sesuatu yang ditimbulkan cukup mempunyai suatu yang sejenis untuk pola dasar yang dapat ditunjukkan atau terlihat, yang mana sesuatu itu dika takan memamerkan pola [WIK07-b].
Secara umum, pola dapat dikatakan sebagai cara untuk mengelola suatu objek. Terdapat bermacam- macam penggunaan pola, misalnya pola penyerangan dan pola bertahan dalam sepakbola, pola pikir, dan pola pemotongan (pola yang akan dibahas lebih lanjut dalam tugas akhir ini). Gambar III-1 dan Gambar III-2 adalah contoh pola pemotongan satu dimensi, dalam hal ini adalah besi.
Gambar III-1 Pola pemotongan menjadi 3 bagian
Gambar III-2 Pola pemotongan menjadi 2 bagian Dalam pola pemotongan, yang dimaksud pengelolaan objek adalah bagaimana cara memotong- motong sebuah objek yang besar menjadi sebuah objek yang lebih kecil. Objek yang besar tersebut dikelola dengan dipotong-potong menjadi potongan yang lebih kecil dengan tujuan agar objek tersebut menjadi lebih berguna. Biasanya pemotongan terhadap suatu objek dilakukan karena adanya kebutuhan terhadap objek yang lebih kecil, sedangkan yang objek yang tersedia tidak bisa memenuhi kebutuhan tersebut. Perbedaan cara yang ditempuh dalam melakukan pemotongan terhadap suatu III-2
objek dapat menghasilkan sesuatu yang jauh berbeda satu sama lain. Untuk lebih jelasnya, definisi pola pemotongan dapat diperjelas melalui ilustrasi berikut ini: Seorang pengusaha lembaran baja memproduksi rol b dengan panjang standar l. Order besar sedang dikerjakan sehubungan dengan permintaan pelanggan yang memerlukan lembaran dengan panjang yang bermacam- macam. Secara khusus, lembaran bi dengan panjang li untuk i= 1, 2, ..., m akan diorder (lebih jelasnya dapat dilihat pada Gambar III-3). Pengusaha berkeinginan untuk memotong
rol
standar
sedemikian
sehingga
memenuhi order
dan
meminimalkan sisanya. Karena potongan sisa tidak berguna bagi pengusaha, tujuannya adalah untuk meminimalkan jumlah rol yang diperlukan untuk memenuhi order. Diketahui lembaran standar dengan panjang l, ada banyak cara memotongnya. Cara yang demikian disebut dengan pola pemotongan.
l Lembaran b
l1 Lembaran b1
l2 Lembaran b2
l3 Lembaran b3
lm Lembaran bm
Gambar III-3 Deskripsi Pola Pemotongan
III-3
3.3 Metode Penyelesaian Permasalahan pada perusahaan konstruksi dalam memilih pola yang cocok untuk diterapkan pada bar steel agar hanya menyisakan potongan bar steel yang tak terpakai seminimal mungkin. Seperti yang telah dijelaskan pada Bab II, permasalahan pencarian pola pemotongan paling optimal dapat diselesaikan dengan berbagai macam algoritma optimasi. Khusus untuk tugas akhir ini, algoritma yang diperbandingkan adalah algoritma greedy, program dinamis, dan brute force. Ketiga algoritma ini terpilih karena ketiga algoritma ini paling lazim digunakan berbagai program optimasi pola pemotongan (kecuali algoritma brute force, yang hanya akan dijadikan pembanding hasil kedua algoritma lainnya).
Algoritma brute force, greedy dan program dinamis memiliki cirri-ciri tersediri dalam menyelesaikan masalah. Secara umum perbedaan karakteristik ketiga algoritma ini telah dijelaskan secara detail pada Bab II, namun pada subbab ini akan dijelaskan lebih spesifik mengenai alur penyelesaian masalah optimasi pola pemotongan dengan ketiga algoritma ini.
Penyelesaian permasalahan optimasi pemotongan bar steel dapat diselesaikan lebih mudah apabila kita telah mengetahui pola-pola pemotongan seperti apa saja yang dapat diterapkan terhadap satu buah rol bar steel. Oleh karena itu, sebelum melalui proses algoritma optimasi perlu digenerasi sebuah list yang berisi semua kemungkinan pola pemotongan yang dapat diterapkan. Berikut adalah penjelasan mengenai list yang dimaksud: Misalkan kita ingin mendapatkan bar steel dengan panjang x 1 meter sebanyak y1 buah, bar steel dengan panjang x 2 meter sebanyak y2 buah, bar steel dengan panjang x 3 meter sebanyak y3 buah, hingga bar steel dengan panjang x n meter sebanyak yn buah dengan cara memotong- motong rol bar steel dari pabrik dengan panjang z1 meter, panjang z2 meter, panjang z3 meter, hingga rol bar steel dengan panjang zm meter (lebih jelasnya dapat dilihat pada Gambar III-4). Kemudian kita harus mencari pola pemotongan terhadap dua rol bar steel dari pabrik untuk mendapatkan bar steel dengan panjang yang diinginkan. Pencarian pola pemotongan dapat direpresentasi dalam persamaan matematika berikut ini: III-4
z1
z
z
2
3
z
n
x1
x
x
2
3
x
n
Gambar III-4 Deskripsi Persoalan Pola Pe motongan a1x 1 + a2x 2 + a3x3 + … + anxn ≤ z1 , atau a1x 1 + a2x 2 + a3x3 + … + anxn ≤ z2 , atau a1x 1 + a2x 2 + a3x3 + … + anxn ≤ z3 , atau . . . a1x 1 + a2x 2 + a3x3 + … + anxn ≤ zm Maka kita dapat merepresentasikan pola dalam bentuk array pattern {a1 ,a2 ,a3 ,…,an } dimana x 1 < x2 < x 3 < … < xn dan z1 < z2 < z3 < … < zm . Kumpulan array pattern inilah yang nantinya akan diolah oleh algoritma optimasi menjadi sebuah solusi yang berupa kumpulan array pattern yang berurut menurut prioritas penerapan array III-5
pattern. Jumlah pattern yang dapat terbentuk dari persoalan semacam ini dapat dihitung menurut cara berikut: Pola-pola yang terbentuk adalah kombinasi dari nilai- nilai a1 ,a2 ,a3 ,…,an dengan kemungkinan nilai 0 ≤ a1 ,a2 ,a3 ,…,an ≤ zm /x 1 . Nilai a1 ,a2 ,a3 ,…,an bernilai antara 0 hingga zm /x 1 karena nilai zm adalah yang terbesar dibanding nilai z yang lain dan niali x 1 adalah yang terkecil dibanding nilai x yang lain sehingga kemungkinan terbesar nilai a adalah zm /a1 .
3.3.1 Brute Force Penyelesaian masalah pemotongan dengan metode brute force dilakukan dengan mencoba seluruh kemungkinan pola pemotongan yang bisa kemudian dibandingan. Hasilnya adalah pola pemotongan yang memiliki potongan terbuang minimal. Metode penyelesaian dengan brute force ini pasti menghasilkan solusi yang paling baik karena metode ini menelusuri dan membandingkan seluruh kemungkinan yang ada, sehingga solusi yang muncul pasti yang terbaik dari semua metode. Namun, metode ini memiliki kompleksitas yang sangat besar (akan dijelaskan selanjutnya), sehingga metode ini tidak akan digunakan sebagai algoritma optimasi terbaik, melainkan sebagai metode pembanding algoritma lain. Solusi yang dihasilkan algoritma optimasi lain akan dibandingkan dengan solusi metode brute force untuk mengetahui seberapa baik suatu algoritma dalam menyelesaikan masalah. Algoritma optimasi yang solusinya paling mendekati solusi yang dihasilkan metode brute force dapat dikatakan sebagai algoritma terbaik.
Pseudocode penyelesaian masalah pola pemotongan dengan algoritma brute force diberikan pada Algoritma III-1.
Untuk lebih jelasnya, langkah-langkah penyelesaian persoalan diatas menggunakan metode brute force adalah sebagai berikut: 1. Buat list list_solusi dan solution, kemudian diinisialisasi kosong. 2. Buat variabel sisa untuk menghitung jumlah sisa yang telah dihasilkan oleh pola pemotongan. Buat juga variabel sisaMin untuk membandingkan pola mana yang menghasilkan pola minimal. Inisisalisasi sisa dengan 0 dan sisaMin dengan 999. 3. Inisialisasi i=0. III-6
procedure bruteforce (input problem: array, wood:array; output solution: list, sisaMin: integer) {Mengembalikan solusi dari persoalan optimasi dengan algoritma brute force Prekondisi: Semua pola pemotongan telah terdefinisi dalam bentuk array pattern Masukan: array problem yang memrepresentasikan ukuran-ukuran bar steel yang dibutuhkan oleh masalah dan array wood yang merepresentasikan ukuran bar steel yang tersedia Keluaran:solusi merupakan himpunan solusi yang bertipe list dan sisaMin merupakan sisa yang dihasilkan} Deklarasi solution, list_solusi: list sisa, sisaMin: integer i,j,k,l: integer Algoritma solution {} list_solusi {} sisa 0 sisaMin 999 i 0 repeat
{Inisialisasi kosong} {Inisialisasi kosong} {Inisialisasi awal} {Inisialisasi awal}
while(isNotZero(problem)) while(isPositif(problem – pattern[i])) list_solusi list_solusi + {pattern[i]} problem problem – pattern[i] sisa sisa + sisapattern[i] endwhile i i+1 endwhile if(sisa < sisaMin) then sisaMin sisa Empty(solution) copy(list_solusi, solution) endif k=1
while(isLastIndex(lastElement)) deleteLast(list_solusi, lastElement) problem problem + lastElement endwhile i index(lastElement) until (isEmpty(list_solusi))
Algoritma III-1 Pseudocode algoritma masalah pemotongan dengan brute force
4. Masukkan pattern[i] kedalam list_solusi. Kurangi problem dengan pattern[i] Tambah sisa dengan sisapattern[i]. 5. Lakukan tahap 6 hingga terdapat minimal satu nilai negatif pada problem. Nilai i bertambah 1. 6. Kembali ke tahap 6 hingga semua nilai pada problem adalah 0. Hitung nilai sisa kemudian bandingkan dengan sisaMin, jika sisa lebih kecil maka nilai sisaMin diganti dengan sisa, kosongkan solution kemudian copy list_solusi ke solution. 7. Hapus pattern[i] dari list_solusi dan tambahkan nilai sisa dengan nilai sisapattern[i]. Nilai i bertambah 1. Kembali ke tahap 8. III-7
8. Lakukan tahap 9 hingga nilai i sama dengan numberofpattern hingga akhirnya seluruh tahap pernah ditempati oleh semua pattern. 9. Tampilkan list solution yang berisi langkah- langkah pemilihan pola pemotongan ke layar.
Penyelesaian persoalan menggunakan algoritma brute force memiliki kompleksitas T(n,k) = n(1+(k-1)(2+(k 2 -k)/2)) dengan n adalah jumlah pattern yang digunakan dari sebuah permasalahan pemotongan dan k adalah jumlah tahap pencarian hingga selesai.
3.3.2 Algoritma Greedy Penyelesaian dengan algoritma persoalan diatas dengan menggunakan algoritma greedy adalah dengan memilih langkah yang terlihat paling mendekati solusi, yaitu dengan memilih pola yang memiliki sisa terkecil terlebih dahulu. Secara umum, pseudocode algoritma greedy untuk permasalahan optimasi pemotongan diberikan pada Algoritma III-2.
procedure greedy (input problem: array, wood:array; output solution: list, sisaMin: integer) {Mengembalikan solusi dari persoalan optimasi dengan algoritma greedy Prekondisi: Semua pola pemotongan telah terdefinisi dalam bentuk array pattern dan telah terurut sesuai dengan aturan prioritas greedy Masukan: array problem yang memrepresentasikan ukuran-ukuran bar steel yang dibutuhkan oleh masalah dan array wood yang merepresentasikan ukuran bar steel yang tersedia Keluaran:solusi merupakan himpunan solusi yang bertipe list dan sisaMin merupakan sisa yang dihasilkan } Deklarasi solution: list sisa: integer i: integer Algoritma solution {} sisa 0 i 0
{Inisialisasi kosong} {Inisialisasi awal}
while(isNotZero(problem)) while(isPositif(problem – pattern[i])) solution solution + {pattern[i]} problem problem – pattern[i] sisa sisa + sisapattern[i] endwhile i i+1 endwhile
Algoritma III-2 Pseudocode algoritma masalah pemotongan dengan greedy
III-8
Pada implementasi algoritma greedy, yang dilakukan hanya memilih pattern yang memiliki sisa yang paling kecil dan menghasilkan bar steel paling panjang dari kumpulan pattern yang masih mungkin diterapkan. Kompleksitas yang dimiliki algoritma greedy dalam menyelesaikan masalah ini adalah T(n,k) = n+(k-1) dengan n adalah jumlah pattern yang dapat terbentuk dari sebuah permasalahan pemotongan dan k adalah jumlah tahap pencarian hingga selesai.
3.3.3 Algoritma Program Dinamis Penyelesaian dengan algoritma persoalan diatas dengan menggunakan algoritma program dinamis adalah dengan memilih langkah yang memenuhi prinsip optimalitas. Dengan prinsip optimalitas ini dijamin bahwa setiap keputusan yang diambil pada suatu tahap adalah keputusan yang benar untuk tahap-tahap selanjutnya juga, tidak hanya benar untuk tahap itu saja.
Secara matematis, penyelesaian masalah ini dengan program dinamis dapat dituliskan sebagai berikut: f 1 (s) = cx1s
(basis)
f k (s) = min{cxks + f k-1 (x k)},
k=2,3,4, …, n
(rekurens)
dengan k adalah tahap (level) pencaraian, s adalah status yang berhubungan dengan masing- masing tahap (level) yang merupakan simpul-simpul dalam graf (x 1 , x2 , x3 , …, xn), cxks menyatakan bobot sisi dari x k ke s, f k(x k,s) menyatakan total bobot lintasan dari x k ke s, f k (s) adalah nilai minimal dari f k(x k,s), dan n adalah jumlah tahap pencarian yang dilakukan.
Pseudocode penyelesaian masalah optimasi pemotongan dengan program dinamis diberikan pada Algoritma III-3.
Implementasi
algoritma
program
dinamis
akan
menggunakan
tabel-tabel
pembandingan pada setiap tahap pencarian. Kompleksitas yang dimiliki algoritma program dinamis dalam menyelesaikan masalah optimasi pemotongan adalah O(k) dengan k adalah jumlah level yang dijalankan oleh algoritma untuk menyelesaikan sebuah permasalahan pemotongan. III-9
procedure programDinamis (input problem: array, wood:array; output solution: list, sisaMin: integer) {Mengembalikan solusi dari persoalan optimasi dengan algoritma program dinamis Prekondisi: Semua pola pemotongan telah terdefinisi dalam bentuk array pattern Masukan: array problem yang memrepresentasikan ukuran-ukuran bar steel yang dibutuhkan oleh masalah dan array wood yang merepresentasikan ukuran bar steel yang tersedia Keluaran:solusi merupakan himpunan solusi yang bertipe list dan sisaMin merupakan sisa yang dihasilkan } Deklarasi solution: list list_content : list yang elemennya terdiri dari list pola pemotongan, sisa, dan array problem sisa: integer i: integer Algoritma solution {} list_content {} sisa 0
{Inisialisasi kosong} {Inisialisasi kosong} {Inisialisasi awal}
i 0 {list_content diisi dengan semua pattern, sisa dihitung, array problem dikurangi} level 2 while(seluruh array problem yang ada di list_content belom bernilai 0) while(belum elemen terakhir) {semua elemen mengurangi array problem miliknya dengan semua pattern yang tersedia pada tahap ke- level} endwhile {Menghapus semua elemen dari list_content yang array problem-nya bernilai negative } level level + 1 endwhile {Mencari elemen list_content yang memiliki sisa pemotongan paling kecil} {Copy isi elemen list_content yang memiliki sisa pemotongan paling kecil kedalam list solution}
Algoritma III-3 Pseudocode algoritma masalah dengan program dinamis
3.4 Penyelesaian Contoh Masalah Untuk mengetahui bagaimana algoritma brute force, greedy, dan program dinamis menyelesaikan masalah yang sama dan membandingkan solusi yang dihasilkannya, berikut ini diberikan sebuah contoh persoalan. Persoalan 1: Misalkan kita ingin mendapatkan bar steel dengan panjang 5 meter sebanyak 3 buah, 7 meter sebanyak 2 buah, dan 8 meter sebanyak 2 buah dengan memotong bar steel yang panjangnya 10 meter dan 12 meter. Penyelesaian masalah ini dapat dimulai dengan membuat daftar pola pemotongan yang mungkin untuk setiap satu rol bar steel. Sebelum masuk III-10
pada tahap pencarian menggunakan algoritma optimasi, terlebih dahulu kita menggenerasi pola-pola apa saja yang dapat terbentuk untuk masalah ini. Daftar pola yang digenerasi dapat dilihat dalam Tabel III-1. Daftar pola pada Tabel III-1 dapat dikompresi lagi dengan mengurangi pola-pola yang memiliki potongan yang sama namun menghasilkan sisa yang lebih besar. Setelah dikompresi, pola-pola yang terbentuk dapat dilihat pada Tabel III-2. Selanjutnya, permasalahan ini dapat diibaratkan seperti sebuah graf yang ditunjukkan pada Gambar III-5. Pada Gambar III-5 diperlihatkan bahwa pencarian dapat dimulai dari pola manapun tanpa aturan, namun pada pemilihan pola selanjutnya tidak boleh sembarangan. Pola dengan indeks pattern lebih kecil tidak boleh dilakukan setelah pola dengan indeks pattern lebih besar. Pemilihan pola berlangsung hingga semua kebutuhan potongan bar steel terpenuhi.
Tabel III-1 Macam-macam pola yang te rbentuk dari persoalan 1 Pola
8 meter
7 meter
5 meter
(juml ah potong an
(juml ah potong an
(juml ah potong an
yang dihasilkan)
yang dihasilkan)
yang dihasilkan)
Sisa (meter)
Pattern[0]
1
0
0
4
Pattern[1]
1
0
0
2
Pattern[2]
0
1
0
5
Pattern[3]
0
1
0
3
Pattern[4]
0
1
1
0
Pattern[5]
0
0
1
7
Pattern[6]
0
0
1
5
Pattern[7]
0
0
2
2
Pattern[8]
0
0
2
0
Tabel III-2 Macam-macam pola yang te rsisa setelah Tabel III-1 dikompresi Pola
8 meter
7 meter
5 meter
(juml ah potong an
(juml ah potong an
(juml ah potong an
yang dihasilkan)
yang dihasilkan)
yang dihasilkan)
Sisa (meter)
Pattern[0]
1
0
0
2
Pattern[1]
0
1
0
3
Pattern[2]
0
1
1
0
Pattern[3]
0
0
1
5
Pattern[4]
0
0
2
0
III-11
Pattern[0]
Pattern[1]
Pattern[2]
Pattern[3] Pattern[0]
Pattern[1] Pattern[4] Pattern[2]
Pattern[1]
Pattern[3]
Start
Pattern[2] Pattern[2]
Pattern[4] Pattern[3] Pattern[3]
Pattern[3]
Pattern[4] Pattern[4]
Pattern[4] Pattern[4]
Gambar III-5 Alur pemilihan pola pemotongan Bar Steel Kemudian kita representasikan permasalahan menjadi sebuah array problem {2,2,3,0} dimana urutan indeks pada array tersebut adalah sebagai berikut: i = 0 jumlah bar steel dengan panjang 8 meter yang masih diperlukan i = 1 jumlah bar steel dengan panjang 7 meter yang masih diperlukan i = 2 jumlah bar steel dengan panjang 5 meter yang masih diperlukan i = 3 jumlah panjang sisa bar steel yang terbuang. Catatan: jumlah panjang sisa bar steel yang terbuang akan bernilai 999 jika setidaknya terdapat nilai negatif pada array problem.
3.4.1 Brute Force Penyelesaian persoalan 1 menggunakan algoritma brute force dapat dilakukan dengan mengimplementasi pseudocode yang telah didefinisikan pada subbab 3.2.1. Langkah-
III-12
langkahnya adalah dengan mencoba semua kemungkinan pola pada setiap pengambilan keputusan.
Solusi yang didapat dari penyelesaian menggunakan metode brute force adalah sebagai berikut: pattern[0] pattern[0] pattern[1] pattern[2] pattern[4] (dibaca: Potong bar steel dengan cara pattern[0], kemudian cara pattern[0], kemudian cara pattern[1], kemudian cara pattern[2], dan yang terakhir dengan cara pattern[4]) Sisa potongan bar steel yang tak terpakai sebanyak 7 meter.
3.4.2 Algortima Greedy Dalam proses penyelesaian persoalan 1 dengan algoritma greedy, perlu dibentuk beberapa elemen-elemen algoritma greedy dari permasalahan tersebut, yaitu:
1. Himpunan kandidat Pattern-pattern yang akan diterapkan pada bar steel dalam pemotongan, yaitu: {pattern[0], pattern[1], pattern[2], …, pattern[8]} 2. Himpunan solusi Pattern-pattern yang terpilih sehingga sisa bar steel yang terbuang akibat penerapan pattern pada proses pemotongan bernilai paling minimal selama nilai array problem tidak ada yang 0. 3. Fungsi seleksi Pilihlah pattern yang bernilai paling optimal, yaitu pattern yang menghasilkan sisa bar steel yang terbuang yang paling minimal. 4. Fungsi layak Fungsi yang memeriksa apakah pattern-pattern yang telah diterapkan tidak membuat array problem bernilai negatif. 5. Fungsi objektif Fungsi yang memilih jumlah sisa yang paling minimal dari kandidat solusi yang layak.
III-13
Untuk lebih jelasnya adalah sebagai berikut: 1. Pilih pola yang menghasilkan sisa paling sedikit terlebih dahulu. Ada 2 pola yang menghasilkan sisa 0 meter (sisa yang paling sedikit), yaitu pola “pattern[2] dan pola “pattern[4]”. Untuk menentukan pola mana yang terpilih, cari pola yang menghasilkan potongan bar steel yang dibutuhkan yang paling banyak. Maka pola pertama yang terpilih adalah pola “pattern[4]” karena pattern[4] menghasilkan 2 buah ukuran 5 meter. Setelah pola “pattern[4]” dimasukkan kedalam himpunan solusi maka array problem menjadi {2,2,1,0}. Setelah diperiksa dengan fungsi layak, pola “pattern[4]” dinyatakan layak karena tidak membuat array problem menjadi negatif. 2. Pada langkah kedua, pola yang pertama kali dicoba juga pola “pattern[4]”, sehingga array problem berubah menjadi {2,2,-1,0}. Setelah diperiksa menggunakan fungsi layak ternyata pola “pattern[4]” tidak layak masuk solusi pada langkah kedua karena membuat array problem menjadi negatif. Pola “pattern[4]” dihapus dari himpunan kandidat dan himpunan solusi. Kemudian, kita coba pola lain dari himpunan kandidat yang memiliki sisa paling minimal, yaitu pola “pattern[2]”, sehingga array problem berubah menjadi {2,1,0,0}. Setelah diperiksa menggunakan fungsi layak ternyata pola “pattern[2]” layak masuk solusi pada langkah ketiga karena tidak membuat array problem menjadi negatif. 3. Pada langkah ketiga, kita coba lagi pola pattern[2]. Setelah pola “pattern[2]” dimasukkan kedalam himpunan solusi , array problem berubah menjadi {2,0,1,0}. Pola ini tidak lolos fungsi layak karena membuat array problem menjadi negatif. Kemudian, kita coba pola lain dari himpunan kandidat yang memiliki sisa paling minimal, yaitu pola “pattern[0]”, sehingga array problem berubah menjadi {1,1,0,2}. Setelah diperiksa menggunakan fungsi layak ternyata pola “pattern[0]” layak masuk solusi pada langkah ketiga karena tidak membuat array problem menjadi negatif. 4. Pada langkah keempat, pola “pattern[0]” kembali dicoba, setelah dimasukkan kedalam himpunan solusi array problem berubah menjadi {0,1,0,4}. Pola ini lolos fungsi layak pada langkah keempat karena tidak membuat array problem menjadi negatif. III-14
5. Pada langkah kelima, pola “pattern[0]” kembali dicoba, setelah dimasukkan kedalam himpunan solusi array problem berubah menjadi {-1,1,0,6}. Pola ini tidak lolos fungsi layak pada langkah kelima karena membuat array problem menjadi negatif. Pola “pattern[0]” dihapus dari himpunan kandidat dan himpunan solusi. Kemudian, kita coba pola lain dari himpunan kandidat yang memiliki sisa paling minimal, yaitu pola “pattern[1]”, sehingga array problem berubah menjadi {0,0,0,7}. Setelah diperiksa menggunakan fungsi layak ternyata pola “pattern[1]” layak masuk solusi pada langkah kelima karena tidak membuat array problem menjadi negatif. 6. Setelah langkah kelima, seluruh kebutuhan ukuran potongan bar steel telah terpenuhi sehingga pencarian selesai dan solusi pola pemotongan optimal menggunakan algoritma greedy adalah: “pattern[4]” “pattern[2]” “pattern[0]” “pattern[0]” “pattern[1]” (dibaca: Potong bar steel dengan cara pattern[4], kemudian cara pattern[2], kemudian cara pattern[0], kemudian cara pattern[0], dan yang terakhir dengan cara pattern[1]) Sisa potongan yang tidak terpakai sebanyak 9 meter.
3.4.3 Algoritma Program Dinamis Penyelesaian persoalan 1 menggunakan algoritma dinamis dapat diselesaikan dengan membagi-bagi proses penyelesaian menjadi tahap-tahap. Penyelesaian masalah ini akan menggunakan program dinamis maju. Misalkan x 1 , x2 , x 3 , …, xn adalah simpulsimpul yang dikunjungi pada tahap k (k = 1, 2, 3, …, n) dimana. Maka rute yang harus dilalui adalah x 1 x2 x3 … xn . Pada persoalan ini, 1. Tahap (k) adalah proses memilih simpul tujuan berikutnya (ada n tahap) 2. Status (s) yang berhubungan dengan masing- masing tahap, yaitu simpul-simpul didalam graf. Relasi rekurens yang menyatakan lintasan terpendek (sisa paling minimal) dari status x1 ke s pada tahap k adalah sebagai berikut:
f 1 (s) = cx1s
(basis)
f k(s) = min {cxks + f k-1 (x k)}, k=2,3,4, …, n
(rekurens) III-15
Tahap 1: Tahap 1 penyelesaian persoalan 1 dengan program dinamis dapat dilihat pada Tabel III-3. f 1 (s) = cx1s Tabel III-3 Tahap 1 Penyelesaian Pe rsoalan 1 dengan Program Dinamis Solusi Opti mum s f1 (s)
Catatan:
x1 *
[0]
{1,2,3,2}
-
[1]
{2,1,3,3}
-
[2]
{2,1,2,0}
-
[3]
{2,2,2,5}
-
[4]
{2,2,1,0}
-
x k* adalah nilai xk yang meminimalkan f k(x k,s) nilai x 1 tidak ada karena pada tahap 0 belom ada pola pemotongan yang dilakukan.
Tahap 2: Tahap 2 penyelesaian persoalan 1 dengan program dinamis dapat dilihat pada Tabel III-4.
f 2 (s) = min {cx2s + f 1 (x2 )} Tabel III-4 Tahap 2 Penyelesaian Pe rsoalan 1 dengan Program Dinamis x2
Solusi
f2 (x2 ,s) = c x2s + f1 (x2 )
Opti mum
s [0]
[1]
[2]
[3]
[0]
{0,2,3,4}
[1]
{1,1,3,5}
{2,0,3,6}
[2]
{1,1,2,2}
{2,0,2,3}
{2,0,1,0}
[3]
{1,2,2,7}
{2,1,2,8}
{2,1,1,5}
{2,2,0,10}
[4]
{1,2,1,2}
{2,1,1,3}
{2,1,0,0}
{2,2,0,5}
[4]
{2,2,-1,999}
f2 (s)
x2 *
4
[0]
5
[0]
0
[2]
5
[2]
0
[2]
III-16
Tahap 3 Tahap 3 penyelesaian persoalan 1 dengan program dinamis dapat dilihat pada Tabel III-5.
f 3 (s) = min {cx3s + f 2 (x3 )}
Tabel III-5 Tahap 3 Penyelesaian Pe rsoalan 1 dengan Program Dinamis x2
Solusi
f3 (x3 ,s) = c x3s + f2 (x3 ) [0] s
[0]
[0]
{-
Opti mum
[1] [1]
[2]
[3]
[4]
[1]
[2] [2]
[3]
[4]
[2]
[3] [3]
[4]
[3]
[4]
f3 (s)
x3
-
-
7
[0][0]
2
[0][2]
5
[2][2]
2
[0][2],
1,2,3,999} [1]
{0,1,3,7}
{1,0,3,8}
{2,1,3,999}
[2]
[3]
{0,1,2,4}
{0,2,2,9}
{1,0,2,5}
{1,1,2,10}
{1,0,1,2}
{1,1,1,7}
{1,2,1,12}
{2,-
{2,-
{2,-
1,2,999}
1,1,999}
1,0,999}
{2,0,2,11}
{2,0,1,8}
{2,1,1,13}
{2,0,0,5}
{2,1,0,10}
{2,2,1,999}
[4]
{0,2,1,4}
{1,1,1,5}
{1,1,0,2}
{1,2,0,2}
{1,2,1,999}
{2,0,1,6}
{2,0,0,3}
{2,1,0,8}
{2,1,-
{2,0,-
{2,1,-
{2,1,-
{2,2,-
{2,2,-
1,999}
1,999}
1,999}
2,999}
2,999}
2,999}
III-17
[0][3]
Tahap 4 Tahap 4 penyelesaian persoalan 1 dengan program dinamis dapat dilihat pada Tabel III-6 dan Tabel III-7. f 4 (s) = min {cx4s + f 3 (x4 )} Tabel III-6 Tahap 4 bagian 1 Penyelesaian Persoalan 1 Solusi
f4 (x4 ,s) = c x4s + f3 (x4 )
x2
Opti mum
[0] [0]
s [1]
[1]
[2]
[3]
[4]
[1]
[1]
[2]
[2] [3]
[4]
[2]
[3]
[3]
[4]
[3]
f4 (s)
x4
[4]
{1,{0,0,3,10}
[2]
{0,0,2,7}
[3] [4]
1,3,999} {0,0,1,4}
{0,1,2,12}
{0,1,1,9}
{0,2,1,14}
{0,1,1,7}
{0,1,0,4}
{0,2,0,9}
{0,2,-
{1,-
{1,-
{1,-
1,2,999}
1,1,999}
1,0,999}
{1,0,2,13}
{1,0,1,10}
{1,1,1,15}
{1,0,1,8}
{1,0,0,5}
{1,1,0,10}
1,999}
{1,0,0,7}
{1,1,0,12}
{1,2,0,17}
{1,1,-
{1,0,-
{1,1,-
{1,1,-
{1,2,-
{1,2,-
1,999}
1,999}
1,999}
2,999}
1,999}
2,999}
10
[0][0][1]
4
[0][0][2]
7
[0][2][2]
4
[0][0][2]
Tabel III-7 Tahap 4 bagian 2 Penyelesaian Persoalan 1 f4 (x4 ,s) = c x4s + f3 (x4 )
x2
Solusi Opti mum
[1] [1] s
[3]
[3]
{2,0,1,16}
[4]
{2,0,0,11}
[4]
[2] [3]
[3] [4]
{2,0,0,13} {2,0,-1,999}
[2]
{2,0,-1,999}
[3]
[2] [4]
{2,1,0,18} {2,0,-2,999}
{2,1,-1,999}
{2,1,-2,999}
[3]
f4 (s)
x4
[3]
[3]
{2,0,-1,999}
{2,1,-1,999}
13
[1][2][3]
{2,0,-2,999}
{2,1,-2,999}
11
[1][1][3]
III-18
Tahap 5 Tahap 5 penyelesaian persoalan 1 dengan program dinamis dapat dilihat pada Tabel III-8 dan Tabel II-9. f 5 (s) = min {cx5s + f 4(x5 )} Tabel III-8 Tahap 5 bagian 1 Penyelesaian Persoalan 1 x2
f5 (x5 ,s) = c x5s + f4 (x5 )
Solusi Opti mum
[0] [0] [1]
[1]
[2]
[2]
[3]
[4]
[2]
[3]
[3]
[4]
f5 (s)
x5
[3]
s [1]
{0,-
-
-
-
-
1,3,999} {0,-
{0,-
{0,-
1,2,999}
1,1,999}
1,0,999}
[3]
{0,0,2,15}
{0,0,1,12}
{0,1,1,17}
[4]
{0,0,1,10}
{0,0,0,7}
{0,1,0,12}
[2]
9 {0,0,0,9}
{0,1,0,14}
{0,1,-
{0,0,-
{0,1,-
1,999}
1,999}
1,999}
{0,2,0,19}
{0,1,-2,999}
{0,2,-2,999}
(Selesai) 7
[0][0][2][2]
[0][0][1][2]
(Selesai)
III-19
Tabel III-9 Tahap 5 bagian 2 Penyelesaian Persoalan 1 x2
f5 (x5 ,s) = c x5s + f4 (x5 )
Solusi Opti mum
[0]
[1]
[1] [1]
[2]
[2]
[3]
[2]
[3]
[3]
[1]
[2]
[3]
[3]
[3]
[3]
[3]
f5 (s
x5
) [3]
[4]
[3]
[4]
[3]
[4]
[3]
[3]
[3]
{1,0,-
{1,1,-
{1,2,-
1,999
1,999
1,999
}
}
}
{1,1,-
{1,0,-
{1,1,-
{1,2,-
2,999
2,999
2,999
2,999
}
}
}
}
[3]
[4]
[3]
[3]
{2,0,-
{2,1,-
1,999
1,999
}
}
{2,0,-
{2,0,-
{2,1,-
2,999
2,999
2,999
}
}
}
s [3 ]
[4 ]
{1,0,1,18
{1,0,0,15
}
{1,0,0,13 }
{1,1,0,20
} {1,0,1,999 }
{1,0,1,999}
} {1,0,2,999} }
{1,1,1,999}
{2,0,0,21 }
{2,0,1,999}
[0][1][2][3 15
]
[0][1][1][3 13
]
Ket: Nilai pada array problem ada yang negatif Tidak dilakukan karena pattern tujuan tidak sesuai dengan aturan lintasan yang telah dijelaskan diawal.
III-20
Setelah tahap lima terlihat bahwa terdapat 2 jalur yang sudah selesai. Dari kedua jalur tersebut, nilai sisa yang paling minimal yang dihasilkan adalah 7 meter dengan jalur: “pattern[0]” “pattern[0]” “pattern[1]” “pattern[2]” “pattern[4]” (dibaca: Potong bar steel dengan cara pattern[0], kemudian cara pattern[0], kemudian cara pattern[1], kemudian cara pattern[2], dan yang terakhir dengan cara pattern[4])
3.5 Analisis Metode Penyelesaian Berdasarkan hasil penelitian yang dilakukan pada subbab 3.3 terhadap algoritma program dinamis, brute force, dan greedy, dapat dilihat bahwa untuk pemecahan masalah yang sama, solusi yang dihasilkan oleh ketiga algoritma optimasi tersebut sama tetapi dengan kompleksitas yang berbeda-beda. Untuk lebih jelasnya dapat kita lihat dari Tabel III-10
Tabel III-10 Perbandingan hasil penyelesaian masalah pe motongan bar steel Algorti ma
Kompleksitas (T(n,k))
Sisa Bar steel mini mal yang ti dak terpakai
Brute fo rce
n(1+(k -1)(2+(k 2 -k)/2))
7 meter
Greedy
n+k-1
9 meter
Program Dinamis
k
7 meter
Keterangan: n: jumlah pola yang terdefinisi k: jumlah tahap yang dilalui hingga selesai
III-21
