Prosiding Seminar Nasional Manajemen Teknologi XX Program Studi MMT-ITS, Surabaya 1 Februari 2014

Prosiding Seminar Nasional Manajemen Teknologi XX Program Studi MMT-ITS, Surabaya 1 Februari 2014

PENGEMBANGAN ALGORITMA DIFFERENTIAL EVOLUTION (DE) UNTUK MENYELESAIKAN PERMASALAHAN TATA LETAK FASILITAS DENGAN LUAS AREA BERBEDA (UNEQUAL AREA FACILITY LAYOUT PROBLEM) M. Bisyrul Jawwad1), Budi Santosa2), dan Nurhadi Siswanto 3) 1)Jurusan teknik Industri, Fakultas Teknologi Industri, Institut Teknologi Sepuluh Nopember Jl. Arief Rahman Hakim, Surabaya 60111 E-mail: [email protected] 2, 3)Jurusan teknik Industri, Fakultas Teknologi Industri, Institut Teknologi Sepuluh Nopember ABSTRAK Tata letak fasilitas merupakan permasalahan penempatan fasilitas pada suatu area atau lantai produksi. Dalam dunia nyata, fasilitas-fasilitas yang akan disusun mempunyai dimensi yang berbeda-beda (unequal area). Penyelesaian permasalahan ini dengan menggunakan algoritma eksak hanya mampu untuk 11 fasilitas saja dan akan menjadi rumit ketika fasilitas yang akan disusun semakin banyak. Untuk itu diperlukan metode pencarian yang efektif untuk menyelesaikan permasalahan tersebut. Pada penelitian ini digunakan algoritma Differential Evolution (DE) yang dipadukan Flexible Bay Structure (FBS) dengan fungsi tujuan meminimasi total biaya perpindahan material. Hasil dari penelitian ini menunjukan bahwa solusi yang dihasilkan algoritma DE cukup bagus dengan menghasilkan 5 solusi optimal dari 11 dataset. Untuk itu memperbaiki kekurangan tersebut, Algoritma DE digabungkan dengan teknik Local Search (DE-LS) dan Particle Swarm Optimization (DEPSO). Algoritma DE-LS memberikan hasil yang tidak jauh berbeda dengan yang dihasilkan oleh DE asli. Sedangkan algoritma DEPSO mampu memberikan solusi yang lebih bagus dari algoritma DE, dibuktikan dengan algoritma ini mampu memberikan solusi optimal pada 6 dataset dari 8 dataset yang digunakan untuk pengujian. Kata kunci: Tata Letak Fasilitas, Uneqal Area, Differential Evolution, Perpindahan Material, Flexible Bay Structure

