its-undergraduate-7662-5205100012-penerapan algoritma genetika gen dominan pada penjadwalan fms...

TUGAS AKHIR CF 1380

PENERAPAN ALGORITMA GENETIKA GEN DOMINAN PADA PENJADWALAN FMS TERDISTRIBUSI DENGAN BATASAN MAINTENANCE BARKHAH PUDYA PERMANA NRP 5205 100 012 Dosen Pembimbing Mahendrawathi Er, S.T, M.Sc, Ph.D Rully Soelaiman, S.Kom, M.Kom JURUSAN SISTEM INFORMASI Fakultas Teknologi Informasi Institut Teknologi Sepuluh Nopember

Surabaya 2009

ii

FINAL PROJECT CF 1380

AN IMPLEMENTATION OF GENETIC ALGORITHM DOMINANT GENE FOR DISTRIBUTED FMS SCHEDULING PROBLEMS SUBJECT TO MAINTENANCE BARKHAH PUDYA PERMANA NRP 5205 100 012 SUPERVISOR Mahendrawathi Er, S.T, M.Sc, Ph.D Rully Soelaiman, S.Kom, M.Kom INFORMATION SYSTEM DEPARTMENT Information Technology Faculty Institut Teknologi Sepuluh Nopember

Surabaya 2009

i

PENERAPAN ALGORITMA GENETIKA GEN

DOMINAN PADA PENJADWALAN FMS

TERDISTRIBUSI DENGAN BATASAN

MAINTENANCE

TUGAS AKHIR

Disusun Untuk Memenuhi Salah Satu Syarat

Memperoleh Gelar Sarjana Komputer

pada

Jurusan Sistem Informasi

Fakultas Teknologi Informasi

Institut Teknologi Sepuluh Nopember

Oleh:

BARKHAH PUDYA PERMANA

5205 100 012

Surabaya, Juli 2009

KETUA

JURUSAN SISTEM INFORMASI

Ir. A. HOLIL NOOR ALI M.KOM

NIP 131 996 150

ii

Halaman ini sengaja dikosongkan

iii

PENERAPAN ALGORITMA GENETIKA GEN

DOMINAN PADA PENJADWALAN FMS

TERDISTRIBUSI DENGAN BATASAN

MAINTENANCE

TUGAS AKHIR

Disusun Untuk Memenuhi Salah Satu Syarat

Memperoleh Gelar Sarjana Komputer

pada

Jurusan Sistem Informasi

Fakultas Teknologi Informasi

Institut Teknologi Sepuluh Nopember

Oleh:

BARKHAH PUDYA PERMANA

5205 100 012

Disetujui Tim Penguji : Tanggal Ujian : 9 Juli 2009

Periode Wisuda : Oktober 2009

Mahendrawathi ER, S.T, M.Sc, Ph.D (Pembimbing I)

Rully Soelaiman S.Kom, M.Kom (Pembimbing II)

Bekti Cahyo, S.Si, M.Kom (Penguji 1)

Ahmad Mukhlashon, S.Kom (Penguji 2)

iv


v

PENERAPAN ALGORITMA GENETIKA GEN DOMINAN PADA

PENJADWALAN FMS TERDISTRIBUSI DENGAN BATASAN

MAINTENANCE

Nama Mahasiswa : BARKHAH PUDYA PERMANA

NRP : 5205 100 0012 Jurusan : SISTEM INFORMASI FTIF-ITS

Dosen Pembimbing : MAHENDRAWATHI Er, Ph.D

RULLY SOELAIMAN, S.Kom, M.Kom

Abstrak

Mesin produksi adalah salah satu sumber daya pada proses produksi yang harus

dimanfaatkan secara optimal. Pada umumnya jadwal disusun tanpa memperhatikan

perawatan mesin, akibatnya kinerja mesin selama menjalankan jadwal produksi

mengalami penurunan. Hal ini berakibat pada kualitas produk yang dihasilkan. Jika

perawatan (maintenance) mesin dijalankan selama penjadwalan, proses penjadwalan

produksi akan terganggu sehingga makespan optimal tidak akan dapat dicapai.

Tugas Akhir ini mencoba mengintegrasikan perawatan (maintenance) mesin pada

penjadwalan FMS terdistrbusi dengan pendekatan Algoritma Genetika Gen Dominan

