-
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
Halaman ini sengaja dikosongkan
-
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
Halaman ini sengaja dikosongkan
-
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
Halaman ini sengaja dikosongkan
-
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
Halaman ini sengaja dikosongkan