PENDAHULAN Fasilitas, menurut Heragu (2008) didefinisikan sebagai bangunan yang digunakan sebagai tempat mesin, material maupun bahan-bahan yang lain untuk membuat produk atau menyediakan jasa. Fasilitas-fasilitas ini perlu untuk disusun sedemikian rupa sehingga bisa memenuhi tujuan dari perusahaan. Tata letak fasilitas adalah permasalahan menempatkan fasilitas dalam perusahaan dengan tujuan mendapatkan susunan yang paling efektif dengan mempertimbangkan kriteria atau tujuan tertentu dan juga batasan tertentu (Kouvelis; dkk, 1992). Unequal Area Facility Layout Problem (UAFLP) adalah salah satu formulasi model dari tata letak fasilitas yang mempertimbangkan ukuran dari fasilitas yang akan disusun. Model ini diformulasikan untuk menyusun fasilitas yang berbentuk rectangular dengan dimensi yang berbeda-beda, dengan ketentuan semua fasilitas harus ditempatkan dalam plant layout dan semua fasilitas tidak boleh overlap antara satu dengan yang lain (Amour & Buffa, ISBN : 978-602-97491-9-9 A-5-1


1963). Tujuan dari UAFLP adalah menempatkan fasilitas dalam suatu area sehingga tujuan yang diinginkan bisa tercapai, misalnya: minimasi biaya perpindahan material, minimasi penggunaan area fasilitas, dsb. Penyelesaian UAFLP dengan menggunakan metode eksak hanya mampu sampai 11 fasilitas saja, dan akan membutuhkan waktu yang semakin lama ketika jumlah fasilitas yang akan disusun bertambah. Penyelesaian untuk permasalahan yang lebih kompleks para peneliti banyak menggunakan metode metaheuristik. Dari semua teknik yang sudah digunakan, Genetic Algorithm yang paling banyak dipakai oleh para peneliti dan tidak ada teknik yang lebih unggul mutlak dibanding dengan yang lain. Namun belum pernah ada penelitian yang menggunakan Algoritma Differential Evolution untuk menyelesaikan permasalahan UAFLP. Dalam menyelesaikan tata letak fasilitas juga diperlukan algoritma untuk menyusun fasilitas-fasilitas pada suatu area. Ada beberapa cara untuk menyusun fasilitas, salah satu diantaranya adalah Flexible bay structure (FBS). Pada penelitian ini akan mencoba menggunakan algoritma Differential Evolution (DE) untuk menyelesaikan permasalahan UAFLP dengan metode penyusunan menggunakan Flexible bay structure (FBS). UNEQUAL AREA FACILITY LAYOUT PROBLEM (UAFLP) Unequal Area Facility Layout Problem (UAFLP) adalah salah satu dari formulasi tata letak fasilitas yang pertama kali ditemukan oleh Armour dan Buffa (1963). UAFLP ini termasuk dalam kategori layout dengan bentuk regular shape. Fasilitas yang akan disusun mempunyai bentuk rectangular dengan dimensi tetap (fix dimension) dan mempunyai ukuran berbeda satu dengan yang lainnya. Hubungan antar fasilitas seperti frekuensi perpindahan material dan biaya perpindahan antar fasilitas pada permasalahan UAFLP ini diasumsikan diketahui. Tujuanya adalah untuk meminimumkan biaya perpindahan material. Gambar 1 menunjukan Ilustrasi dari permasalahan layout dengan luas area yang berbeda.

Gambar 1. Ilustrasi Variabel dan Parameter Multirow Layout Problem dengan Luas Area yang Berbeda (Heragu, 2008).

Dimana: = jumlah departemen = notasi departemen, 1, 2 ,3, …, n = aliran material dari departemen i ke j = panjang departemen i = lebar departemen i = jarak departemen i pada sumbu-x ISBN : 978-602-97491-9-9 A-5-2


= jarak departemen i pada sumbu-y = jarak clearance horizontal dept i ke j = jarak clearance vertikal dept i ke j

ℎ

Fungsi tujuan: ∑ ∑ (

−

Fungsi pembatas: − + ≥ (2) −

1−

+

+ +

1− (3)

≥

=0

( )= −

+ ℎ +

)

1, 0,

∀( , )

+

(1)

∀( , )

(4)

Supaya Permasalahan UAFLP ini lebih memberikan hasil yang realistis, Camp; dkk (1991) menambahkan Maximum Aspect Ratio. Hal ini dimaksudkan agar fasilitas yang akan disusun tidak terlalu sempit. Dengan adanya maksimum aspect ratio ini ukuran dari fasilitas menjadi lebih terbatas .

=

{

{

,

,

}

(5)

}

Dimana: = maximum aspect rasio = panjang fasilitas ke i = lebar fasilitas ke i Perhitungan jarak antar fasilitas dihitung dengan rectilinear. = − + − (6) DIFFERENTIAL EVOLUTION DE pertama kali diperkenalkan oleh Storn dan Price (1995) sebagai metode penyelesaian permasalahan optimasi kontinyu yang berdasarkan populasi (population-based) stokastik. Tahapan DE menurut Santosa dan Willy (2011) adalah sebagai berikut:  Inisialisasi  Membangkitkan nilai parameter  Menentukan batas atas dan batas bawah  Untuk pembangkitan nilai awal variabel generasi ke 0, variabel ke j dan vektor i bisa diwakili dengan notasi berikut: + ( , 1)( − ) ,, = (7)

ISBN : 978-602-97491-9-9 A-5-3