(GADG) dan Strategi Evolusi Adaptif untuk memperoleh makespan yang optimal.

GADG menunjukkan performa yang baik ketika penjadwalan yang mempertimbangkan

maintenance dijalankan. GADG lebih optimal dibandingkan penjadwalan yang memaksa

mesin menjalani maintenance pada batas waktu usia mesin maksimum (M) yang diijinkan

bagi mesin untuk tidak menjalani maintenance.

Kata Kunci: FMS, Algoritma Genetika, Penjadwalan Terdistribusi, Evolusi Adaptif,

Maintenance

vi


vii

AN IMPLEMENTATION OF GENETIC ALGORITHM DOMINANT

GENE FOR DISTRIBUTED FMS SCHEDULING PROBLEMS

SUBJECT TO MAINTENANCE

Name : BARKHAH PUDYA PERMANA

NRP : 5205 100 012

Departement : INFORMATION SYSTEM FTIF-ITS

Supervisor : MAHENDRAWATHI Er, Ph.D

RULLY SOELAIMAN, S.Kom, M.Kom

Abstract

Machines are one of the production resources which have to be used optimally. In

General, schedule is arranged without maintenance consideration, finally machine

performance will be down during production process. It will affect its outcome quality.

Scheduling will be disturbed if machines are forced to be maintained during this process.

This final project try to integrate management of machine maintenance into Distributed

FMS Scheduling Problem using Genetic Algorithm Dominant Gene (GADG) and

Adaptive Evolution Strategy approaches to get optimal makespan

GADG shows good performance while maintenance consideration scheduling is ran.

GADG is more optimal than scheduling by forcing maintenance at maximum age (M) that

is allowed for machines running without maintenance

Key words: FMS, Genetic Algorithm, Distributed Scheduling, Adaptive Evolution,

Maintenance

viii


ix

KATA PENGANTAR

Alhamdulillaahirobbil aalamiin. Allahumma shollialaa Muhammad, wa alaa aali

sayyidina Muhammad. Tiada Dzat yang Maha Perkasa yang mampu menolong selain

Allah SWT sehingga penulis dapat menyelesaikan buku tugas akhir dengan judul:

PENERAPAN ALGORITMA GENETIKA GEN DOMINAN PADA

PENJADWALAN FMS TERDISTRIBUSI DENGAN BATASAN MAINTENANCE

yang merupakan salah satu syarat kelulusan pada Jurusan Sistem Informasi, Fakultas

Teknologi Informasi, Institut Teknologi Sepuluh Nopember Surabaya.

Terima kasih atas pihak-pihak yang telah mendukung, memberikan saran, motivasi,

semangat, bantuan baik materi maupun spiritual demi tercapainya tujuan pembuatan

tugas akhir ini. Secara khusus penulis akan menyampaikan ucapan terima kasih yang

sedalam-dalamnya kepada:

1) Almarhum dan almarhumah ayah dan ibu yang telah merawat, memberikan kasih sayang, doa, mengenalkan kepada Sang Kholiq, dan memberikan pendidikan agama

sehingga bekal-bekal tadi mampu memberikan dorongan spiritual dalam

penyelesaian karya Tugas Akhir ini.

2) Semua keluarga yang memberikan dukungan baik secara moril maupun materil demi tercapainya Tugas Akhir ini.

3) Ibu Mahendrawati ER. Ph.D dan Bapak Rully Soelaiman, S.Kom M.Kom selaku dosen pembimbing yang memberikan petunjuk dan motivasi untuk kelancaran Tugas

Akhir ini.

4) Bapak Ir. A. Holil Noor Ali M.Kom yang berkenan menjadi dosen wali penulis selama menempuh pendidikan di Jurusan Sistem Informasi ITS

5) Adik penulis, Fitri Linawati yang telah sabar menemani, menghibur, serta mendoakan penulis selama proses pengerjaan Tugas Akhir. Semoga Allah SWT tetap

melimpahkan rahmat-Nya.

6) Sahabat-sahabat penulis: Muhammad Mujahidillah, Dhanika Budhi A, Andre Parvian, Aghita Sekarrini Y, Riska Asriana S, Risti Anggraini, Adya Husni M,

Fathcy Nurhidayati, Winda Zulfina, Diana Wenny P, Arif Rakhman, Rama Catur

