ADLN Perpustakaan Universitas Airlangga
PENERAPAN FUZZY MULTI-OBJECTIVE PADA JOB SHOP SCHEDULING MENGGUNAKAN GENETIC ALGORITHM
SKRIPSI
MARISA
PROGRAM STUDI S-1 MATEMATIKA DEPARTEMEN MATEMATIKA FAKULTAS SAINS DAN TEKNOLOGI UNIVERSITAS AIRLANGGA 2012
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
PENERAPAN FUZZY MULTI-OBJECTIVE PADA JOB SHOP SCHEDULING MENGGUNAKAN GENETIC ALGORITHM
SKRIPSI
Sebagai Salah Satu Syarat untuk Memperoleh Gelar Sarjana Sains Bidang Matematika Pada Fakultas Sains dan Teknologi Universitas Airlangga
Disetujui Oleh :
Pembimbing I
Pembimbing II
Herry Suprajitno, S.Si., M.Si NIP. 19680404 199403 1 020
Auli Damayanti, S.Si, M.Si NIP . 19751107 200312 2 004
ii Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
LEMBAR PENGESAHAN NASKAH SKRIPSI Judul Penyusun Nomor Induk Tanggal Ujian
: Penerapan Fuzzy Multi-Objective Pada Job Shop Scheduling Menggunakan Genetic Algorithm : Marisa : 080810576 : 13 Agustus 2012
Disetujui oleh : Pembimbing I,
Pembimbing II,
Herry Suprajitno, S.Si., M.Si NIP.19680404 199403 1 020
Auli Damayanti, S.Si, M.Si NIP . 19751107 200312 2 004
Mengetahui, Ketua Program Studi S-1 Matematika Departemen Matematika Fakultas Sains dan Teknologi Universitas Airlangga
Dr. Miswanto, M.Si NIP. 19680204 199303 1 002
iii Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
PEDOMAN PENGGUNAAN SKRIPSI Skripsi ini tidak dipublikasikan, namun tersedia di perpustakaan dalam lingkungan Universitas Airlangga, diperkenankan untuk dipakai sebagai referensi kepustakaan, tetapi pengutipan harus seijin penulis dan harus menyebutkan sumbernya sesuai kebiasaan ilmiah. Dokumen skripsi ini merupakan hak milik Universitas Airlangga.
iv Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
PEDOMAN PENGGUNAAN SKRIPSI Skripsi ini tidak dipublikasikan, namun tersedia di perpustakaan dalam lingkungan Universitas Airlangga, diperkenankan untuk dipakai sebagai referensi kepustakaan, tetapi pengutipan harus seijin penulis dan harus menyebutkan sumbernya sesuai kebiasaan ilmiah. Dokumen skripsi ini merupakan hak milik Universitas Airlangga.
iv Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
Marisa, 2012, Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm, Skripsi ini dibawah bimbingan Dr. Herry Suprajitno, M.Si dan Auli Damayanti, S.Si., M.Si, Departemen Matematika, Fakultas Sains dan Teknologi, Universitas Airlangga, Surabaya. ABSTRAK Job Shop Scheduling Problems (JSSP) merupakan permasalahan penjadwalan n job dan m mesin yang masing-masing job terdiri dari beberapa operasi yang dilaksanakan oleh mesin yang berbeda. Secara umum, banyak faktor yang mempengaruhi JSSP, namun pada dunia kerja, faktor ketidakpastian seperti keterlambatan proses pengerjaan, dan lamanya proses pengoperasian berpengaruh dalam menentukan scheduling. Untuk mengatasi ketidakpastian tersebut, digunakan bilangan fuzzy untuk processing time dan due date. Tujuan dari skripsi ini adalah untuk menyelesaikan Fuzzy Multiobjective (Agreement Index (AI) dan Completion Time) JSSP (FMOJSSP) dengan menggunakan Genetic Algorithm (GA). Langkah-langkah GA yaitu membangkitkan kromosom awal berdasarkan degree of similarity antar individu, evaluasi, seleksi turnamen, crossover dan mutasi. Program yang dibuat diimplementasikan pada tiga data (problem) yang berukuran 6×6, sehingga diperoleh hasil terbaik dengan nilai rata-rata AI, minimum AI, dan maksimum Completion Time yaitu untuk Problem 1 masingmasing 0,96186; 0,79422 dan (65,0; 87,0; 110,0), untuk Problem 2 masingmasing 0,99227; 0,97460 dan (60,0; 83,0; 99,0), untuk Problem 3 masing-masing 0,84864; 0,69231 dan (28,0; 38,0; 49,0). Ketiga bilangan pada Completion Time secara berurutan menunujukkan waktu penyelesaian tercepat, waktu penyelesaian normal dan waktu penyelesaian terlambat. Kata Kunci : Fuzzy Multi-Objective JSSP, Degree of Similarity, Genetic Algorithm, Agreement Index.
vii Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
Marisa, 2012, Application of Fuzzy Multi-Objective in Job Shop Scheduling Using Genetic Algorithm, This Skripsi is supervised by Dr. Herry Suprajitno, M.Si and Auli Damayanti, S.Si., M.Si, Department of Mathematics, Faculty of Science and Technology, Airlangga University, Surabaya. ABSTRACT Job Shop Scheduling Problems (JSSP) is a scheduling problem containing of n jobs and m machines which each job consists of several operations performed by different machines. Generally, many factors influence the JSSP, but in the real world, the uncertainty factors such as delays in the working process and the duration of the operation give effects in determining the schedule. To overcome these uncertainties, fuzzy number are used for processing time and due date. The purpose of this skripsi is to solved Fuzzy Multi-Objective (Agreement Index (AI) and Completion Time) JSSP (FMOJSSP) by using Genetic Algorithm (GA). The steps of GA are to generating the initial chromosomes based on the degree of similarity between individuals, evaluation, tournament selection, crossover and mutation. The program made is implemented on three datas (problems) of size 6×6 and the best results for mean of AI, minimum of AI and maximum of completion time for Problem 1 respectively are 0,96186; 0,79422 and (65,0; 87,0; 110,0), for Problem 2 respectively are 0,99227; 0,97460 and (60,0; 83,0; 99,0), for Problem 3 respectively are 0,84864; 0,69231 and (28,0; 38,0; 49,0). Three numbers of completion time sequentially showing the fastest completion time, the normal completion time and completion time of late. Keyword
: Fuzzy Multi-Objective JSSP, Degree of Similarity, Genetic Algorithm, Agreement Index.
viii Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
DAFTAR ISI Halaman HALAMAN JUDUL ..................................................................................
i
LEMBAR PERNYATAAN .......................................................................
ii
LEMBAR PENGESAHAN .......................................................................
iii
PEDOMAN PENGGUNAAN SKRIPSI ...................................................
iv
KATA PENGANTAR ................................................................................
v
ABSTRAK .................................................................................................
vii
ABSTRACT ...............................................................................................
viii
DAFTAR ISI ..............................................................................................
ix
DAFTAR TABEL ......................................................................................
xi
DAFTAR GAMBAR .................................................................................
xii
DAFTAR LAMPIRAN ..............................................................................
xiv
BAB I PENDAHULUAN ........................................................................
1
1.1 Latar Belakang Permasalahan ................................................
1
1.2 Rumusan Masalah ..................................................................
4
1.3 Tujuan ....................................................................................
4
1.4 Manfaat ..................................................................................
5
1.5 Batasan Masalah .....................................................................
5
BAB II TINJAUAN PUSTAKA ...............................................................
6
2.1 Job Shop Scheduling Problems ..............................................
6
2.2 Fuzzy ......................................................................................
9
2.3 Algoritma Genetik .................................................................
16
2.4 Fuzzy Multi-Objective JSSP (FMOJSSP) ..............................
25
2.4.1 Fuzzy Number pada JSSP ..........................................
25
2.4.2 Multi-Objective JSSP ................................................
28
2.4.3 Metode Giffler Dan Thompson .................................
30
2.5 JAVA ....................................................................................
31
2.6 NETBEANS IDE ...................................................................
32
BAB III METODE PENELITIAN..............................................................
33
ix Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
BAB IV PEMBAHASAN ..........................................................................
37
4.1 Prosedur Algoritma Genetik Untuk Permasalahan Job Shop Scheduling ..............................................................................
37
4.2 Data ........................................................................................
56
4.3 Penyelesaian Manual terhadap Contoh Kasus Job Shop Scheduling Problem 6x6 ........................................................
57
4.4 Implementasi Program pada Kasus JSSP ..............................
84
4.4.1 Data Problem 1 FMOJSSP 6x6 ................................
84
4.4.2 Data Problem 2 FMOJSSP 6x6 ................................
85
4.4.3 Data Problem 3 FMOJSSP 6x6 ................................
85
4.5 Perbandingan Hasil dengan Parameter yang Berbeda ...........
86
4.5.1 Data Problem 1 FMOJSSP 6x6 ................................
86
4.5.2 Data Problem 2 FMOJSSP 6x6 ................................
87
4.5.3 Data Problem 3 FMOJSSP 6x6 ................................
89
BAB V KESIMPULAN DAN SARAN ....................................................
91
5.1 Kesimpulan ............................................................................
91
5.2 Saran ....................................................................................
92
DAFTAR PUSTAKA ................................................................................
93
LAMPIRAN
x Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
DAFTAR TABEL
No.
Judul Tabel
Halaman
4.1
Data Permasalahan
56
4.2
Kromosom awal yang dibangkitkan
62
4.3
Kromosom awal yang telah diaktifkan
63
4.4
Nilai degree untuk kromosom awal
63
4.5
Fuzzy Completion Time kromosom ke-0
64
4.6
Agreement Index masing-masing job pada kromosom ke-0
67
4.7
Nilai Ranking Fuzzy Completion Time pada kromosom ke-0
68
4.8
Nilai Fungsi Tujuan populasi awal
68
4.9
Derajat keanggotaan fungsi Tujuan pada populasi awal
71
4.10 Nilai Fitness Populasi Awal
72
4.11 Calon Induk Crossover
73
4.12 Induk Crossover
74
4.13 Calon Induk Mutasi
74
4.14 Induk Mutasi
75
4.15 Offspring Crossover yang telah diaktifkan
79
4.16 Nilai Fungsi Tujuan Offspring Hasil Crossover
79
4.17 Offspring Mutasi yang telah diaktifkan
80
4.18 Nilai Fungsi Tujuan Offspring Hasil Mutasi
80
4.19 Derajat Keanggotaan Fungsi Tujuan Populasi Awal dan Offspring
81
4.20 Nilai Fitness Populasi Awal dan Offspring
81
4.21 Hasil Pengurutan Kromosom Gabungan
82
4.22 Populasi Baru
83
xi Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
DAFTAR GAMBAR
No.
Judul Gambar
Halaman
2.1
Representasi Kurva Segitiga
11
2.2
Representasi Kurva Trapesium
12
2.3
Fungsi Keanggotaan Linear Memaksimalkan Fungsi Objektif
15
2.4
Fungsi Keanggotaan Linear Meminimalkan Fungsi Objektif
15
2.5
Contoh perhitungan Degree of Similarity
19
2.6
Doublet Fuzzy duedate
26
2.7
Agreement Index
26
2.8
Contoh Agreement Index (AI)
27
4.1
Prosedur untuk Genetic Algorithm
37
4.2
Prosedur untuk Parameter Setting
38
4.3
Prosedur untuk Inisialisasi
39
4.4
Prosedur untuk Generate Kromosom
39
4.5
Prosedur untuk Generate Urutan Job
40
4.6
Prosedur untuk Menentukan Operasi Job
40
4.7
Prosedur untuk Menentukan Urutan Mesin
41
4.8
Prosedur untuk Pengaktifan Schedule
41
4.9
Prosedur untuk Menghitung Completion Time
dan Delay
42
Time 4.10 Prosedur untuk Pengaktifan
43
4.11 Prosedur untuk Evaluasi z1
44
4.12 Prosedur untuk Evaluasi z2
44
4.13 Prosedur untuk Evaluasi z3
45
4.14 Prosedur untuk Menghitung Fitness
45
4.15 Prosedur Operasi Genetik
46
untuk Mendapatkan
4.16 Prosedur untuk Seleksi Turnamen
47
4.17 Prosedur untuk Seleksi Crossover
48
4.18 Prosedur untuk Seleksi Mutasi
48
xii Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
4.19 Prosedur untuk Partial Schedule Exchange Crossover
49
4.20 Prosedur untuk Menetukan Partial Schedule dari Parent 0
50
4.21 Prosedur untuk Menetukan Partial Schedule dari Parent 1
50
4.22 Prosedur untuk Menentukan Exceeded dan Missed Genes
51
4.23 Prosedur untuk Menentukan Offspring
52
4.24 Prosedur untuk Swap Mutation
53
4.25 Prosedur untuk Membentuk Populasi Baru
53
4.26 Prosedur untuk Menggabungkan Kromosom
54
4.27 Prosedur untuk Mengurutkan Kromosom
55
4.28 Prosedur untuk Mengambil Kromosom Terbaik
55
4.29 Prosedur untuk Tes Pemberhentian Iterasi
56
4.30 Perhitungan Degree of Similarity Kromosom 0 dan
61
Kromosom 1 4.31 Grafik Fuzzy Completion Time dan Fuzzy Due Date ~ 4.32 Daerah C~ D
65 66
xiii Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
DAFTAR LAMPIRAN
No.
Judul Lampiran
1.
Flowchart FMOJSSP Menggunakan GA
2.
Data Fuzzy Multi-Objective Job Shop Scheduling Problem (FMOJSSP)
3.
Gantt Chart Kromosom ke-0 Sebelum Pengaktifan Schedule
4.
Gantt Chart Kromosom ke-0 Setelah Pengaktifan Schedule
5.
Gantt Chart Kromosom ke-11
6.
Source Code Program GA untuk FMOJSSP
7.
Hasil Penyelesaian Problem 1 FMOJSSP
8.
Hasil Penyelesaian Problem 2 FMOJSSP
9.
Hasil Penyelesaian Problem 3 FMOJSSP
10.
Hasil Running Problem 1 FMOJSSP
11.
Hasil Running Problem 2 FMOJSSP
12.
Hasil Running Problem 3 FMOJSSP
13.
Output Program FMOJSSP Menggunakan GA
xiv Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
BAB I PENDAHULUAN
1.1 Latar Belakang Permasalahan Pada saat ini, perkembangan ilmu dan teknologi banyak mempengaruhi perkembangan dunia industri dan manufacturing, hal ini berdampak pada persaingan industri. Dalam menghadapi persaingan tersebut diperlukan strategi yang tepat dalam mengatasi permasalahan-permasalahan yang muncul. Dalam dunia industri, proses produksi merupakan proses pembuatan barang atau jasa. Pada proses ini diperlukan strategi dalam menentukan penempatan urutan job sehingga waktu yang diperlukan menjadi efisien. Dengan waktu yang efisien tersebut diharapkan industri dapat mengurangi pengeluaran biaya produksi serta dapat memenuhi kebutuhaan konsumen tepat waktu. Job
Shop
Scheduling
Problems
(JSSP)
merupakan
permasalahan
penjadwalan yang ada dalam dunia industri. Pada JSSP permasalahan yang ada yaitu dimana terdapat himpunan m mesin dan n job yang akan dijadwalkan. Masing-masing job terdiri dari beberapa operasi yang dilaksanakan oleh mesin yang berbeda. Pada JSSP masing-masing job memiliki urutan mesin tersendiri. Meskipun sebuah job dapat memiliki banyak operasi, bentuk yang paling umum dari JSSP adalah masing-masing job secara pasti memiliki m operasi, yaitu satu operasi pada tiap mesin (Baker dan Trietsch, 2009). Secara umum, banyak faktor yang mempengaruhi JSSP, namun pada dunia kerja, ada beberapa faktor ketidakpastian seperti keterlambatan proses pengerjaan,
1 Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
2
dan lamanya proses pengoperasian yang ikut berpengaruh dalam menentukan scheduling. Untuk mengatasi ketidakpastian tersebut, maka digunakan metode fuzzy yang diharapkan dapat menggambarkan interval waktu pengerjaan dan penyelesaian suatu pekerjaan. Dengan mempertimbangkan banyaknya ketidakpastian yang terjadi maka dalam skripsi ini digunakan dua bilangan fuzzy. Bilangan fuzzy yang digunakan yaitu Triangular Fuzzy Number atau bilangan fuzzy segitiga yang terdiri dari tiga bilangan yang dalam hal ini yaitu waktu proses paling cepat, waktu proses normal dan waktu proses paling lambat untuk processing time pada masing-masing operasi job sebagai toleransi terhadap kesalahan pada faktor manusia. Sedangkan untuk due date (waktu tenggat) pada masing-masing job digambarkan dengan Trapezoidal Fuzzy Number dalam bentuk Doublet yang menunjukkan waktu normal dan waktu penyelesaian paling lambat sebagai toleransi keterlambatan waktu tenggat atau deadline penyelesaian job. Penggunaan bilangan fuzzy ini diharapkan dapat lebih mewakili keadaan dunia nyata yang sebenarnya. Bilangan – bilangan tersebut nantinya akan digunakan untuk menghitung waktu penyelesaian masing-masing job di keseluruhan mesin atau sering disebut dengan Completion time. Setelah completion time didapatkan maka akan diperhitungkan kesesuaian antara waktu penyelesaian tiap-tiap job tersebut dengan due date atau waktu deadline pekerjaan harus diselesaikan yang sering disebut dengan Agreement Index. Diharapkan schedule yang dihasilkan akan menghasilkan completion time yang kecil dan kesesuaian waktu pengerjaan yang maksimal.
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
3
Seiring dengan perkembangan waktu, banyak metode/algoritma digunakan dalam
menyelesaikan
permasalahan
JSSP.
Salah
satu
penelitian
yang
menggunakan informasi fuzzy dalam menyelesaikan JSSP dengan menggunakan algoritma genetik (Genetic Algorithm) sebagai metode pencariannya sesuai yang dilakukan oleh Sakawa pada tahun 2000 yang mengandalkan kriteria derajat kesamaan (degree of similarity) dari masing-masing individu untuk menjaga keragaman solusi yang diperoleh. Penelitian lain yang menggunakan Fuzzy Genetic Algortihm dalam menyelesaikan JSSP dilakukan oleh Lei pada tahun 2010 dengan menggunakan operator genetik seleksi turnamen pada pemilihan induk crossover dan mutasi. Algoritma genetik merupakan suatu metode pencarian yang didasarkan pada proses evolusi. Algoritma ini menggunakan pengkodean sebagai representasi yang berisi informasi dari penyelesaian permasalahan dan menggunakan fungsi fitness untuk menentukan kehandalan masing-masing penyelesaian permasalahan. Penelitian yang telah dilakukan sebelumnya hanya mempertimbangkan satu fungsi objektif (single objective function), sehingga agar lebih memadai dalam menggambarkan dunia nyata maka dalam penelitian ini digunakan fungsi multiobjektif (multiobjective function). Skripsi ini menggabungkan penelitian yang telah dilakukan oleh Sakawa yang menggunakan derajat kesamaan dalam membangkitkan individu awal dengan penelitian yang dilakukan oleh Lei yang menggunakan seleksi turnamen dalam pemilihan induk, sedangkan crossover dan mutasi yang digunakan yaitu Partial Schedule Exchange Crossover dan Swap Mutation. Dengan menggunakan
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
4
Fuzzy Processing Time dan Fuzzy Due Date, penyelesaian JSSP menggunakan Multiobjective Genetic Algorithm akan diperkenalkan lebih lanjut. Pada skripsi ini fungsi objektif yang digunakan tidak hanya memaksimalkan minimum Agreement Index (AI) tetapi juga memaksimalkan rata-rata Agreement Index dan meminimunkan maksimum Completion time.
1.2 Rumusan Masalah Pada penelitian ini, rumusan masalah yang diangkat oleh penulis adalah sebagai berikut : 1. Bagaimana menerapkan Fuzzy Multi-Objective pada Job Shop Scheduling menggunakan Genetic Algorithm ? 2. Bagaimana membuat program Fuzzy Multi-Objective pada Job Shop Scheduling menggunakan Genetic Algorithm ? 3. Bagaimana mengimplementasikan program Fuzzy Multi-Objective pada Job Shop Scheduling menggunakan Genetic Algorithm pada contoh kasus ?
1.3 Tujuan Dari rumusan-rumusan masalah diatas, tujuan yang ingin dicapai oleh penulis adalah : 1. Menerapkan Fuzzy Multi-Objective pada Job Shop Scheduling menggunakan Genetic Algorithm. 2. Membuat program Fuzzy Multi-Objective pada Job Shop Scheduling menggunakan Genetic Algorithm.
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
5
3. Mengimplementasikan program Fuzzy Multi-Objective pada Job Shop Scheduling menggunakan Genetic Algorithm pada contoh kasus.
1.4 Manfaat Manfaat yang akan diperoleh dari hasil penelitian ini yaitu : 1. Menambah wawasan tentang penerapan Riset Operasi khususnya dalam menyelesaikan atau pengoptimalan permasalahan Fuzzy Multi-Objective pada Job Shop Scheduling menggunakan Genetic Algorithm. 2. Program Fuzzy Multi-Objective pada Job Shop Scheduling menggunakan Genetic Algorithm yang telah dibuat diharapkan dapat digunakan oleh perusahaan – perusahaan yang berkaitan dalam menyelesaikan masalah penjadwalan pekerjaan dan sebagainya.
1.5 Batasan Masalah Berdasarkan rumusan masalah yang telah dijelaskan, maka dalam penelitian ini penulis membatasi masalah yang akan diselesaikan dengan batasan sebagai berikut : 1. Seleksi yang digunakan adalah seleksi turnamen (Tournament Selection). 2. Crossover yang digunakan adalah Partial Schedule Exchange Crossover. 3. Mutasi yang digunakan adalah Swap Mutation.
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
BAB II TINJAUAN PUSTAKA
2.1 Job Shop Scheduling Problems Job Shop Scheduling Problems (JSSP) merupakan suatu permasalahan yang sering muncul dalam dunia industri dan manufacturing. JSSP merupakan suatu permasalahan dimana terdapat sekumpulan m mesin dan sekumpulan n job yang akan dijadwalkan. Masing-masing job terdiri dari beberapa operasi yang dilaksanakan oleh mesin yang berbeda. Pada JSSP masing-masing job memiliki urutan mesin tersendiri. Meskipun sebuah job dapat memiliki banyak operasi, bentuk yang paling umum dari JSSP adalah masing-masing job secara pasti memiliki m operasi, yaitu satu operasi pada tiap mesin. (Baker dan Trietsch, 2009) Secara umum, sebuah permasalahan job shop scheduling dirumuskan sebagai berikut. Misalkan terdapat n job Ji dengan Ji adalah job ke-i (i=1,2,…..,n) yang diproses pada m mesin Mr dengan Mr adalah mesin ke-r (r=1,2,…..,m) dan dimisalkan pula operasi dari job Ji pada mesin Mr adalah Oi,j,r dimana {1,2,…,m} adalah posisi operasi urutan mesin pada masing-masing job. Atau dapat diartikan bahwa Oi,j,r menunjukkan operasi ke-j pada job Ji yang diproses pada mesin r. (Sakawa dan Kubota, 2000) Dalam JSSP ada beberapa definisi dan notasi yang sering digunakan, antara lain :
6 Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
7
a. Waktu pemrosesan (Processing Time) Dinotasikan dengan pij, yaitu merupakan panjang waktu yang dibutuhkan untuk melaksanakan masing-masing operasi job termasuk waktu untuk mengatur (set up) mesin dan waktu untuk memindahkan job pada mesin. b. Waktu tenggat (Duedate) Dinotasikan dengan di, yaitu merupakan waktu ideal dimana job ke-i harus sudah diselesaikan. c. Waktu siap (Release date) Dinotasikan dengan ri, yaitu merupakan waktu dari job ke-i dimana Ji siap untuk dijalankan atau siap untuk diproses. d. Waktu penyelesaian (Completion Time) Dinotasikan dengan Ci, yaitu merupakan waktu dimana job ke-i selesai diproses. e. Makespan Dinotasikan dengan Cmax, yaitu merupakan total waktu proses seluruh job. (French, 1982) Pada JSSP setiap operasi dicirikan dengan mesin yang digunakan dan waktu pemrosesan yang sudah ditentukan. Ada beberapa aturan yangterdapat pada JSSP, antara lain : a. Sebuah job tidak akan dikerjakan dua kali pada mesin yang sama. b. Tidak ada kendala operasi yang mendahului pada job yang berbeda. c. Operasi pada masing-masing mesin tidak dapat diganggu atau disela dengan operasi lain sebelum operasi sebelumnya selesai.
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
8
d. Masing-masing mesin hanya dapat mengoperasikan satu job pada satu waktu. e. Waktu siap (Release times) dan waktu tenggat (Due Dates) telah ditentukan. (Gen dan Cheng, 1997) Dalam JSSP sebuah schedule adalah sebuah himpunan completion times (waktu penyelesaian) untuk masing-masing operasi yang memenuhi kendala urutan mesin. Untuk lebih mempermudah penyelesaian dalam permasalahan JSS, digunakan sebuah diagram yang merupakan cara mudah untuk yang menyatakan sebuah solusi visual dari JSSP yang disebut dengan Gantt Chart. (Yamada dan Nakano, 1997) Secara umum, dalam JSSP terdapat tiga tipe schedule, antara lain : a. Semiactive Schedule (Jadwal Semiaktif) Sebuah jadwal dikatakan semiaktif jika tidak ada operasi yang dapat dimulai lebih awal tanpa mengubah urutan operasi yaitu, pada sebuah semiactive schedule tidak ada waktu menganggur yang berlebihan. b. Active Schedule (Jadwal Aktif) Sebuah jadwal dikatakan aktif jika tidak ada operasi yang dapat dimulai lebih awal tanpa menunda beberapa operasi lain atau melanggar kendala urutan mesin. c. Non Delay Schedule Sebuah jadwal dikatakan nondelay jika tidak ada mesin yang tetap menganggur pada suatu waktu dimana mesin tersebut dapat memulai untuk memproses beberapa operasi. (Sakawa, 2002)
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
9
Permasalahan umum pada job shop scheduling adalah untuk mencari urutan pelaksanaan job yang sesuai. Dalam hal ini urutan yang dijadikan sebagai solusi permasalahan harus bersifat feasible. Suatu jadwal dikatakan feasible jika memenuhi syarat urutan mesin pada masing-masing job. (French, 1982)
2.2 Fuzzy Jika diterjemahkan menurut kamus, “fuzzy” dapat diartikan sebagai sesuatu yang tidak jelas atau buram yang menggambarkan ketidakpastian. Ada beberapa definisi yang berkaitan dengan fuzzy, yaitu : Definisi 2.1
: Variabel Fuzzy merupakan variabel yang akan dibahas dalam suatu sistem fuzzy. Contoh : Umur, temperatur.
Definisi 2.2
: Himpunan Fuzzy merupakan suatu grup yang mewakili kondisi atau keadaan tertentu dalam suatu variabel fuzzy. Contoh : Muda, Parobaya, Tua.
Definisi 2.3
: Semesta
Pembicaraan
adalah
keseluruhan
nilai
yang
diperbolehkan untuk dioperasikan dalam suatu variabel fuzzy. Semesta pembicaraan merupakan himpunan bilangan real yang bisa bernilai positif atau negatif yang senantiasa naik (bertambah) secara monoton dari kiri ke kanan. Adakalanya nilai semesta pembicaraan ini tidak dibatasi batas atasnya. Contoh : Semesta pembicaraan untuk variabel umur [0, +∞).
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
Definisi 2.4
10
: Domain himpunan fuzzy adalah keseluruhan nilai yang diijinkan dalam semesta pembicaraan dan boleh dioperasikan dalam suatu himpunan fuzzy. Seperti halnya semesta pembicaraan, domain merupakan himpunan bilangan real positif maupun negatif yang senantiasa naik (bertambah) secara monoton dari kiri ke kanan. Contoh : Muda = [0, 45] artinya batasan umur yang termasuk anggota himpunan Muda terletak antara umur 0 sampai umur 45. (Kusumadewi dan Purnomo, 2010)
Sebuah himpunan X yang merupakan himpunan semesta pada himpunan fuzzy A dinyatakan dengan sebuah Fungsi Keanggotaan (membership function),
A [x] yang menunjukkan pemetaan masing-masing titik x X ke dalam sebuah nilai real pada interval antara 0 dan 1 dan disebut sebagai derajat keanggotaan (degree of membership). Nilai A [x] menyatakan fungsi keanggotaan dari x pada himpunan A. Sehingga, semakin dekat nilai A [x] ke nilai 1, maka semakin tinggi nilai keanggotaan dari x di A. Secara lebih jelas himpunan fuzzy A dinotasikan sebagai berikut : A {( x, A [ x]) | x X }
(Zadeh, 1965) Sebuah himpunan fuzzy A dikatakan convex apabila memenuhi : x (1) , x ( 2) R; dengan R merupakan himpunan bilangan real, dan berlaku :
A [x (1) (1 ) x ( 2) ] A [ x (1) ] A [ x ( 2) ] [0,1],
dengan
merupakan operasi
yang mengambil nilai
keanggotaan terkecil.
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
11
Dan himpunan fuzzy A normal jika hanya jika :
x R;
n
A
[ x] 1
Pengertian normal diatas berarti bahwa nilai tertinggi (highest value) dari derajat keanggotaan A [x] adalah sama dengan 1. (Kaufmann dan Gupta, 1991) Fuzzy number adalah subset himpunan fuzzy yang bersifat convex, dan normal serta direpresentasikan dengan interval kepercayaan. (Chen dan Pham, 2001) Triangular Fuzzy Number (TFN) adalah himpunan fuzzy yang memiliki tiga titik a, b, c dengan nilai tengah b, batas sebelah kiri a dan batas sebelah kanan c seperti ditunjukkan pada Gambar 2.1. Maka fungsi keanggotaannya adalah sebagai berikut :
0; x a atau x c xa [ x ] ; a xb b a c x; b x c cb
1,0 Derajat keanggotaan
[ x] 0
a
b
c
Domain
Gambar 2.1 Representasi Kurva Segitiga
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
12
Trapezoidal Fuzzy Number adalah himpunan fuzzy yang mempunyai empat titik yaitu a, b, c, d seperti ditunjukkan pada Gambar 2.2. Dan fungsi keanggotaannya adalah sebagai berikut :
0; x a atau x d xa; a xb b a [ x ] 1; b x c d x; c xd d c
1,0 Derajat keanggotaan
[x] 0
a
b
c
d
Domain Gambar 2.2 Representasi Kurva Trapesium (Kusumadewi, 2002) Dalam himpunan fuzzy ada beberapa operasi yang diciptakan Zadeh dimana operasi tersebut digunakan untuk mengkombinasi dan memodifikasi himpunan. Derajat keanggotaan dari hasil operasi dua himpunan fuzzy dikenal dengan fire strength atau α-predikat. Misalkan terdapat himpunan fuzzy A dan himpunan fuzzy B dalam himpunan semesta X yang memiliki elemen x, maka dapat dilakukan operasi antara kedua himpunan tersebut. Operasi tersebut antara lain :
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
13
a. Operator AND Digunakan untuk menghubungkan operasi interseksi pada himpunan. Hasil operasi operator AND diperoleh dengan mengambil nilai keanggotaan terkecil antarelemen pada himpunan yang bersangkutan.
AB min( A [ x], B [ x]) b. Operator OR Digunakan untuk menghubungkan operasi union pada himpunan. Hasil operasi operator OR diperoleh dengan mengambil nilai terbesar antarelemen pada himpunan yang bersangkutan.
AB max( A [ x], B [ x]) c. Operator NOT Digunakan untuk menghubungkan operasi komplemen pada himpunan. Hasil operator NOT diperoleh dengan mengurangkan nilai keanggotaan elemen pada himpunan yang bersangkutan dari satu.
A' 1 A [ x] (Kusumadewi dan Purnomo, 2010) ~ ~ Misalkan A (a 1 ,a 2 ,a 3 ) dan B (b1 ,b 2 ,b 3 ) merupakan dua TFN dengan
a 1 , a 2 , a 3 masing-masing adalah bilangan pertama (batas bawah), bilangan
~ kedua (nilai tengah) dan bilangan ketiga (batas atas) himpunan A dan b 1 , b 2 , b 3 masing-masing adalah bilangan pertama (batas bawah), bilangan kedua (nilai
~ tengah) dan bilangan ketiga (batas atas) himpunan B , maka operasi–operasi yang dapat digunakan pada bilangan fuzzy tersebut adalah sebagai berikut :
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
14
~ ~ 1. A B (a 1 ,a 2 ,a 3 ) (b1 ,b 2 ,b 3 ) (a 1 b1 ,a 2 b 2 ,a 3 b 3 )
Operasi ini akan digunakan untuk menghitung waktu penyelesaian operasi. ~ ~ 2. A B (a 1 ,a 2 ,a 3 ) (b1 ,b 2 ,b 3 ) (a 1 b1 ,a 2 b 2 ,a 3 b 3 )
Operasi ini akan digunakan untuk menghitung waktu mulai operasi. (Sakawa dan Kubota, 2000) Untuk lebih mempermudah penyelesaian fungsi objektif yang menggunakan bilangan fuzzy maka digunakan fungsi keanggotaan linear (Linear Membership Function) dengan z i adalah nilai masing-masing fungsi objektif dengan i 1,2,3 , z i0 adalah nilai fungsi objektif i terendah dan z i1 adalah nilai fungsi objektif i
tertinggi. Sedangkan i [ z i ] adalah derajat keanggotaan ke-i untuk fungsi objektif i. Maka dapat dibuat fungsi keanggotaan linear untuk memaksimalkan fungsi objektif yang didefinisikan pada persamaan (2.1) berikut :
1, z i z i1 0 z i zi i [ z i ] 1 0 , z i0 z i z i1 zi zi 0, z i z i0
(2.1)
(Sakawa dan Kubota, 2000) Dengan fungsi keanggotaan diatas maka nilai fungsi objektif terbesar akan memiliki derajat keanggotaan yang besar yaitu 1, sedangkan untuk fungsi objektif terendah akan memiliki derajat keanggotaa terkecil yaitu 0. Fungsi untuk memaksimalkan diatas dapat digambarkan sesuai Gambar 2.3.
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
15
i[ z i ]
1,0
zi0
0
zi
z i1
Gambar 2.3 Fungsi Keanggotaan Linear Memaksimalkan Fungsi Objektif Sedangkan untuk fungsi keanggotaan linear yang meminimalkan fungsi objektif didefinisikan pada persamaan (2.2) berikut :
0, z i z i1 1 z zi i [ z i ] 1i , z i0 z i z i1 0 zi zi 1, z i z i0
(2.2)
Dengan fungsi keanggotaan diatas maka nilai fungsi objektif tekecil akan memiliki derajat keanggotaan yang besar yaitu 1, sedangkan untuk fungsi objektif terbesar akan memiliki derajat keanggotaa terkecil yaitu 0. Fungsi untuk memaksimalkan diatas dapat digambarkan sesuai Gambar 2.4. i[ z i ]
1,0
0
zi0
zi1
zi
Gambar 2.4 Fungsi Keanggotaan Linear Meminimalkan Fungsi Objektif (Sakawa dkk, 2011)
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
16
2.3 Algoritma Genetik Selama ini diketahui bahwa banyak permasalahan optimalisasi dalam dunia industri terutama sistem manufaktur yang sangat sulit diselesaikan dengan menggunakan teknik konvensional. Sehingga telah banyak dikembangkan penelitian yang menggunakan algoritma evolusi yang berdasar pada teori evolusi dalam menyelesaikan permasalahan-permasalahan tersebut. Algoritma ini sering dinilai lebih baik dibandingkan dengan teknik konvensional pada saat diaplikasikan ke permasalahan dunia nyata yang cukup sulit. Salah satu algoritma evolusi yang sangat dikenal saat ini adalah Algoritma Genetik (Genetic Algorithm). Algoritma Genetik ini telah diterima dan mendapat perhatian karena keberhasilannya dalam menyelesaikan permasalahan komplek pada dunia industri. (Gen dan Cheng, 1997) Berikut akan diberikan definisi-definisi yang berkaitan dengan algoritma genetik, antara lain : Definisi 2.5
Algoritma adalah suatu himpunan langkah-langkah atau instruksi yang telah dirumuskan dengan baik (well defined) untuk memperoleh suatu keluaran khusus (spesific output) dari suatu masukan khusus (spesific input) dalam langkah yang jumlahnya berhingga. (Chartrand dan Oellermann, 1993)
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
Definisi 2.6
17
Algoritma genetika adalah teknik pencarian stochastic yang didasari oleh mekanisme seleksi alami (natural selection) dan proses genetik alami (natural genetics). (Gen dan Cheng, 1997)
Konsep GA (Genetic Algorithm) secara umum dimulai dengan menentukan populasi awal. Definisi 2.7
Himpunan dari solusi disebut populasi.
Definisi 2.8
Masing-masing individu yang terdapat dalam populasi yang menyatakan solusi permasalahan disebut kromosom. (Gen dan Cheng, 1997)
Definisi 2.9
Kromosom s terdiri dari sejumlah struktur s1,…, sj ..., sn yang disebut gen.
Definisi 2.10 Gen sj mempunyai posisi locus ke-j pada kromosom. (Sakawa dan Kubota, 2000) Definsi 2.11 Kromosom yang berkembang melalui iterasi yang berturut-turut yang disebut sebagai generasi. Definisi 2.12 Ukuran sebuah populasi pada masing-masing generasi disebut sebagai ukuran populasi (pop_size). (Gen dan Cheng, 1997) Definisi 2.13 Pengkodean (coding) merupakan cara pemetaan suatu solusi yang sesuai dalam ruang pencarian ke kromosom. (Sakawa dan Kubota, 2000)
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
18
Ada beberapa cara untuk mengkode suatu kromosom diantaranya: 1. Pengkodean Biner Dalam pengkodean biner, kromosom adalah barisan bit 0 atau 1. 2. Pengkodean Nilai Dalam pengkodean nilai, setiap kromosom adalah barisan beberapa nilai. 3. Pengkodean Permutasi Dalam pengkodean permutasi, setiap kromosom adalah barisan angka yang memperhatikan urutan dan posisi sehingga tidak terjadi adanya pengulangan angka. 4. Pengkodean Random Keys (Nomor Acak) Dalam random keys, setiap kromosom adalah barisan angka random yang berkisar antara 0 dan 1. (Obitko, 1998) Untuk menjaga keanekaragaman pembangkitan individu awal, pada penyelesaian JSSP dengan menggunakan Genetic Algorithm dalam penelitian yang dilakukan oleh Sakawa dan Kubota (2000) telah diperkenalkan suatu metode pembangkitan solusi awal yang berdasarkan kepada derajat kesamaan (degree of similarity) antar masing-masing individu. Berdasarkan banyak penelitian yang telah dilakukan diketahui bahwa pada saat membangkitkan individu dengan derajat kesamaan 0,8 atau kurang maka solusi yang diperoleh akan lebih konvergen (Sakawa, 2000). Gambar 2.5 menunjukkan contoh perhitungan degree of similarity dari dua individu pada contoh permasalahan 4×4 FJSSP.
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
Individu 1
19
Individu 2
Job
Job
Mesin 1
1
2
4
3
2+2+3+3=10
Mesin 1
2
1
4
3
Mesin 2
3
1
4
2
3+3+3+3=12
Mesin 2
3
1
4
2
Mesin 3
4
3
1
2
Mesin 3
4
3
1
2
Mesin 4
3
2
1
4
Mesin 4
3
2
4
1
3+3+3+3=12 3+3+2+2=10
10 12 12 10 44 0,917 48 48 Gambar 2.5 Contoh perhitungan Degree of Similarity Tabel di atas merupakan tabel urutan job pada tiap-tiap mesin dari individu 1 dan individu 2. Untuk individu 1, job 1 pada mesin 1 memiliki prioritas diatas job 2, 3 dan 4. Untuk individu 2, job 1 pada mesin 1 kehilangan prioritas terhadap job 2 dan memiliki prioritas terhadap job 4 dan 3. Karena kedua individu memiliki prioritas yang sama untuk job 1 pada mesin 1 diatas job 4 dan 3 maka diberi nilai 2. Jika dilakukan perhitungan yang sama pada job 2, 4 dan 3 maka akan diperoleh nilai masing-masing 2, 3 dan 3 pada mesin 1. Jika dihitung untuk semua mesin maka akan diperoleh total nilai 44. Karena 12 x 4 adalah 48 pada saat urutan prioritas sama untuk semua job, maka rasio menjadi 44/48 dan diperoleh degree of similarity sebesar 0,917 yang berarti bahwa tingkat kesamaan individu 1 dan individu 2 sebesar 91,7%. (Sakawa dan Kubota, 2000) Pada masing-masing generasi, masing-masing kromosom pada populasi yang telah dibangkitkan dievaluasi dengan menghitung nilai fitness. Selanjutnya dilakukan dua operasi yaitu proses seleksi yang merupakan operasi evolusi serta crossover dan mutasi yang merupakan operasi genetik dalam algoritma genetik. (Gen dan Cheng, 1997)
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
20
Definisi 2.14 Fungsi fitness adalah ukuran yang menunjukkan tingkat kebaikan atau kesesuaian suatu solusi dengan solusi yang dicari. (Santoso dan Willy, 2011) Definisi 2.15 Seleksi (selection) merupakan proses pemilihan individu dari populasi untuk menjadi induk crossover atau induk mutasi. (Obitko, 1998) Ada beberapa jenis seleksi dalam algoritma genetik, diantaranya adalah : a. Seleksi Elistim (Elitism Selection) Seleksi ini dilakukan dengan memasukkan kromosom terbaik kedalam generasi baru secara langsung. Dan sisanya dilakukan dengan menggunakan seleksi yang lain. b. Seleksi Roda Rolet (Roulete Wheel Selection) Seleksi ini dilakukan dengan menentukan probabilitas masing-masing kromosom yang nilainya sesuai dengan fungsi fitnessnya. Kemudian dibuat sebuah roda yang berdasarkan kepada probabilitas tersebut. Proses seleksi dilakukan dengan memutar roda rolet sebanyak pop_size. c. Seleksi Turnamen Seleksi ini dilakukan dengan memilih secara random sebuah himpunan (set) kromosom dan memilih satu kromosom terbaik dari himpunan tersebut untuk digunakan dalam reproduksi. Jumlah kromosom pada himpunan tersebut disebut tournament size atau tour. Nilai tournament size yang umum adalah 2. (Gen dan Cheng, 1997)
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
21
Individu-individu yang telah terpilih dalam proses seleksi selanjutnya akan diproses crossover dan mutasi. Definisi2.16 Crossover adalah operator genetik yang utama. Pada proses ini dua induk atau kromosom dioperasi untuk mendapatkan individu baru (offspring) dengan mengkombinasi atau menggabungkan sifat-sifat dari keduanya. (Gen dan Cheng, 1997) Tipe dan bentuk dari crossover tergantung pada pengkodean dan jenis permasalahannya. Ada beberapa jenis crossover, diantaranya: a. Partial Schedule Exchange Crossover Langkah-langkah : 1. Memilih satu posisi pada parent 1 secara random. 2. Menentukan job terdekat yang sama dengan job pada posisi terpilih sehingga diperoleh partial schedule 1. 3. Partial schedule selanjutnya dari parent 2 tidak diperoleh secara acak, tetapi harus dimulai dan diakhiri dengan job yang sama dengan job awal dan akhir pada partial schedule 1, sehingga diperoleh partial schedule 2. 4. Menukar posisi partial schedule 1 kedalam parent 2 dan partial schedule 2 kedalam parent 1. 5. Hasil dari pertukaran partial schedule biasanya akan menyebabkan jumlah gen yang tidak sesuai, sehingga harus dicari kelebihan dan kekuranga gen pada masing-masing anak hasil crossover.
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
22
6. Menghapus kelebihan gen dan menambah kekurangan gen pada masingmasing anak hasil crossover dengan memperhatikan urutan operasi job pada parent pembentuk partial schedule. b. Partial-Mapped Crossover (PMX) Memilih dua titik potong secara random. Substring antara kedua titik potong disebut mapping sections. Mapping sections diantara kedua induk ditukar kemudian ditentukan hubungan pemetaan antara kedua mapping sections untuk menghasilkan 2 anak. c. Order Crossover (OX) Memilih substring dari salah satu induk secara random kemudian membentuk calon anak dari substring dengan posisi yang sama. Gen yang telah ada pada induk kedua dihapus, sisanya adalah barisan gen yang belum ada pada calon anak. Kemudian barisan tersebut ditempatkan pada posisi calon anak yang masih kosong berurutan dari kiri ke kanan hingga terbentuk 1 anak. (Gen dan Cheng, 1997) Definisi2.17 Laju crossover ( p c ) adalah rasio banyaknya keturunan yang dihasilkan dari crossover pada tiap-tiap generasi terhadap ukuran populasinya. (Gen dan Cheng, 1997) Pada proses crossover terdapat rasio untuk mengontrol jumlah harapan dari kromosom yang mengalami crossover. Jumlah harapannya dihitung dengan cara p c × pop_size.
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
23
Definisi 2.18 Mutasi merupakan operator yang menghasilkan perubahan random pada kromosom. (Gen dan Cheng, 1997) Ada beberapa jenis mutasi, diantaranya: a. Swap Mutation Memilih dua posisi gen secara acak kemudian menukar gen pada kedua posisi tersebut.
(Lei, 2009)
b. Mutasi Inversi (Inversion Mutation) Memilih dua posisi dalam kromosom secara acak dan kemudian membalik untaian diantara dua posisi itu. c. Mutasi Sisipan (Insertion Mutation) Memilih gen secara acak dan menyisipkannya di posisi acak. d. Mutasi Perpindahan (Displacement Mutation) Memilih sebuah subtour secara acak dan memasukkannya pada posisi lain secara acak. (Gen dan Cheng, 1997) Definisi2.19 Laju mutasi ( p m ) adalah prosentase dari jumlah individu dalam populasi yang dimutasi. (Gen dan Cheng, 1997) Pada proses mutasi terdapat rasio untuk mengontrol jumlah harapan dari kromosom yang mengalami mutasi. Jumlah harapannya dihitung dengan cara p m × pop_size.
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
24
Secara umum langkah-langkah dalam algoritma genetika adalah sebagai berikut: 1. [Mulai] Membangkitkan populasi secara random sebanyak n individu (solusi feasible dari permasalahan) 2. [Fitness] Menilai keandalan setiap individu dalam populasi. 3. [Populasi baru] Membentuk populasi baru lewat pengulangan pengoperasian operator genetik berikut sampai populasi baru lengkap. a. [Seleksi] Memilih induk dari populasi sesuai dengan nilai keandalannya (keandalan yang lebih baik, lebih berpeluang untuk terpilih). b. [Crossover] Dengan suatu laju crossover, crossover induk untuk membentuk anak (individu baru). Jika tidak ada crossover yang dilaksanakan, anak merupakan copian yang sama dengan induknya. c. [Mutasi] Menggunakan suatu probabilitas, mutasi induk pada masingmasing sifat (lokus = posisi dalam kromosom). 4. [Mengganti] Menggunakan populasi yang baru dibentuk untuk menjalankan algoritma lebih lanjut. 5. [Menguji] Jika sudah mencapai n iterasi atau optimal, berhenti dan diperoleh solusi terbaik dari populasi ini. Jika tidak maka kembali ke langkah 2 sampai diperoleh solusi terbaik dari populasi ini. (Obitko, 1998)
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
25
2.4 Fuzzy Multi-Objective JSSP (FMOJSSP) 2.4.1 Fuzzy Number Pada JSSP Pada JSSP ini digunakan fuzzy number
khususnya Triangular Fuzzy
~ Number (TFN) yang dilambangkan dengan bentuk triplet A (a 1 ,a 2 ,a 3 ) pada
Completion Times dengan a 1 adalah batas bawah, a 2 adalah nilai tengah dan a 3
~ adalah batas atas himpunan A . Dalam meranking fuzzy number untuk mencari nilai yang paling besar metode yang digunakan dalam penelitian ini, yaitu : Kriteria 1
: Nilai kelompok terbesar digunakan sebagai kriteria pertama untuk meranking dua bilangan TFN.
~ a 1 2a 2 a 3 K 1( A ) 4 Kriteria 2
: Jika K1 tidak dapat meranking dua TFN, penduga maksimal terbaik dipilih sebagai kriteria kedua. ~ K 2 ( A) a 2
Kriteria 3
: Jika K1 dan K2 tidak dapat meranking dua TFN, beda penyebaran dipilih sebagai kriteria ketiga.
~ K 3( A) a 3 a 1 ~ dengan K i (A) merupakan kriteria ke i yang digunakan untuk merangking ~ bilangan fuzzy A . Selain waktu pemrosesan, fungsi objektif yang dapat digunakan pada Fuzzy Job Shop Scheduling Problem (FJSSP) adalah menghitung Agreement Index (AI) masing-masing job. Dalam penelitian ini Trapezoidal Fuzzy Number yang digunakan untuk mewakili duedate time dilambangkan dalam bentuk doublet
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
26
~ D (d 1,d 2 ) seperti ditunjukkan pada Gambar 2.6 dan digunakan untuk
menghitung AI seperti pada Gambar 2.7.
1
~ D
0
d2
d1
x
Gambar 2.6 Doublet Fuzzy duedate
1
~ D
~ C 0
d2 d1 Gambar 2.7 Agreement Index
x
(Sakawa dan Kubota, 2000) ~ ~ Rasio untuk AI dari C yang bersesuaian dengan D didefinisikan dengan
rumus berikut :
~ ~ ~ AI = (area C i D i )/(area C i ) dimana AI adalah Agreement Index [0,1] yang menunjukkan ketepatan waktu
~ ~ penyelesaian job dengan deadline yang diberikan, area C i D i adalah luasan ~ ~ daerah irisan antara C i yaitu Fuzzy Completion time dari job ke-i dan D i adalah
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
27
~ fuzzy duedate dari job ke-i, sedangkan area C i adalah luas wilayah Fuzzy Completion time dari job ke-i . Untuk lebih memperjelas rumus tersebut, dibawah ini akan diberikan contoh. Gambar 2.5 merupakan contoh Agreement Index dari dua bilangan fuzzy.
1,0
b
~ D
~ C
0,5
c
0,0
a
0,0
5,0
10,0
d
15,0
x
Gambar 2.8 Contoh Agreement Index (AI) Keterangan :
~ = Daerah himpunan bilangan fuzzy D ~ = Daerah himpunan bilangan fuzzy C
~ ~ = Daerah C D ~ ~ C adalah TFN dengan nilai C = (3,10,13) yang berarti waktu penyelesaian
tercepat, normal dan terlambat masing-masing adalah 3, 10 dan 13 satuan waktu,
~ dan D = (8,14). Maka diperoleh :
Skripsi
~ Fungsi keanggotaan C
~ Fungsi keanggotaan D
0; c 3 atau c 13 c 3 [c ] ; 3 c 10 7 13 c ; 10 c 13 3
1; d 8 14 d [ d ] ; 8 d 14 6 0; d 14
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
28
Dimana c dan d masing-masing merupakan bilangan yang dipetakan ke ~ ~ himpunan C dan D .
~ ~ Selanjutnya yaitu menentukan nilai luasan C D yaitu dengan cara : ~ ~ 1. Menentukan titik batas a, b, c, d untuk wilayah C D
a=3
b 3 14 b 7 6
13 c 14 c 3 6 3c 36 c 12
13b 116
d = 14
b 8,92307
~ ~ 2. Menghitung area C D :
~ ~ area C D
8, 92307
x 3
12
13
x 3 14 x 13 x dx dx dx 7 6 3 x 8, 92307 x 12
2,50530 1,81459 0,16666 4,48715 ~ Kemudian dihitung area C sebesar : ~ 111 5,5 area C 2
maka diperoleh AI sebesar : AI
4,48715 0,81584 5,5
Nilai tersebut menunjukkan ketepatan waktu penyelesaian dengan duedate sebesar 81,584%. (Kaufmann dan Gupta, 1991)
2.4.2 Multi-Objective JSSP Penyelesaian masalah JSSP biasanya hanya meggunakan perhitungan makespan sebagai fungsi objektif, namun agar lebih memenuhi keadaan nyata
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
maka
digunakan
multifungsi
objektif
(Multi-Objective
29
Function)
yang
didefinisikan sebagai berikut : Memaksimalkan
z1 :
1 n AI i n i 1
Memaksimalkan
z2 :
AI min min AI i
Meminimalkan
z3 :
~ ~ C max max C i
i 1, 2,...,n
i 1, 2,...,n
~ Dimana n adalah banyak job, AIi dan C i masing-masing adalah Agreement Index dan Completion Time dari job Ji. Fungsi objektif yang pertama digunakan untuk memaksimalkan rata-rata kesesuaian waktu penyelesaian dengan waktu tenggat atau deadline job harus diselesaikan. Fungsi objektif yang kedua adalah untuk memaksimalkan kesesuaian waktu penyelesaian dengan waktu tenggat atau deadline job yang paling kecil. Sedangkan fungsi objektif yang ketiga digunakan untuk meminimalkan waktu penyelesaian (completion time) yang paling besar dari masing-masing job. Setelah didapatkan nilai setiap fungsi objektif maka dihitung fungsi keanggotaan untuk masing masing fungsi objektif menggunakan persamaan (2.1) dan persamaan (2.2). Dari masing-masing derajat keanggotaan fungsi objektif atau fungsi tujuan maka permasalahan tersebut dapat ditransformasi untuk mencari nilai maksimal dari :
f min { i ( z i )} i 1, 2,3
yang akan digunakan sebagai fungsi fitness. Dengan i [ z i ] (i=1,2,3) merupakan derajat keanggotaan ke-i untuk fungsi objektif ke-i.
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
30
2.4.3 Metode Giffler Dan Thompson Pada permasalahan JSSP suatu optimal schedule akan diperoleh dari sebuah himpunan active schedule. Sebuah jadwal dikatakan aktif jika tidak ada operasi yang dapat dimulai lebih awal tanpa menunda beberapa operasi lain atau melanggar kendala urutan mesin. Algoritma Giffler dan Thompson dikenal sebagai sebuah prosedur untuk membangkitkan active schedule. Untuk lebih menyesuaikan dengan FJSSP algoritma tersebut dapat dikembangkan sebagai berikut : Step 1 : Tentukan himpunan S, himpunan semua operasi paling awal pada urutan mesin diantara operasi yang belum dijadwalkan. Himpunan S disebut cut. Step 2 : Abaikan bahwa hanya satu operasi yang dapat diproses pada masingmasing mesin pada suatu waktu, buat sebuah jadwal dari fuzzy completion
time
masing-masing
operasi
dan
tentukan
EC i1, j ,r , EC i2, j , r , EC i3, j ,r yang merupakan fuzzy completion time yang diperoleh dari masing-masing operasi Oi,j,r S. Step 3 : Tentukan operasi Oi*,j*,r* yang mempunyai nilai EC1 minimum pada himpunan S : EC i1*, j*,r* min{EC i1, j ,r | Oi , j , r S} . Tentukan himpunan G yang merupakan himpunan operasi Oi , j , r * S dan menggunakan mesin yang sama yaitu Mr* dengan operasi Oi*, j *,r * dan pemrosesan
Oi , j , r * dan Oi*, j *,r * tumpang tindih (overlap). Karena operasi pada G overlap dalam satu waktu maka G disebut conflict set.
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
31
Step 4 : Pilih satu operasi Ois , js , r * diantara conflict set G secara acak. Step 5 : Ambil operasi terpilih sebagai standart, update EC1, EC2, dan EC3 dengan menambahkan waktu pemrosesan pada waktu mulai operasi yang ditentukan dengan nilai maksimum dari operasi terpilih sebagai pendahulu pada job yang sama diantara job yang termasuk operasi dengan konflik. Hapus operasi terpilih dari cut. Step 6 : Ulangi langkah 3-5 hingga semua operasi telah terjadwal. (Sakawa dan Kubota, 2000)
2.5 JAVA Java menurut definisi dari Sun adalah nama untuk sekumpulan teknologi untuk membuat dan menjalankan perangkat lunak pada komputer standalone ataupun pada lingkungan jaringan. Java berdiri diatas sebuah mesin interpreter yang diberi nama Java Virtual Machine (JVM). JVM inilah yang akan membaca bytecode dalam file .class dari suatu program sebagai representasi langsung program yang berisi bahasa mesin. Oleh karena itu, bahasa Java disebut sebagai bahasa pemrograman yang portable karena dapat dijalankan pada berbagai sistem operasi, asalkan pada sistem operasi tersebut terdapat JVM. Java merupakan bahasa pemrograman yang bersifat case sensitive yang berarti penulisan menggunakan huruf besar ataupun huruf kecil pada kode program dapat berarti lain, misalnya penulisan “System” akan diartikan berbeda dengan “system” oleh interpreter. (Shalahuddin dan Rosa, 2007)
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
32
2.6 NETBEANS IDE NetBeans sebagai IDE (Integrated Development Environment) ditujukan untuk memudahkan pemrograman Java. Dalam NetBeans, pemrograman dilakukan berbasiskan visual dan event-driven. Persis seperti IDE lain, misalnya Borland Delphi dan Microsoft Visual Studio. Untuk membuat dialog atau user interface, kita tidak perlu membuat teks program secara manual baris per baris, tetapi cukup klik pada component-pallete. Teks program akan dihasilkan secara otomatis. NetBeans mencakup compiler atau builder, dan debugger internal. Hal ini sangat memudahkan proses paska perancangan program. Proses deployment dan/atau tes dapat juga dilakukan dari dalam NetBeans. (Hartati dkk, 2007)
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
BAB III METODE PENELITIAN
Adapun langkah-langkah yang dilakukan oleh penulis dalam menyelesaikan permasalahan adalah sebagai berikut : 1. Study literature atau studi pustaka yang terkait dengan Job Shop Scheduling Problems (JSSP), Fuzzy, Genetic Algorithm (GA) dan Fuzzy Multi-objective JSSP. 2. Menyusun algoritma untuk menyelesaikan JSSP dengan Fuzzy Multi-objective dan GA, yaitu sebagai berikut : a. Menginputkan parameter yang akan digunakan yaitu antara lain pop_size, derajat kesamaan tiap individu (degree), nilai tour, nilai probabilitas crossover (Pc), nilai probabilitas mutasi (Pm) dan max_gen. b. Membangkitkan individu awal satu persatu dan mengaktifkan individu yang terbentuk dengan menggunakan metode Giffler dan Thompson. Jika individu yang dibangkitkan merupakan individu awal yang pertama maka pengecekan derajat kesamaan (degree) belum dilakukan sehingga akan dibangkitkan individu awal yang selanjutnya. Setelah terbentuk individuindividu maka dilakukan pengecekan derajat kesamaan (degree) antar individu. c. Melakukan pengecekan jumlah individu berdasarkan pop_size, jika pop_size terpenuhi maka lanjut kelangkah e, jika tidak maka kembali ke langkah d.
33 Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
34
d. Mengevaluasi masing-masing individu dengan menghitung nilai setiap fungsi objektifnya (zi). e. Menentukan nilai keanggotaan linear untuk masing-masing zi pada tiap individu. f. Melakukan operator genetic pada GA dengan langkah sebagai berikut : 1) Menentukan seleksi induk crossover dan mutasi. Seleksi yang akan digunakan adalah seleksi turnamen (Tournament Selection). Tahapan-tahapan seleksi turnamen yaitu : 1.1 Menetukan nilai tour seleksi, yaitu banyaknya kromosom yang akan mengalami turnamen. 1.2 Memilih
secara random
kromosom-kromosom
yang akan
diturnamenkan pada populasi sebanyak tour. 1.3 Menentukan calon induk untuk crossover dan mutasi dengan memilih
nilai
fitness
terbesar
diantara
kromosom
yang
diturnamenkan. 1.4 Membangkitkan atau generate bilangan acak dari interval [0,1] untuk masing-masing calon induk. 1.5 Menentukan induk yang akan digunakan pada operasi crossover dan mutasi. 2) Melakukan Partial Schedule Exchange Crossover (PSEX) pada kromosom induk crossover. Tahapan-tahapan pada PSEX yaitu :
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
35
2.1 Memilih satu posisi pada parent 1 secara random. 2.2 Menentukan job terdekat yang sama dengan job pada posisi terpilih, sehingga diperoleh partial schedule 1. 2.3 Partial schedule selanjutnya tidak diperoleh secara acak, tetapi harus dimulai dan diakhiri dengan job yang sama dengan job awal dan akhir pada partial schedule 1, sehingga diperoleh partial schedule 2. 2.4 Menukar posisi partial schedule 1 kedalam parent 2 dan partial schedule 2 kedalam parent 1. 2.5 Hasil
dari
pertukaran
partial
schedule
biasanya
akan
menyebabkan jumlah gen yang tidak sesuai, sehingga harus dicari kelebihan dan kekuranga gen pada masing-masing anak hasil crossover. 2.6 Menghapus kelebihan gen dan menambah kekurangan gen pada masing-masing anak hasil crossover dengan memperhatikan urutan operasi job pada parent pembentuk partial schedule. 3) Melakukan Swap Mutation pada kromosom induk mutasi. Tahapan-tahapan Swap Mutation yaitu : 3.1 Memilih 2 posisi gen secara acak. 3.2 Menukar gen pada kedua posisi tersebut. g. Mengaktifkan masing-masing individu anak yang dihasilkan pada operator GA dengan menggunakan metode Giffler dan Thompson.
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
36
h. Mengevaluasi masing-masing individu anak dengan menghitung nilai setiap fungsi objektif. i. Membentuk populasi baru yaitu dengan cara : 1.) Mengumpulkan individu dari populasi awal, anak hasil crossover dan anak hasil mutasi. 2.) Semua individu tersebut diurutkan berdasarakan fungsi tujuannya. 3.) Diambil individu terbaik sebanyak pop_size. j. Ulangi proses e-g sebanyak maksimum generasi (max_gen). 3. Membuat program dari algoritma yang telah disusun. 4. Mengimplementasikan program yang telah dibuat pada contoh kasus.
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
BAB IV PEMBAHASAN
Pada bab ini dijelaskan mengenai penyelesaian Job Shop Scheduling dengan Fuzzy Multi-Objective menggunakan Genetic Algorithm (GA). Permasalahan Job Shop Scheduling adalah suatu permasalahan mencari urutan proses dari job-job pada tiap-tiap mesin yang berbeda sebagai suatu solusi yang sesuai dengan fungsi tujuan dan memenuhi batasan urutan mesin untuk masing-masing job. 4.1
Prosedur Algoritma Genetik Untuk Permasalahan Job Shop Scheduling Prosedur Algoritma Genetik yang digunakan dalam menyelesaikan
permasalahan Job Shop Scheduling adalah sebagai berikut : Prosedur GA secara ringkas dapat dilihat pada Gambar 4.1. Misalkan P(t) dan C(t) masing-masing adalah induk dan anak pada generasi ke-t dan max_gen merupakan iterasi maksimum yang ditentukan. Prosedur untuk Genetic Algorithm begin t ← 0; parameter setting; inisialisasi P(t); evaluasi P(t); while (t ≠ max_gen) do operasi genetik pada P(t) untuk mendapatkan C(t); pengaktifan schedule C(t); evaluasi C(t); pilih P(t+1) dari P(t) dan C(t); t ← t + 1; end end
Gambar 4.1 Prosedur untuk Genetic Algorithm
37 Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
Terdapat
beberapa
parameter
yang
digunakan
38
dalam
GA
untuk
menyelesaikan JSSP. Parameter tersebut antara lain jumlah job (n), jumlah mesin (m), urutan operasi mesin untuk tiap-tiap job (seqMachine), waktu proses untuk setiap operasi (processTime), duedate untuk setiap job (duedate), ukuran populasi (pop_size), batas derajat kesamaan kromosom awal (degree), probabilitas crossover
(Pc), probabilitas
mutasi
(Pm),
ukuran individu
yang akan
diturnamenkan (tour), dan maksimum generasi (max_gen). Prosedur penentuan parameter dapat dilihat pada Gambar 4.2. Prosedur untuk Parameter Setting begin jumlah job : jumlah mesin : urutan operasi mesin : waktu proses : duedate : ukuran populasi : degree of similarity : probabilitas crossover : probabilitas mutasi : ukuran turnamen : maksimum iterasi : end
n; m; seqMachine; processTime; duedate; pop_size; degree; P c; P m; tour; max_gen;
Gambar 4.2 Prosedur untuk Parameter Setting Flowchart penyelesaian dengan menggunakan GA dapat dilihat pada Lampiran 1. Langkah I
: Generate Populasi Awal
Populasi awal merupakan kumpulan dari individu atau kromosom yang dibangkitkan secara random. Kromosom tersebut merupakan solusi urutan scheduling dari permasalahan job shop. Generate populasi awal merupakan proses pembangkitan sejumlah kromosom secara random dalam suatu ruang pencarian yaitu berupa kode urutan
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
39
job yang merupakan himpunan solusi feasible. Sejumlah kromosom yang dibangkitkan akan dibentuk menjadi sebuah populasi pada masing-masing iterasi atau generasi dan diproses hingga mencapai max_gen yang ditentukan. Pengkodean kromosom diberikan dalam bentuk permutasi dengan pengulangan (permutation with repetition) dari job-job sebanyak perkalian jumlah job yang dikerjakan dengan banyak mesin. Prosedur yang digunakan untuk melakukan generate populasi awal dapat dilihat pada Gambar 4.3. Misal ind adalah banyak kromosom yang telah dibangkitkan pada saat i dan degij merupakan derajat kesamaan dari kromosom ke-i yang baru dibangkitkan dengan kromosom ke-j yang sudah dibangkitkan terlebih dahulu. Prosedur untuk Inisialisasi 𝐏 𝐭 begin i ← 0; while (i <pop_size ) do j ← 0; membangkitkan sebuah kromosom(); pengaktifan schedule (); if (i ≠ 1) then ind = i; while ( j
degree) then i = i − 1; end end i ← i + 1; end end
Gambar 4.3 Prosedur untuk Inisialisasi Pada prosedur generate populasi awal terdapat langkah untuk generate sebuah kromosom. Prosedur generate kromosom dapat dilihat pada Gambar 4.4. Prosedur untuk Generate Kromosom begin generate urutan job (); menentukan operasi job (); menentukan urutan mesin (); end
Gambar 4.4 Prosedur untuk Generate Kromosom
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
40
Prosedur generate kromosom dilakukan dengan cara membangkitkan kode urutan job secara random dengan menggunakan pengkodean permutasi yang mewakili gen-gen pembentuk kromosom. Gambar 4.5 menunjukkan prosedur pembentukan kode urutan job. Misalkan untuk jumlah gen disimbolkan dengan genes, jobk merupakan kode job ke-k, random (n-1) merupakan proses random bilangan integer antara 0 sampai (n-1), dan num, a, temp adalah variabel bantuan. Prosedur untuk Generate Urutan Job begin k ← 0; genes ← n × m; num() ← 0: n ; while (k
Gambar 4.5 Prosedur untuk Generate Urutan Job Setelah didapatkan urutan dari job, langkah selanjutnya yang dilakukan adalah menentukan urutan operasi dari masing-masing job. Prosedur yang digunakan untuk menentukan urutan operasi dapat dilihat pada Gambar 4.6. Misalkan operationk
menunjukkan operasi pada urutan job atau gen ke-k,
jobOperjobk merupakan variable bantuan untuk menentukan jumlah operasi. Prosedur untuk Menentukan Operasi Job begin k ← 0; jobOper() ← 0: m ; while (k
Gambar 4.6 Prosedur untuk Menentukan Operasi Job
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
41
Setelah didapatkan urutan opebbrasi masing-masing job, selanjutnya ditentukan mesin yang digunakan dan waktu proses (Processing Time) untuk masing-masing job. Prosedur tersebut dapat dilihat pada Gambar 4.7. Misalkan machinek menunjukkan mesin yang digunakan untuk gen ke-k, dan karena waktu pemrosesan menggunakan tiga bilangan fuzzy maka processingTkl menunjukkan bilangan fuzzy ke-l untuk waktu pemrosesan gen ke-k, processTime menunjukkan waktu pemrosesan . Prosedur untuk Menetukan Urutan Mesin begin k ← 0; while (k < genes ) do 𝑚𝑎𝑐ℎ𝑖𝑛𝑒𝑘 = 𝑠𝑒𝑞𝑀𝑎𝑐ℎ𝑖𝑛𝑒𝑗𝑜𝑏𝑘 𝑜𝑝𝑒𝑟𝑎𝑡𝑖𝑜𝑛𝑘 ; for l ← 0to l < 3 do 𝑝𝑟𝑜𝑐𝑒𝑠𝑠𝑖𝑛𝑔𝑇𝑘𝑙 = 𝑝𝑟𝑜𝑐𝑒𝑠𝑠𝑇𝑖𝑚𝑒𝑗𝑜𝑏𝑘 𝑜𝑝𝑒𝑟𝑎𝑡𝑖𝑜𝑛𝑘 𝑙 ; end k ← k + 1; end end
Gambar 4.7 Prosedur untuk Menentukan Urutan Mesin Setelah pembangkitan kromosom selesai maka kromosom-kromosom yang mewakili sebuah schedule tersebut akan diaktifkan menggunakan algoritma Giffler-Thompson. Prosedur pengaktifan schedule dapat dilihat pada Gambar 4.8.
Prosedur untuk Pengaktifan Schedule begin menghitung completion time dan delay time(); pengaktifan(); end
Gambar 4.8 Prosedur untuk Pengaktifan Schedule Langkah awal yang dilakukan untuk mengaktifkan schedule adalah dengan menghitung waktu penyelesaian job pada masing-masing kromosom. Misalkan timeJobij dan timeMachineij masing-masing adalah waktu penyelesaian ke-j untuk
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
42
job dan mesin pada gen ke-i, startingij merupakan waktu mulai ke-j untuk job pada gen ke-i dan delayij merupakan waktu luang ke-j pada gen ke-i. Prosedur untuk menghitung waktu penyelesaian dan waktu luang dapat dilihat pada Gambar 4.9. Prosedur untuk Menghitung Completion Time dan Delay Time begin i ← 0; j ← 0; timeJob ← 0, 𝑛, 3 ; timeMachine ← 0: 𝑚, 3 ; delay ← (0: genes, 3); while (i < genes ) do for j ← 0 to j < 3 do if (𝑡𝑖𝑚𝑒𝐽𝑜𝑏𝑗𝑜𝑏𝑖 𝑗 < 𝑡𝑖𝑚𝑒𝑀𝑎𝑐ℎ𝑖𝑛𝑒𝑚𝑎𝑐ℎ𝑖𝑛𝑒𝑖 𝑗 ) then 𝑠𝑡𝑎𝑟𝑡𝑖𝑛𝑔𝑖𝑗 = 𝑡𝑖𝑚𝑒𝑀𝑎𝑐ℎ𝑖𝑛𝑒𝑚𝑎𝑐ℎ𝑖𝑛𝑒𝑖 𝑗 ; else 𝑠𝑡𝑎𝑟𝑡𝑖𝑛𝑔𝑖𝑗 = 𝑡𝑖𝑚𝑒𝐽𝑜𝑏𝑗𝑜𝑏𝑖 𝑗 ; 𝑑𝑒𝑙𝑎𝑦𝑖𝑗 = 𝑡𝑖𝑚𝑒𝐽𝑜𝑏𝑗𝑜𝑏𝑖 𝑗 − 𝑡𝑖𝑚𝑒𝑀𝑎𝑐ℎ𝑖𝑛𝑒𝑚𝑎𝑐ℎ𝑖𝑛𝑒𝑖 𝑗 ; end 𝑡𝑖𝑚𝑒𝑀𝑎𝑐ℎ𝑖𝑛𝑒𝑚𝑎𝑐ℎ𝑖𝑛𝑒𝑖 𝑗 = 𝑠𝑡𝑎𝑟𝑡𝑖𝑛𝑔𝑖𝑗 + 𝑝𝑟𝑜𝑐𝑒𝑠𝑠𝑖𝑛𝑔𝑇𝑖𝑗 𝑡𝑖𝑚𝑒𝐽𝑜𝑏𝑗𝑜𝑏𝑖𝑗 = 𝑡𝑖𝑚𝑒𝑀𝑎𝑐ℎ𝑖𝑛𝑒𝑚𝑎𝑐ℎ𝑖𝑛𝑒𝑖 𝑗 ; end i ← i + 1; end end
Gambar 4.9 Prosedur untuk Menghitung Completion Time dan Delay Time Setelah terbentuk schedule untuk penghitungan waktu penyelesaian, selanjutnya adalah melakukan pengaktifan schedule dengan menggunakan informasi waktu luang yang telah didapat sebelumnya. Misalkan genes adalah jumlah gen, machinei dan jobi merupakan mesin dan job yang berproses pada gen ke-i, startingij dan completeij merupakan waktu mulai dan selesai ke-j untuk job pada gen ke-i, dan delayij merupakan waktu luang ke-j pada gen ke-i. Prosedur untuk mengaktifkan schedule dapat dilihat pada Gambar 4.10.
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
43
Prosedur untuk Pengaktifan begin a = (0:genes); c = (0: genes); for i←0 to i 0) then for ii← 0 to ii
Gambar 4.10 Prosedur untuk Pengaktifan Setelah individu yang dibangkitkan sesuai dengan pop_size maka langkah selanjutnya yang dilakukan yaitu mengevaluasi setiap individu. Langkah II
: Evaluasi
Proses evaluasi merupakan proses penghitungan nilai fungsi tujuan yang terdiri dari tiga fungsi yang masing-masing dinyatakan dengan z1, z2, z3 untuk masing-masing kromosom. Fungsi-fungsi tersebut kemudian dinyatakan dengan fungsi fitness (F).
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
44
Misalkan pop_size adalah banyaknya populasi, n adalah banyaknya job, completion time adalah waktu penyelesaian untuk masing-masing job, duedate adalah waktu tenggat untuk masing-masing job,
∩
merupakan irisan dari
completion time dengan duedate, agreementIndexij menyatakan nilai agreement indexjob j (j = 0, 1, …., n) dari kromosom ke-i (i = 0, 1, …., pop_size), dan
1
merupakan nilai fungsi tujuan pertama yaitu rata-rata dari agreement index kromosom ke-i. Prosedur evaluasi fungsi z1 dapat dilihat pada Gambar 4.11. Prosedur untuk Evaluasi z1 begin i ← 0; j ← 0; k ← 0; sum ← 0; for i←0 to i<pop_size do for j←0 to j
Cij ∩Dij Cij
;
sum = sum + agreementIndexij ; end sum 𝑧1𝑖 = ; end n
end
Gambar 4.11 Prosedur untuk Evaluasi z1 Misalkan
merupakan nilai fungsi tujuan kedua yaitu minimal dari
agreement index kromosom ke-i. Prosedur untuk menentukan nilai fungsi tujuan kedua dapat dilihat pada Gambar 4.12. Prosedur untuk Evaluasi z2 begin for i=0 to i<pop_size do for j=0 to j
Gambar 4.12 Prosedur untuk Evaluasi z2
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
45
Misalkan completionTimeij menyatakan nilai waktu penyelesaian job j (j = 0, 1, …., n) pada keseluruhan mesin dari kromosom ke-i (i = 0, 1, …., pop_size), dan
merupakan nilai fungsi tujuan ketiga yaitu waktu penyelesaian maksimal
job-job pada kromosom ke-i. Prosedur untuk menentukan nilai fungsi tujuan ketiga dapat dilihat pada Gambar 4.13. Prosedur untuk Evaluasi z3 begin for i = 0 to i < pop_size do for j=0 to j
Gambar 4.13 Prosedur untuk Evaluasi z3 Setelah didapatkan nilai dari ketiga fungsi tujuan untuk masing-masing kromosom, maka selanjutnya ditentukan nilai fitness setiap kromosom. Misalkan dan
1
masing-masing menyatakan nilai fungsi tujuan ke-i (i = 0, 1, 2) yang
terendah dan tertingi, degreeMemberkl merupakan derajat kenggotaan fuzzy untuk fungsi tujuan ke-l (l = 0, 1, 2) pada kromosom ke-k (k = 0, 1, .., pop_size), dan fa merupakan nilai fitness dari kromosom ke-a (a = 0, 1, .., pop_size). Prosedur untuk menentukan nilai fitness dapat dilihat pada Gambar 4.14. Prosedur untuk Menghitung Fitness begin for i=0 to i<3 do for j=0 to j< pop_size do 𝑧𝑖 =min (𝑧𝑖𝑗 ); 𝑧𝑖1 =max (𝑧𝑖𝑗 ); end end for k=0 to k< pop_size do for l=0 to l<3 do calculate degreeMemberkl ; end end for a=0 to a< pop_size do for b=0 to b<3 do fa = min(degreeMemberab); end end end
Gambar 4.14 Prosedur untuk Menghitung Fitness
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
46
Langkah selanjutnya yaitu operasi genetik untuk memperoleh keturunan atau anak. Prosedur yang dilakukan untuk melakukan operasi genetik dapat dilihat pada Gambar 4.15. Misalkan P(t) dan C(t) masing-masing merupakan induk dan anak pada proses operasi genetik pada generasi ke-t.
Prosedur Operasi Genetik P(t) untuk Mendapatkan C(t) begin seleksi turnamen(); partial schedule exchange crossover(); swap mutation (); end
Gambar 4.15 Prosedur Operasi Genetik
untuk Mendapatkan
Langkah III : Seleksi Tahapan seleksi merupakan tahapan untuk menyeleksi atau menentukan calon induk pada proses crossover dan mutasi pada kromosom-kromosom dalam satu populasi. Seleksi yang digunakan adalah seleksi tournament. Prosedur seleksi dapat dilihat pada Gambar 4.16. Misalkan tour menyatakan banyanknya kromosom random yang akan diturnamenkan, rij (i = 0, 1, .., pop_size dan j = 0, 1, .., tour) merupakan angka random yang membangkitkan kromosom ke-rij untuk diturnamenkan,
adalah
nilai fitness dari kromosom ke-ril (l = 0, 1, .., tour), candidatei adalah calon induk ke-i , dan
Skripsi
merupakan kromosom ke-ai atau kromosom terpilih.
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
47
Prosedur untuk Seleksi Turnamen begin maks = (0: pop_size); a = (0: pop_size); for i=0 to i< pop_size do for j=0 to j< tour do rij = random (pop_size-1); end for l=0 to l < tour do if (maksl < 𝑓𝑟𝑖𝑙 )then maksl = 𝑓𝑟𝑖𝑙 ; a i = rij ; end candidatei = 𝑣𝑎𝑖 ; end end
Gambar 4.16 Prosedur untuk Seleksi Turnamen Proses tournament diatas dilakukan sebanyak dua kali untuk memperoleh calon induk pada proses crossover dan mutasi. Setelah proses tersebut selesai maka langkah selanjutnya yang dilakukan yaitu seleksi induk untuk proses crossover dan mutasi. 1. Seleksi Crossover Tahapan ini dilakukan untuk mendapatkan induk yang akan di crossover dari calon induk yang telah didapat dari hasil seleksi. Proses ini dilakukan dengan cara mengenerate bilangan random dengan interval [0,1] yang dinyatakan dengan rc dan c = 1, 2, …, pop_size. Pemilihan induk yang akan di crossover harus memenuhi ketentuan sebagai berikut : Jika rc < pc, maka kromosom ke-c tersebut akan terpilih menjadi induk yang akan mengalami crossover. Prosedur untuk seleksi crossover dapat dilihat pada Gambar 4.17. Misalkan rc adalah bilangan random ke-c, Pc adalah probabilitas crossover, dan vc adalah kromosom ke-c.
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
48
Prosedur untuk Seleksi Crossover begin c ← 0; crossover ← 0; while (c<pop_size) do rc random [0,1]; if (rc
Gambar 4.17 Prosedur untuk Seleksi Crossover 2. Seleksi Mutasi Seleksi induk mutasi dilakukan seperti pada seleksi crossover. Misalkan bilangan random yang digenerate dinyatakan dengan rq dan q = 1, 2, …, pop_size. Pemilihan induk yang akan di mutasi harus memenuhi ketentuan sebagai berikut : Jika rq < pm, maka kromosom ke-q tersebut akan terpilih menjadi induk yang akan mengalami mutasi. Prosedur untuk seleksi mutasidapat dilihat pada Gambar 4.18. Misal rq adalah random ke-q, Pm adalah probabilitas mutasi, dan vq adalah kromosom ke-q.
Prosedur untuk Seleksi Mutasi begin q ← 0; mutation ← 0; while (q < pop_size) do rq random [0,1]; if (rq
Gambar 4.18 Prosedur untuk Seleksi Mutasi Dari proses diatas telah diperoleh induk yang akan mengalami crossover dan langkah selanjutnya yang dilakukan yaitu mengcrossover induk tersebut.
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
49
Langkah IV : Crossover Setelah diperoleh induk yang akan di crossover, proses selanjutnya yang dilakukan adalah mengcrossover induk-induk tersebut menggunakan partial schedule exchange crossover. Jika dari seleksi crossover dihasilkan induk crossover yang jumlahnya gasal, maka induk pada urutan terakhir dibuang sehingga jumlah induk crossover menjadi genap. Selanjutnya induk tersebut akan mengalami crossover dengan cara mengambil dua induk yang akan dicrossover untuk menghasilkan dua anak. Proses tersebut dilakukan sampai semua induk mengalami crossover. Jika pada proses seleksi crossover tidak diperoleh induk crossover maka proses crossover tidak dilakukan. Prosedur crossover menggunakan partial schedule exchange crossover dapat dilihat pada Gambar 4.19. Prosedur untuk Partial Schedule Exchange Crossover begin menentukan partial schedule dari parent 0(); menentukan partial schedule dari parent1(); menentukan exceeded dan missed genes (); menentukan offspring (); end
Gambar 4.19 Prosedur untuk Partial Schedule Exchange Crossover Prosedur untuk menentukan partial schedule dari induk ke-0 dapat dilihat pada Gambar 4.20. Misalkan genes menyatakan jumlah gen pada satu kromosom, pos1 adalah posisi gen yang dibangkitkan secara acak, n1 adalah banyaknya partial schedule 0, parentC0j merupakan gen ke-j dari induk crossover ke-0, dan partial0ii merupakan partial schedule 0 ke-ii.
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
50
Prosedur untuk Menetukan Partial Schedule dari Parent 0 begin n1 ← 0; pos1 = random (genes-1); for j ← (pos1 + 1) to j < genes do n1++; if (𝑝𝑎𝑟𝑒𝑛𝑡𝐶0𝑗 = 𝑝𝑎𝑟𝑒𝑛𝑡𝐶0𝑝𝑜𝑠1 ) then break end end ii ← 0; for k ← pos1 to k ≤ (pos1 + n1) do partial0ii = parentC0k; ii ← ii + 1; end end
Gambar 4.20 Prosedur untuk Menetukan Partial Schedule dari Parent 0 Sedangkan prosedur untuk menentukan partial schedule dari induk ke-1 dapat dilihat pada Gambar 4.21. Misalkan genes menyatakan jumlah gen pada satu kromosom, pos1 adalah posisi gen yang diperoleh pada induk crossover pertama, pos2 adalah posisi gen yang bersesuaian dengan pos1, banyaknya partial schedule 1, parentC1i
2 adalah
merupakan gen ke-i dari induk
crossover ke-1, dan partial1jj merupakan partial schedule 1 ke-jj. Prosedur untuk Menetukan Partial Schedule dari Parent 1 begin for i ← 0 to i < genes do if(𝑝𝑎𝑟𝑒𝑛𝑡𝐶1𝑖 = 𝑝𝑎𝑟𝑒𝑛𝑡𝐶0𝑝𝑜𝑠1 ) then pos2 = i; break end end n2 ← 0; for j ←pos2 to j < genes do n2++; if(𝑝𝑎𝑟𝑒𝑛𝑡𝐶1𝑗 = 𝑝𝑎𝑟𝑒𝑛𝑡𝐶1𝑝𝑜𝑠 ) then break end end jj ← 0; for k ← pos2 to k ≤(pos2 + n2) do partial1jj = parentC1k; jj ← jj + 1; end end
Gambar 4.21 Prosedur untuk Menetukan Partial Schedule dari Parent 1
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
Setelah
diperoleh
masing-masing
partial
51
schedule,
maka
langkah
selanjutnya adalah menukarkan partial schedule1 ke calon anak ke-0 dan partial schedule0 ke calon anak ke-1 dan menentukan gen kurang dan berlebih pada masing-masing calon anak. Prosedur untuk menentukan gen kurang dan lebih dapat dilihat pada Gambar 4.22. Misalkan ii dan jj merupakan jumlah partial schedule 0 dan jumlah partial schedule 1, partial0i dan partial1j merupakan partial schedule 0 ke-i dan partial schedule 1 ke-j, missed0i dan missed1i merupakan gen kurang ke-i pada calon anak 0 dan calon anak 1, dan exceed0i dan exceed1i merupakan gen lebih ke-i pada calon anak 0 dan calon anak 1. Prosedur untuk Menentukan Exceeded dan Missed Genes begin for i ← 0 to i < 𝑖𝑖 do for j ← 0 to j < 𝑗𝑗 do if (partial0i = partial1j) then partial0i = partial1j = -1; break end end n3= 0; n4 = 0; for k ← 0 to k < 𝑖𝑖 do if (partial0k ≠ -1) then n3++; end for l ← 0 to l < 𝑖𝑖 do if (partial1l ≠ -1) then n4++; end i2 = 0; if (n3!=0) then for j ← 0 to j < 𝑖𝑖 do if (partial0j ≠ -1) then missed0i2 = exceed1i2 = partial0j ; i2++; end i3 = 0; if (n3!=0) then for k ← 0 to k < 𝑗𝑗 do if (partial1k ≠ -1) then missed1i3 = exceed0i3 = partial1k ; i3++; end end
Gambar 4.22 Prosedur untuk Menentukan Exceeded dan Missed Genes
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
52
Langkah selanjutnya yaitu membentuk offspring crossover. Prosedur pembentukan offspring dapat dilihat pada Gambar 4.23. Misalkan offspringC0 dan offspringC1 merupakan anak hasil crossover ke-0 dan anak hasil crossover ke-1. Prosedur untuk Menentukan Offspring begin for i ← 0 to i < genes do offspringC0 = parent0i ; offspringC1 = parent1i ; end hapus partial schedule 0 dari offspringC0; tambahkan partial schedule 1 ke offspringC0; hapus partial schedule 1 dari offspringC1; tambahkan partial schedule 0 ke offspringC1; hapus exceed gen pada offspringC0dan offspringC1; tambahkan missed gen pada offspringC0dan offspringC1; end
Gambar 4.23 Prosedur untuk Menentukan Offspring Setelah melakukan proses crossover, langkah selanjutnya yang dilakukan yaitu proses mutasi induk yang telah diperoleh pada proses seleksi mutasi. Langkah V
: Mutasi
Langkah selanjutnya yaitu melakukan proses mutasi pada induk yang terpilih pada seleksi mutasi. Mutasi merupakan proses perubahan sifat kromosom secara acak sehingga dihasilkan struktur kromosom yang baru. Jika dari seleksi mutasi tidak diperoleh induk mutasi maka proses mutasi tidak dilakukan. Prosedur mutasi menggunakan swap mutation dapat dilihat pada Gambar 4.24. Misalkan pos1 dan pos2 adalah dua posisi gen yang dibangkitkan secara acak, mutation adalah banyak kromosom yang akan mengalami mutasi, parentm merupakan induk yang akan di mutasi, offspringmipos1 dan offspringmipos2 masingmasing merupakan gen pada posisi pos1 dan pos2 individu atau anak ke-i.
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
53
Prosedur untuk Swap Mutation begin i ← 0; pos1 = random (genes-1); pos2 = random (genes-1); while (pos1= pos2) do pos2 = random (genes-1); end offspringm ← parentm; while (i<mutation ) do temp = offspringmipos1; offspringmipos1 = offspringmipos2; offspringmipos2 = temp; i ← i + 1; end end
Gambar 4.24 Prosedur untuk Swap Mutation Setelah individu baru hasil proses crossover dan mutasi diperoleh, maka dibentuk populasi baru yang akan diproses pada iterasi selanjuntnya. Langkah VI : Pembentukan Populasi Baru Untuk membentuk populasi baru, langkah awalnya yaitu mengumpulkan populasi awal, anak hasil crossover dan anak hasil mutasi. Kemudian kromosom tersebut diurutkan sesuai fitnessnya. Kromosom yang terbaik dipilih sebanyak pop_size untuk membentuk populasi baru. Sedangkan kromosom yang tidak terpilih akan dikeluarkan dari populasi. Prosedur untuk membentuk populasi baru dapat dilihat dalam Gambar 4.25. Prosedur untuk Membentuk Populasi Baru begin menggabungkan kromosom; mengurutkan kromosom; mengambil kromosom terbaik sebanyak pop_size; end
Gambar 4.25 Prosedur untuk Membentuk Populasi Baru
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
54
Dalam pembentukan populasi baru, langkah pertama yang dilakukan yaitu menggabungkan individu atau kromosom awal dan anak hasil crossover dan mutasi. Misalkan sumOffS merupakan jumlah offspring hasil crossover dan mutasi, sumChrom merupakan jumlah kromosom dari populasi awal dan offspring, mutation dan crossover merupakan banyanknya offspring hasil crossover dan mutasi, offspringci dan offspringmj masing-masing menyatakan offspring hasil crossover ke-i dan mutasi ke-j, chromk merupakan kromosom ke-k dari populasi awal dan nChromk merupakan kromosom ke-k dari populasi gabungan. Prosedur penggabungan populasi awal dengan offspring hasil crossover dan mutasi dapat dilihat pada Gambar 4.26. Prosedur untuk Menggabungkan Kromosom begin j ← 0;k ← 0;l ← 0; sumOffS ←mutation + crossover; sumChrom ← pop_size + sumOffS; for i ← 0 to i <sumOffS do if (i
Gambar 4.26 Prosedur untuk Menggabungkan Kromosom Langkah kedua yang dilakukan yaitu mengurutkan seluruh kromosom gabungan berdasarkan nilai fitness masing-masing kromosom. Prosedur pengurutan kromosom dapat dilihat pada Gambar 4.27. Misalkan fitnessi dan fitnessj adalah nilai fitness untuk kromosom ke-i dan ke-j.
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
55
Prosedur untuk Mengurutkan Kromosom begin for i← 0 to i <(sumChrom-1) do for j ←i + 1 to j < sumChrom do if ( fitnessi < fitnessj) do temp = fitnessi; fitnessi = fitnessj; fitnessj = temp; temp = nChromi; nChromi = nChromj; nChromj = temp; end end end
Gambar 4.27 Prosedur untuk Mengurutkan Kromosom Setelah diurutkan, langkah terakhir yaitu kromosom-kromosom gabungan tersebut dipilih yang terbaik sebanyak pop_size untuk membentuk populasi baru. Prosedur pemilihan kromosom untuk populasi baru dapat dilihat pada Gambar 4.28. Misalkan newChromi adalah kromosom ke-i pada populasi baru.
Prosedur untuk Mengambil Kromosom Terbaik begin for i← 0 to i <pop_size do newChromi = nChromi ; end end
Gambar 4.28 Prosedur untuk Mengambil Kromosom Terbaik Setelah diperoleh individu pada populasi baru, maka selanjutnya populasi baru tersebut akan diuji.
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
56
Langkah VII : Menguji Populasi Baru Pada langkah ini dilakukan proses pengujian untuk menguji populasi baru dengan kriteria yang telah ditentukan yaitu max_gen. Jika kriteria tersebut dipenuhi, maka proses iterasi berhenti dan diperoleh solusi terbaik dari populasi terakhir tersebut. Sebaliknya, jika tidak dipenuhi, maka kembali ke Langkah III, dan populasi baru pada Langkah VI akan dijadikan populasi awal pada generasi selanjutnya. Prosedur pengujian dapat dilihat pada Gambar 4.29. Prosedur untuk Tes Pemberhentian Iterasi begin t ← t + 1; if (t < max_gen ) then ulangi langkah seleksi; else berhenti dan diperoleh individu terbaik; end
Gambar 4.29 Prosedur untuk Tes Pemberhentian Iterasi Kromosom terbaik yang diperoleh pada generasi terakhir merupakan solusi dari permasalahan, dan proses algoritma berhenti.
4.2
Data Data yang digunakan diambil dari Sakawa (2002). Data yang digunakan
terdiri dari tiga permasalahan dan ditunjukkan pada Tabel 4.1. Tabel 4.1 Data Permasalahan No. 1. 2. 3.
Skripsi
Nama Permasalahan (Job x Mesin) Problem 1 FMOJSSP (6 x 6) Problem 2 FMOJSSP (6 x 6) Problem 3 FMOJSSP (6 x 6)
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
57
Data urutan operasi mesin pada masing-masing job, waktu proses fuzzy (Fuzzy Processing Time) dan waktu duedate fuzzy (Fuzzy Due Date) secara lengkap dapat dilihat pada Lampiran 2. Berikut penjelasan mengenai data yang ditunjukkan pada Lampiran 2. Data pertama menyatakan bahwa job 0 pada operasi ke-0 diproses pada mesin 3 dengan waktu proses fuzzy yaitu (9, 13, 17) satuan waktu, kemudian job 0 pada operasi ke-1 diproses pada mesin 2 dengan waktu proses fuzzy yaitu (6, 9, 12) satuan waktu, dan seterusnya. Untuk job 1, job 2, job 3, job 4dan job 5 sesuai dengan penjelasan pada job 0.
4.3
Penyelesaian Manual terhadap Contoh Kasus Job Shop Scheduling Problem 6x6 Pada contoh kasus ini, terdapat 6 job yang akan dikerjakan pada 6 mesin.
Masing-masing job akan diproses pada tiap mesin sebanyak satu kali dan tiap job memiliki urutan proses mesin masing-masing. Urutan operasi mesin, waktu proses dan waktu duedate tiap-tiap job dapat dilihat pada Lampiran 2. Penyelesaian Tahapan awal penyelesaian masalah tersebut adalah menentukan parameterparameter yang akan digunakan untuk proses selanjutnya. Parameter-parameter yang digunakan antara lain: pop_size
= 10
= 0,6
degree of similarity = 0,9
= 0,1
tour
Skripsi
= 2
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
58
Generasi ke-0 Langkah I
: Generate Populasi Awal
Proses generate populasi awal dimulai dengan melakukan generate kromosom yaitu membangkitkan gen-gen yang berupa kode job secara random sejumlah n × m dimana n adalah banyaknya job dan m adalah banyaknya mesin. Pada kasus ini terdapat 6 job dan 6 mesin, maka dalam satu kromosom akan dibangkitan 36 gen. Proses pembangkitan kromosom dilakukan berdasarkan pengecekan degree of similarity masing-masing kromosom dan dilakukan sebanyak pop_size. Misalkan kromosom pertama yang dibangkitkan adalah : Kode Job 0 0 2 0 5 1 3 2 4 4 5 3 1 1 4 3 0 4 2 5 5 5 1 1 2 4 5 1 3 0 3 0 4 3 2 2
Dari kode job yang dihasilkan tersebut ditentukan operasi untuk masingmasing job. Untuk kromosom diatas urutan operasi masing-masing job adalah sebagai berikut : J 0 02 051324453114304255511245130304322 O0 10 200010111122233223434345534455545 Penjelasan untuk hasil diatas yaitu : Gen ke-0 yaitu job 0 merupakan operasi ke-0 karena urutan pertama pada job 0. Gen ke-1 yaitu job 0 merupakan operasi ke-1 karena urutan kedua pada job 0. Gen ke-3 yaitu job 0 merupakan operasi ke-2 karena urutan ketiga pada job 0. Gen ke-16 yaitu job 0 merupakan operasi ke-3 karena urutan keempat pada job 0. Gen ke-29 yaitu job 0 merupakan operasi ke-4 karena urutan kelima pada job 0. Gen ke-31 yaitu job 0 merupakan operasi ke-5 karena urutan keenam pada job 0.
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
59
Untuk operasi job 1, job 2, job 3, job 4, dan job 5 digunakan cara yang sama dengan job 0. Berdasarkan job (J) dan operasi (O) maka dapat ditentukan urutan mesin (M) berdasarkan data yang diberikan sesuai Lampiran 2. Sebagai contoh pada kromosom pertama yang dibangkitkan untuk kode J = 0 dan O = 0, pada persoalan tersebut didapatkan job 0 operasi ke-0 dilakukan pada mesin 3 sehingga diperoleh indeks JOM = 003, yaitu J = 0, O = 0 dan M = 3. Untuk gen yang lain dilakukan dengan cara yang sama, sehingga diperoleh : J 002051324453114304255511245130304322 O 010200010111122233223434345534455545 M 324013532432145041252420000531153415 Setelah didapatkan indeks JOM, maka selanjutnya adalah menghitung waktu penyelesaian setiap job dan makespan pada kromosom tersebut dengan membentuk Gantt Chart yang dapat dilihat pada Lampiran 3. Penjelasan mengenai Lampiran 3 yaitu 003 merupakan indeks JOM untuk job 0 yang dijadwalkan pada awal proses dimesin 3, setelah proses 003 selesai maka 012 dijadwalkan dimesin 2, setelah proses 012 selesai maka 020 dijadwalkan dimesin 0, 103 dijadwalkan di mesin 3 setelah indeks 003 dan berlanjut dengan cara yang sama untuk indeks lainnya sesuai dengan urutan indeks JOM yang telah didapat sebelumnya. Dari pembentukan Gantt Chart diperoleh nilai fuzzy waktu penyelesaian maksimal keseluruhan job yaitu (73, 108,138) satuan waktu yang berarti waktu penyelesaian paling cepat 73 satuan waktu, waktu penyelesaian normal 108 satuan waktu dan waktu penyelesaian paling lambat 138 satuan waktu.
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
60
Setelah pembentukan Gantt Chart kromosom yang telah dibangkitkan selanjutnya dilakukan pengaktifan schedule. Untuk pengaktifan schedule kromosom pertama dapat dilihat pada Gantt Chart bahwa pada mesin 2, delay time dari 012 adalah (9, 13, 17), sedangkan waktu proses untuk 402 adalah (8, 12, 13) sehingga 402 dapat disisipkan di depan 012 yang mengakibatkan 312 bergeser tepat setelah 012 dan 414 bergeser kedepan dengan waktu starting sama dengan waktu selesai 402. Untuk perhitungan delay time dan penggeseran job-job yang lain dilakukan dengan cara yang sama. Hasil Gant Chart kromosom 0 yang telah diaktifkan dapat dilihat pada Lampiran 4. Dan diperoleh kode job kromosom ke0 menjadi sebagai berikut : 0 4 0 2 0 5 1 3 2 4 5 3 1 1 4 3 0 4 2 5 1 5 5 1 2 4 5 1 3 0 3 0 4 3 2 2
Karena jumlah kromosom awal yang telah dibangkitkan adalah satu maka dibangkitkan kromosom yang berikutnya. Misalkan pembangkitan kromosom kedua menghasilkan kode job : 2 5 1 4 2 3 1 0 2 4 5 4 5 5 1 5 3 3 1 2 5 4 3 0 2 1 1 0 3 0 3 4 0 0 4 2
Seperti kromosom yang pertama dilakukan pembentukan indeks JOM pada kromosom yang kedua ini dan dilakukan pengaktifan schedule sehingga diperoleh kode hasil pengaktifan : 2 5 1 4 2 3 1 0 2 4 5 4 5 3 1 0 5 1 5 3 2 5 4 3 2 1 2 1 0 3 3 0 4 0 0 4
Langkah selanjutnya yang dilakukan yaitu mengecek dearajat kesamaan antara kromosom-kromosom yang telah dibangkitkan. Untuk pengecekan derajat kesamaan kromosom pertama dan kedua, kromosom-kromosom tersebut dirubah
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
61
kedalam tabel mesin dan urutan job berdasarkan tabel JOM yang telah diperoleh sebelumnya. Sebagai contoh untuk kromosom yang pertama yaitu : Mesin M0 M1 M2 M3 M4 M5
Job 0 5 4 0 2 3
3 1 0 1 4 4
1 4 3 2 1 5
2 0 2 5 0 1
4 3 1 3 5 0
5 2 5 4 3 2
Baris pertama pada tabel diatas menunjukkan urutan job yang dikerjakan pada mesin pertama atau mesin ke-0 yaitu job pertama yang dikerjakan adalah job ke-0, kemudian job ke-3, job ke-1, job ke-2, job ke-4, dan job terakhir yaitu job ke-5. Untuk mesin yang lain dilakukan dengan cara yang sama. Setelah diperoleh tabel mesin untuk masing-masing kromosom maka dilakukan perhitungan derajat kesamaan sebagai berikut : Kromosom 0 M0 M1 M2 M3 M4 M5
0 5 4 0 2 3
3 1 0 1 4 4
1 4 3 2 1 5
2 0 2 5 0 1
4 3 1 3 5 0
5 2 5 4 3 2
1+ 4+ 2+ 3+ 4+ 2= 16 5+ 5+ 5+ 3+ 3+ 3= 24 5+ 2+ 3+ 3+ 4+ 5= 22 3+ 4+ 4+ 5+ 5+ 5= 26 5+ 5+ 5+ 3+ 4+ 4= 26 5+ 5+ 5+ 3+ 4+ 4= 26
Kromosom 1 M0 M1 M2 M3 M4 M5
3 5 4 1 2 3
2 1 2 2 4 4
5 4 3 0 1 5
1 2 1 5 5 2
0 3 0 3 3 1
4 0 5 4 0 0
16 + 24 + 22 + 26 + 26 + 26 140 = = 0,77778 180 180
Gambar 4.30 Perhitungan Degree of Similarity Kromosom 0 dan Kromosom 1 Penjelasan tentang Gambar 4.30 yaitu untuk mesin ke-0, pada kromosom pertama job ke-0 mendahului job ke-3, job ke-1, job ke-2, job ke-4 dan job ke-5 namun tidak didahului oleh job manapun, sedangkan untuk kromosom kedua job
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
62
ke-0 hanya mendahului job ke-4, sehingga kesamaan job yang didahului dan mendahului untuk job ke-0 hanya bernilai 1. Untuk perhitungan job selanjutnya dan mesin yang lain dilakukan dengan cara yang sama. Dari hasil tersebut diperoleh hasil 140 untuk keseluruhan mesin dan job pada kromosom pertama dan kedua. Pada kasus ini jika setiap job memiliki urutan yang sama maka akan diperoleh nilai 5 untuk setiap job, dankarena banyaknya job 6 dan mesin 6 maka didapat nilai 5 × 6 × 6 yang menghasilkan nilai 180 untuk kesamaan pada seluruh job dan mesin. Dari hasil perhitungan kromosom pertama dan kedua diperoleh degree 140/180 yaitu 0,77778. Kromosom akan diterima apabila rasionya bernilai kurang dari atau sama dengan degree yang telah ditentukan. Karena pada kasus ini degree yang digunakan 0,9 maka kromosom kedua diterima. Hasil dari generate populasi awal sebanyak pop_size dapat dilihat pada Tabel 4.2. Tabel 4.2 Kromosom awal yang dibangkitkan Kromosom
Kode job 002051324453114304255511245130304322
1
251423102454551533125430211030340042 513250031002525402141553014434231243 353341555204012004151222343130541204 352355202420251014314005453120311344 531030153103534511422210254224435400 311221055144334233524002442355010051 251034412025314455124303130545210302 543410530352321513030440222114502514 533022430241224033145054102515101534
hasil pengaktifan kromosom diatas dapat dilihat pada Tabel 4.3.
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
63
Tabel 4.3 Kromosom awal yang telah diaktifkan Kode job
Kromosom
040205132453114304251551245130304322 1
251423102454531105532543212103304004 513250355111055002240243014233441243 353341555201140205041224233130542104 352325502420251014312404055310311344 531030153210353451142210254224435400 311221055431434233524002442355010051 251034412302514451532403135045221030 543241053035321115300344022214502514 533022430241212403345105115554021034
sedangkan perhitungan nilai degree dapat dilihat pada Tabel 4.4. Tabel 4.4 Nilai degree untuk kromosom awal Kromosom 1
1
0,78 0,64 0,78 0,74 0,8 0,77 0,87 0,84 0,83
0,78 0,62 0,8 0,77 0,72 0,86 0,87 0,76 0,83
0,64 0,62 0,76 0,68 0,71 0,61 0,6 0,69 0,63
0,78 0,8 0,76 0,77 0,87 0,79 0,84 0,84 0,83
0,7 0,77 0,68 0,77 0,7 0,71 0,75 0,7 0,82
0,8 0,72 0,71 0,87 0,7 0,77 0,8 0,87 0,81
0,77 0,86 0,61 0,79 0,71 0,77 0,88 0,83 0,8
0,87 0,87 0,6 0,84 0,75 0,8 0,88 0,84 0,88
0,84 0,76 0,69 0,84 0,7 0,87 0,83 0,84 0,81
0,83 0,83 0,63 0,83 0,82 0,81 0,8 0,88 0,81 -
Karena degree setiap kromosom memenuhi maka populasi awal yang digunakan sesuai hasil pengaktifan yaitu pada Tabel 4.3. Setelah populasi awal terbentuk, maka langkah selanjutnya yaitu mengevaluasi masing-masing kromosom.
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
Langkah II
64
: Evaluasi
Masing-masing kromosom akan dievaluasi dengan menghitung nilai ketiga fungsi tujuan yang digunakan yaitu :
Dimana job,
z1(
)
:
1 n AI i n i 1
z2(
)
:
AI min min AI i
z3(
)
:
~ ~ Cmax max Ci
i 1, 2,...,n
i 1, 2,...,n
adalah kromosom ke-k (k= 0, 1, .., pop_size), n adalah banyak
~ dan C i masing-masing adalah Agreement Index dan waktu penyelesaian
(Completion Time) dari job Ji (i = 0, 1, ..., n). Berikut ini adalah proses evaluasi masing-masing fungsi tujuan : 1. Misalkan gen-gen pada kromosom pertama, pada proses penghitungan makespan dan pengaktifan telah diperoleh Fuzzy Completion Time untuk masing-masing job. Hasil yang diperoleh pada kromosom yang pertama dapat dilihat pada Tabel 4.5. Tabel 4.5 Fuzzy Completion Time kromosom ke-0 Job Fuzzy Completion Time 0 (57, 78, 101) 1 (48, 67, 86) 2 (58, 81, 105) 3 (55, 75, 92) 4 (56, 80, 103) 5 (54, 77, 100) Hasil tersebut menunjukkan bahwa untuk job 0 waktu penyelesaian tercepat, normal dan terlambat masing-masing adalah 57, 78 dan 101, untuk job yang lain menunjukkan arti yang sama.
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
65
2. Dari hasil fuzzy completion time dan data tentang fuzzy duedate untuk masingmasing job sesuai dengan Lampiran 2, maka dapat dihitung Agreement Index (AI) masing-masing job. Misalkan untuk job ke-0 pada kromosom ke-0 perhitungan agreement indexnya adalah : Fuzzy Completion Time Job ke-0
: (57, 78, 101)
Fuzzy Due DateJob ke-0
: (112, 121)
1,0
~ D
~ C 0,0 0,0
57
78
101
112
121
x
Gambar 4.31 Grafik Fuzzy Completion Time dan Fuzzy Due Date Gambar 4.31 menunjukkan daerah Fuzzy Completion Time dan Fuzzy Due ~ ~ Date dengan C merupakan Fuzzy Completion Time dan D merupakan Fuzzy
Due Date. Dari nilai fuzzy diatas maka dapat dibentuk fungsi keanggotaan sebagai berikut : ~ Fungsi keanggotaan C
0; x 57 x 57 ; 57 x 78 21 C~ [ x] 101 x ; 78 x 101 23 0; x 101
Skripsi
~ Fungsi keanggotaan D 1; x 112 121 x D~ [ x] ; 112 x 121 9 0; x 121
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
66
Dimana x merupakan bilangan Real yang dipetakan ke fungsi keanggotaan ~ ~ C dan D , C~ [ x] dan D~ [ x] masing-masing merupakan derajat keanggotaan ~ ~ bilangan real x pada himpunan C dan D . Selanjutnya yaitu menentukan nilai
~ ~ luasan daerah C D yaitu dengan cara : ~ ~ a. Menentukan titik batas a, b, c untuk wilayah C D seperti yang ditunjukkan pada Gambar 4.32 a = 57
b = 78
c = 101
1,0
~ ~ C D
0,0 0,0
57
78
101
112
~ ~ Gambar 4.32 Daerah C D
121
x
~ ~ b. Menghitung area C D : ~ ~ area C D
78
101
101 x x 57 dx dx 21 23 x 57 x 78 10,5 11,5 22
~ Kemudian dihitung area C sebesar : ~ 44 x1 22 area C 2
c. Diperoleh nilai AI sebesar : AI
Skripsi
22 1 22
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
67
Dengan cara yang sama maka akan diperoleh nilai AI untuk masing-masing job pada setiap kromosom. Untuk kromosom pertama nilai AI untuk tiap job dapat dilihat pada Tabel 4.6. Tabel 4.6 Agreement Index masing-masing job pada kromosom ke-0 Job Agreement Index 0 1 1 1 2 0,002503 3 1 4 0,754693 5 0,01941 3. Dari hasil tersebut dapat dihitung fungsi tujuan pertama dan kedua dari kromosom ke-0. z1( 1 )
z2( 1 )
1 n 1 6 AI i AI i n i 1 6 i 1 1 (1 1 0,002503 1 0,754693 0,01941) 6 1 (3,776606) 0.629434 6
AI min min AI i i 1, 2 ,...,n
min AI i i 1, 2 ,...,6
= min 1; 1; 0,002503; 1; 0,754693; 0,01941 = 0,002503
4. Untuk menghitung fungsi tujuan yang ketiga, digunakan Fuzzy Completion Time masing-masing job. Fuzzy Completion Time untuk masing-masing job
~ dinotasikan dengan C i (i = 0, 1, ..., n) diranking berdasarkan aturan rangking fuzzy number sebagai berikut : Kriteria ranking yang pertama dinotasikan dengan K 1 . Misalkan dihitung nilai ranking untuk job ke-0 pada kromosom ke-0 yaitu :
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
68
57 2(78) 101 ~ K 1(C0 ) 78,5 4 Dengan cara yang sama maka akan didapat nilai ranking untuk job ke-1, job ke-2, job ke-3, job ke-4 dan job ke-5. Hasil ranking Fuzzy Completion Time untuk kromosom pertama dapat dilihat pada Tabel 4.7. Tabel 4.7 Nilai Ranking Fuzzy Completion Time pada kromosom ke-0 Job Nilai Ranking 0 78,5 1 67 2 81,25 3 74,25 4 79,75 5 77 Karena dengan menggunakan kriteria ranking yang pertama sudah didapatkan nilai yang berbeda untuk masing-masing job, maka tidak digunakan kriteria ranking yang selanjutnya. Dari hasil diatas diperoleh :
~ ~ z3( 1 ) C max max Ci (58, 81, 105) i 1, 2,...,6
Untuk hasil perhitungan setiap fungsi tujuan keseluruhan kromosom populasi awal dapat dilihat pada Tabel 4.8. Tabel 4.8 Nilai Fungsi Tujuan populasi awal Kromosom
z1
z2
0,629434 0,002503 1
z3 (58, 81, 105)
0,732327 0,378788 (81, 112, 141) 0,436059
0
(83, 114, 145)
0,507627 0,000882 (78, 104, 128) 0,656752 0,050256
(69, 98, 124)
0,46476
0
(79, 115, 145)
0,510681
0
(80, 108, 133)
0,672076 0,028571
Skripsi
(65, 91, 118)
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
Kromosom
69
z1
z2
z3
0,464795
0
(69, 98, 121)
0,496585 0,006522 (77, 108, 135)
Setelah diperoleh nilai fungsi tujuan masing-masing kromosom, maka langkah selanjutnya adalah menghitung nilai fitness masing-masing kromosom yaitu dengan langkah : 1. Menentukan nilai z i0 dan z i1 yang masing-masing merupakan nilai terendah dan tertinggi dari setiap fungsi tujuan. Dan diperoleh hasil : a. Untuk fungsi tujuan yang pertama (z1) z10
min
i 1, 2,...,pop _ size
z 1 min z 1 i 1, 2,...,5
= min 0,629434; 0,732327; 0,436059; 0,507627; 0,656752; 0,46476; 0,510681; 0,672076; 0,464795; 0,496585 = 0,436059
z11
max
i 1, 2,...,pop _ size
z 1 max z 1 i 1, 2,...,5
= ma 0,629434; 0,732327; 0,436059; 0,507627; 0,656752; 0,46476; 0,510681; 0,672076; 0,464795; 0,496585 = 0,732327
b. Untuk fungsi tujuan yang kedua (z2) z 20
min
i 1, 2,...,pop _ size
z 2 min z 2 i 1, 2,...,5
= min 0,002503; 0,378788; 0; 0,000882; 0,050256; 0; 0; 0,028571; 0; 0,006522 = 0
z 12
max
i 1, 2,...,pop _ size
z 2 max z 2 i 1, 2,...,5
= ma 0,002503; 0,378788; 0; 0,000882; 0,050256; 0; 0; 0,028571; 0; 0,006522 = 0,378788
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
70
c. Untuk fungsi tujuan yang ketiga (z3), karena hasil yang diperoleh berbentuk ~ bilangan fuzzy C = (
1
,
,
) maka yang digunakan sebagai standart
waktu penyelesaian adalah nilai ranking dan diperoleh :
z 30
min
i 1, 2,...,pop _ size
z 3 min z 3 i 1, 2,...,5
= min 81,5; 111,5; 114; 103,5; 97,25; 113,5; 107,25; 91,25; 96,5; 107 = 81,25
z 31
max
i 1, 2,...,pop _ size
z 3 max z 3 i 1, 2,...,5
= min 81,5; 111,5; 114; 103,5; 97,25; 113,5; 107,25; 91,25; 96,5; 107 = 114
2. Langkah selanjutnya yaitu menentukan fungsi keanggotaan linear untuk masing-masing fungsi tujuan yaitu dengan cara : a. Untuk fungsi tujuan yang pertama (z1), karena memaksimalkan maka : 1, z1 0,73233 z 0,43606 1[ z 1 ] 1 , 0,43606 z1 0,73233 0,29627 0, z 1 0,43606
b. Untuk fungsi tujuan yang kedua (z1), karena memaksimalkan maka : 1, z 2 0,37879 z2 2[z 2 ] , 0 z 2 0,37879 0,37879 0, z 2 0
c. Untuk fungsi tujuan yang ketiga (z1), karena meminimalkan maka : 0, z 3 114 115 z 3 3[ z 3 ] , 81 z 3 115 34 1, z 3 81,25
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
71
3. Setelah didapat fungsi keanggotaan untuk masing-masing fungsi tujuan maka dihitung derajat keanggotaan fungsi tujuan masing-masing kromosom. Misalkan untuk kromosom ke-0 derajat keanggotaan fungsi tujuannya adalah:
1[ z 1 ]
0,629434 0,43606 0,653 0,29627
2[ z 2 ]
0,002503 0,007 0,37879
3[ z 3 ]
114 81,25 1 32,75
Untuk kromosom yang lain dilakukan dengan perhitungan yang sama. Hasil derajat keanggotaan untuk kromosom awal dapat dilihat pada Tabel 4.9. Tabel 4.9 Derajat keanggotaan fungsi Tujuan pada populasi awal Kromosom 1
1[ z1]
2[ z 2 ]
3[ z 3 ]
0,6527 1 0 0,24157 0,74491 0,09688 0,25187 0,79663 0,09699 0,2043
0,00661 1 0 0,00233 0,13268 0 0 0,07543 0 0,01722
1 0,07634 0 0,32061 0,51145 0,01527 0,20611 0,69466 0,53435 0,21374
4. Setelah didapat derajat keanggotaan tiap fungsi tujuan untuk masing-masing kromosom, maka selanjutnya ditentukan nilai fitness untuk masing-masing kromosom yaitu dengan rumus :
f min { i ( z i )} i 1, 2,3
Misalkan untuk kromosom ke-0 akan diperoleh nilai : f= min 0,6527; 0,00661; 1 = 0,00661
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
72
Penentuan nilai fitness untuk kromosom lain dilakukan dengan cara yang sama. Dan hasil nilai untuk masing-masing kromosom dapat dilihat pada Tabel 4.10. Tabel 4.10 Nilai Fitness Populasi Awal F
Kromosom 1
0,00661 0,07634 0 0,00233 0,13268 0 0 0,07543 0 0,01722
Setelah masing-masing individu dievaluasi dan diperoleh nilai fitnessnya, maka selanjutnya akan dilakukan proses seleksi untuk memilih induk yang akan digunakan pada proses crossover dan mutasi. Langkah III : Seleksi Proses seleksi dilakukan dengan menggunakan seleksi turnamen. Seleksi ini dilakukan dengan memilih secara random kromosom sebanyak nilaitur (tour), kemudian dipilih nilai fitness terbaik. Pada kasus ini nilai tour yang digunakan adalah 2 artinya kromosom yang akan dibandingkan sebanyak 2, dan dilakukan sebanyak pop_size yaitu 10. Langkah yang dilakukan dalam seleksi ini yaitu : a. Mengambil secara acak kromosom sejumlah nilai tour. b. Memilih kromosom fitness terbesar sebagai calon induk yang akan mengalami crossover dan mutasi.
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
73
c. Mengulang proses a. sebanyak ukuran pop_size. Proses seleksi turnamen ini akan dilakukan sebanyak dua kali untuk memilih calon induk yang digunakan dalam proses crossover dan mutasi. 1. Seleksi Crossover Untuk menentukan calon induk crossover dilakukan proses seleksi turnamen. Misalkan pada random kromosom yang pertama diperoleh kromosom ke-1 dan kromosom ke-2. Karena nilai f kromosom ke-1 yaitu 0,07634 lebih besar dari nilai f kromosom ke-2 yaitu 0 maka kromosom yang terpilih sebagai calon induk crossover adalah kromosom ke-1. Selanjutnya secara random diperoleh kromosom yang di turnamenkan dan didapat calon induk seperti pada Tabel 4.11. Tabel 4.11 Calon Induk Crossover Individu 1
Individu 2
1
Calon Induk 1
1
1
1
1
1
1
Setelah diperoleh calon induk, maka dilakukan random bilangan acak dengan interval [0,1] untuk menentukan induk crossover. Kromosom yang berperan sebagai induk crossover adalah kromosom dengan nilai r ≤ Pc, dimana
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
74
nilai Pc telah ditentukan sebelumnya yaitu 0,6. Hasil dari random bilangan untuk pemilihan induk crossover dapat dilihat dalam Tabel 4.12. Tabel 4.12 Induk Crossover Random ke0 1 2 3 4 5 6 7 8 9
Calon Induk 1 1
1
1
Induk Crossover
Bilangan acak 0,039203 0,925276 0,608947 0,646933 0,102769 0,687449 0,792584 0,942374 0,950996 0,555158
1
1
Setelah ditentukan induk crossover, maka selanjutnya dilakukan seleksi untuk memilih induk mutasi. 2. Seleksi Mutasi Untuk menentukan calon induk mutasi dilakukan proses seleksi turnamen seperti pemilihan calon induk crossover. Selanjutnya secara random diperoleh kromosom yang di turnamenkan dan didapat calon induk mutasi seperti pada Tabel 4.13. Tabel 4.13 Calon Induk Mutasi Individu 1 1
Skripsi
Individu 2
Calon Induk 1
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
Individu 1
Individu 2
75
Calon Induk
Setelah diperoleh calon induk, maka dilakukan random bilangan acak dengan interval [0,1] untuk menentukan induk mutasi. Kromosom yang berperan sebagai induk mutasi adalah kromosom dengan nilai r ≤ Pm (probabilitas mutasi), dimana nilai Pm telah ditentukan sebelumnya yaitu 0,1. Hasil dari random bilangan untuk pemilihan induk mutasi dapat dilihat dalam Tabel 4.14. Tabel 4.14 Induk Mutasi Random ke0 1 2 3 4 5 6 7 8 9
Calon Induk 1
IndukMutasi
Bilangan acak 0,583844 0,721572 0,819991 0,056469 0,518785 0,202691 0,992964 0,619268 0,614698 0,431484
Langkah IV : Crossover Setelah diperoleh induk crossover, proses selanjutnya yang dilakukan adalah melakukan partial schedule exchange crossover. Hasil seleksi diatas menunjukkan bahwa induk yang terpilih adalah
Skripsi
1
,
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
dan
1
. Crossover
Marisa
ADLN Perpustakaan Universitas Airlangga
76
merupakan persilangan antara dua kromosom, sehingga jika induk crossover berjumlah ganjil maka induk terakhir akan dihapus, dalam kasus ini induk yang digunakan hanya 2 induk sehingga crossover hanya terjadi hanya satu kali. Proses crossover ini akan menghasilkan dua anak. Pada kasus ini 1 dan
1
akan menjadi parent
akan menjadi parent 2. Tahapan partial schedule exchange crossover
adalah sebagai berikut : 1. Memilih satu posisi pada parent 1 secara random. Dari hasil random diperoleh posisi gen ke-13. Job yang ada pada gen ke-13 adalah job ke-3. 1: 2 5 1 4 2 3 1 0 2 4 5 4 5 3 1 1 0 5 5 3 2 5 4 3 2 1 2 1 0 3 3 0 4 0 0 4
2. Menentukan job terdekat yang sama dengan job pada posisi terpilih, yaitu job 3, sehingga diperoleh partial schedule 1 sebagai berikut : 1: 2 5 1 4 2 3 1 0 2 4 5 4 5 3 1 1 0 5 5 3 2 5 4 3 2 1 2 1 0 3 3 0 4 0 0 4 Partial schedule 1 :
3
1
1
0
5
5
3
3. Partial schedule selanjutnya dari parent 2 tidak diperoleh secara acak, tetapi harus dimulai dan diakhiri dengan job yang sama dengan job awal dan akhir pada partial schedule 1, sehingga diperoleh partial schedule 2. 2: 3 5 2 3 2 5 5 0 2 4 2 0 2 5 1 0 1 4 3 1 2 4 0 4 0 5 5 3 1 0 3 1 1 3 4 4 Partial schedule 2 :
Skripsi
3
5
2
3
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
77
4. Menukar posisi partial schedule 1 kedalam parent 2 dan partial schedule 2 kedalam parent 1 1 2 5 1 4 2 3 1 0 2 4 5 4 5 3 5 2 3 2 5 4 3 2 1 2 1 0 3 3 0 4 0 0 4
Partial Schedule 2 2 31105532550242025101431240405531 0 3 1 1 3 44
Partial Schedule 1 5. Hasil dari pertukaran partial schedule biasanya akan menyebabkan jumlah gen yang tidak sesuai, sehingga harus dicari kelebihan dan kekurangan gen pada masing-masing anak hasil crossover. 1: Partial schedule 1: 3 1 1 0 5 5 Partial schedule 2:
3
5
2
3
Gen yang kurang Gen yang lebih
3
1
1
0
5
1
0
5
2
2: Partial schedule 1: 3 1 1 0 5 5 Partial schedule 2:
3
5
2
3
3
Gen yang lebih
1
Gen yang kurang
2
6. Menghapus kelebihan gen dan menambah kekurangan gen pada masingmasing anak hasil crossover dengan memperhatikan urutan operasi job pada parent pembentuk partial schedule.
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
78
a. Menghapus gen yang berlebih pada calon anak 1: 2 5 1 4 2 3 1 0 2 4 5 4 5 3 5 2 3 2 5 4 3 2 1 2 1 0 3 3 0 4 0 0 4 2 31105532550242025101431240405531 0 3 1 1 3 44
b. Menambahkan gen yang kurang pada calon anak 1: 5 1 4 2 3 1 0 2 4 5 4 5 3 5 2 3 1 1 0 5 2 5 4 3 2 1 2 1 0 3 3 0 4 0 04
2 3 1 1 0 5 5 3 2 2 5 2 4 2 0 2 5 0 4 3 1 2 4 0 4 0 5 5 3 1 0 3 1 1 3 44
Dari hasil proses diatas diperoleh offspring hasil crossover yaitu : 1: 5 1 4 2 3 1 0 2 4 5 4 5 3 5 2 3 1 1 0 5 2 5 4 3 2 1 2 1 0 3 3 0 4 0 04 2: 3 1 1 0 5 5 3 2 2 5 2 4 2 0 2 5 0 4 3 1 2 4 0 4 0 5 5 3 1 0 3 1 1 3 44
Setelah diperoleh anak atau offspring hasil crossover, maka offspring tersebut dibentuk kedalam indeks JOM yang kemudian dihitung waktu penyelesaiannya dan dilakukan pengaktifkan, langkah yang dilakukan sama seperti pada populasi awal di Langkah I. Hasil pengaktifan kromosom offspring crossover dapat dilihat pada Tabel 4.15.
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
79
Tabel 4.15 Offspring Crossover yang telah diaktifkan Kromosom
Kode job
1
514231024545320531512445321210330004
11
310515322542320250142450334051110344
Setelah didapatkan kromosom dengan schedule aktif maka dihitung nilai ketiga fungsi tujuan dari masing-masing offspring dengan cara yang sama seperti pada Langkah II. Hasil ketiga nilai fungsi objektif untuk offspring crossover dapat dilihat pada Tabel 4.16. Tabel 4.16 Nilai Fungsi Tujuan Offspring Hasil Crossover Kromosom
Langkah V
z1
z2
z3
1
0,88480 0,66667 (81, 112, 141)
11
0,62379 0,26997
(69, 98, 125)
: Mutasi
Setelah diperoleh induk mutasi, proses selanjutnya yang dilakukan adalah melakukan swap mutation. Hasil seleksi diatas menunjukkan bahwa induk yang terpilih hanya satu kromosom yaitu
. Sehingga mutasi yang terjadi hanya satu
kali. Proses mutasi ini akan menghasilkan satu anak. Tahapan swap mutation adalah sebagai berikut : a. Menentukan dua posisi gen parent secara random. Dari hasil random 36 posisi gen untuk kasus ini hasil posisi acak yang diperoleh adalah gen ke-13 dan gen ke-20.
3 5 3 3 4 1 5 5 5 2 0 1 1 4 0 2 0 5 0 4 1 2 2 4 2 3 3 1 3 0 5 4 2 1 04
Gen ke-13
Skripsi
Gen ke-20
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
80
b. Membentuk anak hasil mutasi dengan menukar gen pada kedua posisi acak yang diperoleh. Dari hasil proses diatas maka offspring yang diperoleh adalah :
3 5 3 3 4 1 5 5 5 2 0 1 1 1 0 2 0 5 0 4 4 2 2 4 2 3 3 1 3 0 5 4 2 1 04
Sama seperti offspring hasil crossover, maka offspring mutasi dibentuk kedalam indeks JOM yang kemudian dihitung waktu penyelesaiannya dan dilakukan pengaktifkan, langkah yang dilakukan sama seperti pada populasi awal di Langkah I. Hasil pengaktifan kromosom offspring dapat dilihat pada Tabel 4.17. Tabel 4.17 Offspring Mutasi yang telah diaktifkan Kromosom
Kode job
1
353341555201101255040422423313042104
Setelah didapatkan kromosom dengan schedule aktif maka dihitung nilai ketiga fungsi tujuan dari masing-masing offspring dengan cara yang sama seperti pada Langkah II. Hasil ketiga nilai fungsi objektif untuk offspring mutasi dapat dilihat pada Tabel 4.18. Tabel 4.18 Nilai Fungsi Tujuan Offspring Hasil Mutasi Kromosom 1
z1
z2
z3
0,66645 0,06803 (78, 108, 133)
Langkah VI : Pembentukan populasi baru Setelah dilakukan proses genetik langkah selanjutnya yaitu membentuk populasi baru yang akan digunakan pada generasi selanjutnya. Pembentukan
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
81
populasi baru dipilih dari kromosom pada populasi awal dan kromosom anakan. Tahapan pembentukan populasi baru dilakukan dengan cara : 1. Menghitung nilai fitness untuk masing-masing kromosom awal dan kromosom offspring. Perhitungan nilai fitness ini dilakukan seperti pada tahap Evaluasi di Langkah II. Dalam perhitungan fitness dari kromosom awal dan offspring diperoleh nilai derajat keanggotaan seperti pada Tabel 4.19. Tabel 4.19 Derajat Keanggotaan Fungsi Tujuan Populasi Awal dan Offspring Kromosom
1[ z1]
2[ z 2 ]
0,43093 0,00375 1
3[ z 3 ] 1
0,66022 0,56818 0,07634 0
0
0
0,15949 0,00132 0,32061 0,4918
0,07538 0,51145
0,06396
0
0,01527
0,16629
0
0,20611
0,52595 0,04286 0,69466 0,06404
0
0,53435
0,13488 0,00978 0,21374 1
1
1
0,07634
11
0,41835 0,40496 0,50382
1
0,51342 0,10204 0,22137
Setelah didapatkan derajat keanggotaan tersebut maka dapat dihitung nilai fitness untuk kromosom awal dan offspring. Nilai fitness dari kromosom awal dan offspring dapat dilihat pada Tabel 4.20. Tabel 4.20 Nilai Fitness Populasi Awal dan Offspring Kromosom
f 0,00375
1
Skripsi
0,07634
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
Kromosom
82
f 0 0,00132 0,07538 0 0 0,04286 0 0,00978
1
0,07634
11
0,40496
1
0,10204
2. Setelah diperoleh nilai fitness untuk setiap kromosom, selanjutnya kromosom diurutkan sesuai fitnessnya. Hasil pengurutan kromosom dapat dilihat pada Tabel 4.21. Tabel 4.21 Hasil Pengurutan Kromosom Gabungan Kromosom
f
11
0,40496
1
0,10204
1
0,07634
1
0,07634 0,07538 0,04286 0,00978 0,00375 0,00132 0 0 0 0
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
83
3. Langkah selanjutnya yaitu kromosom yang terbaik berdasarkan pengurutan dipilih sebanyak pop_size untuk membentuk populasi baru. Sedangkan kromosom yang tidak terpilih akan dikeluarkan dari populasi. Hasil populasi baru pada generasi pertama dapat dilihat pada Tabel 4.22. Tabel 4.22 Populasi Baru Kromosom
f
11
0,40496
1
0,10204
1
0,07634
1
0,07634 0,07538 0,04286 0,00978 0,00375 0,00132 0
Pada generasi pertama diperoleh kromosom terbaik yaitu kromosom
11
dengan nilai fitness 0,40496 dengan urutan job sebagai berikut : Gen 310515322542320250142450334051110344 Bentuk urutan JOM kromosom
11
adalah sebagai berikut :
J 310515322542320250142450334051110344 O 000011101202231432215243434533554545 M 533113243522002120445544111032550403 Kromosom tersebut memiliki hasil rata-rata dan minimal agreement index 0,62379 dan 0,26997 yang menunjukkan rata-rata dan minimal kesesuaian waktu penyelesaian dengan duedate (deadline) sebesar 62,379% dan 26,997% serta makespan sebesar (69, 98, 125) yang secara berurutan menunjukkan waktu
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
84
penyelesaian pekerjaan tercepat, normal dan terlambat. Gantt Chart untuk solusi yang diperoleh dapat dilihat pada Lampiran 5.
4.4
Implementasi Program pada Kasus JSSP Program Fuzzy Multi-Objective Job Shop Scheduling Problem dengan
Genetic Algorithm yang telah dibuat dapat diterapkan dalam problem dan hasil yang didapat adalah sebagai berikut : 4.4.1 Data Problem 1 FMOJSSP 6x6 Problem 1 FMOJSSP 6x6 yang ada pada Lampiran 2 diselesaikan dengan menggunakan program sesuai Lampiran 6 menggunakan parameter : pop_size
= 20
= 0,6
degree of similarity = 0,8
= 0,1
tour
= 100
= 2
Urutan job yang diperoleh : 152354224532013503541521021403414300 Dari solusi tersebut diperoleh kode JOM : J 152354224532013503541521021403414300 O 000010121213012313422543254334455545 M 314532324520310223454012050141053415 Solusi tersebut memiliki hasil rata-rata dan minimal Agreement Index 0,96186 dan 0,79422 yang menunjukkan rata-rata dan minimal kesesuaian waktu penyelesaian dengan duedate (deadline) sebesar 96,186% dan 79,422% serta makespan sebesar (65,0; 87,0; 110,0) yang secara berurutan menunjukkan waktu penyelesaian pekerjaan tercepat, normal dan terlambat.
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
85
4.4.2 Data Problem 2 6x6 FMOJSSP Problem 2 FMOJSSP 6x6 yang ada pada Lampiran 2 diselesaikan dengan menggunakan program sesuai Lampiran 6 menggunakan parameter : pop_size
= 20
= 0,6
degree of similarity = 0,8
= 0,1
tour
= 100
= 2
Urutan job yang diperoleh : 312213035540330155514032012144504422 Dari solusi tersebut diperoleh kode JOM : J 312213035540330155514032012144504422 O 000111020101342223431352443523554545 M 534312301322310452424442100551050515 Solusi tersebut memiliki hasil rata-rata dan minimal Agreement Index 0,99227 dan 0,97460 yang menunjukkan rata-rata dan minimal kesesuaian waktu penyelesaian dengan duedate (deadline) sebesar 99,227% dan
97,460%
serta makespan
sebesar (60,0; 83,0; 99,0) yang secara berurutan menunjukkan waktu penyelesaian pekerjaan tercepat, normal dan terlambat.
4.4.3 Data Problem 3 6x6 FMOJSSP Problem 3 FMOJSSP 6x6 yang ada pada Lampiran 2 diselesaikan dengan menggunakan program sesuai Lampiran 6 menggunakan parameter : pop_size
= 20
degree of similarity = 0,8
Skripsi
tour
= 2
= 0,6
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
= 0,1
86
= 100
Urutan job yang diperoleh : 322114053333222121440450134510045055 Dari solusi tersebut diperoleh kode JOM : J 322114053333222121440450134510045055 O 001010001234234253121312454253453545 M 543312312031201452452130040554132540 Solusi tersebut memiliki hasil rata-rata dan minimal Agreement Index 0,84864 dan 0,69231 yang menunjukkan rata-rata dan minimal kesesuaian waktu penyelesaian dengan duedate (deadline) sebesar 84,864% dan 69,231% serta makespan sebesar (28,0; 38,0; 49,0) yang secara berurutan menunjukkan waktu penyelesaian pekerjaan tercepat, normal dan terlambat.
4.5
Perbandingan Hasil dengan Parameter yang Berbeda Pada perbandingan ini, problem diselesaikan dengan nilai parameter yang
berbeda untuk parameter degree of similarity, Pc dan Pm. Sedangkan parameter lain yang bernilai tetap adalah sebagai berikut :
= 20
tour
= 2
= 100
4.5.1 Data Problem 1 FMOJSSP 6x6 Hasil yang diberikan pada Lampiran 7 menujukkan bahwa penyelesaian untuk Problem 1 jika dilihat berdasarkan nilai rata-rata Agreement Index maka hasil terbaik adalah 0,96586 pada saat nilai degree = 0,9, Pc = 0,5 dan Pm =
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
87
0,01.jika dilihat berdasarkan nilai minimal Agreement Index maka hasil terbaik adalah 0,79422 dan diperoleh pada 14 kali percobaan yaitu pada nilai degree, Pc dan Pm sebagai berikut : Degree = 0,7; Pc = 0,5 dan Pm= 0,2
Degree= 0,8; Pc = 0,6 dan Pm= 0,01
Degree= 0,7; Pc = 0,6 dan Pm= 0,01
Degree = 0,8; Pc = 0,6 dan Pm= 0,1
Degree = 0,7; Pc = 0,6 dan Pm= 0,2
Degree = 0,8; Pc = 0,6 dan Pm= 0,2
Degree= 0,7; Pc = 0,7 dan Pm= 0,01
Degree= 0,8; Pc = 0,7 dan Pm= 0,01
Degree = 0,7; Pc = 0,7 dan Pm= 0,2
Degree = 0,9; Pc = 0,6 dan Pm= 0,2
Degree = 0,8; Pc = 0,5 dan Pm= 0,1
Degree= 0,9; Pc = 0,7 dan Pm= 0,01
Degree = 0,8; Pc = 0,5 dan Pm= 0,2
Degree = 0,9; Pc = 0,7 dan Pm= 0,2
Sedangkan jika dilihat berdasarkan nilai Completion Time maka hasil terbaik adalah (58,0; 84,0; 109,0) pada saat nilai degree 0,9, Pc = 0,7 dan Pm = 0,1. Berdasarkan hasil diatas ditunjukkan bahwa untuk Problem 1 dengan menggunakan parameter yang berbeda tidak didapatkan pola perubahan hasil yang tetap.
4.5.2 Data Problem 2 FMOJSSP 6x6 Hasil yang diberikan pada Lampiran 8 menujukkan bahwa penyelesaian untuk Problem 2 jika dilihat berdasarkan nilai rata-rata Agreement Index maka hasil terbaik adalah 0,99227 dan diperoleh pada 5 kali percobaan yaitu pada nilai degree, Pc dan Pm sebagai berikut : Degree = 0,7; Pc = 0,6 dan Pm= 0,1
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
88
Degree = 0,8; Pc = 0,5 dan Pm= 0,01 Degree = 0,8; Pc = 0,7 dan Pm= 0,01 Degree = 0,9; Pc = 0,5 dan Pm= 0,1 Degree = 0,9; Pc = 0,6 dan Pm= 0,2 Jika dilihat berdasarkan nilai minimal Agreement Index maka hasil terbaik adalah 0,97460 dan diperoleh pada 5 kali percobaan yaitu pada nilai degree, Pc dan Pm sebagai berikut : Degree = 0,7; Pc = 0,6 dan Pm= 0,1 Degree = 0,8; Pc = 0,5 dan Pm= 0,01 Degree = 0,8; Pc = 0,7 dan Pm= 0,01 Degree = 0,9; Pc = 0,5 dan Pm= 0,1 Degree = 0,9; Pc = 0,6 dan Pm= 0,2 Sedangkan jika dilihat berdasarkan nilai Completion Time maka hasil terbaik adalah (54,0; 73,0; 89,0) dan diperoleh pada 8 kali percobaan yaitu pada nilai degree, Pc dan Pm sebagai berikut : Degree = 0,7; Pc = 0,5 dan Pm= 0,2
Degree = 0,8; Pc = 0,5 dan Pm= 0,1
Degree= 0,7; Pc = 0,6 dan Pm= 0,01
Degree = 0,8; Pc = 0,6 dan Pm= 0,1
Degree = 0,7; Pc = 0,6 dan Pm= 0,2
Degree= 0,9; Pc = 0,6 dan Pm= 0,01
Degree= 0,7; Pc = 0,7 dan Pm= 0,01
Degree = 0,9; Pc = 0,7 dan Pm= 0,2
Berdasarkan hasil diatas ditunjukkan bahwa untuk Problem 2 dengan menggunakan parameter yang berbeda tidak didapatkan pola perubahan hasil yang tetap.
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
89
4.5.3 Data Problem 3 FMOJSSP 6x6 Hasil yang diberikan pada Lampiran 9 menujukkan bahwa penyelesaian untuk Problem 3 jika dilihat berdasarkan nilai rata-rata Agreement Index dannilai minimal Agreement Index maka hasil terbaik adalah 0,84864 dan 0,69231 dan diperoleh pada 7 kali percobaan yaitu pada nilai degree, Pc dan Pm sebagai berikut : Degree = 0,7; Pc = 0,6 dan Pm= 0,1 Degree = 0,7; Pc = 0,7 dan Pm= 0,01 Degree = 0,8; Pc = 0,5 dan Pm= 0,2 Degree = 0,8; Pc = 0,6 dan Pm= 0,1 Degree = 0,8; Pc = 0,6 dan Pm= 0,2 Degree = 0,9; Pc = 0,5 dan Pm= 0,1 Degree = 0,9; Pc = 0,6 dan Pm= 0,2 Sedangkan jika dilihat berdasarkan nilai Completion Time maka hasil terbaik adalah (27,0; 36,0; 47,0) dan diperoleh pada 13 kali percobaan yaitu pada nilai degree, Pc dan Pm sebagai berikut : Degree = 0,7; Pc = 0,5 dan Pm= 0,1
Degree = 0,8; Pc = 0,7 dan Pm= 0,2
Degree = 0,7; Pc = 0,5 dan Pm= 0,2
Degree= 0,9; Pc = 0,5 dan Pm= 0,01
Degree= 0,7; Pc = 0,6 dan Pm= 0,01
Degree = 0,9; Pc = 0,6 dan Pm= 0,1
Degree = 0,7; Pc = 0,6 dan Pm= 0,2
Degree= 0,9; Pc = 0,7 dan Pm= 0,01
Degree = 0,7; Pc = 0,7 dan Pm= 0,2
Degree = 0,9; Pc = 0,7 dan Pm= 0,1
Degree= 0,8; Pc = 0,5 dan Pm= 0,01
Degree = 0,9; Pc = 0,7 dan Pm= 0,2
Degree = 0,8; Pc = 0,5 dan Pm= 0,1
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
90
Berdasarkan hasil diatas ditunjukkan bahwa untuk Problem 3 dengan menggunakan parameter yang berbeda tidak didapatkan pola perubahan hasil yang tetap.
Dari hasil yang diperoleh, penggabungan penerapan degree of similarity antar individu awal yang dilakukan oleh Sakawa dengan penggunaan seleksi turnamen untuk Job Shop Scheduling pada jurnal Lei menggunakan Genetic Algorithm dapat menghasilkan solusi yang baik. Implementasi program yang dilakukan
sebanyak
20
kali
percobaan
pada
masing-masing
problem
menghasilkan solusi yang semakin baik. Untuk penyelesaian ketiga problem, jika dibandingkan berdasarkan nilai fitness untuk setiap hasil yang diperoleh, maka didapatkan hasil terbaik pada saat degree = 0,8, Pc = 0,6 dan Pm= 0,1.
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
BAB V KESIMPULAN DAN SARAN
5.1 Kesimpulan 1.
Algoritma
Genetik
(Genetic
Algorithm)
dapat
digunakan
untuk
menyelesaikan Fuzzy Multi-Objective Job Shop Scheduling Problem. Prosesproses yang dilakukan antara lain : membangkitkan kromosom awal, evaluasi, seleksi turnamen, crossover, mutasi, pembentukan populasi baru dan mengulangi langkah-langkah tersebut sampai mencapai iterasi maksimum. 2.
Program untuk menyelesaikan Fuzzy Multi-Objective Job Shop Scheduling dengan menggunakan Genetic Algorithm (GA) dapat dibuat menggunakan bahasa pemrograman JAVA dengan NetBeans IDE 7.0.
3.
Implementasi program untuk problem FMOJSSP 6×6 diperoleh hasil terbaik pada saat nilai parameter degree = 0,8 yang berarti bahwa tingkat kesamaan antar individu awal yang dibangkitkan adalah sebesar 80%, Pc = 0,6 yang berarti bahwa kemungkinan individu yang mengalami crossover sebesar 60%, dan Pm = 0,1 yang berarti bahwa kemungkinan individu yang mengalami mutasi sebesar 10%.
4.
Hasil terbaik yang diperoleh yaitu : Untuk Problem 1 diperoleh nilai rata-rata Agreement Index (AI) dan minimum AI masing-masing sebesar 0,96186 dan 0,79422 yang berarti nilai rata-rata dan nilai minimum ketepatan waktu penyelesaian dengan duedate yaitu sebesar 96,186% dan 79,422%, serta waktu penyelesaian
91 Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
92
maksimum (Maximum Completion Time) yaitu (65,0; 87,0; 110,0), dengan 65, 87 dan 110 masing-masing merupakan waktu penyelesaian tercepat, normal dan waktu penyelesaian terlambat. Untuk Problem 2 diperoleh nilai rata-rata AI dan minimum AI masingmasing sebesar 0,99227 dan 0,97460 yang berarti nilai rata-rata dan nilai minimum ketepatan waktu penyelesaian dengan duedate yaitu sebesar 99,227% dan 97,460%, serta waktu penyelesaian maksimum (Maximum Completion Time) yaitu (60,0; 83,0; 99,0), dengan 60, 83 dan 99 masingmasing merupakan waktu penyelesaian tercepat, normal dan waktu penyelesaian terlambat. Untuk Problem 3 diperoleh nilai rata-rata AI dan minimum AI masingmasing sebesar 0,84864 dan 0,69231 yang berarti nilai rata-rata dan nilai minimum ketepatan waktu penyelesaian dengan duedate yaitu sebesar 84,864% dan 69,231%, serta waktu penyelesaian maksimum (Maximum Completion Time) yaitu (28,0; 38,0; 49,0), dengan 28, 38 dan 49 masingmasing merupakan waktu penyelesaian tercepat, normal dan waktu penyelesaian terlambat.
5.2
Saran Dalam penelitian berikutnya, algoritma GA untuk menyelesaikan Fuzzy
Multi-Objective Job Shop Scheduling Problem dapat dihybrid dengan beberapa algoritma lain seperti ant colony, PSO. Dengan algoritma hybrid tersebut diharapkan dihasilkan solusi yang lebih baik dengan waktu yang lebih cepat.
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
DAFTAR PUSTAKA 1.
Baker, K. R. and Trietsch, D. 2009, Principles of Sequencing and Scheduling, Wiley, New York.
2.
Chen, G. and Pham, T. T., 2001, Introduction to Fuzzy Sets, Fuzzy Logic, and Fuzzy Control Systems, CRC Press, New York.
3.
Chartrand, G. and Oellermann, O.R., 1993, Applied and Algorithmic Graph Theory, McGraw-Hill, New York.
4.
French, S, 1982, Sequencing and Scheduling : An Introduction to the Mathematics of Job Shop, Wiley, New York.
5.
Gen, M. and Cheng, R., 1997, Genetic Algorithms and Engineering Design, Wiley, New York.
6.
Hartati, Sri G., Suharto, B. H. dan Wijono, M. S., 2007, Pemrograman GUI Swing JavaTM dengan NetBeansTM 5, Penerbit ANDI, Yogyakarta.
7.
Kaufmann, A. and Gupta, M. M., 1991, Introduction to Fuzzy Arithmetic Theory and Applications, Van Nostrand Reinhold, New York.
8.
Kusumadewi, S. dan Purnomo, H., 2010, Aplikasi Logika Fuzzy untuk Pendukung Keputusan, Graha Ilmu, Yogyakarta.
9.
Kusumadewi, S., 2002, Analisis Desain Sistem Fuzzy Menggunakan Tool Box Matlab, Graha Ilmu, Yogyakarta.
10. Lei, D., 2009, Solving Fuzzy Job Shop Scheduling Problems Using Random Key Genetic Algorithm, Springer-Verlag London Limited Int J Adv Manuf Technol 49:253–262. 11. Obitko, M., 1998, Introduction to Genetic Algorithms, Czech Technical University. 12. Sakawa, M., Nishizaki, I. and Katagiri, H., 2011, Fuzzy Stochastic Multiobjective Programming, Springer, New York.
93 Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
13. Sakawa, M, 2002, Genetic Algorithms Optimization, Kluwer Academic Publisher.
and
94
Fuzzy
Multiobjective
14. Sakawa, M. and Kubota, R., 2000, Fuzzy Programming For Multiobjective Job Shop Scheduling With Fuzzy Processing Time and Fuzzy Duedate Through Genetic Algoritms, Europan Journal of Operational Research 120, pp. 393-407. 15. Shalahuddin, M. dan Rosa A.S., 2007, Belajar Pemrograman dengan Bahasa C++ dan Java dari Nol menjadi Andal, Informatika, Bandung. 16. Santoso, B. dan Paul W., 2011, Metode Metaheuristik Konsep dan Implementasi, Guna Widya, Surabaya. 17. Yamada, T and Nakano, R., 1997, Genetic Algorithms in Engineering Systems, Chapter 7 : Job Shop Scheduling, pp. 134-160. 18. Zadeh, L. A., 1965, Fuzzy Sets Information and Control 8, pp. 338-353.
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
Lampiran 1
Lampiran 1
Flowchart FMOJSSP Menggunakan GA START Input Parameter Generate Individu awal Pengaktifan Schedule i≠1
i = i-1
No
Yes Degree of similarity dengan individu lain ≤ 0,8
No
Yes No
i = pop_size Yes Evaluasi Seleksi
Crossover
Mutasi
Anak Pengaktifan Schedule Evaluasi Populasi Baru
No
Iterasi = Max_gen Yes END
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
Lampiran 2
Lampiran 2 - 1
Data Fuzzy Multi-Objective Job Shop Scheduling Problem (FMOJSSP)
1. Tabel Problem1 dari 6 x 6 FMOJSSP Operasi Job
0 M
1
FPT
M
2
FPT
M
3
FPT
M
4
FPT
M
5
FPT
M
FPT
0
3 (9,13,17) 2 (6,9,12) 0 (10,11,13) 4 (5,8,11) 1 (10,14,17) 5 (9,11,15)
1
3
(5,8,9)
1 (7,8,10) 4
(3,4,5)
2
2
4
(3,5,6)
3
(2,4,6)
0 (5,8,11) 1
3
5 (8,11,14) 2 (5,8,10) 0
4
2 (8,12,13) 4 (6,9,11) 5 (10,13,17) 1
(4,6,8)
0
(3,5,7)
3
(4,7,9)
5
1 (8,10,13) 3 (8,9,10) 5
(1,3,4)
4
(3,4,5)
0
(2,4,6)
FDD
(3,4,5) 2
(9,13,17) (6,9,12)
(3,5,6)
0 (10,14,17) 5 5
(1,3,4)
3 (8,12,13) 1 (10,12,13) 4
(3,5,7)
2
(3,5,6)
(4,7,10)
Job 0
Job 2
Job 2
Job 3
Job 4
Job 5
(112,121)
(82,91)
(49,60)
(97,102)
(83,89)
(54,59)
Sumber : Sakawa, 2002, halaman 216
2. Tabel Problem 2 dari 6 x 6 FMOJSSP Operasi Job
0 M
FPT
1 M
2
FPT
M
3
4
5
FPT
M
FPT
M
FPT
M
FPT
(1,3,5)
2
(1,3,5)
1
(4,6,8)
0
(9,10,11)
(9,13,17) 2 (8,12,13) 5
(2,3,4)
3 (10,13,16) 1
0
5 (5,7,10) 4 (10,14,17) 3
1
4
(6,7,8)
0
2
2
(4,5,6)
0 (10,11,12) 4 (9,12,16) 1 (8,12,13) 5
(6,9,12)
3
(4,7,9)
3
3
(1,2,4)
4
(2,4,5)
5
(5,7,8)
2
0
(3,5,7)
1
(6,8,10)
4
3 (9,11,15) 0
(4,6,9)
4
(1,2,3)
5 (10,11,15) 1
(4,7,8)
2 (10,11,12)
5
4
(1,2,4)
1
(6,9,11)
5 (10,14,18) 3
(1,2,3)
0
FDD
(6,7,9)
2
(5,8,10)
(2,3,4)
(9,13,14)
Job 0
Job 2
Job 2
Job 3
Job 4
Job 5
(81,88)
(66,80)
(89,92)
(51,60)
(91,96)
(75,78)
Sumber : Sakawa, 2002, halaman 216
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
Lampiran 2 - 2
3. Tabel Problem 3 dari 6 x 6 FMOJSSP Operasi Job
0 M
FPT
1 M
2
3
4
5
FPT
M
FPT
M
FPT
M
FPT
M
FPT
0
0 (5,6,13) 4
(3,4,5)
1
(1,2,3)
5
(3,4,5)
3
(2,3,4)
2
(2,3,4)
1
0
(3,4,5)
1
(2,4,5)
2
(1,3,5)
5
(4,5,6)
3
(5,6,7)
4
(6,7,8)
2
2
(1,2,3)
5
(5,6,7)
4
(4,5,6)
3
(3,4,5)
1
(1,2,3)
0
(1,2,3)
3
5
(2,3,4)
4
(1,2,3)
3
(2,3,4)
1
(2,3,5)
0
(3,4,6)
2
(3,4,5)
4
5
(3,4,5)
4
(2,3,4)
3
(1,2,3)
2
(2,3,4)
1
(4,5,6)
0
(2,3,4)
5
4
(6,7,8)
5
(4,5,6)
0
(2,3,4)
1
(3,4,5)
2
(2,3,4)
3
(1,2,3)
FDD
Job 0
Job 2
Job 2
Job 3
Job 4
Job 5
(30,40)
(35,40)
(20,28)
(32,40)
(30,35)
(40,45)
Sumber : Sakawa, 2002, halaman 201 Keterangan : M FPT FDD
Skripsi
= Mesin = Fuzzy Processing Time = Fuzzy Dua Date
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
Lampiran 3
Gantt Chart Kromosom ke-0 Sebelum Pengaktifan Schedule
Mesin 0
020
140
320
Mesin 1
111
501 Mesin 2
012
Mesin 3
103
003
431
402
213
312
222
414
30
35
40
45
525 50
55
155 60
65
70
75
80
85
055 90
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
255 95
100
105
110
115
120
125
130
135 138
Marisa
Lampiran 3
Skripsi
25
354
544
425 20
453
034
124
Mesin 5 15
132
333
513
204
10
241
341
532
Mesin 4
305 5
041
550
440
230
ADLN Perpustakaan Universitas Airlangga
Lampiran 4
Gantt Chart Kromosom ke-0 Setelah Pengaktifan Schedule
Mesin 0
020
Mesin 1
111
501 Mesin 2
012
402
Mesin 3
312
103
003
Mesin 4
213
414
204
222
10
15
20
341
241
532
513
333
034
453
544
354
525 25
550
440
30
155 35
40
45
50
55
055 60
65
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
255 70
75
80
85
90
95
100
105
Marisa
Lampiran 4
5
041
132
425
305
230
140
431
124
Mesin 5
Skripsi
320
ADLN Perpustakaan Universitas Airlangga
Lampiran 5
Gantt Chart Kromosom ke-11
Mesin 0
Mesin 1 501
111
Mesin 2
Mesin 3
241
402
312
103
003
222
513
Mesin 4
213
124
204
15
20
25
140
341
532
440
431
041
132
453
544
30
255 35
40
034
354
425 45
50
055
155 55
60
65
70
75
80
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
85
90
95
100
105
110
115
120
125
Marisa
Lampiran 5
10
550
333
525
305
Skripsi
012
414
Mesin 5 5
020
230
320
ADLN Perpustakaan Universitas Airlangga
Lampiran 6
Lampiran 6 - 1
Source Code Program GA untuk FMOJSSP
Source Code Kelas Main.java package fmojss; public class Main { public static void main(String[] args) { Input Start = new Input(); Start.setVisible(true); } }
Source Code Kelas Input.java package fmojss; import import import import import import import
java.io.File; java.io.IOException; javax.swing.JFileChooser; javax.swing.JOptionPane; jxl.Sheet; jxl.Workbook; jxl.read.biff.BiffException;
public class Input extends javax.swing.JFrame { private int n; private int m; private static int pop_size; private int max_gen; private int[][] seqM; //Sequence of machine private double[][] due; private double[][][] process; private private private private private
ParameterSetting par; double degree; double Pc; double Pm; int tour;
private private private private private
static static static static static
String best; String meanBest; String minBest; String msBest; double[] ms;
private static int genes; private static int nJob; private static int nMesin; //Solusi private static int[] code; private static int[] operasi; private static int[] mesin; private Help h; private About abt; private int index; private String text; private String text1="Data";
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
Lampiran 6 - 2
public Input() { initComponents(); par = new ParameterSetting(); h = new Help(); abt = new About(); } private void button1ActionPerformed(java.awt.event.ActionEvent evt) { try{ RUN(); }catch(Exception Ex){} } private void jMenuItem3ActionPerformed(java.awt.event.ActionEvent evt){ getInput(); if(text.equals("")){ par.setVisible(true); } } private void jMenuItem2ActionPerformed(java.awt.event.ActionEvent evt){ text1=""; try{ JFileChooser d=new JFileChooser(); int save=d.showOpenDialog(this); if(save==JFileChooser.APPROVE_OPTION){ File file=d.getSelectedFile(); String dir=file.getPath(); setData(dir); } }catch(Exception e){ System.out.println(e); } } private void jMenuItem4ActionPerformed(java.awt.event.ActionEvent evt){ h.setVisible(true); } private void jMenuItem5ActionPerformed(java.awt.event.ActionEvent evt){ abt.setVisible(true); } public static void main(String args[]) { java.awt.EventQueue.invokeLater(new Runnable() { public void run() { new Input().setVisible(true); } }); } private void getInput(){ text=""; try{ pop_size=Integer.parseInt(inputPopSize.getText()); max_gen=Integer.parseInt(inputMaxGen.getText()); }catch(Exception e){ text="You must input Pop_Size and Max_Gen first \n"; JOptionPane.showMessageDialog(this,text+e,"Error",JOptionPane .ERROR_MESSAGE); } }
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
Lampiran 6 - 3
private void getParameter(){ degree = par.getDegree(); Pc = par.getPc(); Pm = par.getPm(); tour =par.getTour(); } public public public public public public
static static static static static static
int getPop(){return pop_size;} int getJumJ(){return nJob;} int getJumM(){return nMesin;} int[] getCode(){return code;} int[] getMes(){return mesin;} int[] getOp(){return operasi;}
private void RUN() { if(text1.equals("")){ try{ getInput(); getParameter(); long start = System.currentTimeMillis(); StartPopulation SP; SP=new StartPopulation(seqM, process, due, pop_size, degree); System.out.println("===*** Iterasi Awal ***==="); System.out.println("--- Populasi Awal ---"); SP.Show(); Population p = null; for (int i =0;i<max_gen;i++){ System.out.println(); System.out.println("===*** ITERASI KE-"+(i+1)+" ***==="); System.out.println(); if(i==0){ p=new Population(SP, seqM, process, due, tour, Pc, Pm);} else{ p=new Population(p, seqM, process, due, tour, Pc, Pm);} System.out.println("--- Populasi Baru ---"); p.Show();} this.dispose(); code=p.getbBest(); Individu ind=new Individu(seqM, process, due); ind.setJob(code); operasi=ind.getOperation(); mesin=ind.getMachine(); ms=p.getbMakespanBest(); meanBest=""+p.getbMeanBest()+""; minBest=""+p.getbMinBest()+""; msBest="("+getStringCode(ms)+")"; System.out.println(); System.out.println("---+ SOLUSI +---"); best=" Urutan Job :\n"+getStringCode(code)+""; System.out.println(""+best); System.out.println("Rata-rata AI = "+meanBest); System.out.println("Minimum AI = "+minBest); System.out.println("Makespan = "+msBest); Result r=new Result(); r.setVisible(true); }catch(NumberFormatException e){ JOptionPane.showMessageDialog(this,"Cek Your Input\n\n"+e," Warning!!!!",JOptionPane.WARNING_MESSAGE); }} else{ text="Input Your Data !\n";
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
Lampiran 6 - 4
JOptionPane.showMessageDialog(this,text,"Error",JOptionPane.E RROR_MESSAGE); } } private String getStringCode(int[] Code) { String kode=" "; int mn=Code.length; for(int i=0;i<mn;i++) { kode=kode+Code[i]+" "; } return kode; } private String getStringCode(double[] Code) { String kode=""; int mn=Code.length; for(int i=0;i<mn;i++) { if(i==(mn-1)){ kode=kode+Code[i]; }else{ kode=kode+Code[i]+", "; } } return kode; } public public public public
static static static static
private void Workbook Sheet s0 Sheet s1 Sheet s2 Sheet s3 Sheet s4
String getBest(){return best;} double[] getMsBest(){return ms;} String getMeanBest(){return meanBest;} String getMinBest(){return minBest; }
setData(String Dir) throws IOException, BiffException{ book = Workbook.getWorkbook(new File(Dir)); = book.getSheet(0); //ambil sheet tabel urut mesin = book.getSheet(1); //ambil sheet tabel waktu proses #1 = book.getSheet(2); //ambil sheet tabel waktu proses #2 = book.getSheet(3); //ambil sheet tabel waktu proses #3 = book.getSheet(4); //ambil sheet tabel waktu duedate
n = s0.getRows(); m = s0.getColumns(); nJob=n; nMesin=m; seqM=new int[n][m]; process=new double[n][m][3]; due=new double[n][2]; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { seqM[i][j]=Integer.parseInt(s0.getCell(j,i).getContents()); process[i][j][0]=Double.parseDouble(s1.getCell(j,i).getContents()); process[i][j][1]=Double.parseDouble(s2.getCell(j,i).getContents()); process[i][j][2]=Double.parseDouble(s3.getCell(j,i).getContents());} for (int k = 0; k < 2; k++) { due[i][k]=Double.parseDouble(s4.getCell(k,i).getContents());} }} }
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
Lampiran 6 - 5
Source Code Kelas ParameterSetting.java package fmojss; import javax.swing.JOptionPane; public class ParameterSetting extends javax.swing.JFrame { private private private private
Double degree; Double Pc; Double Pm; int tour;
public ParameterSetting() { initComponents(); reset(); } private void defaultSettingActionPerformed(java.awt.event.ActionEvent evt) { if(defaultSetting.isSelected()){ inputDegree.setText("0.8"); inputPc.setText("0.6"); inputPm.setText("0.1"); inputTour.setText("2"); inputDegree.setEnabled(false); inputPc.setEnabled(false); inputPm.setEnabled(false); inputTour.setEnabled(false); }else{ inputDegree.setEnabled(true); inputPc.setEnabled(true); inputPm.setEnabled(true); inputTour.setEnabled(true); } } private void bApplyActionPerformed(java.awt.event.ActionEvent evt) { try{ save(); }catch(Exception e){ JOptionPane.showMessageDialog(this,"Ceck Your Input \n"+e, "Error", JOptionPane.ERROR_MESSAGE); } } private void bCancelActionPerformed(java.awt.event.ActionEvent evt) { this.dispose();} private void bResetActionPerformed(java.awt.event.ActionEvent evt) { reset();} public static void main(String args[]) { java.awt.EventQueue.invokeLater(new Runnable() { public void run() { new ParameterSetting().setVisible(true); } }); } private void save() { String text=""; degree=Double.parseDouble(inputDegree.getText()); if(degree<=0||degree>=1){
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
Lampiran 6 - 6
text="Degree of Similarity must be at interval (0,1) Pc=Double.parseDouble(inputPc.getText()); if(Pc<=0||Pc>=1){ text="Probability of Crossover must be at interval (0,1) Pm=Double.parseDouble(inputPm.getText()); if(Pm<=0||Pm>=1){ text="Probability of Mutation must be at interval (0,1) tour=Integer.parseInt(inputTour.getText()); if(tour<=1||tour>=Input.getPop()){ text="Tournament size at least 2 and maximum Population Size if(text.equals("")){ this.dispose(); }else{ reset(); String newText=text+"\nInput Your Setting Again !!!"; wrong(newText); }
!!!";} !!!";} !!!";} !!!";}
} private void reset() { degree=0.8; inputDegree.setText("0.8"); Pc=0.6; inputPc.setText("0.6"); Pm=0.1; inputPm.setText("0.1"); tour=2; inputTour.setText("2"); defaultSetting.setSelected(true); inputDegree.setEnabled(false); inputPc.setEnabled(false); inputPm.setEnabled(false); inputTour.setEnabled(false); } private void wrong(String text){ JOptionPane.showMessageDialog(this,text,"Warning!!!",JOptionPane. WARNING_MESSAGE); } public public public public
double getDegree(){return degree;} double getPc(){return Pc;} double getPm(){return Pm;} int getTour(){return tour;}
}
Source Code Kelas Result.java package fmojss; import import import import import import import import
java.awt.Color; java.awt.Component; java.util.logging.Level; java.util.logging.Logger; javax.swing.JLabel; javax.swing.JTable; javax.swing.table.DefaultTableCellRenderer; jxl.write.WriteException;
public class Result extends javax.swing.JFrame { //Makespan private double[] mas; private Object[][] isiTabel; //Gantt chart private int[] job;
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
private private private private private private private private private
Lampiran 6 - 7
int[] oper; int[] mesin; int n; int m; int gen; int end; int endi; int[][] scheJob; int[][][] schedule;
public Result() { initComponents(); mas=new double[3]; mas=Input.getMsBest(); mean.setText(Input.getMeanBest()); min.setText(Input.getMinBest()); code.setText(Input.getBest()); setTMakespan(); setTabel(); setGanttChart(); } private void setTMakespan() { String[] ket={"Lambat","Normal","Cepat"}; JTable tabelMs = new JTable(getMakespan(),ket); tabelMs.setEnabled(false); tabelMakespan.setViewportView(tabelMs); } private Object[][] getMakespan() { Object[][] hasil = new Object[1][3]; for(int i=0;i<3;i++) { hasil[0][i]=""+mas[i];} return hasil; } private void setTabel() { String[] ket={"Job","Operasi","Mesin"}; JTable tabel=new JTable(getTable(),ket); tabelJOM.setViewportView(tabel); } private Object[][] getTable() { n=Input.getJumJ(); m=Input.getJumM(); gen=n*m; job = Input.getCode(); mesin = Input.getMes(); oper = Input.getOp(); isiTabel=new Object[gen][3]; for(int i=0;i
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
Lampiran 6 - 8
public static void main(String args[]) { java.awt.EventQueue.invokeLater(new Runnable() { public void run() { new Result().setVisible(true); } }); } private void setGanttChart() { //Tabel keterangan mesin String[] ketMesin = {"Mesin"}; JTable tabelMesin = new JTable(getTabelMesin(),ketMesin); tabelMesin.setEnabled(false); ketTMesin.setViewportView(tabelMesin); getGanttChartA(); //Tabel Gantt Chart String[] ket= new String[end+1]; for (int i=0;i<end+1;i++) { ket[i]=" "; } final JTable tabelGantt = new JTable(nullTable(), ket); tabelGantt.setDefaultRenderer(Object.class,new DefaultTableCellRenderer() { @Override public Component getTableCellRendererComponent(JTable table,Object value,boolean isSelected, boolean hasFocus, int row,int column) { JLabel label = (JLabel) super. getTableCellRendererComponent(table, value, isSelected, hasFocus, row, column); label.setBackground(Color.white); try { getGanttChart(); } catch (WriteException ex) { Logger.getLogger(Result.class.getName()).log(Level.SEVERE, null, ex); } for (int i=0;i<m;i++) { for (int j=0;j=schedule[i][j][0] && column <= schedule[i][j][1] )) { label.setText(""+scheJob[i][j]+""); } } } return label; } }); for (int i=0;i<end+1;i++){ tabelGantt.getColumnModel().getColumn(i).setPreferredWidth(1); } tabelGantt.setAutoResizeMode(JTable.AUTO_RESIZE_OFF); tabelGantt.getColumnModel().getColumn(0).setPreferredWidth(1); tabelGantt.setEnabled(false); tableGanttC.setViewportView(tabelGantt); }
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
Lampiran 6 - 9
private Object[][] getTabelMesin() { Object[][] hasil = new Object[m][1]; for(int i=0;i<m;i++) { hasil[i][0]="Mesin "+i; } return hasil; } private Object[][] nullTable() { Object[][] hasil=new Object[m][end+1]; return hasil; } private void getGanttChart() throws WriteException { int[] timeJ = new int[n]; int[] timeM = new int[m]; int start=0; end=0; int oprADmesin[] = new int[m]; scheJob = new int[m][n]; schedule = new int[m][n][2]; for (int i=0;itimeJ[job[i]]) { start=timeM[mesin[i]]+1; timeM[mesin[i]]=timeM[mesin[i]]+1; end=timeM[mesin[i]]; } else { start=timeJ[job[i]]+1; timeM[mesin[i]]=timeJ[job[i]]+1; end=timeM[mesin[i]]; } timeJ[job[i]]=timeM[mesin[i]]; scheJob[mesin[i]][oprADmesin[mesin[i]]]=job[i]; schedule[mesin[i]][oprADmesin[mesin[i]]][0]=start; schedule[mesin[i]][oprADmesin[mesin[i]]][1]=end; oprADmesin[mesin[i]]+=1; } } private void getGanttChartA() { int[] timeJ = new int[n]; int[] timeM = new int[m]; int start=0; end=0; int oprADmesin[] = new int[m]; scheJob = new int[m][n]; schedule = new int[m][n][2]; for (int i=0;itimeJ[job[i]]) { start=timeM[mesin[i]]+1; timeM[mesin[i]]=timeM[mesin[i]]+1; end=timeM[mesin[i]]; }
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
Lampiran 6 - 10
else { start=timeJ[job[i]]+1; timeM[mesin[i]]=timeJ[job[i]]+1; end=timeM[mesin[i]]; } timeJ[job[i]]=timeM[mesin[i]]; scheJob[mesin[i]][oprADmesin[mesin[i]]]=job[i]; schedule[mesin[i]][oprADmesin[mesin[i]]][0]=start; schedule[mesin[i]][oprADmesin[mesin[i]]][1]=end; oprADmesin[mesin[i]]+=1; } } }
Source Code Kelas Individu.java package fmojss; import java.util.Random; public class Individu extends Input{ //For saving Data private int[][] seqMachine; private double[][] duedate; private double[][][] processTime; //Parameters private int n; private int m; private int pop_size; private double degree; private int tour; private double Pc; private double Pm; //For generate individu private int[] job; private int[] operation; private int[] machine; private double[][] timeP; //Definition of Completion Time and Activate Schedule private double[] mC; private double[][] tJob; private double[][] start; private double[][] delay; private boolean[] act; private double ranking; public Individu(int[][] mes, double[][][] pros, double[][] due) { seqMachine=mes; processTime=pros; duedate=due; n=seqMachine.length; m=seqMachine[0].length; Job(); Operation(); Machine(); Time(); Complete(); actSchedule(); }
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
Lampiran 6 - 11
public void setJob(int[] jOb){ job=jOb; Operation(); Machine(); Time(); Complete(); actSchedule(); } public void setOperation(int[] jOb){ job=jOb; Operation(); } public public public public public public public public public public
int[] getJob(){return job;} int[] getOperation(){return operation;} int[] getMachine(){return machine;} double[] getmC(){return mC;} double[][] getCompletion(){return tJob;} double getRanking(){return ranking;} int getNJOb(){return n;} int getNMachine(){return m;} double[][] getDueDate(){return duedate;} int getGenes(){return n*m;}
private void Job(){ int nJob=n; int nMesin=m; int genes=nJob*nMesin; int i=0, a, acak; int[] num; job=new int[genes]; num=new int[nJob]; while(i
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
Lampiran 6 - 12
machine=new int[genes]; for(int i=0;i=0){ indexNon=getNonActive(indexDel+1, machine[indexDel]);
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
Lampiran 6 - 13
if(indexNon>=0){ jobAct=getJobAct(indexDel,indexNon); reSchedule(jobAct); } }else{ break; } }while(ranking<maks); } private int getDelay(){ int nJob=n; int nMesin=m; int index=-1; int genes=nJob*nMesin; int a; for(int i=0;i0){ a=a+1; }} if(a==3){ index=i; break;} } return index; } private int getNonActive(int startJob,int machineA){ int nJob=n; int nMesin=m; int index=-1; int genes=nJob*nMesin; int a; for(int i=startJob;i=timeP[i][j]){ a=a+1; } } if(a==3){ index=i; break; } }else if(operation[i]>0){ for(int k=0;k=timeP[i][l]){ a=a+1; }} if(a==3){ index=i; } break; } } } } } return index; }
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
Lampiran 6 - 14
private int[] getJobAct(int start,int start1){ int nJob=n; int nMesin=m; int genes=nJob*nMesin; int[] Job=new int[genes]; System.arraycopy(job, 0, Job, 0, genes); int titip=Job[start1]; for(int i=start1;i>start;i--){ Job[i]=Job[i-1]; } Job[start]=titip; return Job; } private void reSchedule(int[] Job){ job=Job; Operation(); Machine(); Time(); Complete(); } private double[] maxComplete(double[][] jobT){ int tem=0, tem1=0, tem2=0, tem3=0; double maks=0, maks1, maks2; double[] maxC =new double[3]; int nJob=jobT.length; ranking=0; double[] c1=new double [nJob]; double[] c2=new double [nJob]; double[] c3=new double [nJob]; for(int i=0;imaks){ maks=c1[i]; tem=i; } } tem1=tem; maks1=maks; for(int j=0;jmaks1){ maks1=c2[j]; tem=j; }} } tem2=tem; maks2=maks1; for(int k=0;kmaks2){ maks2=c3[k]; tem=k; }} } System.arraycopy(jobT[tem], 0, maxC, 0, 3); ranking = c1[tem]; return maxC; } }
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
Lampiran 6 - 15
Source Code Kelas StartPopulation.java package fmojss; public class StartPopulation { private Individu ind; private int[][] chrom; private int[][] mes; private int nJob; private int nMesin; private int popsize; //For degree calculation private double degree; private int[][] MTable; private int[][][] before; private int[][][] after; //For calculation objective function; private Object[] makespan; private Object[] completion; private double[] ranking; private double[][] z; private double[][] linz; private double[] f; public StartPopulation(int[][] mesin, double[][][] pros, double[][] due, int pop, double deg){ ind=new Individu(mesin, pros, due); nJob=ind.getNJOb(); nMesin=ind.getNMachine(); Objective obj; Evaluation F; degree=deg; popsize=pop; int genes=nJob*nMesin; chrom=new int [popsize][genes]; mes=new int [popsize][genes]; makespan=new Object [popsize]; completion=new Object [popsize]; ranking=new double [popsize]; z=new double [popsize][3]; f=new double [popsize]; int[][][][] bf=new int [popsize][nMesin][nJob][nJob]; int[][][][] aft=new int [popsize][nMesin][nJob][nJob]; int suit=0; for(int i=0;i<popsize;i++){ if(i==0){ ind=new Individu(mesin, pros, due); chrom[i]=ind.getJob(); mes[i]=ind.getMachine(); MTable(chrom[i], mes[i]); TableContent(); bf[i]=before; aft[i]=after; }else{ while(suit!=i){ ind=new Individu(mesin, pros, due); chrom[i]=ind.getJob(); mes[i]=ind.getMachine(); MTable(chrom[i], mes[i]); TableContent(); bf[i]=before; aft[i]=after;
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
suit=Degree(bf, aft, i); }} makespan[i]=ind.getmC(); completion[i]=ind.getCompletion(); ranking[i]=ind.getRanking(); obj=new Objective(mesin, pros, completion[i], ranking[i]); z[i]=obj.getZ();
Lampiran 6 - 16
due,
(double[][])
} F=new Evaluation(z); linz=F.getLinZ(); f=F.getFitness(); } public public public public
Object[] Object[] Object[] double[]
getStartPop(){return chrom;} getMakespan(){return makespan;} getZ(){return z;} getF(){return f;}
private void MTable(int[] job, int[] ms){ int genes=job.length; MTable=new int [nMesin][nJob]; int[] temp1=new int [nMesin]; int temp; for(int i=0;i
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
Lampiran 6 - 17
int[][] a=new int [index][nJob]; double[] rasio=new double [index]; int hasil=0; for(int i=0;i Makespan "); Out((double[]) makespan[i]); System.out.println(); System.out.print(" Nilai Tujuan : "); Out((double[]) z[i]); System.out.println(); System.out.print(" Nilai Keanggotaan Linear : "); Out(linz[i]); System.out.println(); System.out.print(" Nilai Fitness : "); System.out.println(f[i]); } } private void Out(int[] a){ int col=a.length; for(int i=0;i
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
Lampiran 6 - 18
Source Code Kelas Population.java package fmojss; public class Population { private Individu ind; private int[][] mesin; private double[][][] proses; private double[][] dued; private private private private private private private private private private private private private private private private private private private private private private private private
int pop; int tour; int nC; int nM; Object[] gChrom; Object[] ZgChrom; Object[] chrom; Object[] chromC; Object[] chromM; double[] Fchrom; Object[] Zchrom; Object[] ZchromC; Object[] ZchromM; double[] f; double[] fNew; Object[] ZNew; Object[] makespan; int[][] newChrom; int[] best; double meanBest; double minBest; double[] msBest; double[] ZBest; double[][] Lz;
public Population(StartPopulation populasi, int[][] mes, double[][][] pros, double[][] due, int tur, double pc, double pm){ ind= new Individu(mes, pros, due); mesin=mes; proses=pros; dued=due; chrom=populasi.getStartPop(); pop=chrom.length; Fchrom=populasi.getF(); Zchrom=populasi.getZ(); tour=tur; System.out.println("-> Partial Schedule Exchange Crossover <-"); Crossover(pc); System.out.println("-> Swap Mutation <-"); Mutation(pm); setOPandGO(); double[][] nZ=new double[pop+nC+nM][3]; for(int i=0; i<pop+nC+nM; i++){ nZ[i]= (double[]) ZgChrom[i]; } Evaluation eval=new Evaluation(nZ); f=eval.getFitness(); Lz=eval.getLinZ(); setOrderPop(); setNewPop(); }
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
Lampiran 6 - 19
public Population(Population populasi, int[][] mes, pros, double[][] due, int tur, double pc, double pm){ ind= new Individu(mes, pros, due); mesin=mes; proses=pros; dued=due;
double[][][]
chrom=populasi.getNewPop(); pop=chrom.length; Fchrom=populasi.getF(); Zchrom=populasi.getZ(); tour=tur; System.out.println("-> Partial Schedule Exchange Crossover <-"); Crossover(pc); System.out.println("-> Swap Mutation <-"); Mutation(pm); setOPandGO(); double[][] nZ=new double[pop+nC+nM][3]; for(int i=0; i<pop+nC+nM; i++){ nZ[i]= (double[]) ZgChrom[i]; } Evaluation eval=new Evaluation(nZ); f=eval.getFitness(); Lz=eval.getLinZ(); setOrderPop(); setNewPop(); } public public public public public public public
Object[] getNewPop(){return newChrom;} double[] getF(){return fNew;} Object[] getZ(){return ZNew;} int[] getbBest(){return best;} double getbMeanBest(){return meanBest;} double getbMinBest(){return minBest;} double[] getbMakespanBest(){return msBest;}
private void Crossover(double prob){ Tournament T = new Tournament(tour, Fchrom, prob); int[] parentC=T.getParent(); int cek=parentC.length; if(cek!=0){ PSEX cross = new PSEX(mesin, proses, dued, parentC, (int[][]) chrom); chromC = cross.getChild(); ZchromC = cross.getZChild(); nC = cross.getSumChild(); } } private void Mutation(double prob){ Tournament T = new Tournament(tour, Fchrom, prob); int[] parentM=T.getParent(); int cek=parentM.length; if(cek!=0){ SwapMutation mut = new SwapMutation(mesin, proses, parentM, (int[][]) chrom); chromM = mut.getChild(); ZchromM = mut.getZChild(); nM = mut.getSumChild(); } }
dued,
private void setOPandGO(){ int tot = pop+nC+nM;
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
Lampiran 6 - 20
gChrom = new Object[tot]; ZgChrom = new Object[tot]; int m1=0, c1=0; for(int i=0;i=pop && i<(pop+nC)){ gChrom[i]=chromC[c1]; ZgChrom[i]=ZchromC[c1]; c1++; } else{ gChrom[i]=chromM[m1]; ZgChrom[i]=ZchromM[m1]; m1++; } } } private void setOrderPop(){ Object temp=0; double temp1=0; Object temp2=0; double[] temp3=new double [3]; int tot = pop+nC+nM; for(int i=0;i<(tot-1);i++){ for(int j=i;j
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
Lampiran 6 - 21
ZBest=(double[]) ZNew[0]; meanBest=ZBest[0]; minBest=ZBest[1]; msBest=(double[]) makespan[0]; } public void Show(){ for(int i=0;i<pop;i++){ System.out.print(i+".) Kromosom :"); Out((int[]) newChrom[i]); System.out.print(" => Makespan "); Out((double[]) makespan[i]); System.out.println(); System.out.print(" Nilai Fungsi Tujuan :"); Out((double[])ZNew[i]); System.out.println(""); System.out.print(" Nilai keanggotaan Linear :"); Out(Lz[i]); System.out.println(""); System.out.print(" Nilai Fitness : "); System.out.print(f[i]); System.out.println(); } } private void Out(int[] a){ int col=a.length; for(int i=0;i
Source Code Kelas Objective.java package fmojss; public class Objective{ private Individu D; private int nJob; private double[] z; private double[][] complete; private double rank; private double[] agree; public Objective(int[][] mes, double[][][] double[][] completion, double ranking){ D=new Individu(mes, pros, due); nJob=completion.length; complete=completion; rank=ranking; double sum=0; z=new double[3]; AI();
Skripsi
pros,
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
double[][]
due,
Marisa
ADLN Perpustakaan Universitas Airlangga
Lampiran 6 - 22
for(int i=0;id1 && c3d1 && c3>=d2){ integral1=Area1(c1,c2,d1,d2,c1,0); integral2=Area2(0,0,d1,d2,integral1[0],d2); integral3[1]=0;} else if(c2==d1 && c3>d2){ integral1=Area1(c1,c2,d1,d2,c1,c2); integral2=Area2(0,0,d1,d2,d1,d2); integral3[1]=0;} else if(c2d2){ integral1=Area1(c1,c2,d1,d2,c1,c2); integral2=Area2(c2,c3,d1,d2,c2,0); integral3=Area2(0,0,d1,d2,integral2[0],d2);} else if(c1>=d2){ agree[i]=0; } if(agree[i]==-1){ areaCD=integral1[1]+integral2[1]+integral3[1]; agree[i]=areaCD/areaC; } } } private double[] Area1(double v, double w, double x, double y, double b1, double b2){ double[] batas = new double[2]; double a, b; a=w-v; b=y-x;
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
if(b2==0){ batas[0]=(y*w-v*x)/(b+a); } else{ batas[0]=b2; } batas[1]=(1/a)*(((Math.pow(batas[0], (v*(batas[0]-b1))); return batas;
Lampiran 6 - 23
2)-Math.pow(b1,
2))/2)-
} private double[] Area2(double v, double w, double x, double y, double b1, double b2){ double[] batas = new double[2]; double a,b = 0; if(b2==0){ if(b1==v){ a=y-x; b=w-v; batas[0]=(x*w-v*y)/(b-a); y=w; } else{ a=w-v; b=y-x; batas[0]=(x*w-v*y)/(a-b); } } else{ b=y-x; batas[0]=b2; } batas[1]=(1/b)*((y*(batas[0]-b1))-((Math.pow(batas[0], 2)Math.pow(b1, 2))/2)); return batas; } private double Min(double[] a) { int row=a.length; double min=a[0]; for(int i=1;i
Source Code Kelas Evaluation.java package fmojss; public class Evaluation { private double[] z0; private double[] z1; private double[][] z; private double[] f; private double[][] linZ; public Evaluation(double[][] Z){ z=Z; int pop_size=z.length; z0=new double[3]; z1=new double[3];
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
Lampiran 6 - 24
f = new double [pop_size]; linZ = new double[pop_size][3]; for(int i=0;i<3;i++){ z0[i]=Min(z, i); z1[i]=Max(z, i); } for(int j=0;j<pop_size;j++){ for(int k=0;k<3;k++){ if(z0[k]!=z1[k]){ if(k==2){ linZ[j][k]=(z1[k]-z[j][k])/(z1[k]-z0[k]); } else{linZ[j][k]=(z[j][k]-z0[k])/(z1[k]-z0[k]); } } else{linZ[j][k]=1;} } } f = Min(linZ); } double[] getFitness() { return f; } double[][] getLinZ() { return linZ; } private double Min(double[][] a, int index) { int row=a.length; double min=a[0][index]; for(int i=1;imaks){ maks=a[i][index]; } } return maks; } private double[] Min(double[][] a) { int row=a.length; int col=a[0].length; double[] min=new double[row]; for(int i=0;i
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
Lampiran 6 - 25
private void Out(double[] a){ int col=a.length; System.out.print("("); for(int i=0;i<(col-1);i++){ System.out.print(a[i]+", "); } System.out.print(a[col-1]+")"); } private void Out(double[][] a){ int row = a.length; int col = a[0].length; for(int i=0;i
Source Code Kelas Tournament.java package fmojss; import java.util.Random; public class Tournament{ private ParameterSetting PS; private int[] Parent; public Tournament(int tur, double[] a, double prob) { int popsize=a.length; int[] pos= new int[tur]; double[] fit = new double [tur]; double[] ind = new double [tur]; int[] caParent = new int [popsize]; for(int i=0;i<popsize;i++){ for(int j=0;j
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
Lampiran 6 - 26
k=0; } } } fit[j] = a[pos[j]]; } caParent[i]=pos[Max(fit)]; } Selection(caParent, prob); } public int[] getParent(){return Parent;} private int Max(double[] a) { int row=a.length; int temp=0; double maks=a[0]; for(int i=1;imaks){ maks=a[i]; } } for(int j=0;j
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
Lampiran 6 - 27
Source Code Kelas PSEX.java package fmojss; import java.util.Random; public final class PSEX { private int[][] childC; private int totC; private Individu indi; private double[][] z; private Object[] makespan; private double[] mc; private int[][] mesin; private double[][][] proses; private double[][] dued; //Partial Schedule private int pos11=0, pos12=0, pos21=0, pos22=0; private int nPart1=0, nPart2=0; private int nParent1=0, nParent2=0; private int[] partial1; private int[] partial2; private int[] OCross1; private int[] OCross2; //Missed and Exceed genes private int[] miss1; private int[] miss2; private int[] exceed1; private int[] exceed2; //Operation Parent and Child for Exceed genes private int[] oprP1; private int[] oprP2; private int[] oprC1; private int[] oprC2; //Operation Parent and Child for Missed genes private int[] part1; private int[] part2; private int[] child1; private int[] child2; public PSEX(int[][] mes, double[][][] pros, double[][] due, int[] par, int[][] ind) { mesin=mes; proses=pros; dued=due; int genes=ind[0].length; totC=par.length; int nP=0; int[] index=new int [totC]; int mod = totC%2; if(mod!=0){ totC=totC-1; } for(int i=0;i
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
Lampiran 6 - 28
nP=nP+1; } } totC=nP; childC=new int[totC][genes]; z=new double[totC][genes]; makespan=new Object[totC]; int[] cParent1=new int[genes]; int[] cParent2=new int[genes]; int k=0, sum=0; if(totC!=0){ for(int i1=0;i1
int[][] getChild(){return childC;} int getSumChild(){return totC;} double[][] getZChild(){return z;} Object[] getMakespan(){return makespan;}
private void getPosition(int[] Par1, int[] Par2) { int genes=Par1.length; int temp=0, t=0; int job=0; Random r = new Random(); pos11 = r.nextInt(genes); job=Par1[pos11]; for(int j1=(pos11+1);j1=0;k1--){ if(Par1[k1]==job){ t=pos11; pos11=k1; pos12=t; break;} } } nPart1=(pos12+1)-pos11;
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
Lampiran 6 - 29
for(int j2=0;j2
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
Lampiran 6 - 30
private void getMissExceed() { for(int i=0;i
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
Lampiran 6 - 31
if(pM1!=0){ for(int i=0;i
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
Lampiran 6 - 32
} private int[] delGen(int awal, int akhir, int jum, int pos, int lPart, int[] anak, int lebih) { //Menghapus gen lebih pada anak int[] hasil=new int[2]; hasil[1]=pos; int m1=0, posisi=0; if(akhir<=awal){ for(int i=(pos+lPart);i<jum;i++){ if(anak[i]==lebih){ posisi=i; m1=1; } } if(m1==0){ for(int i1=0;i1<pos;i1++){ if(anak[i1]==lebih){ posisi=i1; hasil[1]=pos-1; } } } } else if (akhir>awal){ for(int i2=0;i2<pos;i2++){ if(anak[i2]==lebih){ posisi=i2; m1=1; hasil[1]=pos-1; } } if(m1==0){ for(int i3=(pos+lPart);i3<jum;i3++){ if(anak[i3]==lebih){ posisi=i3; } } } } for(int j=posisi;j<(jum-1);j++){ anak[j]=anak[j+1]; } hasil[0]=jum-1; return(hasil); } private void addBack(int lAnak, int start, int[] anak, int miss) { //Menambah gen kurang pada anak yang tidak ada dalam partial schedule for(int i=(lAnak-1);i>start;i--){ anak[i]=anak[i-1]; } anak[start]=miss; } private int addFront(int lAnak, int start, int[] anak, int miss) { //Menambah gen kurang pada anak yang ada dalam partial schedule int pos=0; for(int i=(lAnak-1);i>start;i--){ anak[i]=anak[i-1]; } anak[start]=miss; pos=start+1; return pos; }
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
Lampiran 6 - 33
private double[] setObj(int[] a){ indi=new Individu(mesin, proses, dued); indi.setJob(a); double[][] complete = indi.getCompletion(); double rank = indi.getRanking(); mc = indi.getmC(); Objective obj = new Objective(mesin, proses, dued, complete, rank); double[] ob = obj.getZ(); return ob; } private void giveValue(int[] a){ int row=a.length; for(int i=0;i Makespan "); Out((double[]) makespan[i]); System.out.print(" Nilai Tujuan : "); Out((double[]) z[i]); System.out.println(); } } private void Out(int[] a){ int col=a.length; for(int i=0;i
Source Code Kelas SwapMutation.java package fmojss; import java.util.Random; public final class SwapMutation { private Individu ind; private int[][] childM; private int totM; private double[][] z; private Object[] makespan; private double[] mc; private int[][] mesin; private double[][][] proses;
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
Lampiran 6 - 34
private double[][] dued; public SwapMutation(int[][] mes, double[][][] pros, double[][] due, int[] par, int[][] ind) { mesin=mes; proses=pros; dued=due; int genes=ind[0].length; totM=par.length; int sum=0, r0=0, r1=0, temp=0; int[][] cParent=new int[totM][genes]; for(int j=0;j
int[][] getChild(){return childM;} int getSumChild(){return totM;} double[][] getZChild(){return z;} Object[] getMakespan(){return makespan;}
private double[] setObj(int[] a){ ind=new Individu(mesin, proses, dued); ind.setJob(a); double[][] complete = ind.getCompletion(); double rank = ind.getRanking(); mc = ind.getmC(); Objective obj = new Objective(mesin, proses, dued, complete, rank); double[] ob = obj.getZ(); return ob; } private static void Out(int[][] a){ int row = a.length; int col = a[0].length; for(int i=0;i
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
Lampiran 6 - 35
System.out.println(); } } public void Show(int jum){ for(int i=0;i<jum;i++){ System.out.print(i+".) Kromosom :"); Out((int[]) childM[i]); System.out.print(" => Makespan "); Out((double[]) makespan[i]); System.out.println(); System.out.print(" Nilai Tujuan : "); Out((double[]) z[i]); System.out.println(); } } private void Out(int[] a){ int col=a.length; for(int i=0;i
Source Code Kelas About.java package fmojss; public class About extends javax.swing.JFrame { public About() { initComponents(); } private void jButton1ActionPerformed(java.awt.event.ActionEvent evt) { dispose();} public static void main(String args[]) { java.awt.EventQueue.invokeLater(new Runnable() { public void run() { new About().setVisible(true);} }); } }
Source Code Kelas Help.java package fmojss; public class Help extends javax.swing.JFrame { public Help() { initComponents(); start(); }
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
Lampiran 6 - 36
private void jButton1ActionPerformed(java.awt.event.ActionEvent evt) { dispose(); } private void choiceItemStateChanged(java.awt.event.ItemEvent evt) { try{ int index=choice.getSelectedIndex(); if(index==0){ text.setText(" Welcome to Help Content\n Choose the item !"); }else if(index==1){ text.setText(" *) File --> Data\n"+ " Digunakan untuk menginputkan Data\n"+ " yang akan diproses. \n\n"+ " *) Setting --> Parameters\n"+ " Digunakan untuk mengatur inputan\n"+ " Parameter. \n\n"+ " *) Help --> Help\n"+ " Digunakan untuk mengetahui hal-hal\n"+ " terkait dengan program.\n\n"+ " *) Help --> About\n"+ " Penjelasan tentang Program.\n\n"+ " *) Process\n"+ " Melakukan proses iterasi untuk\n"+ " memperoleh hasil permasalahan.\n\n"); }else if(index==2){ text.setText(" Proses Inputan :\n"+ " 1) Select Data yang akan diproses dengan\n"+ " memilih menu File -> Data\n\n"+ "2)Pada tampilan awal, inputkan Population\n"+ " Size dan Maximum Generation\n"+ " Parameter \n\n"+ " 3) Jika ingin merubah parameter, pilih\n"+ " Setting -> Parameters\n\n"+ " --- Silahkan Process ---\n\n"); }else if(index==3){ text.setText(" *) Population Size \n"+ " -> Banyaknya jumlah kromosom atau\n"+ " individu yang dibangkitkan. \n\n"+ " *) Maximum Generation\n"+ "-> Batas iterasi yang akan dilakukan.\n\n"+ " *) Degree of Similarity\n"+ " -> Batas derajat kesamaan antar\n"+ " individu awal yang dibangkitkan. \n"+ " Nilai harus (0,1).\n\n"+ " *) Probability of Crossover\n"+ " -> Prosentase individu yang akan \n"+ " dicrossover. Nilai harus (0,1).\n\n"+ " *) Probability of Mutasi\n"+ " -> Prosentase individu yang akan\n"+ " dimutasi. Nilai harus (0,1).\n\n"+ " *) Tournament Size\n"+ "-> Banyak individu yang diturnamenkan\n"+ " pada proses seleksi. Nilai harus \n"+ " (0,1).\n\n"); }else if(index==4){ text.setText(" Ketentuan inputan Data :\n\n"+ " 1) Data harus dalam file berbentuk\n"+ " Microsoft Excel 97-2003 Worksheet \n"+ " (.xls).\n\n"+ "2) Untuk sheet 1-4, Baris merupakan Job\n"+ " dan kolom merupakan operasi.\n\n"+ " 3) Sheet pertama diisi dengan urutan \n"+
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
Lampiran 6 - 37
" Mesin untuk tiap Job.\n\n"+ " 4) Sheet kedua diisi dengan waktu \n"+ " operasi pertama tiap operasi.\n\n"+ " 5) Sheet ketiga diisi dengan waktu \n"+ " operasi kedua tiap operasi.\n\n"+ " 6) Sheet keempat diisi dengan waktu \n"+ " operasi ketiga tiap operasi.\n\n"+ " 7) Sheet kelima diisi dengan waktu \n"+ " duedate Job, dengan baris merupakan \n"+ " Job dan kolom merupakan waktu.\n\n"); }else if(index==5){ text.setText(" Keterangan Output :\n\n"+ " 1) Rata-rata Agreement Index, Minimum\n"+ " Agreement Index, Maximum \n"+ " Completion Time merupakan nilai \n"+ " tujuan hasil terbaik yang diperoleh.\n\n"+ " 2) Solusi merupakan kode Job hasil.\n\n"+ " 3) JOM merupakan tabel urutan \n"+ " pekerjaan, operasi dan mesin yang \n"+ " digunakan.\n\n"+ " 4) Tabel mesin merupakan tabel urutan\n"+ " job pada tiap mesin.\n\n"); }else if(index==6){ text.setText(" Tabel JOM merupakan tabel urutan Job,\n"+ " operasi dan mesin.\n\n"+ " Contoh :\n\n"+ " Job = 0 1 1 0\n"+ " Operasi = 0 0 1 1\n"+ " Mesin = 1 1 0 0\n\n"+ " Contoh tersebut menunjukkan bahwa\n"+ " Job ke-0 operasi ke-0 diproses pada\n"+ " mesin 1 dst.\n\n"); } else if(index==7){ text.setText("Tabel Mesin merupakan tabel urutan Job,\n"+ " pada tiap mesin.\n\n"+ " Contoh :\n\n"+ " Mesin | Urutan Job\n"+ " 0 | 0 1\n"+ " 1 | 1 0\n\n"+ " Contoh tersebut menunjukkan bahwa\n"+ "pada mesin ke-0 Job ke-0 diproses lebih\n"+ " dulu dari mesin 1 dst.\n\n"); } } catch(Exception e){} } public static void main(String args[]) { java.awt.EventQueue.invokeLater(new Runnable() { public void run() { new Help().setVisible(true); } }); } private void start() { choice.setSelectedIndex(0); text.setText(" Welcome to Help Content\n }
Choose the item !");
}
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
Lampiran 7 degree
Hasil Penyelesaian Problem 1 FMOJSSP Pc
0.5
0.7
0.6
0.7
0.5
0.8
0.6
0.7
0.9
0.5
0.6
Skripsi
Lampiran 7 - 1
Pm
z1
z2
z3
0.01
0.88632
0.62241
(65.0, 87.0, 111.0)
0.1
0.91206
0.70968
(62.0, 86.0, 110.0)
0.2
0.96186
0.79422
(65.0, 87.0, 110.0)
0.01
0.96186
0.79422
(65.0, 87.0, 110.0)
0.1
0.91206
0.70968
(62.0, 86.0, 110.0)
0.2
0.96186
0.79422
(65.0, 87.0, 110.0)
0.01
0.96186
0.79422
(66.0, 89.0, 111.0)
0.1
0.91206
0.70968
(62.0, 86.0, 110.0)
0.2
0.96186
0.79422
(65.0, 87.0, 110.0)
0.01
0.93547
0.68182
(70.0, 93.0, 120.0)
0.1
0.96186
0.79422
(65.0, 87.0, 110.0)
0.2
0.96186
0.79422
(65.0, 87.0, 110.0)
0.01
0.96186
0.79422
(65.0, 87.0, 110.0)
0.1
0.96186
0.79422
(65.0, 87.0, 110.0)
0.2
0.96186
0.79422
(65.0, 87.0, 110.0)
0.01
0.96186
0.79422
(65.0, 87.0, 110.0)
0.1
0.83345
0.42078
(58.0, 84.0, 110.0)
0.2
0.91206
0.70968
(62.0, 86.0, 110.0)
0.01
0.96586
0.80620
(73.0, 99.0, 124.0)
0.1
0.84516
0.51042
(63.0, 88.0, 109.0)
0.2
0.86556
0.57100
(62.0, 88.0, 109.0)
0.01
0.91206
0.70968
(62.0, 86.0, 110.0)
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
degree
Pc 0.6
0.9 0.7
Skripsi
Lampiran 7 - 2
Pm
z1
z2
z3
0.1
0.91206
0.70968
(62.0, 86.0, 110.0)
0.2
0.96186
0.79422
(65.0, 87.0, 110.0)
0.01
0.96186
0.79422
(65.0, 87.0, 110.0)
0.1
0.78339
0.42078
(58.0, 84.0, 109.0)
0.2
0.96186
0.79422
(65.0, 87.0, 110.0)
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
Lampiran 8 degree
Hasil Penyelesaian Problem 2 FMOJSSP Pc
0.5
0.7
0.6
0.7
0.5
0.8
0.6
0.7
0.5 0.9 0.6
Skripsi
Lampiran 8 - 1
Pm
z1
z2
z3
0.01
0.98861
0.95192
(61.0, 83.0, 101.0)
0.1
0.99084
0.97143
(60.0, 81.0, 100.0)
0.2
0.97588
0.91176
(54.0, 73.0, 89.0)
0.01
0.97588
0.91176
(54.0, 73.0, 89.0)
0.1
0.99227
0.97460
(60.0, 83.0, 99.0)
0.2
0.97588
0.91176
(54.0, 73.0, 89.0)
0.01
0.97588
0.91176
(54.0, 73.0, 89.0)
0.1
0.99084
0.97143
(60.0, 81.0, 100.0)
0.2
0.99084
0.97143
(60.0, 81.0, 100.0)
0.01
0.99227
0.97460
(60.0, 83.0, 99.0)
0.1
0.97588
0.91176
(54.0, 73.0, 89.0)
0.2
0.96718
0.82949
(58.0, 75.0, 93.0)
0.01
0.96718
0.82949
(58.0, 75.0, 93.0)
0.1
0.97588
0.91176
(54.0, 73.0, 89.0)
0.2
0.99084
0.97143
(60.0, 81.0, 100.0)
0.01
0.99227
0.97460
(60.0, 83.0, 99.0)
0.1
0.98861
0.95192
(61.0, 83.0, 101.0)
0.2
0.99084
0.97143
(60.0, 81.0, 100.0)
0.01
0.96718
0.82949
(58.0, 75.0, 93.0)
0.1
0.99227
0.97460
(60.0, 83.0, 99.0)
0.2
0.99084
0.97143
(60.0, 81.0, 100.0)
0.01
0.97588
0.91176
(54.0, 73.0, 89.0)
0.1
0.99187
0.97333
(62.0, 83.0, 99.0)
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
degree
0.9
Skripsi
Lampiran 8 - 2
Pc
Pm
z1
z2
z3
0.6
0.2
0.99227
0.97460
(60.0, 83.0, 99.0)
0.01
0.99084
0.97143
(60.0, 81.0, 100.0)
0.1
0.99084
0.97143
(60.0, 81.0, 100.0)
0.2
0.97588
0.91176
(54.0, 73.0, 89.0)
0.7
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
Lampiran 9 degree
Hasil Penyelesaian Problem 3 FMOJSSP Pc
0.5
0.7
0.6
0.7
0.5
0.8
0.6
0.7
0.5 0.9 0.6
Skripsi
Lampiran 9 - 1
Pm
z1
z2
z3
0.01
0.74314
0.23923
(38.0, 49.0, 60.0)
0.1
0.61465
0.37594
(27.0, 36.0, 47.0)
0.2
0.71662
0.37594
(27.0, 36.0, 47.0)
0.01
0.62310
0.28444
(27.0, 37.0, 47.0)
0.1
0.84864
0.69231
(28.0, 38.0, 49.0)
0.2
0.73071
0.36000
(27.0, 36.0, 47.0)
0.01
0.84864
0.69231
(28.0, 38.0, 49.0)
0.1
0.66618
0.34375
(34.0, 45.0, 56.0)
0.2
0.73071
0.36000
(27.0, 36.0, 47.0)
0.01
0.68343
0.37594
(27.0, 36.0, 47.0)
0.1
0.73071
0.36000
(27.0, 36.0, 47.0)
0.2
0.84864
0.69231
(28.0, 38.0, 49.0)
0.01
0.56189
0.37594
(30.0, 42.0, 56.0)
0.1
0.84864
0.69231
(28.0, 38.0, 49.0)
0.2
0.84864
0.69231
(28.0, 38.0, 49.0)
0.01
0.66885
0.35714
(29.0, 36.0, 45.0)
0.1
0.68602
0.26738
(30.0, 39.0, 52.0)
0.2
0.71662
0.37594
(27.0, 36.0, 47.0)
0.01
0.71272
0.33750
(27.0, 36.0, 48.0)
0.1
0.84864
0.69231
(28.0, 38.0, 49.0)
0.2
0.74259
0.54135
(30.0, 40.0, 50.0)
0.01
0.71759
0.32010
(39.0, 49.0, 60.0)
0.1
0.71662
0.37594
(27.0, 36.0, 47.0)
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
degree
0.9
Skripsi
Lampiran 9 - 2
Pc
Pm
z1
z2
z3
0.6
0.2
0.84864
0.69231
(28.0, 38.0, 49.0)
0.01
0.67665
0.37594
(27.0, 36.0, 47.0)
0.1
0.73071
0.36000
(27.0, 36.0, 47.0)
0.2
0.71662
0.37594
(27.0, 36.0, 47.0)
0.7
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
Lampiran 10
Lampiran 10 - 1
Hasil Running Problem 1 FMOJSSP
===*** ITERASI AWAL ***=== == POPULASI AWAL == 0.) Kromosom : 4 3 3 5 2 3 0 4 4 4 4 3 0 2 0 1 4 0 0 1 0 2 3 2 5 5 3 1 2 1 2 1 1 5 5 5 Makespan : (96.0, 133.0, 165.0) Nilai Tujuan : (0.5007256606833795, 0.007876496534341911, 131.75) 1.) Kromosom : 4 5 3 2 1 4 5 2 1 1 4 2 2 0 1 2 4 4 0 5 4 3 3 0 2 0 3 0 3 0 1 3 5 1 5 5 Makespan : (91.0, 124.0, 156.0) Nilai Tujuan : (0.5419873245949839, 0.009765625, 123.75) 2.) Kromosom : 2 1 0 2 5 4 3 3 0 0 5 1 1 1 3 5 4 1 3 2 0 4 3 2 2 1 5 5 0 3 0 5 4 4 4 2 Makespan : (81.0, 115.0, 143.0) Nilai Tujuan : (0.4968959988408992, 0.006746626686657545, 113.5) 3.) Kromosom : 3 0 2 4 2 2 0 0 2 5 3 5 2 0 5 3 3 2 0 4 0 1 5 3 5 5 4 4 1 4 4 3 1 1 1 1 Makespan : (98.0, 136.0, 175.0) Nilai Tujuan : (0.4164371678945444, 0.013539651837524595, 136.25) 4.) Kromosom : 1 0 5 3 1 5 4 0 2 0 2 2 0 5 5 5 0 5 1 1 1 4 0 1 2 4 4 4 3 2 4 2 3 3 3 3 Makespan : (105.0, 149.0, 187.0) Nilai Tujuan : (0.38437569724605436, 0.0022399203583867164, 147.5) 5.) Kromosom : 3 1 4 5 2 2 5 5 0 4 5 4 0 0 5 2 0 2 3 1 0 1 2 3 5 2 0 3 3 1 4 3 1 4 4 1 Makespan : (84.0, 117.0, 144.0) Nilai Tujuan : (0.2613414002222901, 0.0, 115.5 6.) Kromosom : 0 4 2 4 5 0 5 0 1 5 5 2 5 4 4 4 3 2 0 1 3 3 3 4 1 3 5 1 1 1 2 3 2 0 0 2 Makespan : (96.0, 135.0, 173.0) Nilai Tujuan : (0.22568395002368488, 0.0031055900621114467, 134.75) 7.) Kromosom : 4 1 3 2 4 1 3 4 4 1 0 5 3 1 4 4 1 2 3 3 0 5 3 0 5 5 0 2 2 5 1 5 0 2 0 2 Makespan : (84.0, 121.0, 150.0) Nilai Tujuan : (0.5209907940476955, 0.04879032258064517, 119.0) 8.) Kromosom : 5 3 2 1 5 4 0 0 4 2 3 0 3 5 4 3 0 0 5 5 4 0 3 5 3 4 2 4 1 1 2 1 1 2 2 1 Makespan : (97.0, 130.0, 162.0) Nilai Tujuan : (0.36840791010542273, 0.01318681318681439, 129.75) 9.) Kromosom : 2 3 0 3 0 2 2 4 4 3 5 5 2 1 1 2 4 4 4 0 0 0 2 5 4 3 0 5 5 1 5 3 1 1 1 3 Makespan : (90.0, 130.0, 165.0) Nilai Tujuan : (0.2171491840883081, 2.7210884353756154E-4, 128.75) 10.) Kromosom : 0 1 3 2 5 1 0 0 2 2 2 0 3 1 3 4 2 4 3 5 4 5 3 2 3 1 5 5 5 1 4 4 1 0 4 0 Makespan : (90.0, 127.0, 162.0) Nilai Tujuan : (0.22840405052722557, 0.0023640661938536906, 126.5) 11.) Kromosom : 5 3 1 0 2 2 4 3 2 4 3 5 5 4 1 5 4 1 2 0 3 2 3 5 5 2 1 4 3 0 4 0 1 1 0 0 Makespan : (85.0, 117.0, 147.0) Nilai Tujuan : (0.5761586867390758, 0.09695512820512821, 116.5) 12.) Kromosom : 2 1 4 1 5 5 2 1 4 1 1 4 3 0 2 0 2 1 0 3 0 3 3 2 0 3 5 2 5 3 5 5 4 0 4 4 Makespan : (98.0, 134.0, 166.0) Nilai Tujuan : (0.4332860823671409, 0.02836134453781492, 133.0) 13.) Kromosom : 1 3 1 2 1 5 2 2 2 4 1 0 5 2 2 0 3 5 4 0 3 5 1 1 5 0 4 3 3 3 5 4 0 0 4 4 Makespan : (93.0, 131.0, 165.0) Nilai Tujuan : (0.43192614143732566, 7.012622720891998E-4, 130.0) 14.) Kromosom : 2 4 4 3 5 4 4 3 3 4 4 2 5 1 5 1 5 0 2 0 5 1 1 1 5 2 1 0 0 2 2 0 3 0 3 3 Makespan : (124.0, 176.0, 219.0) Nilai Tujuan : (0.2489966789871723, 1.8031013342948183E-4, 173.75)
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
15.) Kromosom Makespan Nilai Tujuan 16.) Kromosom Makespan Nilai Tujuan 17.) Kromosom Makespan Nilai Tujuan 18.) Kromosom Makespan Nilai Tujuan 19.) Kromosom Makespan Nilai Tujuan
: : : : : : : : : : : : : : :
Lampiran 10 - 2
213331131132444525143544002225000055 (109.0, 150.0, 189.0) (0.5156139767810681, 0.007692307692307361, 149.5) 241530302000312102221311334445555445 (96.0, 135.0, 171.0) (0.39970220785755034, 0.010943912448700834, 134.25) 105121151450030421505303453442322342 (97.0, 132.0, 168.0) (0.406334188885475, 3.885003885000462E-4, 132.25) 353055340522435413153440242011220011 (95.0, 131.0, 164.0) (0.5110994501254899, 0.005152979066023166, 130.25) 040530544405343410105511151332232222 (74.0, 111.0, 139.0) (0.5503732804430096, 0.01940700808625312, 108.75)
===*** ITERASI KE-100 ***=== 0.) Kromosom : 1 5 2 3 5 4 2 2 4 5 3 2 0 1 3 5 0 3 5 4 1 5 2 1 0 2 1 4 0 3 4 1 4 3 0 0 Makespan : (65.0, 87.0, 110.0) Nilai Tujuan : (0.9618567939996511, 0.7942176870748296, 87.25) 1.) Kromosom : 1 5 4 2 2 5 3 5 0 2 1 4 3 2 5 5 4 3 2 0 1 2 5 0 3 1 0 1 4 1 4 3 4 0 0 3 Makespan : (65.0, 87.0, 110.0) Nilai Tujuan : (0.9618567939996511, 0.7942176870748296, 87.25) 2.) Kromosom : 1 5 4 2 2 5 3 5 0 2 1 4 3 2 5 5 4 3 2 0 1 2 5 0 3 1 0 1 4 1 4 3 4 0 0 3 Makespan : (65.0, 87.0, 110.0) Nilai Tujuan : (0.9618567939996511, 0.7942176870748296, 87.25) 3.) Kromosom : 1 5 4 2 2 5 5 2 3 4 3 2 5 1 0 5 4 3 2 0 1 2 5 0 3 1 0 1 4 1 4 3 4 0 0 3 Makespan : (65.0, 87.0, 110.0) Nilai Tujuan : (0.9618567939996511, 0.7942176870748296, 87.25) 4.) Kromosom : 1 5 4 2 2 5 3 5 0 2 1 4 3 2 5 5 4 3 2 0 1 2 5 0 3 1 0 1 4 1 4 3 4 0 0 3 Makespan : (65.0, 87.0, 110.0) Nilai Tujuan : (0.9618567939996511, 0.7942176870748296, 87.25) 5.) Kromosom : 1 5 4 2 2 5 3 5 0 2 1 4 3 5 4 2 2 5 3 5 0 2 1 4 1 0 1 3 0 1 4 3 4 0 0 3 Makespan : (65.0, 87.0, 110.0) Nilai Tujuan : (0.9618567939996511, 0.7942176870748296, 87.25) 6.) Kromosom : 1 5 4 2 2 5 3 5 0 2 1 4 3 2 2 3 4 5 5 0 1 2 5 0 3 1 0 1 4 1 4 3 4 0 0 3 Makespan : (65.0, 87.0, 110.0) Nilai Tujuan : (0.9618567939996511, 0.7942176870748296, 87.25) 7.) Kromosom : 1 5 4 2 2 5 3 5 0 2 1 4 3 2 5 5 4 3 2 0 1 2 5 0 3 1 0 1 4 1 4 3 4 0 0 3 Makespan : (65.0, 87.0, 110.0) Nilai Tujuan : (0.9618567939996511, 0.7942176870748296, 87.25) 8.) Kromosom : 1 5 4 2 2 5 5 2 3 4 3 2 5 1 0 2 3 5 4 2 1 0 5 0 3 1 0 1 4 1 4 3 4 0 0 3 Makespan : (65.0, 87.0, 110.0) Nilai Tujuan : (0.9618567939996511, 0.7942176870748296, 87.25) 9.) Kromosom : 1 5 4 2 2 5 3 5 0 2 1 4 3 2 2 3 4 5 5 0 1 2 5 0 3 1 0 1 4 1 4 3 4 0 0 3 Makespan : (65.0, 87.0, 110.0) Nilai Tujuan : (0.9618567939996511, 0.7942176870748296, 87.25) 10.) Kromosom : 1 5 4 2 2 5 3 5 0 2 1 4 3 5 4 2 2 5 3 5 0 2 1 4 1 0 1 3 0 1 4 3 4 0 0 3 Makespan : (65.0, 87.0, 110.0) Nilai Tujuan : (0.9618567939996511, 0.7942176870748296, 87.25)
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
11.) Kromosom Makespan Nilai Tujuan 12.) Kromosom Makespan Nilai Tujuan 13.) Kromosom Makespan Nilai Tujuan 14.) Kromosom Makespan Nilai Tujuan 15.) Kromosom Makespan Nilai Tujuan 16.) Kromosom Makespan Nilai Tujuan 17.) Kromosom Makespan Nilai Tujuan 18.) Kromosom Makespan Nilai Tujuan 19.) Kromosom Makespan Nilai Tujuan
: : : : : : : : : : : : : : : : : : : : : : : : : : :
Lampiran 10 - 3
154225523350214325421050310141434003 (65.0, 87.0, 110.0) (0.9618567939996511, 0.7942176870748296, 87.25) 154225325102342554320150310141434003 (65.0, 87.0, 110.0) (0.9618567939996511, 0.7942176870748296, 87.25) 152425350214322345501250310141434003 (65.0, 87.0, 110.0) (0.9618567939996511, 0.7942176870748296, 87.25) 154225325235021434520150310141434003 (65.0, 87.0, 110.0) (0.9618567939996511, 0.7942176870748296, 87.25) 154225352435021435201250310141434003 (65.0, 87.0, 110.0) (0.9618567939996511, 0.7942176870748296, 87.25) 154222553350214325421050310141434003 (65.0, 87.0, 110.0) (0.9618567939996511, 0.7942176870748296, 87.25) 154225523350012452341250310141434003 (65.0, 87.0, 110.0) (0.9618567939996511, 0.7942176870748296, 87.25) 154225325235014354225100310141434003 (65.0, 87.0, 110.0) (0.9618567939996511, 0.7942176870748296, 87.25) 154225350214325543201250310141434003 (65.0, 87.0, 110.0) (0.9618567939996511, 0.7942176870748296, 87.25)
---+ SOLUSI +--Urutan Job :
152354224532013503541521021403414300
Rata-rata AI Minimum AI Makespan
Skripsi
= 0.9618567939996511 = 0.7942176870748296 = (65.0, 87.0, 110.0)
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
Lampiran 11
Lampiran 11 - 1
Hasil Running Problem 2 FMOJSSP
===*** ITERASI AWAL ***=== == POPULASI AWAL == 0.) Kromosom : 4 5 1 0 1 4 0 5 3 1 4 3 2 2 3 1 1 3 1 5 4 5 5 0 0 3 4 3 4 2 5 2 2 0 0 2 Makespan : (84.0, 117.0, 144.0) Nilai Tujuan : (0.19880395608452947, 0.005247813411078634, 115.5) 1.) Kromosom : 5 3 2 5 3 1 3 5 1 1 3 0 3 0 2 5 5 1 0 2 4 5 3 4 4 0 0 2 4 1 0 2 1 2 4 4 Makespan : (87.0, 117.0, 142.0) Nilai Tujuan : (0.17215714538005164, 0.038571428571431136, 115.75) 2.) Kromosom : 1 2 4 5 2 2 1 2 0 4 0 2 5 2 4 3 0 5 1 0 5 1 4 0 1 1 3 5 4 0 5 4 3 3 3 3 Makespan : (89.0, 121.0, 148.0) Nilai Tujuan : (0.45227070562607224, 0.06288819875776572, 119.75) 3.) Kromosom : 0 3 3 3 3 5 3 4 3 5 2 5 5 1 1 1 1 4 0 5 5 2 2 4 4 4 0 1 2 4 1 0 2 2 0 0 Makespan : (108.0, 147.0, 181.0) Nilai Tujuan : (0.32189489532262644, 0.0016708437761055377, 145.75) 4.) Kromosom : 5 2 0 0 5 2 4 4 2 4 4 0 0 4 5 4 3 5 1 1 1 3 5 5 2 2 3 1 3 3 3 2 1 0 1 0 Makespan : (94.0, 129.0, 164.0) Nilai Tujuan : (0.28989478863205126, 0.012244897959183675, 129.0) 5.) Kromosom : 3 2 4 4 3 5 1 3 0 5 2 4 3 5 2 5 1 3 5 4 0 3 5 0 0 1 4 1 0 4 2 0 2 1 1 2 Makespan : (69.0, 97.0, 125.0) Nilai Tujuan : (0.5603327293387593, 0.07971698113207525, 97.0 6.) Kromosom : 2 3 4 4 5 0 0 1 4 0 5 0 4 0 0 5 2 1 3 4 4 1 1 3 5 1 2 3 2 3 2 5 1 3 5 2 Makespan : (85.0, 119.0, 149.0) Nilai Tujuan : (0.37183020017143664, 0.020692567567570243, 118.0) 7.) Kromosom : 3 1 4 1 3 4 5 4 5 1 0 3 2 3 2 4 2 0 2 1 1 3 0 2 1 0 0 5 0 5 4 2 3 4 5 5 Makespan : (88.0, 124.0, 154.0) Nilai Tujuan : (0.27379856573916067, 0.03885003885003926, 122.5) Nilai 8.) Kromosom : 2 1 3 1 1 5 4 3 2 1 0 5 1 3 5 1 5 2 5 4 5 2 2 2 4 0 3 3 4 3 4 4 0 0 0 0 Makespan : (92.0, 128.0, 156.0) Nilai Tujuan : (0.4374809506962953, 0.0058139534883731815, 126.0) 9.) Kromosom : 2 0 3 3 4 2 3 0 1 0 3 0 3 1 0 4 3 2 0 4 4 1 4 5 5 2 5 1 5 1 5 4 2 5 2 1 Makespan : (83.0, 118.0, 150.0) Nilai Tujuan : (0.5234961869799603, 0.010725010725008186, 117.25) 10.) Kromosom : 1 0 4 2 0 3 0 1 2 2 5 4 3 5 5 4 3 5 2 5 4 3 0 4 4 2 2 1 1 3 3 0 1 0 5 1 Makespan : (103.0, 135.0, 167.0) Nilai Tujuan : (0.14591256402736238, 0.00206398348813255, 135.0) 11.) Kromosom : 5 1 3 2 5 0 1 3 0 3 3 3 4 1 4 0 4 0 2 0 1 3 1 0 2 2 5 1 2 2 4 5 4 5 4 5 Makespan : (94.0, 128.0, 159.0) Nilai Tujuan : (0.3243469967280711, 0.03361344537815476, 127.25) 12.) Kromosom : 4 4 3 5 4 4 1 0 1 2 2 2 2 5 0 2 2 1 4 4 3 3 1 5 0 1 3 3 0 3 0 1 0 5 5 5 Makespan : (106.0, 142.0, 173.0) Nilai Tujuan : (0.2905230747296799, 0.033498759305210464, 140.75) 13.) Kromosom : 3 2 2 5 1 2 0 3 2 5 2 1 3 5 2 0 4 3 4 3 0 0 4 4 5 3 0 5 1 5 4 0 1 1 1 4 Makespan : (94.0, 125.0, 156.0) Nilai Tujuan : (0.1989224648556708, 0.006114130434782609, 125.0) 14.) Kromosom : 5 2 5 5 5 1 4 4 0 0 1 2 3 5 5 1 2 0 3 2 2 2 4 0 3 3 4 4 0 0 4 3 1 1 3 1 Makespan : (104.0, 143.0, 181.0) Nilai Tujuan : (0.3502660220991025, 0.009100837277029044, 142.75)
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
15.) Kromosom Makespan Nilai Tujuan 16.) Kromosom Makespan Nilai Tujuan 17.) Kromosom Makespan Nilai Tujuan 18.) Kromosom Makespan Nilai Tujuan 19.) Kromosom Makespan Nilai Tujuan
: : : : : : : : : : : : : : :
Lampiran 11 - 2
500250345103355432540132230411121244 (95.0, 130.0, 160.0) (0.1890538170743087, 3.7664783427476204E-4, 128.75) 440041433451130143315522320512002255 (108.0, 147.0, 179.0) (0.24096801537535809, 0.0062160062160043755, 145.25) 440421005545040051152253133411222333 (109.0, 153.0, 191.0) (0.24612425132805751, 0.03819444444444455, 151.5) 141305441505413152000333154022425322 (101.0, 138.0, 172.0) (0.377243657336318, 0.015216068167986286, 137.25) 340442151233341213253255254405100100 (105.0, 144.0, 184.0) (0.11922984262671182, 0.006818181818182261, 144.25)
===*** ITERASI KE-100 ***=== 0.) Kromosom : 3 2 2 5 3 0 1 5 3 4 2 4 5 2 3 4 1 1 3 0 5 4 3 5 1 0 0 4 5 0 1 0 2 1 2 4 Makespan : (54.0, 73.0, 89.0) Nilai Tujuan : (0.9758761282290692, 0.9117647058823529, 72.25) 1.) Kromosom : 3 2 4 5 3 0 1 5 3 2 2 4 5 2 3 4 1 1 3 0 5 4 3 5 1 0 0 4 5 0 1 0 2 1 2 4 Makespan : (54.0, 73.0, 89.0) Nilai Tujuan : (0.9758761282290692, 0.9117647058823529, 72.25) 2.) Kromosom : 3 5 3 4 2 0 1 5 3 2 2 4 5 2 3 4 1 1 3 0 5 4 3 5 1 0 0 4 5 0 1 0 2 1 2 4 Makespan : (54.0, 73.0, 89.0) Nilai Tujuan : (0.9758761282290692, 0.9117647058823529, 72.25) 3.) Kromosom : 3 5 3 2 2 0 1 5 3 4 5 2 3 4 1 2 4 3 5 0 1 5 4 3 5 1 0 0 4 0 1 0 2 1 2 4 Makespan : (54.0, 73.0, 89.0) Nilai Tujuan : (0.9758761282290692, 0.9117647058823529, 72.25) 4.) Kromosom : 3 5 3 2 2 0 4 1 2 4 1 3 5 3 5 2 4 3 5 0 1 5 4 3 5 1 0 0 4 0 1 0 2 1 2 4 Makespan : (54.0, 73.0, 89.0) Nilai Tujuan : (0.9758761282290692, 0.9117647058823529, 72.25) 5.) Kromosom : 3 2 4 5 3 0 1 5 3 2 2 4 5 2 3 4 1 1 3 0 5 4 3 5 1 0 0 4 5 0 1 0 2 1 2 4 Makespan : (54.0, 73.0, 89.0) Nilai Tujuan : (0.9758761282290692, 0.9117647058823529, 72.25) 6.) Kromosom : 3 5 3 4 2 0 1 5 3 2 2 4 5 2 3 4 1 1 3 0 5 4 3 5 1 0 0 4 5 0 1 0 2 1 2 4 Makespan : (54.0, 73.0, 89.0) Nilai Tujuan : (0.9758761282290692, 0.9117647058823529, 72.25) 7.) Kromosom : 3 5 3 2 2 0 5 3 4 1 5 3 4 1 2 2 4 3 5 0 1 5 4 3 5 1 0 0 4 0 1 0 2 1 2 4 Makespan : (54.0, 73.0, 89.0) Nilai Tujuan : (0.9758761282290692, 0.9117647058823529, 72.25) 8.) Kromosom : 3 5 3 4 2 0 1 5 3 2 2 4 5 2 3 4 1 1 3 0 5 4 5 3 0 1 5 4 0 0 1 0 2 1 2 4 Makespan : (54.0, 73.0, 89.0) Nilai Tujuan : (0.9758761282290692, 0.9117647058823529, 72.25) 9.) Kromosom : 3 5 3 4 2 0 1 5 3 2 2 4 5 2 3 4 1 1 3 0 5 4 3 5 1 0 0 4 5 0 1 0 2 2 1 4 Makespan : (54.0, 73.0, 89.0) Nilai Tujuan : (0.9758761282290692, 0.9117647058823529, 72.25) 10.) Kromosom : 3 5 4 3 5 1 0 2 3 2 2 4 5 2 3 4 1 1 3 0 5 4 5 3 0 1 5 4 0 0 1 0 2 1 2 4 Makespan : (54.0, 73.0, 89.0) Nilai Tujuan : (0.9758761282290692, 0.9117647058823529, 72.25)
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
11.) Kromosom Makespan Nilai Tujuan 12.) Kromosom Makespan Nilai Tujuan 13.) Kromosom Makespan Nilai Tujuan 14.) Kromosom Makespan Nilai Tujuan 15.) Kromosom Makespan Nilai Tujuan 16.) Kromosom Makespan Nilai Tujuan 17.) Kromosom Makespan Nilai Tujuan 18.) Kromosom Makespan Nilai Tujuan 19.) Kromosom Makespan Nilai Tujuan
: : : : : : : : : : : : : : : : : : : : : : : : : : :
Lampiran 11 - 3
352452310324523411305435100450102124 (54.0, 73.0, 89.0) (0.9758761282290692, 0.9117647058823529, 72.25) 354351023245322411305453015400102124 (54.0, 73.0, 89.0) (0.9758761282290692, 0.9117647058823529, 72.25) 354351022345322411305453015400102124 (54.0, 73.0, 89.0) (0.9758761282290692, 0.9117647058823529, 72.25) 354351023224523411305453015400102124 (54.0, 73.0, 89.0) (0.9758761282290692, 0.9117647058823529, 72.25) 354351023245322411305453015400120124 (54.0, 73.0, 89.0) (0.9758761282290692, 0.9117647058823529, 72.25) 353420153224523411305435100450102124 (54.0, 73.0, 89.0) (0.9758761282290692, 0.9117647058823529, 72.25) 345351023245322411305435100450102124 (54.0, 73.0, 89.0) (0.9758761282290692, 0.9117647058823529, 72.25) 353510223452341243501543510040102124 (54.0, 73.0, 89.0) (0.9758761282290692, 0.9117647058823529, 72.25) 353015223452341243501543510040102124 (54.0, 73.0, 89.0) (0.9758761282290692, 0.9117647058823529, 72.25)
---+ SOLUSI +--Urutan Job : 322530153424523411305435100450102124 Rata-rata AI = 0.9758761282290692 Minimum AI = 0.9117647058823529 Makespan = (54.0, 73.0, 89.0)
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
Lampiran 12
Lampiran 12 - 1
Hasil Running Problem 3 FMOJSSP
===*** ITERASI AWAL ***=== == POPULASI AWAL == 0.) Kromosom : 1 0 5 4 5 2 2 4 0 3 5 4 2 0 4 5 4 5 2 3 0 1 5 3 2 2 3 4 1 0 0 1 3 1 3 1 Makespan : (38.0, 50.0, 68.0) Nilai Tujuan : (0.27169828795215795, 0.007843137254902864, 51.5) 1.) Kromosom : 0 5 4 3 5 5 3 5 0 5 2 0 3 1 0 5 0 3 0 2 3 3 4 2 1 2 4 2 4 1 1 1 4 4 1 2 Makespan : (50.0, 66.0, 83.0) Nilai Tujuan : (0.5019810576008656, 0.05144032921810622, 66.25) 2.) Kromosom : 1 2 3 1 2 5 1 4 0 0 1 3 4 5 2 3 4 4 3 0 4 0 2 4 2 5 1 5 1 2 0 3 5 0 3 5 Makespan : (35.0, 49.0, 70.0) Nilai Tujuan : (0.17598660468252014, 0.0072595281306716795, 50.75) 3.) Kromosom : 0 2 4 0 4 1 0 5 1 3 4 2 0 2 2 1 1 3 1 5 0 3 3 5 3 0 5 4 3 1 2 5 2 4 4 5 Makespan : (44.0, 58.0, 79.0) Nilai Tujuan : (0.09474677369414221, 0.0, 59.75) 4.) Kromosom : 1 4 4 1 2 1 2 1 1 0 3 4 4 0 4 2 2 1 2 5 0 2 0 0 3 4 0 3 3 5 5 3 3 5 5 5 Makespan : (44.0, 62.0, 83.0) Nilai Tujuan : (0.20415741330596404, 0.001114827201783158, 62.75) 5.) Kromosom : 4 2 3 0 1 5 1 0 5 5 4 3 2 4 3 2 4 0 2 4 4 2 5 3 3 2 3 0 1 5 0 0 1 5 1 1 Makespan : (50.0, 65.0, 87.0) Nilai Tujuan : (0.20050372962524696, 0.001225490196078887, 66.75) 6.) Kromosom : 2 2 4 3 1 4 0 2 5 3 2 0 5 4 3 1 2 1 1 1 1 4 2 3 0 5 3 5 0 5 4 3 5 0 0 4 Makespan : (39.0, 52.0, 68.0) Nilai Tujuan : (0.09127476238365213, 0.0, 52.75) 7.) Kromosom : 5 2 1 0 4 4 1 5 0 2 1 3 4 4 0 1 4 5 0 1 0 5 1 3 2 3 2 2 3 3 4 3 0 2 5 5 Makespan : (54.0, 71.0, 90.0) Nilai Tujuan : (0.2754797319385422, 0.10227272727272663, 71.5) 8.) Kromosom : 0 3 5 5 5 3 2 1 2 3 2 4 0 4 3 5 0 0 0 1 1 3 2 5 2 2 3 1 4 4 1 4 4 5 0 1 Makespan : (43.0, 55.0, 67.0) Nilai Tujuan : (0.07530012762547399, 0.022058823529411162, 55.0) 9.) Kromosom : 1 0 5 0 1 1 1 2 2 2 1 0 3 1 3 4 4 4 4 3 5 2 4 5 3 4 5 0 3 0 2 0 3 2 5 5 Makespan : (46.0, 65.0, 85.0) Nilai Tujuan : (0.1923639596812077, 0.0010683760683764813, 65.25) 10.) Kromosom : 0 3 4 5 3 3 5 5 3 1 3 4 2 3 5 2 4 0 1 4 5 2 4 1 5 1 1 0 0 1 0 4 2 0 2 2 Makespan : (42.0, 58.0, 76.0) Nilai Tujuan : (0.3939678649237475, 0.0013888888888894052, 58.5) 11.) Kromosom : 0 1 3 4 1 4 1 4 0 3 3 1 2 0 5 3 2 1 5 5 3 1 5 5 3 4 4 5 4 2 2 0 2 0 2 0 Makespan : (43.0, 60.0, 82.0) Nilai Tujuan : (0.21028906162146013, 0.0010395010395008726, 61.25) 12.) Kromosom : 3 0 1 2 2 1 5 0 0 0 4 3 1 0 4 2 2 3 2 0 4 5 2 3 1 1 3 4 5 3 4 5 4 1 5 5 Makespan : (41.0, 58.0, 82.0) Nilai Tujuan : (0.17398716423106653, 0.0, 59.75) 13.) Kromosom : 1 2 2 4 4 1 0 4 4 2 0 3 1 2 5 0 0 2 1 3 0 4 5 0 3 5 4 2 5 3 1 5 3 1 5 3 Makespan : (43.0, 58.0, 75.0) Nilai Tujuan : (0.11623294323009968, 0.002450980392155778, 58.5) 14.) Kromosom : 3 5 2 0 2 5 3 2 0 1 4 5 2 4 2 4 1 2 5 5 3 3 1 3 5 3 1 0 1 4 4 1 0 0 4 0 Makespan : (38.0, 52.0, 65.0) Nilai Tujuan : (0.36972390440814146, 0.00181488203266839, 51.75)
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
15.) Kromosom Makespan Nilai Tujuan 16.) Kromosom Makespan Nilai Tujuan 17.) Kromosom Makespan Nilai Tujuan 18.) Kromosom Makespan Nilai Tujuan 19.) Kromosom Makespan Nilai Tujuan
: : : : : : : : : : : : : : :
Lampiran 12 - 2
033550155255244031424123113430122400 (42.0, 58.0, 74.0) (0.19607503607503626, 0.0, 58.0) 343422211100332202153101455030555444 (42.0, 56.0, 71.0) (0.4215251829709505, 0.08892921960072689, 56.25) 354342515450235044520341320032201111 (50.0, 67.0, 87.0) (0.29628939784426556, 0.007054673721340454, 67.75) 230423015544202100420241453533315115 (46.0, 62.0, 86.0) (0.09248662217412201, 0.0011904761904768435, 64.0) 412105504155220002503544114432233133 (41.0, 57.0, 79.0) (0.31191811398048497, 0.0010964912280706039, 58.5)
===*** ITERASI KE-100 ***=== 0.) Kromosom : 3 2 2 1 1 4 0 5 3 3 3 3 2 2 2 1 2 1 4 4 0 4 5 0 1 3 4 5 1 0 0 4 5 0 5 5 Makespan : (28.0, 38.0, 49.0) Nilai Tujuan : (0.848637745696569, 0.6923076923076912, 38.25) 1.) Kromosom : 3 2 2 1 1 4 0 5 3 3 3 3 2 2 2 1 2 1 4 4 0 4 5 1 0 3 4 5 1 0 0 4 5 0 5 5 Makespan : (28.0, 38.0, 49.0) Nilai Tujuan : (0.848637745696569, 0.6923076923076912, 38.25) 2.) Kromosom : 3 2 2 1 1 4 0 5 3 3 3 3 2 2 2 1 1 2 4 4 0 4 5 0 1 3 4 5 1 0 0 4 5 0 5 5 Makespan : (28.0, 38.0, 49.0) Nilai Tujuan : (0.848637745696569, 0.6923076923076912, 38.25) 3.) Kromosom : 3 2 2 1 2 1 4 0 5 3 3 3 3 2 2 2 1 1 4 4 0 4 5 1 0 3 4 5 1 0 0 4 5 0 5 5 Makespan : (28.0, 38.0, 49.0) Nilai Tujuan : (0.848637745696569, 0.6923076923076912, 38.25) 4.) Kromosom : 3 2 2 1 1 4 0 5 3 3 3 3 2 2 2 1 2 1 4 4 0 4 5 1 0 3 4 5 1 0 0 4 5 0 5 5 Makespan : (28.0, 38.0, 49.0) Nilai Tujuan : (0.848637745696569, 0.6923076923076912, 38.25) 5.) Kromosom : 3 2 2 1 1 4 0 5 3 3 3 3 2 2 2 2 1 1 4 4 0 4 5 0 1 3 4 5 1 0 0 4 5 0 5 5 Makespan : (28.0, 38.0, 49.0) Nilai Tujuan : (0.848637745696569, 0.6923076923076912, 38.25) 6.) Kromosom : 3 2 2 1 2 1 4 0 5 3 3 3 3 2 2 2 1 1 4 4 0 4 5 1 0 3 4 5 1 0 0 4 5 0 5 5 Makespan : (28.0, 38.0, 49.0) Nilai Tujuan : (0.848637745696569, 0.6923076923076912, 38.25) 7.) Kromosom : 3 2 2 1 1 4 0 5 3 3 3 3 2 2 2 1 2 1 4 4 0 4 5 1 0 3 4 5 1 0 0 4 5 0 5 5 : (28.0, 38.0, 49.0) Makespan Nilai Tujuan : (0.848637745696569, 0.6923076923076912, 38.25) 8.) Kromosom : 3 2 2 1 2 1 4 0 5 3 3 3 3 2 2 2 1 1 4 4 0 4 5 1 0 3 4 5 1 0 0 4 5 0 5 5 Makespan : (28.0, 38.0, 49.0) Nilai Tujuan : (0.848637745696569, 0.6923076923076912, 38.25) 9.) Kromosom : 3 2 2 1 2 1 4 0 5 3 3 3 3 2 2 2 1 1 4 4 0 4 5 1 0 4 5 0 1 3 0 4 5 0 5 5 Makespan : (28.0, 38.0, 49.0) Nilai Tujuan : (0.848637745696569, 0.6923076923076912, 38.25) 10.) Kromosom : 3 2 2 1 1 4 0 5 3 3 3 3 2 2 2 1 1 2 4 4 4 0 5 0 1 3 4 5 1 0 0 4 5 0 5 5 Makespan : (28.0, 38.0, 49.0) Nilai Tujuan : (0.848637745696569, 0.6923076923076912, 38.25)
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
11.) Kromosom : Makespan : Nilai Tujuan : 12.) Kromosom : Makespan : Nilai Tujuan : 13.) Kromosom : Makespan : Nilai Tujuan : 14.) Kromosom : Makespan : Nilai Tujuan : 15.) Kromosom : Makespan : Nilai Tujuan : 16.) Kromosom : Makespan : Nilai Tujuan : 17.) Kromosom : Makespan : Nilai Tujuan : 18.) Kromosom : Makespan : Nilai Tujuan : 19.) Kromosom : Makespan : Nilai Tujuan :
Lampiran 12 - 3
322211405333322211440451034510045055 (28.0, 38.0, 49.0) (0.848637745696569, 0.6923076923076912, 38.25) 322114053333222114404501215430045055 (28.0, 38.0, 49.0) (0.848637745696569, 0.6923076923076912, 38.25) 322121333145103422240451034510045055 (28.0, 38.0, 49.0) (0.848637745696569, 0.6923076923076912, 38.25) 322121405333322211440451034510045055 (28.0, 38.0, 49.0) (0.848637745696569, 0.6923076923076912, 38.25) 322114053233322211440451034510045055 (28.0, 38.0, 49.0) (0.848637745696569, 0.6923076923076912, 38.25) 322121405333322211444050134510045055 (28.0, 38.0, 49.0) (0.848637745696569, 0.6923076923076912, 38.25) 322121405333322211440451034510045055 (28.0, 38.0, 49.0) (0.848637745696569, 0.6923076923076912, 38.25) 322114053333222112444050134510045055 (28.0, 38.0, 49.0) (0.848637745696569, 0.6923076923076912, 38.25) 322211405333322211440451034510045055 (28.0, 38.0, 49.0) (0.848637745696569, 0.6923076923076912, 38.25)
---+ SOLUSI +--Urutan Job : 322114053333222121440450134510045055 Rata-rata AI = 0.848637745696569 Minimum AI = 0.6923076923076912 Makespan = (28.0, 38.0, 49.0)
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
Lampiran 13
Lampiran 13 - 1
Output Program FMOJSSP Menggunakan GA
1. Input Awal (Tampilan Awal)
2. Input Parameter
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa
ADLN Perpustakaan Universitas Airlangga
Lampiran 13 - 2
3. Hasil (Tampilan Akhir)
4. Help Content
Skripsi
Penerapan Fuzzy Multi-Objective pada Job Shop Scheduling Menggunakan Genetic Algorithm
Marisa