Fasilitas Random

1 0.9

2 0.2

3 0.7

4 0.5

5 0.8

6 0.1

0.1 6

0.2 2

0.5 4

0.7 3

0.8 5

0.9 1

For i=1:jumlah populasi x(i,:)=lb+(ub-lb)*rand Urutan = sort (x,2) End

Gambar 2. Pembentukan Urutan Solusi dengan Pembangkitan Bilangan Random



Mutasi Setelah diinisialisasi, DE akan memutasi dan mengkombinasi populasi awal untuk menghasilkan populasi dengan ukuran N vektor percobaan. Dalam DE, mutasi dilakukan dengan cara menambahkan perbedaan dua vektor terhadap vektor ketiga dengan cara: (8) , = , + ( , − , ) F = Faktor skala (F ∈ (0, 1+)) Beberapa peneliti lain juga menerapkan cara mutasi yang sedikit diubah dari cara awal seperti yang dikemukakan oleh Storn dan Price (Ali,dkk, 2009). DE/rand/1: , = , + ( , − , ) (9) DE/rand/2: , = + ( , − , + , − , , ) (10) DE/best/1: , = (11) , + ( , − , )



DE/best/2: , = + ( , − , + , − , , ) (12) DE/rand-to-best/1: , = + ( , − , + , − , , ) (13) Crossover Pada tahap ini DE menyilangkan setiap vektor, , , dengan vektor mutan, membentuk vektor hasil persilangan, , dengan formula. ,,

=

(14)



,,

,

, untuk

,,

Probabilitas crossover, Cr ∈ (0, 1) adalah nilai yang dideﬁnisikan untuk mengendalikan fraksi nilai variabel yang disalin dari mutan.

Seleksi Jika trial vektor, u , ,, mempunyai nilai fungsi tujuan yang lebih kecil dari fungsi tujuan vektor targetnya, x , , maka u , , akan menggantikan posisi x , , dalam populasi pada generasi berikutnya. Jika terjadi sebaliknya, vektor target akan tetap pada posisinya dalam populasi.

ISBN : 978-602-97491-9-9 A-5-4


,,



=

(

,,

,,

,,

)≤ (

)

,,

(15)

Kriteria Pemberhentian (Stopping Criteria) Apabila sudah memenuhi kriteria pemberhentian maka bisa di hentikan, namun jika belum ulangi dari tahap mutasi.

FLEXIBLE BAY STRUCTURE Flexible bay structure (FBS) merupakan cara penempatan fasilitas pada suatu area dengan membagi area menjadi kolom-kolom vertikal ataupun horizontal. Setelah area dibagi dalam bentuk kolom-kolom, selanjutnya menempatkan fasilitas pada kolom tersebut. Jumlah kolom yang terbentuk juga flekisbel (Komarudin, 2010). Pada FBS, setiap solusi yang dihasilkan dari teknik optimasi mempunyai dua segmen, segmen yang pertama menunjukan urutan dari fasilitas sebanyak n, sedangkan segmen yang kedua menunjukan kapan fasilitas yang disusun tersebut berpindah kolom sebanyak n-1. Gambar 3 merupakan ilustrasi flexible bay structure.

5

2

1

3

4 6 susunan fasilitas

Gambar 3. Flexible Bay Structure

PENGUJIAN DATASET Dataset permasalahan Unequal Area Facility Layout Problem (UAFLP) ini terdiri dari sejumlah departemen yang sudah diketahui luasnya, namun tidak diketahui dimensinya secara pasti (unfixed dimension), untuk menjaga agar departemen yang terbentuk tidak terlalu sempit maka digunakan aspect ratio. Tabel 1. Dataset Penelitian Facility Size

No

Problem Set

Number of Departments

Width

Height

1 2 3 4 5 6 7 8 9 10 11

O7 FO7 FO8 O9 V10a V10s BA12 BA14 M25 SC30 SC35

7 7 8 9 10 10 12 14 25 30 35

8.54 8.54 11.31 12 25 25 7 6 15 12 15

13 13 13 13 51 51 9 10 15 15 16

ISBN : 978-602-97491-9-9 A-5-5