serta teman-teman seperjuangan penghuni Laboratorium Tugas Akhir. Terima kasih

atas semua doa dan dukungannnya.

7) Seluruh dosen pengajar beserta staf dan karyawan di Jurusan Sistem Informasi, FTIF ITS Surabaya yang telah memberikan ilmu dan bantuan kepada penulis selama ini.

8) Rekan-rekan mahasiswa Jurusan Sistem Informasi, SHOGUN 2003, NARSIIS 2004, PHOENIC 2005, ANONIMS 2006, GENESIS 2007, dan mahasiswa angkatan 2008

atas semua bantuan ketika penulis kuliah di Sistem Informasi.

9) Saudara-saudara seiman, seaqidah serta semua pihak yang telah membantu dalam pengerjaan Tugas Akhir ini yang belum mampu penulis sebutkan diatas.

x

Terima kasih atas segala bantuan, dukungan, serta doanya. Semoga Allah SWT

senantiasa melimpahkan rahmat hidayah serta membalas kebaikan-kebaikan yang telah

diberikan kepada penulis.

Surabaya, 23 April 2009

Penulis

xi

DAFTAR ISI

Abstrak ................................................................................................................................. v KATA PENGANTAR ........................................................................................................ ix DAFTAR ISI....................................................................................................................... xi DAFTAR GAMBAR ....................................................................................................... xiii DAFTAR TABEL.............................................................................................................. xv BAB I PENDAHULUAN ................................................................................................. 17

1.1. Latar Belakang ..................................................................................................... 17 1.2. Rumusan permasalahan ....................................................................................... 18 1.3. Batasan Permasalahan ......................................................................................... 19 1.4. Tujuan .................................................................................................................. 19 1.5. Manfaat ................................................................................................................ 19 1.6. Sistematika Penulisan .......................................................................................... 19

BAB II TINJAUAN PUSTAKA ...................................................................................... 21 2.1. Penjadwalan Terdistribusi ................................................................................... 21 2.2. Flexible Manufacturing System (FMS) ............................................................... 21

2.2.1. Pengertian FMS ............................................................................................ 22 2.2.2. Komponen-komponen FMS ......................................................................... 22 2.2.3. Perbandingan FMS dengan Sistem Manufaktur lainnya .............................. 24 2.2.4. Penjadwalan FMS ......................................................................................... 25 2.2.5. Tantangan yang Dihadapi dalam Implementasi FMS .................................. 26

2.3. Algoritma Genetika ............................................................................................. 26 2.3.1. Gambaran Umum Tentang Algoritma Genetika .......................................... 26 2.3.2. Sejarah Algoritma Genetika ......................................................................... 28 2.3.3. Teori Dasar Algoritma Genetika .................................................................. 29 2.3.4. Proses-proses pada Algoritma Genetika ....................................................... 32 2.3.5. Perbedaan Algoritma Genetika dengan Metode Heuristik Lain ................... 38 2.3.6. Keunggulan Algoritma Genetika .................................................................. 39

2.4. Strategi Evolusi Adaptif ...................................................................................... 39 BAB III METODOLOGI PENELITIAN ......................................................................... 41 BAB IV PEMBAHASAN MODEL ................................................................................. 45

4.1. Diskripsi Permasalahan ....................................................................................... 45 4.2. GADG untuk Permasalahan Penjadwalan FMS Terdistribusi dengan Batasan

Maintenance......................................................................................................... 47 4.2.1. Pengodean Kromosom .................................................................................. 47 4.2.2. Gen Dominan ................................................................................................ 48 4.2.3. Pindah Silang (Crossover) ............................................................................ 48 4.2.4. Mutasi (Mutation) ......................................................................................... 50 4.2.5. Operator Saturasi .......................................................................................... 51 4.2.6. Strategi Elitist ............................................................................................... 51

4.3. Strategi Evolusi Adaptif untuk Penjadwalan FMS Terdistribusi dengan Batasan Maintenance......................................................................................................... 52

BAB V PERANCANGAN DAN IMPLEMENTASI MODEL ....................................... 52 5.1. Penerapan Model ke Dalam Algoritma ............................................................... 53