Common Shape Constraint max = 4 max = 5 max = 5 max = 5 lmin = 5 max = 5 lmin = 1 lmin = 1 max = 5 max = 5 max = 4

Reference data set Meller et al. (1998) Meller et al. (1998) Meller et al. (1998) Meller et al. (1998) van Camp (1989) van Camp (1989) van Camp (1989) van Camp (1989) Bozer et al. (1994) Liu and Meller (2007) Liu and Meller (2007)


Dari Tabel 2 bisa diketahui bahwa algoritma DE mampu mendapatkan nilai yang lebih baik pada 5 dataset, sedangkan untuk 6 dataset yang lain algoritma ini masih kalah dibanding dengan penelitian sebelumnya. Untuk dataset ukuran kecil (7-9 fasilitas), algoritma DE unggul pada dataset O7 dan FO7, namun kurang baik pada dataset FO8 dan O9. Untuk data ukuran sedang (10-14 fasilitas), algoritma DE unggul hanya pada dataset V10s, sedangkan untuk data V10a, BA12, dan BA14, biaya perpindahan material yang dihasilkan algoritma DE masih kalah. Untuk data ukuran besar (25-35 fasilitas), algoritma DE unggul pada dataset M25 dan SC35. Dari hasil percobaan terhadap dataset, bisa diketahui bahwa algoritma DE tidak unggul mutlak pada data set ukuran kecil, sedang dan besar. Algoritma DE ini pun juga bisa dikatakan tidak terlalu buruk dalam menemukan solusi, sebab DE mampu menemukan solusi 5 dari sebelas dataset . Kelebihan dari algoritma DE adalah kemampuannya dalam melakukan pencarian yang cepat dan handal, namun ada kemungkinan terjebak pada lokal optimal. Pada dataset permasalahan UAFLP ini ada kemungkinan hal sama juga terjadi. Lokal optimal kemungkinan terjadi karena proses mutasi algoritma DE ini tidak mampu menghasilkan kombinasi solusi yang berbeda dari solusi sebelumnya, sehingga solusi yang dihasilkan sama seperti iterasi sebelumnya. Misal dari individu (0,2; 0,8; 0,5) menghasilkan urutan (1-3-2), kemudian dilakukan mutasi sebagai berikut. , = , + ( , − , ) 0.2 0.9 0.5 0.32 = 0.8 + 0.3 0.5 − 0.1 = 0.92 0.5 0.3 0.8 0.35

Maka hasil dari mutasi (0.32; 0,92; 0,35) akan menghasilkan urutan (1-3-2). Tabel 2. Hasil Pengujian Dataset No 1 2 3 4 5 6 7 8 9 10 11

Dataset O7 FO7 FO8 O9 V10a V10s BA12 BA14 M25 SC30 SC35

x worst 141.88 21.929 32.788 288.3754 2.69E+04 2.47E+04 1.00E+04 5.63E+03 1.30E+03 4.22E+03 4.35E+03

x mean 136.53 20.634 25.4115 269.692 2.53E+04 2.18E+04 9.71E+03 5.44E+03 1.16E+03 4.08E+03 4.07E+03

x best 130.14 19.225 22.4809 246.508 2.28E+04 1.95E+04 8.95E+03 5.09E+03 1.04E+03 3.71E+03 3.83E+03

Best Known 132 20.73 22.31 235.95 21463.07 19994.1 8180 4712.33 1496.42 3679.85 3962.72

%gap 1.409091 7.26001 -0.76602 -4.47468 -6.43864 2.391205 -9.38875 -7.94023 30.5008 -0.71878 3.475391

Computation Time 1.485 1.29 1.383 1.3837 1.483 3.5397 3.7269 4.0264 5.0794 5.3976 6.0638

ALGORITMA ALTERNATIF Kemampuan algoritma DE untuk melakukan pencarian yang cepat ada kemungkinan terjebak pada kondis local optimal. Untuk memperbaiki solusi yang dihasilkan, algoritma DE selanjutnya dimodifikasi dengan diharapkan mampu menghasilkan solusi yang lebih baik dari DE-asli yang sebelumnya. Modifikasi yang dilakukan meliputi dua cara, yaitu: Hybrid DE-Particle Swarm Optimization (DEPSO) Particle Swarm Optimization (PSO) adalah sebuah teknik stochastic optimization berdasarkan populasi yang terinspirasi oleh perilaku sosial dari pergerakan burung atau ikan (bird flocking or fish schooling). ). PSO digolongkan ke dalam teknik ISBN : 978-602-97491-9-9 A-5-6


metaheuristik optimasi swarm intelligence (SI) di mana prinsip sosio-psikologi yang mempengaruhi perilaku sosial makhluk hidup diadopsi. Perilaku sosial terdiri dari tindakan individu dan pengaruh dari individu-individu lain dalam suatu kelompok (Santosa dan Willy, 2010). Dalam konteks optimasi , setiap individu dalam populasi terletak pada suatu ruang tertentu dan masing-masing memiliki posisi juga kecepatan. Jika ada individu yang mampu menghasilkan nilai lebih baik, maka individu lain yang memiliki nilai kurang baik akan mendekat (update posisi) sesuai dengan kecepatannya. Dalam bentuk matematis, update posisi dan kecepatan dari setiap individu bisa digambarkan pada formulasi = ℎ ∗ + 1∗( − ) + 2( − ) (16) = + (17)

DE membutuhkan waktu komputasi yang lebih sedikit (cepat), lebih bagus dalam mencari solusi pada permasalahan skala besar. Sedangkan PSO bagus dalam keluar dari jebakan lokal optimal. Dua keuntungan dari algoritma ini akan coba digabungkan. Penggabungan dilakukan atau penggunaan update posisi dilakukan pada proses crossover sebagai pilihan jika mutan yang dihasilkan tidak memenuhi kriteria crossover. Hybrid PSO Set parameter (np, F, CR, itmax) Inisialisasi For it<=itmax Mutasi ( 1, − 1 = 0, + Crossover

2,

)

r=rand

Seleksi It=it+1 End

If r < CR Crossover=mutan Else PSO (update velocity dan posisi) = ℎ ∗ + 1∗ ( − ) + 2( − ) = + End

Hybrid DE-Local Search (DE-LS) Modifikasi dilakukan pada proses mutasi dan menambahkan pencarian lokal . Penggunaan local search bertujuan untuk mendapatkan nilai solusi yang lebih beragam lagi. Dari Tabel 3 bisa diketahui bahwa algoritma DE-LS dan DEPSO yang diujikan pada dataset UAFLP, tidak unggul mutlak dibanding penelitian sebelumnya, tetapi setidaknya lebih baik dibanding dengan biaya perpindahan material yang dihasilkan oleh algoritma DE-asli. Bila dibandingkan dengan hasil terbaik yang diperoleh pada penelitian terdahulu, algoritma DE-LS masih kurang bagus pada tiga data set (O9, V10a, dan SC30). Sedangkan algoritma DEPSO masih kurang bagus hanya pada dua dataset (O9 dan V10a). Penyebab dari kelemahan DE-LS kemungkinan juga sama seperti yang terjadi pada DE asli, yaitu terjebak pada kondisi lokal optimal. sebab individu yang digunakan DE-LS sama dengan individu DE asli, hanya saja urutan penempatannya yang dibalik.

ISBN : 978-602-97491-9-9 A-5-7


Modifikasi mutasi DE/rand/1: = DE/rand-to-best/1: + ( , − , Mutan : = +

,

+ (

=

) (1 − ) ,

,

−

,

,

+

)

,

−

Local search 1. Mengubah urutan bilangan random dari kecil ke besar menjadi besar ke kecil Sort (random, 2, ‘ascend’)  sort (random, 2, ‘descend’) 2. Mengubah urutan pergantian baris. Dari 0 menjadi 1, begitu juga sebaliknya 00010101110101

Tabel 3. Perbandingan Hasil DE, DE_LS dan DEPSO terhadap Nilai Terbaik Data Set O7 FO7 FO8 O9 V10a M25 SC30 SC35