5.1.1. Model Algoritma Genetika ........................................................................... 53 5.1.2. Algoritma Pembangkitan Populasi ............................................................... 54 5.1.3. Algoritma Evaluasi Kromosom .................................................................... 55 5.1.4. Algoritma Persilangan Genetika ................................................................... 55

xii

5.1.5. Algoritma Mutasi .......................................................................................... 57 5.1.6. Algoritma Pemeriksaan Similaritas Gen ...................................................... 58 5.1.7. Algoritma Pemberian Peringkat ................................................................... 59 5.1.8. Penerjemahan Kromosom ke dalam Jadwal ................................................. 60

5.2. Perancangan Model Perangkat Lunak ................................................................. 61 5.2.1. Diagram Use Case ........................................................................................ 61 5.2.2. Diagram Class Model ................................................................................... 62 5.2.3. Diagram Class GUI dan Controller .............................................................. 65 5.2.4. Diagram Sequence GUI dan Controller ....................................................... 66

5.3. Implementasi ke Dalam Bahasa Pemrograman Java ........................................... 67 5.3.1. Implementasi Model ..................................................................................... 67 5.3.2. Implementasi GUI dan Controller ................................................................ 78

BAB VI UJI COBA DAN ANALISA .............................................................................. 83 6.1. Lingkungan Uji Coba .......................................................................................... 83 6.2. Data Parameter Uji Coba ..................................................................................... 84 6.3. Verifikasi Keluaran Program Aplikasi ................................................................ 84 6.4. Uji Coba Pengaruh Threshold pada GADG ........................................................ 86

6.4.1. Uji Coba Pengaruh Adaptive Threshold pada Solusi Optimal yang Dihasilkan ..................................................................................................... 86

6.4.2. Analisa Hasil Uji Coba Pengaruh Adaptive Threshold ................................ 87 6.4.3. Uji Coba Prngaruh Similarity Threshold pada Solusi Optimal yang

Dihasilkan ..................................................................................................... 87 6.4.4. Analisa Hasil Uji Coba Pengaruh Similarity Threshold ............................... 88

6.5. Uji Coba Perbandingan Solusi Optimal GADG dengan Simple GA ................... 89 6.5.1. Skenario Uji Coba dengan Satu Populasi Acak ........................................... 89 6.5.2. Skenario Uji Coba dengan Menggunakan Preliminary Run ........................ 90 6.5.3. Skenario Uji Coba dengan Satu Kali Inisialisasi Populasi Acak ................. 91 6.5.4. Skenario Uji Coba dengan 30 Populasi Acak............................................... 92 6.5.5. Analisa Uji Coba Perbandingan Solusi Optimal GADG dengan Simple GA

...................................................................................................................... 93 6.6. Uji Coba GADG pada Proses Maintenance ........................................................ 94

6.6.1. Makespan Rata-rata Uji Coba 30 Populasi Acak ......................................... 94 6.6.2. Makespan Minimal Uji Coba 30 Populasi Acak .......................................... 95 6.6.3. Analisa Uji Coba GADG pada Proses Maintenance .................................... 96

BAB VII KESIMPULAN ................................................................................................. 98 7.1. Kesimpulan .......................................................................................................... 98 7.2. Saran .................................................................................................................... 98

DAFTAR PUSTAKA ....................................................................................................... 99 LAMPIRAN A PARAMETER PERMASALAHAN......................................................... 1 LAMPIRAN B HASIL UJI COBA .................................................................................... 1 LAMPIRAN C JADWAL .................................................................................................. 1 LAMPIRAN D DIAGRAM DESAIN APLIKASI ............................................................. 1

xiii

DAFTAR GAMBAR

Gambar 2.1 Skema Tata Letak Komponen-komponen FMS ........................................................ 23 Gambar 2.2 Alur Perintah dan Informasi dalam FMS .................................................................. 23 Gambar 2.3 Perbandingan FMS dengan Sistem Manufaktur Lain (Upton, 1992)......................... 25 Gambar 2.4 Bagan Pembagian Macam-macam Teknik Pencarian ............................................... 27 Gambar 2.5 Siklus Algoritma Genetika ........................................................................................ 28 Gambar 2.6 Mekanisme Sederhana Algoritma Genetika (Holland, 1975) .................................... 32 Gambar 2.7 Proses Pengodean dan Penerjemahan Kode Menghubingkan Antara Daerah Kode dan