Best known 132 20.73 22.31 235.95 21463.07 1496.42 3679.85 3962.72

DE(%) 130.14 19.225 22.368 246.508 2.28E+04 1.22E+03 3.71E+03 3.83E+03

DE-LS (%) 131.5942 0.31 19.51 5.89 21.447 3.87 245.675 -4.12 2.39E+04 -11.36 1.17E+03 21.77 3.80E+03 -3.36 3.93E+03 0.94

1.41 7.26 -0.26 -4.47 -6.44 18.49 -0.72 3.48

DEPSO (%) 128.043 3.00 18.59 10.32 21.918 1.76 241.4928 -2.35 2.22E+04 -3.38 1.11E+03 25.84 3.63E+03 1.33 3.61E+03 8.93

Modifikasi algoritma DE dengan menambahkan pencarian lokal dan update posisi akan membuat waktu komputasi yang dibutuhkan untuk menyelesaikan program juga bertambah. Tabel 4 menunjukan perbandingan waktu yang diperlukan oleh algoritma DE asli, DE_LS dan DEPSO untuk menyelesaikan program. Dari kedua Tabel 3 dan tersebut menunjukan bahwa modifikasi DE dengan menambahkan update posisi didalamnya akan membuat hasil yang dicapai lebih baik dari DE asli, tetapi modifikasi ini juga membuat waktu komputasi semakin bertambah. Sedangkan modifikasi DE dengan pencarian lokal tidak terlalu berpengaruh pada hasil pencarian, sebab individu yang digunakan dalam pencarian lokal bukanlah individu yang berbeda dari hasil mutasi, melainkan individu yang sama, hanya saja urutan penempatanya yang dibalik. Waktu yang dibutuhkan pun lebih lama dibanding dengan DE asli. Sehingga modifikasi DE dengan pencarian lokal bisa dikatakan tidak lebih baik dibanding DE asli. Tabel 4. Perbandingan Waktu Komputasi Dataset O7 FO7 FO8 O9 V10a M25 SC30 SC35

DE 1.485 1.29 1.383 1.3837 1.483 5.0794 5.3976 6.0638

DE-LS 1.59 1.58 1.435 1.59 13.25 4.625 5.297 5.91

ISBN : 978-602-97491-9-9 A-5-8

DEPSO 1.8127 2.379 2.1232 2.3291 8.3726 5.5677 6.2354 6.8375


PENGARUH PARAMETER DE TERHADAP HASIL Parameter yang digunakan dalam percobaan sedikit banyak juga berpengaruh pada biaya perpindahan material handling yang dihasilkan dari algoritma DE. Parameter-parameter tersebut meliputi; nilai faktor pertumbuhan mutan (F), nilai crossover ratio (CR), serta jumlah populasi yang dibangkitkan diawal (jml_populasi). Nilai Faktor Pertumbuhan Mutan (F) Gambar 4 menunjukan pengaruh nilai F terhadap solusi yang dihasilkan. Dari gambar grafik tersebut bisa diketahui bahwa penambahan nilai parameter F tidak terlalu memberikan dampak pada pencarian solusi optimal. Hasil yang dicapai algoritma DE asli dan DE-LS pada rentang nilai F, menunjukan bahwa diawal dengan semakin bertambahnya nilai F didapatkan hasil yang semakin bagus, namun hasil bagus ini tidak terjadi terus menerus seiring dengan bertambahnya nilai F. Nilai solusi yang dihasilkan dengan menambah nilai F (dari 0.7 hingga 0.99) tidak lebih baik dari sebelumnya bahkan cenderung kurang baik.

145 140 135 130 125 0.9

0.99

0.8

0.7

0.5

0.3

DE asli 0.1

BIAYA

GRAFIK PENGARUH NILAI F

DEPSO DE-LS

F

Gambar 4. Grafik Pengaruh Nilai F Terhadap Solusi

Hasil paling mencolok untuk membuktikan tidak ada pengaruh nilai F terhadap pencarian solsusi diperlihatkan oleh algoritma DEPSO, penambahan nilai parameter F tidak memebuat solusi yang dihasilkan oleh algoritma DEPSO menjadi lebih baik dari sebelumnya. Jadi bisa disimpulkan perubahan nilai parameter F tidak memberikan dampak yang cukup berarti pada pencarian solusi, namun parameter ini harus tetap dibutuhkan untuk proses mutasi. Nilai Crossover Ratio (CR) Nilai CR berpengaruh pada probabilitas diterima atau tidaknya hasil mutasi, jika nilai CR yang digunakan besar maka akan membuat probabilitas mutan diterima semakin besar, yang artinya akan semakin besar tercipta peluang timbulnya individu baru yang berbeda dari sebelumnya, sehingga diharapkan segera didapatkan solusi yang optimal dari adanya individu yang semakin beragam tersebut.

Biaya

Grafik pengaruh CR 150 100

DE asli 0.1 0.3 0.5 0.7 0.9 0.99

DEPSO

Crossover Ratio

DE-LS

Gambar 5. Grafik Pengaruh CR Terhadap Solusi

ISBN : 978-602-97491-9-9 A-5-9


Gambar 5 menunjukan dengan semakin bertambahnya nilai CR membuat solsui yang dihasilkan semakin bagus. Pengaruh ini lebih terasa pada algoritma DE asli dan DE-LS, sebab pada kedua algoritma ini hanya mendapatkan nilai individu baru yang berasal dari mutasi. Sedangkan pada DEPSO, selain berasal dari mutasi, individu baru juga bisa diperoleh daro proses update posisi yang ditambahkan dan inilah yang membuat algoritma CR mampu menemukan solusi yang bagus pada nilai CR berapapun. Sehingga bisa dikatakan bahwa kelemahan proses crossover pada DE bisa diatasi dengan menambahkan proses update posisi (DEPSO). Jumlah Populasi Hasil dari percobaan tersebut terhadap ketiga algoritma menunjukan tren yang sama, bahwa semakin besar jumlah populasi yang dibangkitkan akan membuat algoritma semakin muda menemukan solusi yang optimal. Namun jika jumlah populasi terus ditambah solusi yang didapatkan akan mengurucut pada satu titik solusi optimal yang tetap atau solusi tidak bisa semakin baik lagi, karena sudah sampai pada puncaknya. Sehingga penentuan jumlah populasi harus menjadi perhatian yang serius, sebab dengan jumlah populasi yang sedikit sulit menemukan solusi optimal, sedangkan jika populasinya banyak maka waktu komputasinya pun akan bertambah.

biaya

Grafik Populasi terhadap biaya 160 140 120 10

50

100

200

500

1000 5000

Populasi yang dibangkitkan DE asli

DEPSO

DE-LS

Gambar 6. Grafik Pengaruh Jumlah Populasi Terhadap Biaya

KESIMPULAN Kesimpulan yang bisa diambil, dari percobaan yang sudah dilakukan sebagai berikut: 1. Algoritma Differential Evolution (DE) yang dikembangkan mampu digunakan untuk menyelesaikan permasalahan Unequal Area Facility Layout Problem (UAFLP). 2. Algoritma DE kurang kompetitif untuk menyelesaikan permasalahan UAFLP, terbukti hanya mampu mendapatkan 5 hasil optimal dari 11 data set. 3. Modifikasi algoritma DE dengan menambahkan local Search pada crossover tidak memberikan solusi yang lebih baik, dan membutuhkan waktu komputasi yang lebih tinggi. 4. Modifikasi algoritma DE dengan menambahkan update posisi sebagaimana yang digunakan pada algoritma Particle Swarm Optimization (PSO), mampu memberikan hasil yang lebih baik. 5. Parameter CR dan jumlah populasi yang dibangkitkan dalam algoritma DE memberikan pengaruh pada proses pencarian solusi. Sedangkan F tidak memberikan pengarus pada pencarian solsusi. meskipun demikian keberadaan ketiga parameter ini harus tetap ada pada algoritma DE

ISBN : 978-602-97491-9-9 A-5-10