Solusi ............................................................................................................................................ 33 Gambar 2.8 Struktur Solusi Algoritma Genetika .......................................................................... 33 Gambar 2.9 Pemetakan antara Fisibilitas dan Legalitas Solusi ..................................................... 34 Gambar 2.10 Pindahsilang dengan Satu Titik Potong ................................................................... 37 Gambar 2.11 Pindahsilang dengan Dua Titik Potong ................................................................... 38 Gambar 2.12 Mutasi Kromosom .................................................................................................. 38 Gambar 3.1 Flowchart Metodologi ............................................................................................... 43 Gambar 4.1 Skema Hipotetik Maintenance (Chan, 2006) ............................................................ 45 Gambar 4.2 Representasi Kromosom ........................................................................................... 47 Gambar 4.3 Pemilihan Jalur Alternatif dalam Penjadwalan FMS ................................................. 48 Gambar 4.4 a. Pasangan Gen Induk yang Mengalami Konflik pada Locus Gen yang Sama b.

Pasangan Gen Induk yang Mengalami Konflik dengan Nomer Job yang Sama ........................... 49 Gambar 4.5 Mekanisme Pindah Silang Tipe A ............................................................................. 49 Gambar 4.6 Mutasi dengan Mempertukarkan Posisi Locus Gen .................................................. 50 Gambar 4.7 Mutasi dengan Merubah Nomer Mesin ..................................................................... 50 Gambar 4.8 Contoh Similarity Checking ...................................................................................... 51 Gambar 5.1 Diagram Alir Representasi Algoritma Genetika pada Model .................................... 53 Gambar 5.2 Diagram Alir Pembangkitan Kromosom Bagian 1 .................................................... 54 Gambar 5.3 Diagram Alir Pembangkitan Kromosom Bagian 2 .................................................... 54 Gambar 5.4 Diagram Alir Evaluasi Kromosom ............................................................................ 55 Gambar 5.5 Diagram Alir Persilangan Genetika Bagian 1 ........................................................... 56 Gambar 5.6 Diagram Alir Persilangan Genetika Bagian 2 ........................................................... 57 Gambar 5.7 Diagram Alir Mutasi ................................................................................................. 58 Gambar 5.8 Diagram Alir Pemeriksaan Similaritas Gen Bagian 1 ............................................... 58 Gambar 5.9 Diagram Alir Pemeriksaan Similaritas Gen Bagian 2 ............................................... 59 Gambar 5.10 Diagram Alir Pemberian Peringkat Kromosom ...................................................... 59 Gambar 5.11 Diagram Use Case Perancangan Aplikasi Model .................................................... 60 Gambar 5.12 Empat Variable Class SimpGen .............................................................................. 68 Gambar 5.13 Constructor dan Method Class SimpGen................................................................ 68 Gambar 5.14 Kode Program Class DomGen ................................................................................ 68 Gambar 5.15 Kode Program Class DomGenMaint....................................................................... 69 Gambar 5.16 Kode Program Class Chromosome ......................................................................... 70 Gambar 5.17 Kode Program Class ChromDg............................................................................... 71 Gambar 5.18 Kode Program Class Evaluation ............................................................................. 71 Gambar 5.19 Kode Program Proses Generasi ............................................................................... 72 Gambar 5.20 Kode Program Method computeFitnessRangkings ................................................. 73 Gambar 5.21 Kode Program Strategi Evolusi Adaptif .................................................................. 73 Gambar 5.22 Kode Program Proses Elitist ................................................................................... 74 Gambar 5.23 Kode Program Persilangan Genetika....................................................................... 74 Gambar 5.24 Kode Program method doRandomMutation ............................................................ 74 Gambar 5.25 Kode Program Pencarian Gen-gen yang Sama Pada Method similarityChecking ... 75 Gambar 5.26 Kode Program Penyisipan Kromosom Baru pada Method similarityChecking ....... 75 Gambar 5.27 Kode Program Implementasi Algoritma Roulette Wheel pada Method selection ... 75 Gambar 5.28 Variabel-variabel pada Class GADominant ............................................................ 76

xiv