Saran untuk penelitian selanjutnya permasalahan bisa dikembangkan untuk kasus layout fasilitas dinamis (dynamic unequal area facility layout problem). pengukuran jarak bisa digunakan cara lain yang lebih mendekati kondisi sesungguhnya, dalam hal ini bisa digunakan titik input/output (I/O). Dengan semakin berkembangnya teknik metaheuristik, bisa digunakan algoritma penyelesaian yang lain, sehingga bisa menemukan solusi yang lebih baik lagi. Metode penyusunan layout bisa menggunakan cara yang berbeda, seperti Space Filling Curve (SFC) mauapun cara kontinyus yang lain. UCAPAN TERIMAKASIH Penulis menyampaikan terima kasih kepada Dosen Jurusan Teknik Industri, Fakultas Teknologi Industri, Institut Teknologi Sepuluh Nopember yang memberikan banyak dukungan dalam pelaksanaan penelitian ini. Juga seseorang yang sudah memberikan data pada penelitian ini DAFTAR PUSTAKA Ali, M; Pant, M.;& Abraham, A.; (2008),”Simplex Differential Evolution”, Vol. 6, No. 5, 2009. Armour, G..C., dan Buffa, E.S. (1963). “A Heuristic Algorithm and Simulation Approach to Relative Allocation of Facilities”, Management Science, 9(2), 294-300. Camp, D.J., Carter, M.W. dan Vannelli, A. (1991), “A Nonlinear Optimization Approach for Solving Facility Layout Problem”, European Journal of Operation Research. Vol. 57, N. 2, pp. 174-189. Heragu , S.S. (2008), Facilities Design, 3rd edition, CRC Press, New York. Hernandez, L.G; Pierreval, H.; Morrera L.S.; & Azofra, A.A.(2013),” Handling qualitative aspects in Unequal Area Facility Layout Problem:An Interactive Genetic Algorithm”, Applied Soft Computing, 13, 1718–1727. Komarudin dan Wong, K.Y.(2010), “Applying Ant System for solving Unequal Area Facility Layout Problems”, European Journal of Operational Research, Vol. 202, N. 3, pp. 730-746. Konak, A., Kulturel-Konak, S., Norman, B.A., dan Smith, A.E. (2006), “A New Mixed Integer Formulation for Optimal Facility Layout Design”, Operation Research Letters. 34(6), 660-672. Konak, S.K dan Ulutas, B.H.(2012), “An Artificcial Immune System based Algorithm to Solve Unequal Area Facility Layout Problem”, Expert System with Application, 39,5384-5395. Kouvelis, P.; Kurawarwala, A.A. dan Gutiérrez, G.J.(1992), “Algorithms for Robust Single and Multiple Period Layout Planning for Manufacturing Systems, European Journal of Production Research, Vol. 63, pp. 287-303. Kushida, J. I; Oba, K. dan Hara, A. (2012), “Solving Quadratic Assignment Problem by Differential Evolution”, Departement of Intelegent System, Hiroshima City University, Hiroshima, Japan. Meller, R. D., Narayanan, V., dan Vance, P. H. (1999), “Optimal Facility Layout Design”, Operations Research Letters, 23(3–5), 117–127. ISBN : 978-602-97491-9-9 A-5-11


Meller, R. D., Chen, W. dan Sherali, H.D.(2007), “Applying the Sequence Pair Representation to Optimal Facility Layout Problems”, Operations Research Letters, Vol. 35, N. 5, pp. 651-659. Santosa, B. dan Willy, P.(2011), “Metoda Metaheuristik Konsep dan Implementasi”, Guna Widya, Surabaya. Storn, R. dan Price, K.(1995), “Differential Evolution - a Simple and Efficient Adaptive Scheme for Global Optimization Over Continuous Spaces, Technical Report TR-95012, ICSI. Van Camp, D. J. (1989). A Nonlinear Optimization Approach for Solving Facility Layout Problem. Master of Applied Science, Department of Industrial Engineering, University of Toronto, Canada.

ISBN : 978-602-97491-9-9 A-5-12

Prosiding Seminar Nasional Manajemen Teknologi XX Program Studi MMT-ITS, Surabaya 1 Februari 2014

Recommend Documents