Gambar 5.29 Kode Program Method initPopulation..................................................................... 76 Gambar 5.30 Kode Program Pemeriksaan Dominasi Gen pada method Mutation1 ...................... 77 Gambar 5.31 Kode Program Pemeriksaan Dominasi Gen pada method Mutation2 ...................... 77 Gambar 5.32 Kode Program Pemeriksaan Dominasi Gen pada method Crossover ...................... 77 Gambar 5.33 Kode Program Method getFitness ........................................................................... 77 Gambar 5.34 Kode Program Class GAException ......................................................................... 78 Gambar 5.35 Antarmuka Pengaturan Data Parameter dan Input Parameter.................................. 78 Gambar 5.36 Antarmuka Pengaturan Parameter GADG .............................................................. 78 Gambar 5.37 Antarmuka Digram Batang Makespan Generasi ..................................................... 79 Gambar 5.38 Kode Program Class MainFrame ............................................................................ 79 Gambar 5.39 Kode Program Class Control .................................................................................. 80 Gambar 5.40 Kode Program Class InputControl .......................................................................... 80 Gambar 5.41 Kode Program Class radioControl .......................................................................... 80 Gambar 5.42 Tampilan Class GuiGanchart .................................................................................. 80 Gambar 5.43 Kode Program Class GuiGanchart .......................................................................... 81 Gambar 5.44 Kode Program Class MakespanGraph .................................................................... 81 Gambar 6.1 Hasil Keluaran Jadwal yang Mempertimbangkan Maintenance ................................ 85 Gambar 6.2 Diagram Batang Pengaruh Adaptive Threshold Terhadap Solusi ............................. 87 Gambar 6.3 Diagram Batang Pengaruh Similarity Threshold Terhadap Solusi ............................ 88 Gambar 6.4 Diagram Batang Makespan 50 kali Uji GADG dan GA ........................................... 90 Gambar 6.5 Diagram Batang Uji Coba GADG dan GA dengan Preliminary Run ........................ 91 Gambar 6.6 Diagram Batang Uji Coba dengan Sekali Inisialisasi Populasi acak ......................... 92 Gambar 6.7 Diagram Batang Rata-rata Makespan Uji Coba dengan 30 Populasi Acak ............... 93 Gambar 6.8 Diagram Batang Rata-rata Makespan Uji Coba 30 Populasi Acak ............................ 95 Gambar 6.9 Diagram Batang Minimum Makespan Uji Coba 30 Populasi Acak .......................... 96

xv

DAFTAR TABEL

Tabel 2.1 Istilah-istilah dalam Algoritma Genetika ...................................................................... 30 Tabel 6.1 Spesifikasi Perangkat Keras Uji Coba .......................................................................... 83 Tabel 6.2 Perangkat Lunak yang Digunakan Sebagai Alat Uji Coba ............................................ 83 Tabel 6.3 Pengaruh Adaptive Threshold Terhadap Solusi Optimal .............................................. 86 Tabel 6.4 Pengaruh Similarity Threshold Terhadap Solusi Optimal ............................................. 88 Tabel 6.5 Parameter Uji Coba yang Digunakan GADG dan GA .................................................. 89 Tabel 6.6 Data Statistik Uji Coba Berdasarkan Tabel 6.6 ............................................................. 89 Tabel 6.7 Parameter Uji Coba dengan Menggunakan Prelimary run ............................................ 90 Tabel 6.8 Data Statistik Uji Coba Berdasarkan Tabel 6.9 ............................................................. 90 Tabel 6.9 Parameter Uji Coba dengan Sekali Inisialisasi Populasi Acak ...................................... 91 Tabel 6.10 Statistik Uji Coba Berdasarkan Tabel 6.12 ................................................................. 91 Tabel 6.11 Parameter Uji Coba dengan 30 Populasi Acak ........................................................... 92 Tabel 6.12 Statistik Uji Coba Berdasarkan Tabel 6.15 ................................................................. 93 Tabel 6.13 Hasil Keseluruhan Uji Coba Perbandingan GADG dan GA ....................................... 93 Tabel 6.14 Parameter Uji Coba Maintenance ............................................................................... 94 Tabel 6.15 Statistik Rata-rata Makespan pada Uji Coba 30 Populasi Acak .................................. 95 Tabel 6.16 Statistik Minimum Makespan pada Uji Coba 30 Populasi Acak ................................. 96

xvi


its-undergraduate-7662-5205100012-penerapan algoritma genetika gen dominan pada penjadwalan fms...

Documents