IMPLEMENTASI ALGORITMA GENETIKA UNTUK MASALAH PENJADWALAN JOB-SHOP

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

IMPLEMENTASI ALGORITMA GENETIKA UNTUK MASALAH PENJADWALAN JOB-SHOP Skripsi

Diajukan untuk Memenuhi Salah Satu Syarat Memperoleh Gelar Sarjana Sains Program Studi Matematika

Oleh: R. Altoria Mavida NIM : 02 3114 003

PROGRAM STUDI MATEMATIKA JURUSAN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SANATA DHARMA YOGYAKARTA 2007




Dengan penuh kasih dan ucapan syukur Skripsi ini Kupersembahkan untuk: Bapa di Surga juru selamatku, Bunda Maria pelindung, pengharapan, dan penghiburanku Bapakku Antonius Karjiman (Alm) yang sudah tenang di alam surga Ibuku Agnes Sarinten Kakak dan adikku tersayang: E. Dony Sopranita dan Fredeswinda Ferina Yesilvia Teman-teman angkatan ‘02 Almamaterku Sanata Dharma

iv


“ Ia membuat segala sesuatu indah pada waktunya, bahkan Ia memberikan kekekalan dalam hati kita, Dialah yang dapat melakukan jauh lebih banyak daripada yang kita pikirkan atau doakan” (Pengkhotbah 3:11)

Berjuanglah dalam segala hal, sertakan Tuhan di dalamnya dan percayalah apa yang terjadi semuanya karena Tuhan

“Serahkanlah segala kekuatiranmu kepadaNya, sebab Ia yang memelihara kamu” (1 Petrus 5:7)

v



ABSTRAK

Masalah penjadwalan Job-Shop (JSP) merupakan permasalahan optimasi yang paling sulit dan termasuk masalah NP (Non-deterministic Polynomial). Bila penjadwalan dilakukan secara manual dan mencoba seluruh kemungkinan maka membutuhkan waktu yang lama. Karena menggunakan cara manual membutuhkan waktu yang cukup lama, maka metode heuristik merupakan solusi alternative yang dapat digunakan. Algoritma genetika merupakan suatu metode penyelesaian masalah yang tergolong heuristik. Dengan menggunakan Algoritma Genetika (AG) maka dapat dihasilkan solusi yang baik dengan waktu yang singkat. Pada penelitian ini, pembentukan generasi-generasi baru dilakukan dengan persilangan / crossover menggunakan metode Precedence Preservative Crossover (PPX) dan mutasi menggunakan job-pair exchange mutation. Pemilihan kromosom untuk dilakukan regenerasi pada proses persilangan / crossover dipilih dua kromosom yang mempunyai fitnes terbaik dan untuk proses mutasi dipilih satu kromosom yang mempunyai fitnes terburuk. Diharapkan algoritma genetika memperoleh jadwal optimal (makespan minimum) pada masalah penjadwalan Job-Shop. Dari percobaan, tampak bahwa untuk mendapatkan solusi optimal terjadi pada Pcross = 0.5 dan Pmut = 0.09. Hasil tersebut tidak mutlak mengingat bahwa prinsip dasar dari Algoritma Genetika (AG) adalah menggunakan pemilihan secara acak / random.

vii


ABSTRACT

Job-Shop Scheduling Problem (JSP) is one of the most difficult problems, as it is classified an NP-complete one. If scheduling is conducted as manual and try all possibilities, hence is requires a lot of time. Because by manual takes a lot of time, therefore, by using heuristic method is the alternative solution to use. Genetic algorithm is a method to solve problem that pertained heuristic. By using Genetic Algorithm (GA), good solutions can be solved in a quickly time. In this research, the forming of new generations conducted by the crossover using the method of Precedence Preservative Crossover (PPX) and mutation using the job-pair exchange mutation. Selection of chromosome to be conducted by regeneration at process of crossover selected by two chromosomes having best fitness and to process mutation selected by one chromosome that having one worst fitness. By expectation of genetic algorithm is obtained the optimal schedule (minimum makespan) on Job-Shop scheduling problem. According to the experiments, it is visible to get the optimal solution that is done to Pcross = 0.5 and Pmut = 0.09. The result is not absolute because of the base principle of genetic algorithm (GA) is using the random selection.

viii


KATA PENGANTAR

Puji syukur kepada Bapa di Surga dan Bunda Maria yang memberikan kasih-Nya dan melimpahkan karunia-Nya, memberikan kekuatan, menuntun dan memberkati penulis secara luar biasa sehingga penulisan skripsi ini dapat diselesaikan. Skripsi ini disusun untuk memenuhi salah satu syarat memperoleh gelar Sarjana Sains di Program Studi Matematika Jurusan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Sanata Dharma Yogyakarta. Penulis dalam menyusun skripsi ini dari awal sampai akhir mendapat dukungan dan bantuan dari berbagai pihak. Pada kesempatan ini penulis menyampaikan ucapan terima kasih yang sebesar-besarnya kepada: 1. Bapak Ir. Ig. Aris Dwiatmoko, M.Sc selaku Dekan Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Sanata Dharma Yogyakarta dan dosen pembimbing akademik. 2. Bapak Drs. HJ Haris Sriwindono, M.Kom selaku Dosen Pembimbing yang dengan kesabarannya telah banyak membimbing dan memberikan petunjuk dalam penyusunan skripsi ini. 3. Bapak YG. Hartono, S.Si.,M.Sc dan Bapak St. Eko Parmadi, S.Si.,M.Kom sebagai dosen penguji atas diskusi dan masukan-masukannya untuk skripsi ini. 4. Bapak dan Ibu dosen serta staf karyawan terima kasih untuk bimbingan dan bantuan serta sabar mendidik penulis sampai akhir semester.

ix


5. Bapak ku yang telah tenang di alam surga dan Ibu ku dengan penuh kasih setia dan sabar untuk mendidik, memberi dorongan semangat, pengertian, cinta dan doa serta biaya pada penulis selama menempuh studi. 6. Kakak dan adikku (Mbak Nita & Mas Andre dan Dek Fredes) terima kasih untuk cinta, doa, dukungan, pengertian dan motivasinya. 7. Seseorang

yang sampai saat ini masih ada di hatiku dan yang sebagai

motivasiku, terima kasih karena kamu aku bisa seperti ini. 8. Keluarga besarku di Lampung dan di Yogyakarta terima kasih untuk doanya. 9. Yoan terima kasih untuk doa, dukungan, motivasi dan perhatiannya (habis ini kita bakal ketemu koq, moga kita gak cooling down ya!!). 10. Sahabat-sahabatku: Dian, Citra, Monic, Margareta, Acoy, Danu, Made, Indra (wa2n), Dede, Mervin, Lingsia, Rima, Yuli, Kak Ike, Friska, Anto, Danang terima kasih buat persahabatan, cinta, perhatian dan dukungannya, Andre yang pernah memberi motivasi, dukungan, dan setia mendengar keluhanku. 11. Teman-teman seperjuanganku di Matematika 2002: Preezk, Archy, Ika, Lenta, Debby, Lia, Sari, Aan, Tato, Bani, Lili, Taim, Ijup, Markus, Felix, Retno, Galih, Aning, Desy, Rita, Wuri, Deon, Cheea, Nunung, Dani, Palma, dan Asih. Kakak-kakak dan adik-adik angkatan terima kasih untuk bantuan dan keramahannya. 12. Yayank’s Family terima kasih untuk dukungan dan bantuan. Mas guntur terima kasih atas semua bantuannya dan sering dikasih gretongan hingga aku bisa PP Jogja-Metro semaunya sendiri.

x


13. Teman-teman kostku: Endra+Dika, Mbak Dian, Mbak Think, Mas Ardian (terima kasih untuk kostnya), Mas Doyo, Lulu, Rani makasih buat kebersamaan dan keceriaan kita selama ini. 14. Teman seperjuanganku dalam bimbingan (Marlen SoeMonroo) terimakasih atas semua bantuan, kerjasama dan kesabarannya. 15. Teman-teman KKN ku: Albert, Alfina, Dek Ciciel, Mbak Reni, Dek Gu2n, Obeth, Nana, dan Tyo thanks ya atas perhatian dan dukungannya. 16. Terima kasih juga untuk BE-FA 8397 yang setia menemani kemanapun aku pergi untuk mencari inspirasi dan komputer ku yang sering bermasalah terima kasih karena kamu tugas-tugas dan skripsi ku bisa kelar. 17. Semua pihak yang telah turut membantu hingga selesainya skripsi ini yang tidak dapat disebutkan satu persatu.

Semoga kasih Tuhan selalu menyertai semua pihak yang telah membantu dalam penyusunan skripsi ini. Penulis menyadari sepenuhnya bahwa penyusunan ini jauh dari sempurna, untuk itu saran dan kritik yang sifatnya membangun penulis menerima dengan senang hati demi perbaikan skripsi ini. Penulis berharap semoga skripsi ini dapat memberikan manfaat bagi setiap orang dan semua pihak.

Yogyakarta,

Juli 2007

Hormat Penulis

R. Altoria Mavida

xi


DAFTAR ISI

Halaman HALAMAN JUDUL.....................................................................................

i

HALAMAN PERSETUJUAN PEMBIMBING ...........................................

ii

HALAMAN PENGESAHAN.......................................................................

iii

HALAMAN PERSEMBAHAN ...................................................................

iv

HALAMAN MOTTO ...................................................................................

v

PERNYATAAN KEASLIAN KARYA .......................................................

vi

ABSTRAK ....................................................................................................

vii

ABSTRACT..................................................................................................

viii

KATA PENGANTAR ..................................................................................

ix

DAFTAR ISI.................................................................................................

xii

DAFTAR TABEL.........................................................................................

xv

DAFTAR GAMBAR ....................................................................................

xvii

DAFTAR GRAFIK.......................................................................................

xviii

BAB I PENDAHULUAN A. Latar Belakang Masalah.................................................................

1

B. Perumusan Masalah .......................................................................

5

C. Pembatasan Masalah ......................................................................

5

D. Tujuan Penulisan............................................................................

6

E. Metode Penulisan ...........................................................................

6

F. Manfaat Penulisan..........................................................................

6

xii


G. Sistematika Penulisan ....................................................................

7

BAB II LANDASAN TEORI A. Latar Belakang Biologi ..................................................................

8

B. Algoritma Genetika........................................................................

9

1. Pengantar Algoritma Genetika.................................................

9

2. Deskripsi Algoritma Genetika .................................................

11

3. Sruktur Umum Algoritma Genetika.........................................

14

4. Operator dan Fungsi Evaluasi ..................................................

17

5. Pengkodean ..............................................................................

18

5.1. Pengkodean biner (Binery Encoding) .............................

18

5.2. Pengkodean permutasi (Permutation Encoding) ............

18

5.3. Pengkodean nilai (Value Encoding)................................

19

5.4. Pengkodean pohon (Tree Encoding)...............................

19

6. Seleksi ......................................................................................

20

6.1. Seleksi Roda Roulette .....................................................

21

6.2. Seleksi Ranking...............................................................

22

6.3. Seleksi Turnament...........................................................

23

7. Operasi Genetik........................................................................

23

7.1. Persilangan / Crossover...................................................

23

7.1.1. Persilangan Satu Titik .........................................

24

7.1.2. Persilangan Dua Titik..........................................

25

7.2. Mutasi..............................................................................

26

C. Penjadwalan Job-Shop ...................................................................

27

xiii


BAB III ALGORITMA GENETIKA UNTUK PENJADWALAN JOB-SHOP A. Representasi masalah .....................................................................

32

B. Pembangkitan kromosom...............................................................

35

C. Pencarian nilai fitnes untuk masing-masing kromosom ................

35

D. Pemilihan kromosom untuk dijadikan induk .................................

36

E. Proses reproduksi untuk mendapatkan kromosom-kromosom baru.................................................................................................

37

1. Operasi persilangan..................................................................

38

2. Operasi mutasi..........................................................................

38

F. Proses pembentukan populasi baru ................................................

40

BAB IV IMPLEMENTASI DAN ANALISA HASIL PROGRAM A. Flowchart .......................................................................................

41

B. Hasil program dan Analisis............................................................

43

BAB V PENUTUP A. Kesimpulan ....................................................................................

56

B. Saran...............................................................................................

57

DAFTAR PUSTAKA ...................................................................................

58

LAMPIRAN..................................................................................................

59

xiv


DAFTAR TABEL Halaman Tabel 2.1

Contoh populasi dengan 5 kromosom yang diberi fitness baru

22

Tabel 2.2

Contoh masalah penjadwalan 3 x 3..........................................

29

Tabel 3.1

Contoh inisialisasi populasi awal sebanyak 10 kromosom......

35

Tabel 3.2

Contoh kromosom dengan nilai fitness....................................

37

Tabel 4.1

Tabel masalah penjadwalan 4 x 4 ............................................

44

Tabel 4.2

Tabel masalah penjadwalan 6 x 6 ............................................

45

Tabel 4.3

Hasil penelitian masalah 6 x 6, Pcross = 0.25..........................

46

Tabel 4.4

Hasil penelitian masalah 6 x 6, Pcross = 0.3............................

46

Tabel 4.5


47

Tabel 4.6


47

Tabel 4.7


48

Tabel 4.8


48

Tabel 4.9


49

Tabel 4.10 Hasil penelitian masalah 6 x 6, Pcross = 0.6............................

49

Tabel 4.11 Hasil penelitian masalah 6 x 6, Pcross = 0.65..........................

50

Tabel 4.12 Hasil penelitian masalah 6 x 6, Pcross = 0.7............................

50

Tabel 4.13 Hasil penelitian masalah 6 x 6, Pmut = 0.01............................

51


51


52


52


53

xv



53


54


54


55

Tabel 4.22 Hasil penelitian masalah 6 x 6, Pmut = 0.1..............................

55

xvi


DAFTAR GAMBAR Halaman Gambar 2.1

Ilustrasi Algoritma Genetika ..................................................

15

Gambar 2.2

Contoh kromosom dengan pengkodean biner........................

18

Gambar 2.3

Contoh kromoson dengan pengkodean permutasi .................

19

Gambar 2.4

Contoh kromosom dengan pengkodean nilai .........................

19

Gambar 2.5

Contoh kromosom dengan pengkodean pohon ......................

20

Gambar 2.6

Contoh penggunaan metode seleksi roda roulette..................

21

Gambar 2.7 Contoh proses persilangan satu titik ......................................

25

Gambar 2.8

Contoh proses persilangan dua titik .......................................

26

Gambar 2.9

Contoh proses mutasi .............................................................

27

Gambar 2.10 Representasi Gantt-Chart dari solusi masalah 3 x 3...............

30

Gambar 2.11 Hubungan jadwal Semiactive, Active dan Nondelay diperlihatkan oleh diagram Venn ..........................................

31

Gambar 3.1 Operasi dari job dan korespondensi mesin..............................

34

Gambar 3.2 Urutan proses dari job pada mesin1 ........................................

34

Gambar 3.3 Satu jadwal yang dikerjakan ...................................................

34

Gambar 3.4 Ilustrasi proses persilangan .....................................................

39

Gambar 3.5 Ilustrasi proses mutasi .............................................................

40

Gambar 4.1 Flowchart penyelesaian masalah penjadwalan Job-Shop........

42

Gambar 4.2 Representasi Gantt-Chart untuk masalah penjadwalan 4 x 4..

45

xvii


DAFTAR GRAFIK Halaman Grafik 4.1 Grafik hasil penelitian masalah 6 x 6, Pcross = 0.25................

46

Grafik 4.2 Grafik hasil penelitian masalah 6 x 6, Pcross = 0.3..................

46

Grafik 4.3 Grafik hasil penelitian masalah 6 x 6, Pcross = 0.35................

47


47


48


48


49


49


50


50

Grafik 4.11 Grafik hasil penelitian masalah 6 x 6, Pmut = 0.01..................

51

Grafik 4.12. Grafik hasil penelitian masalah 6 x 6, Pmut = 0.02..................

51


52


52


53


53


54


54


55

Grafik 4.20. Grafik hasil penelitian masalah 6 x 6, Pmut = 0.1....................

55

xviii


BAB I PENDAHULUAN

A. Latar Belakang Masalah Masalah penjadwalan tidak terlepas dari kehidupan kita sehari-hari. Masalah penjadwalan Job-Shop sering muncul di berbagai bidang, seperti pada sistem manufaktur, perencanaan produksi, perencanaan komputer, logistik, komunikasi, dan lain sebagainya (Gen dan Cheng,1997). Pada umumnya masalah penjadwalan tersebut sulit untuk dipecahkan, karena berkaitan dengan kompleksnya sifat dari penjadwalan tersebut. Masalah ini telah diteliti selama beberapa dekade, namun tidak ada solusi algoritma yang efisien yang dikenal untuk memecahkannya. Masalah penjadwalan Job-Shop merupakan satu dari masalah penjadwalan yang ada (Garey et al., 1976). Secara umum, permasalahan tersebut dapat dijelaskan sebagai berikut: terdapat n pekerjaan dan m mesin. Masing-masing n pekerjaan meliputi o operasi, dimana masing-masing operasi tersebut memiliki durasi waktu yang harus diproses oleh masing-masing mesin

dan

tidak

dapat

diinterupsi

hingga

mesin

tersebut

selesai

memprosesnya. Masing-masing mesin dapat memproses paling banyak satu operasi pada waktu yang sama. Membuat jadwal pekerjaan untuk satu mesin dan n pekerjaan ada n! (n faktorial) kemungkinan solusi jadwal, tetapi jika terdapat m mesin maka banyaknya jadwal yang mungkin adalah (n!)m kemungkinan solusi jadwal, sehingga akan memerlukan waktu yang cukup

1

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI 2

lama

untuk

mendapatkan

jadwal

yang

optimal.

Jadwal

adalah

mpengalokasikan operasi pada interval waktu untuk diproses oleh mesin. Permasalahannya adalah bagaimana mendapatkan jadwal dengan total waktu yang minimum antara operasi pertama mulai diproses dan operasi terakhir selesai diproses (the makespan), dengan tetap memenuhi urutan proses operasi. Masalah penjadwalan Job-Shop merupakan masalah optimasi yang paling sulit, maka prosedur heuristik merupakan solusi alternatif yang cukup menarik (Moon dan Lee, 1997). Algoritma yang bersifat pendekatan dan probabilistik terhadap solusi yang ingin dicari biasanya dikenal dengan algoritma heuristik. Sebagai contoh, untuk mendapatkan total waktu (makespan) minimum pada masalah penjadwalan Job-Shop, harus dilakukan kombinasi operasi agar dapat diselesaikan oleh suatu mesin, dengan tetap memenuhi urutan proses operasi tersebut. Dalam hal tersebut membutuhkan waktu yang cukup lama dalam menyelesaikannya jika dilakukan dengan metode konvensional. Karena itu dibutuhkan suatu algoritma yang cepat dengan melakukan pendekatan terhadap solusi dari masalah penjadwalan JobShop, walaupun total waktu (makespan) tidak yang terminimum, akan tetapi mendekati solusi yang diinginkan. Algoritma genetika merupakan suatu metode penyelesaian masalah yang tergolong heuristik. Algoritma genetika dapat memberikan kemungkinan penyelesaian masalah yang sangat banyak dan mempertimbangkan suatu kemungkinan tersebut dalam mengambil keputusan. Algoritma genetika telah


digunakan pada masalah-masalah yang tergolong sulit dan dalam berbagai variasi telah diterapkan ke berbagai masalah sains dan teknik yang salah satunya adalah masalah penjadwalan Job-Shop. Algoritma genetika pertama kali diperkenalkan oleh John Holland dan murid-muridnya di Universitas Michigan pada tahun 1960. Algoritma genetika adalah algoritma yang berdasarkan konsep teori evolusi alam dan genetika. Teori evolusi alam dan genetika pertama kali dikemukakan oleh Charles Darwin. Dalam teori genetika disebutkan bahwa sifat tertentu dari suatu mahluk hidup ditentukan oleh susunan gen dalam kromosom mahluk hidup tersebut. Teori genetika dalam algoritma genetika digunakan untuk merepresentasikan setiap solusi dari masalah yang ada, karena setiap solusi diandaikan mempunyai kromosom yang berbeda dengan solusi yang lainnya. Sedangkan evolusi alam adalah proses seleksi terhadap anggota dari berbagai populasi berdasarkan tingkat ketahanan hidup suatu makhluk hidup. Prosesproses dalam evolusi alam yang digunakan dalam algoritma genetika adalah seleksi alam dan reproduksi. Proses seleksi alam digunakan untuk memilih solusi yang baik, sedangkan proses reproduksi digunakan untuk menghasilkan solusi baru yang diharapkan mempunyai kromosom lebih baik dari solusi sebelumnya. Algoritma genetika merupakan algoritma yang dapat digunakan untuk menyelesaikan masalah yang sulit dicari penyelesaian eksaknya karena mempunyai banyak pilihan penyelesaian. Dengan menggunakan algoritma genetika dapat ditemukan penyelesaian dengan waktu yang relatif cepat


karena tidak harus menelusuri semua kemungkinan penyelesaian. Walaupun ada kemungkinan dengan menggunakan algoritma genetika tidak dapat ditemukan solusi terbaik, tetapi paling tidak dapat ditemukan solusi yang mendekati solusi terbaik dalam waktu yang relatif cepat. Algoritma genetika diawali dengan himpunan solusi yang disebut populasi.

Setiap

individu

pada

populasi

disebut

kromosom

yang

menggambarkan sebuah solusi dari masalah yang akan diselesaikan. Sebuah kromosom dapat dinyatakan dengan simbol string misalnya kumpulan string bit. Kromosom-kromosom dapat berubah terus menerus yang disebut juga regenerasi. Pada setiap generasi, kromosom dievaluasi dengan menggunakan alat ukur yang disebut fungsi fitnes (tingkat kesesuaian). Untuk membuat generasi berikutnya, kromosom-kromosom baru yang disebut offspring (keturunan) terbentuk dengan cara menggabungkan dua kromosom dari generasi sekarang dengan menggunakan metode crossover / persilangan atau mengubah kromosom dengan menggunakan operator mutasi. Generasi baru dibentuk dengan cara seleksi yang dilakukan terhadap parents (induk) dan offspring berdasarkan nilai fitnesnya dan menghilangkan yang lainnya. Kromosom-kromosom yang lebih sesuai memiliki probabilitas untuk dipilih. Setelah beberapa generasi, algoritma ini akan konvergen ke arah bentuk kromosom yang terbaik, dengan harapan dapat menyatakan solusi optimal dari masalah yang diselesaikan.


B. Perumusan Masalah Pokok-pokok permasalahan yang akan dibahas dalam skripsi adalah: 1. Bagaimana

penerapan

algoritma

genetika

pada

masalah

penjadwalan Job-Shop? 2. Bagaimana membuat program untuk mendapatkan total waktu (makespan) minimum pada masalah penjadwalan Job-Shop?

C. Pembatasan Masalah Pembahasan skripsi ini dibatasi pada: 1. Pengkodean penjadwalan Job-Shop menggunakan representasi berbasis operasi (operation-based representation). 2. Jumlah input mesin dan job sama, minimal 3 dan maksimal 10. 3. Input ukuran populasi minimal 10 dan maksimal 50. 4. Input generasi minimal 10 dan maksimal 500 5. Proses persilangan menggunakan Precedence Preservative Crossover (PPX). 6. Proses mutasi menggunakan job-pair exchange mutation. 7. Untuk

mendapatkan

makespan

minimum

pada

masalah

penjadwalan Job-Shop penulis akan menggunakan software aplikasi MATLAB. 8. Program hanya dapat dioperasikan dengan satu komputer saja.


D. Tujuan Penulisan Tujuan penulisan skripsi ini untuk menambah pengetahuan kepada pembaca mengenai algoritma genetika dan penjadwalan Job-Shop, serta penerapan algoritma genetika untuk masalah penjadwalan Job-Shop.

E. Metode Penulisan Penulisan skripsi ini menggunakan metode studi pustaka, yaitu dengan menggunakan buku-buku, jurnal-jurnal, dan makalah-makalah yang berkaitan dengan algoritma genetika dan penjadwalan Job-Shop, sehingga tidak ditemukan hal baru.

F. Manfaat Penulisan Manfaat yang diharapkan dari penulisan skripsi ini adalah

dapat

menyelesaikan masalah penjadwalan Job-Shop dengan waktu yang lebih singkat dengan algoritma genetika.


G. Sistematika Penulisan Bab pertama adalah pendahuluan, yang berisi tentang latar belakang masalah, perumusan masalah, pembatasan masalah, tujuan penulisan, metode penulisan, manfaat penulisan, dan sistematika penulisan. Bab kedua adalah landasan teori, pada bab ini diuraikan tentang latar belakang

biologi,

algoritma

genetika,

pengertian

penjadwalan

dan

penjadwalan Job-Shop. Bab ketiga adalah algoritma genetika untuk masalah penjadwalan JobShop. Bab ini menguraikan mengenai langkah-langkah algoritma genetika dalam menyelesaikan masalah penjadwalan Job-Shop, representasi masalah, pembentukan kromosom, pencarian nilai fitness masing-masing kromosom, operasi perkawinan silang, dan operasi mutasi. Bab keempat adalah implementasi dan analisa hasil program, pada bab ini berisi tentang implementasi sistem yang dibangun, meliputi penjelasan flowchart dan analisa hasil program. Bab kelima adalah penutup, pada bab ini berisi kesimpulan dan saran dari sistem yang telah dibangun berdasarkan hasil pembahasan bab-bab sebelumnya.


BAB II LANDASAN TEORI

A.

Latar Belakang Biologi Semua makhluk hidup terdiri dari beberapa sel dimana setiap selnya terdapat kumpulan kromosom yang sama. Kromosom adalah untaian dari DNA yang membentuk model yang membedakan seluruh organisme. Sebuah kromosom terdiri dari gen-gen yang merupakan blok dari DNA. Setiap gen terbentuk dari protein tertentu. Gen tersebut mengkodekan sebuah trait (ciri bawaan) misalnya warna mata, warna kulit, dan lain-lain. Kemungkinan penentuan untuk sebuah trait disebut allele seperti warna hitam dan sawo matang untuk warna kulit. Setiap gen memiliki posisi tersendiri pada kromosom yang disebut locus. Saat melakukan reproduksi, yang muncul pertama kali adalah rekombinasi (crossover atau persilangan). Gen-gen dari parents (induk) membentuk kromosom baru menjadi offspring (keturunan) baru yang kemudian juga dapat bermutasi. Mutasi merupakan perubahan yang terjadi pada elemen suatu DNA. Perubahan itu terjadi mungkin disebabkan karena kesalahan penggandaan gen-gen dari parents (induknya). Fitnes dari makhluk hidup diukur dari kesuksesannya mempertahankan hidupnya.

8


Ruang Pencarian Untuk menyelesaikan suatu masalah, maka dicari solusi yang terbaik dari semua kemungkinan solusi yang ada. Kumpulan semua kemungkinan solusi disebut ruang pencarian (search space). Setiap titik pada ruang pencarian merupakan satu solusi yang mungkin (feasible solution) dan dapat diberi pengenal dalam bentuk nilai atau fitnesnya terhadap masalah yang akan diselesaikan. Proses pencarian solusi menjadi rumit jika tidak diketahui di mana harus mencari atau pencarian dimulai dari mana. Banyaknya metode yang dikenal untuk menemukan solusi yang layak, diantaranya adalah algoritma genetika yang dibuat berdasarkan analogi mekanisme yang terjadi terhadap proses evolusi.

B.

Algoritma Genetika 1. Pengantar Algoritma Genetika Algoritma genetika ditemukan oleh John H. Holland dari Universitas of Michigan pada tahun 1960-an. Saat ini algoritma genetika mulai banyak digunakan untuk menyelesaikan berbagai masalah optimasi yang kompleks. Algoritma ini merupakan metode optimasi yang tidak berdasarkan matematika, melainkan berdasarkan pada fenomena alam yang dalam penelusurannya mencari titik optimal berdasarkan ide yang ada pada genetika dan teori Darwin (1809-1882) yaitu “survival of the fittest” yang menyatakan bahwa evolusi jenis-jenis spesies makhluk hidup dan ekosistemnya terjadi karena seleksi alam.


Individu yang lebih kuat (fit) akan memiliki tingkat survival dan tingkat reproduksi yang lebih tinggi jika dibandingkan dengan individu yang kurang fit. Beberapa aplikasi yang diselesaikan dengan algoritma genetika yaitu sistem dinamikal nonlinear, lintasan robot, program LISP, perancangan jaringan syaraf tiruan, strategi perencanaan, Film-copy Deliverer Problem, Knapsack Problem, Quadratic Assigment Problem, Traveling Salesman Problem dan Minimum Spanning Tree Problem. Algoritma genetika merupakan suatu metode penyelesaian yang tergolong heuristik. Algoritma heuristik adalah algoritma yang bersifat pendekatan atau probabilistik terhadap solusi yang ingin dicari. Ciri-ciri dari algoritma heuristik adalah: i.

Akan selalu memberikan solusi yang baik walaupun belum tentu merupakan solusi yang optimal.

ii.

Lebih cepat dan mudah untuk mengimplementasikan daripada algoritma eksak yang diketahui menjamin memberikan solusi yang lebih optimal.

Sedangkan ciri-ciri dari algoritma genetika adalah: i.

Bekerja dengan sebuah himpunan pengkodean solusi yang bukan merupakan himpunan solusi itu sendiri.

ii.

Mencari solusi dari suatu populasi yang bukan merupakan sebuah solusi yang tunggal.

iii.

Menggunakan informasi fungsi fitnes.


iv.

Menggunakan operasi random dengan aturan perubahan probabilitas, bukan operasi dengan aturan tertentu dalam setiap iterasi.

2. Deskripsi Algoritma Genetika Algoritma genetika adalah teknik pencarian stokastik yang berdasarkan pada mekanisme seleksi alam dan sifat genetika. Dalam implementasinya, algoritma genetika meniru beberapa proses yang terdapat pada evolusi alam dimana evolusi terjadi pada kromosom yang mengkodekan struktur makhluk hidup. Individu-individu yang ada pada saat tertentu dalam suatu populasi merupakan individu-individu yang berhasil mempertahankan hidupnya sedangkan yang lemah akan punah. Individu-individu yang berhasil mempertahankan hidupnya akan membentuk individu baru. Beberapa teori dasar evolusi yang diadopsi oleh algoritma genetika adalah: a. Evolusi adalah proses seleksi alam dan reproduksi yang bekerja pada kromosom. b. Seleksi alamiah berhubungan dengan kinerja dari struktur yang dikodekan oleh kromosom. c. Proses reproduksi adalah titik dimana terjadi evolusi. Rekombinasi akan menciptakan kromosom baru yang berbeda dengan induknya, demikian pula dengan mutasi.


Teori dasar evolusi tersebut bila diimplementasikan dalam bentuk algoritma genetika, maka diharapkan mampu menyelesaikan masalahmasalah yang sulit dengan cara yang sama seperti yang dilakukan melalui evolusi. Keuntungan algoritma genetika adalah sifat metode pencariannya yang lebih optimal, tanpa terlalu memperbesar ruang pencarian dan tanpa kehilangan kesempurnaan (completness) sehingga dapat dengan mudah diimplementasikan ke suatu permasalahan. Algoritma genetika merupakan algoritma yang bermanfaat dan efisien, ketika diterapkan dalam masalah dengan: a. Pencarian dalam ruang pencarian yang besar, kompleks atau hanya sedikit yang diketahui. b. Tidak ada analisis matematika yang memungkinkan. c. Kurang atau tidak ada pengetahuan yang memadai untuk merepresentasikan masalah ke dalam ruang pencarian yang lebih sempit. d. Metode konvensional sudah tidak mampu menyelesaikan masalah yang dihadapi. Algoritma genetika berbeda dengan teknik optimasi konvensional dan prosedur pencarian dalam beberapa segi fundamental: 1) Algoritma genetika bekerja dengan sebuah himpunan pengkodean dari sekumpulan solusi, bukan pada solusi itu sendiri.


2) Algoritma genetika mencari beberapa solusi dari sebuah populasi, bukan satu solusi. 3) Algoritma genetika menggunakan fungsi fitnes, bukan menggunakan turunan atau pengetahuan lainnya. 4) Algoritma

genetika

menggunakan

aturan

perubahan

probabilistik, bukan aturan deterministik. Istilah-istilah yang digunakan dalam algoritma genetika, dijelaskan dalam tabel dibawah ini: Istilah dalam algoritma

Keterangan.

genetika Populasi

Himpunan beberapa solusi

Kromosom

Solusi

Gen

Bagian dari kromosom

Parent

Solusi yang akan dikenakan proses persilangan atau mutasi

Offspring

Solusi baru yang dihasilkan melalui proses persilangan atau mutasi

Persilangan

Proses yang melibatkan dua solusi untuk mendapatkan solusi baru

Mutasi

Proses yang melibatkan satu solusi untuk mendapatkan solusi baru

Seleksi

Pemilihan kromosom yang baik


3. Struktur Umum Algoritma Genetika Bila P(t) dan C(t) adalah induk dan keturunan pada generasi t, struktur umum algoritma genetika adalah sebagai berikut: prosedur algoritma genetika : begin t ← 0; inisialisasi P(t); evaluasi P(t); while(kondisi terminasi tidak terpenuhi) do rekombinasi P(t) untuk menghasilkan anak C(t); evaluasi C(t); seleksi P(t+1) dari P(t) dan C(t); t ← t+1; end end Struktur umum algoritma genetika (Mitsuo Gen dan Runwei Cheng, 1997) dapat pula dideskripsikan seperti pada gambar 2.1 berikut.


Ilustrasi Algoritma Genetika

crossover chromosomes encoding solutions

1100101010 1011101110 0011011001 1100110001

1100101010 1011101110

1100101110 1011101010

mutation 0011011001

0011001001

selection new population

evaluation offspring 1100101110 1011101010 0011001001 decoding solutions fitness computation

Gambar 2.1. Ilustrasi Algoritma Genetika


Keterangan gambar Dalam menyelesaikan masalah, algoritma genetika diawali dengan menginisialisasikan himpunan solusi yang dibangkitkan secara acak. Himpunan solusi ini disebut populasi. Setiap individu pada populasi disebut kromosom yang menggambarkan sebuah solusi dari masalah yang akan diselesaikan. Sebuah kromosom dapat dinyatakan dalam simbol string misalnya kumpulan string bit. Kromosom-kromosom dapat berubah terus menerus disebut dengan regenerasi. Pada setiap generasi, kromosom dievaluasi dengan mengunakan alat ukur yang disebut fungsi fitnes (tingkat kesesuaian). Untuk membuat generasi berikutnya, kromosom-kromosom baru yang disebut offspring (keturunan) terbentuk dengan cara menggabung dua kromosom dari generasi sekarang dengan menggunakan operator crossover / persilangan atau mengubah sebuah kromosom dengan menggunakan operator mutasi. Generasi baru dibentuk dengan cara seleksi yang dilakukan terhadap parents dan offspring berdasarkan nilai fitnesnya dan menghilangkan yang lainnya. Kromosom-kromosom yang lebih sesuai memiliki probabilitas untuk dipilih. Setelah beberapa generasi, algoritma ini akan konvergen ke arah bentuk kromosom yang

terbaik, dengan harapan dapat

menyatakan solusi optimal dari permasalahan yang diselesaikan.


4. Operator dan Fungsi Evaluasi Biasanya, inisialisasi diasumsikan secara random. Rekombinasi melibatkan crossover dan mutasi untuk menghasilkan keturunan (offspring). Pada kenyataannya, hanya ada dua jenis operasi dalam algoritma genetika, yaitu operasi genetik (crossover / persilangan dan mutasi) dan operasi evolusi (seleksi). Pada teori evolusi, mutasi ini merupakan operator kromosom yang memungkinkan makhluk hidup melakukan penyesuaian dengan lingkungannya walaupun lingkungan barunya tidak sesuai dengan lingkungan induknya semula. Faktor terbesar dalam teori evolusi yang menyebabkan suatu kromosom bertahan, punah, melakukan persilangan atau mutasi adalah lingkungan. Pada algoritma genetika, faktor lingkungan diperankan oleh fungsi evaluasi. Fungsi evaluasi menggunakan kromosom sebagai masukan dan menghasilkan angka tertentu yang menunjukkan kinerja pada masalah yang diselesaikan. Pada masalah optimasi, fungsi evaluasi adalah fungsi tujuan (objective function). Nilai fungsi evaluasi disebut nilai kesesuaian (fitness value). Nilai inilah yang akan menentukan apakan suatu string akan muncul pada generasi berikutnya atau mati.


5. Pengkodean Beberapa jenis pengkodean yang sering digunakan dalam mengkodekan solusi terhadap suatu masalah, yaitu: 5.1. Pengkodean biner (Binary Encoding) Pengkodean biner ini merupakan cara pengkodean yang paling umum digunakan karena pengkodean ini merupakan yang pertama kali digunakan dalam Algoritma Genetika oleh Holland. Dalam pengkodean biner, setiap kromosom dinyatakan dalam barisan bit 0 atau 1. Gambar 2.2 merupakan contoh kromosom dengan pengkodean biner. Kromosom 1

1 0 1 0 1 0 0 1

Kromosom 2

0 0 1 1 1 0 1 0

Gambar 2.2: Contoh kromosom dengan pengkodean biner

Pengkodean biner memberikan banyak kemungkinan untuk kromosom walaupun dengan jumlah allele yang sedikit yaitu 0 atau 1. Pada pihak lain, pengkodean biner ini sering tidak sesuai untuk banyak masalah dan kadang-kadang pengoreksian harus dilakukan setelah proses evolusi (persilangan dan/ atau mutasi). Contoh masalah yang sesuai untuk pengkodean biner antara lain masalah knapsack. 5.2. Pengkodean permutasi (Permutation Encoding) Pengkodean permutasi dapat digunakan dalam masalah pengurutan. Dalam pengkodean permutasi setiap kromosom merupakan suatu barisan bilangan yang menyatakan bilangan


dalam suatu urutan. Gambar 2.3 merupakan contoh kromosom dengan pengkodean permutasi. Kromosom 1

1 3 4 2 6 5 7 8

Kromosom 2

3 4 6 1 5 2 8 7

Gambar 2.3 : Contoh kromoson dengan pengkodean permutasi

Pengkodean permutasi hanya berguna untuk masalah pengurutan. 5.3. Pengkodean nilai (Value Encoding) Pengkodean nilai dapat digunakan untuk masalah yang mempunyai nilai yang rumit. Dengan pengkodean nilai ini, setiap kromosom merupakan suatu barisan dari nilai-nilai. Nilai-nilai dapat berupa apa saja yang berhubungan dengan masalah. Gambar 2.4 merupakan contoh kromosom dengan pengkodean nilai. Kromosom 1

1.2 5.6 0.3 2.6 4.5 3.7 1.4

Kromosom 2

A B D H F I E H

Gambar 2.4: Contoh kromosom dengan pengkodean nilai

Pengkodean nilai ini baik digunakan untuk beberapa masalah. Di pihak lain, untuk mengkodekan tipe ini sering perlu pengembangan persilangan dan mutasi baru yang spesifik untuk permasalahannya. Contohnya dalam masalah mencari bobot untuk jaringan syaraf. 5.4. Pengkodean pohon (Tree Encoding) Pengkodean pohon ini lebih banyak digunakan untuk menyusun

program

untuk

pemrograman

genetika.

Dalam

pengkodean pohon, setiap kromosom merupakan suatu pohon dari


beberapa objek, seperti fungsi atau perintah dalam bahasa pemrograman. Pengkodean pohon ini baik digunakan untuk menyusun program untuk masalah mencari fungsi berdasarkan nilai-nilai yang diberikan. Gambar 2.5 merupakan contoh kromosom dengan pengkodean pohon.

Kromosom: +

x

/

5

y

( + x (/ 5 y)) Gambar 2.5 : Contoh kromosom dengan pengkodean pohon

6. Seleksi Seleksi akan menentukan individu-individu mana saja yang akan dipilih untuk dilakukan rekombinasi dan bagaimana offspring/keturunan terbentuk dari individu-individu terpilih. Langkah pertama yang dilakukan dalam seleksi ini adalah pencarian nilai fitnes. Ada beberapa metode seleksi, antara lain:


6.1. Seleksi Roda Roulette Metode seleksi roda roulette merupakan metode yang paling sederhana, dan sering juga dikenal dengan nama stochastic sampling with replacement. Sesuai dengan namanya, metode ini menirukan permainan roulette-wheel di mana masing-masing kromosom menempati potongan lingkaran pada roda roulette secara proporsional sesuai dengan nilai fitnesnya. Kromosom yang mempunyai nilai fitnes lebih besar menempati potongan lingkaran yang lebih besar dibandingkan dengan kromosom bernilai fitnes rendah. Gambar 2.6 ilustrasi sebuah contoh penggunaan metode roda roulette. Kromosom K1 K2 K3 K4 Jumlah

Nilai Fitnes 1 2 0.5 0.5 4

Probabilitas 0.25 0.5 0.125 0.125

K1

K3 K4 K2

Gambar 2.6 Contoh penggunaan metode seleksi roda roulette.

Kromosom K1 mempunyai probabilitas 25% untuk dipilih setiap kali suatu kromosom dipilih (setiap roda diputar). Probabilitas masing-masing individu dapat dicari dari pembagian fitnes masing-masing individu dengan total fitnes dalam populasi. Seleksi dengan roda roulette berdasarkan skala fitnes. Karena terpilihnya suatu kromosom dalam populasi untuk dapat berkembang biak adalah sebanding dengan fitnesnya, maka akan terjadi kecenderungan kromosom yang baik akan terpelihara terus


sehingga dapat membawa ke hasil optimum lokal (konvergensi dini) ke suatu hasil yang bukan optimum global. Sebaliknya, jika semua kromosom dalam populasi mempunyai fitnes yang hampir sama, maka seleksi ini akan menjadi seleksi yang bersifat acak. 6.2. Seleksi Ranking Seleksi dengan roda roulette sebelumnya memiliki kelemahan ketika fitnes yang tersebar dalam populasi berbeda jauh misalnya jika fitnes dari kromosom terbaik dalah 90% dari keseluruhan roda roulette, maka kromosom lain akan mempunyai kesempatan yang kecil untuk terpilih. Pada seleksi ranking, pertama yang dilakukan adalah merangkingkan kromosom dalam populasi kemudian setiap kromosom menerima nilai fitnes dari ranking tersebut. Kromosom yang terjelek akan mendapatkan nilai fitnes 1, yang kedua mendapat nilai fitnes 2 dan seterusnya sampai yang terbaik mendapatkan nilai fitnes N (jumlah kromosom dalam populasi). Sebagai ilustrasi dapat dilihat pada tabel 2.1. Kromosom B D E C A

Fitnes

Fitnes Baru

5 5 5 10 15

1 2 3 4 5

Tabel 2.1: Contoh populasi dengan 5 kromosom yang diberi fitness baru


6.3. Seleksi Turnament Seleksi turnamen merupakan jenis seleksi yang divariasi berdasarkan seleksi roda Roulette dan seleksi ranking. Sejumlah k kromosom tertentu dari populasi dengan n kromosom (k ≤ n) dipilih secara acak dengan probabilitas yang sama. Dari k kromosom yang terpilih tersebut kemudian dipilih suatu kromosom dengan fitnes terbaik, yang diperoleh dari hasil pengurutan rangking fitnes kromosom-kromosom yang dipilih tersebut. Perbedaan dengan seleksi roda Roulette adalah bahwa pemilihan kromosom yang akan digunakan untuk berkembang biak tidak berdasarkan skala fitnes dari populasi. Untuk k = 1, seleksi turnament ini akan sama dengan seleksi secara acak karena hanya melibatkan satu kromosom. Untuk k = 2, maka dua kromosom dalam populasi akan dipilih secara acak, kemudian dari dua kromosom tersebut dipilih satu kromosom dengan fitnes terbaik. Biasanya yang sering digunakan adalah untuk k = 2 tergantung dari ukuran populasi. 7. Operasi Genetik 7.1. Persilangan / Crossover Salah satu komponen paling penting dalam algoritma genetika adalah persilangan atau crossover. Persilangan atau crossover berfungsi menggabungkan dua string induk yang berbeda menjadi dua string keturunan yang berbeda dengan


induknya. Sebuah kromosom yang mengarah pada solusi yang bagus dapat diperoleh dari proses persilangan dua buah kromosom. Persilangan bisa juga berakibat buruk jika ukuran populasinya sangat kecil. Dalam suatu populasi yang sangat kecil, suatu kromosom dengan gen-gen yang mengarah ke solusi akan sangat cepat

menyebar

ke

kromosom-kromosom

lainnya.

Untuk

mengatasi masalah ini dilakukan dengan suatu probabilitas tertentu Pc. Artinya, penyilangan bisa dilakukan hanya jika suatu bilangan random [0,1) yang dibangkitkan kurang dari Pc yang ditentukan. Dari hasil penelitian yang sudah pernah dilakukan oleh praktisi algoritma genetika menunjukkan bahwa angka probabilitas persilangan sebaiknya cukup tinggi, yaitu 80% sampai 95% untuk memberikan hasil yang baik. Untuk beberapa masalah tertentu probabilitas persilangan 60% memberikan hasil yang lebih baik (Obitko,1998). Segera setelah induk untuk persilangan terpilih maka digunakan operasi persilangan sehingga terbentuk keturunan dari induk tersebut. Ada beberapa persilangan / Crossover: 7.1.1. Persilangan satu titik Proses persilangan ini adalah dengan memilih satu titik persilangan. Kromosom offspring kemudian dibentuk sebagai barisan bit

dari awal kromosom sampai titik


persilangan. Yang disalin dari induk pertama selebihnya disalin dari induk ke dua. Sebagai contoh, andaikan terdapat dua kromosom induk dengan panjang L = 6 yaitu 000000 dan 111111. Jika titik persilangan adalah 4 maka dihasilkan dua offspring yaitu 000011 dan 111100. Gambar 2.7 merupakan contoh proses persilangan satu titik. Kromosom induk1

0 0 0 0 0 0

Kromosom induk2

1 1 1 1 1 1

Offspring 1

0 0 0 0 1 1

Offspring 2

1 1 1 1 0 0

Gambar 2.7: Contoh proses persilangan satu titik

7.1.2. Persilangan dua titik Proses persilangan ini adalah memilih dua titik persilangan. Kromosom offspring kemudian dibentuk sebagai barisan bit dari awal sampai titik persilangan pertama disalin dari induk pertama, bagian dari titik persilangan pertama dan kedua disalin dari induk kedua, kemudian selebihnya disalin dari induk pertama lagi. Sebagai contoh, andaikan terdapat dua kromosom induk dengan panjang L = 6 yaitu 000000 dan 111111. Jika terdapat dua titik persilangan yaitu 2 dan 4 maka dihasilkan 2 offspring yaitu 001100 dan 110011. Gambar 2.8 merupakan contoh proses persilangan dua titik.


Kromosom 1

0 0 0 0 0 0

Kromosom 2

1 1 1 1 1 1

Offspring 1

0 0 1 1 0 0

Offspring 2

1 1 0 0 1 1

Gambar 2.8: Contoh proses persilangan dua titik

7.2. Mutasi Setelah proses persilangan selesai, kemudian dilakukan proses mutasi yang dikenakan pada keturunannya. Mutasi adalah proses mengubah nilai dari satu atau beberapa gen dalam 1 kromosom. Mutasi berfungsi dalam melakukan perubahan yang bukan disebabkan oleh persilangan. Jika dalam proses pemilihan kromosom-kromosom cenderung terus pada kromosom yang baik saja maka sangat mudah terjadi konvergensi dini, yaitu mencapai solusi optimum lokal. Untuk menghindari terjadinya konvergensi dini dan tetap menjaga perbedaan kromosom-kromosom dalam populasi, selain melakukan pendekatan selektif yang lebih efisien, operasi mutasi juga dapat dilakukan. Proses mutasi ini adalah acak, sehingga tidak selalu menjamin bahwa setelah proses mutasi akan diperoleh kromosom fitnes yang lebih baik, tetapi dengan adanya mutasi ini diharapkan agar kromosom yang diperoleh akan mempunyai fitnes yang lebih baik dibandingkan sebelum operasi mutasi. Gambar 2.9 merupakan contoh proses mutasi.


Kromosom sebelum mutasi

1 1 0 0 1 1

Kromosom sesudah mutasi

1 1 0 1 0 0

Gambar 2.9: Contoh proses mutasi

Akan tetapi operasi mutasi mendapat kontroversi penerapannya dalam algoritma genetika karena sifatnya yang acak sehingga dapat menggangu kromosom dengan fitnes terbaik yang telah diperoleh. Kadang operasi mutasi tetap digunakan dengan probabilitas yang sangat kecil yaitu Pm<1. Jadi kemungkinan kromosom mengalami perubahan akibat mutasi sangat kecil.

C.

Penjadwalan Job-Shop Menurut Baker (1974) penjadwalan adalah proses pengalokasian sumber daya yang tersedia untuk mengerjakan tugas dalam jangka waktu tertentu. Masalah penjadwalan muncul apabila pada saat yang sama terdapat sekumpulan job yang harus dihadapi dengan terbatasnya mesin atau fasilitas produksi yang tersedia. Salah satu usaha yang dilakukan untuk tercapainya penjadwalan yang optimal adalah dengan melakukan peminimalan total waktu penyelesaian serangkaian proses produksi (makespan). Masalah penjadwalan Job-Shop merupakan persoalan pengurutan sejumlah operasi yang diproses pada mesin-mesin tertentu. Masalah penjadwalan Job-Shop adalah bagaimana menyusun semua operasi dari semua job pada tiap mesin dalam rangka meminimasi fungsi obyektif. Fungsi obyektif yang dimaksud dapat berupa waktu pengerjaan total.


Mesin yang umum adalah satu, dimana terdapat m mesin yang akan memproses n job. Masing-masing job memerlukan operasi yang harus diproses secara berurutan, dimana masing-masing operasi memiliki durasi waktu dan tidak dapat diinterupsi hingga mesin tersebut berhenti berproses. Masing-masing mesin dapat memproses paling banyak satu operasi pada waktu yang sama.

Model Job-Shop Klasik Masalah penjadwalan Job-Shop klasik dapat dinyatakan sebagai berikut: terdapat m mesin yang berbeda dan n job yang berbeda untuk dijadwalkan. Setiap job terdiri atas satu set operasi dan urutan operasi pada mesin sudah terspesifikasi. Beberapa batasan untuk job dan mesin diantaranya: a. Job tidak boleh dikerjakan mesin yang sama lebih dari satu kali. b. Tidak ada batasan antara operasi dari job yang berbeda. c. Operasi tidak dapat diinterupsi. d. Masing-masing mesin dapat memproses hanya satu job pada satu waktu. e. Tidak ada ketetapan maupun batas waktu penyelesaian seluruh pekerjan. Permasalahannya adalah menentukan urutan operasi pada mesin untuk meminimasi makespan, yaitu waktu yang ditetapkan untuk menyelesaikan semua job.


Sebagai contoh penjadwalan 3 job dan 3 mesin (Yamada dan Nakano, 1997) Tabel 2.2: masalah 3 x 3 Mesin 1 2 3 1 3 2 2 1 3

Job 1 Job 2 Job 3

Waktu 3 3 3 2 3 4 3 2 1

Job 1 Job 2 Job 3

Terdapat 3 job yang harus diproses oleh 3 mesin. Job 1 harus diproses oleh ke-3 mesin, urutan pertama mesin 1 memproses job 1 dengan waktu 3 satuan waktu, urutan kedua mesin 2 memproses dengan waktu 3 satuan waktu, dan urutan ketiga mesin 3 memproses dengan 3 satuan waktu. Pada job 2 dan job 3 sama halnya dengan job 1. Didapatkan total waktu yang diperlukan untuk memproses seluruh job dari mulai diprosesnya job awal hingga job akhir selesai diproses, digambarkan dalam bentuk Gantt-Chart seperti pada gambar 2.10 berikut.

M1

J1

M2

J3

J2

J3

J1

J2

M3

J2

0

2

4

6

J1

8

J3

10

Gambar 2.10: Representasi Gantt-Chart dari solusi masalah 3 x 3

12

waktu


Pada prinsipnya, terdapat sejumlah jadwal yang mungkin pada permasalahan penjadwalan Job-Shop sebab waktu yang kosong diantara dua operasi dapat disisipi sehingga dapat dilakukan pergeseran ke kiri pada operasi yang masih mungkin. Pergeseran suatu jadwal dikatakan local left shift jika suatu operasi dapat dimulai dalam waktu yang lebih awal tanpa mengubah urutan operasi. Pergeseran suatu jadwal dikatakan global left shift adalah jika suatu operasi dapat dimulai dalam waktu yang lebih awal tanpa penundaan operasi lain sampai pergeseran mengubah urutan operasi. Berdasarkan dua konsep diatas, penjadwalan dapat dibedakan menjadi [Gen dan Cheng,1997]: a) Jadwal Semiactive Dikatakan semiactive jika tidak terdapat local left shift b) Jadwal Active Jadwal dikatakan active jika tidak terdapat global left shift c) Jadwal Nondelay Jadwal

dikatakan

nondelay

jika

tidak

ada

mesin

yang

menganggur/tidak memproses apa-apa pada suatu waktu ketika dapat dimulainya beberapa operasi untuk diproses.


Hubungan jadwal Semiactive, Active dan Nondelay diperlihatkan oleh diagram Venn pada gambar 2.11 berikut:

*opt

nondelay active Semi-active

Gambar 2.11: Hubungan jadwal Semiactive, Active dan Nondelay diperlihatkan oleh diagram Venn

Jadwal yang optimal terletak pada himpunan jadwal active. Jadwal Nondelay lebih kecil daripada jadwal active, tetapi tidak menjamin optimum [Baker, 1974 dalam Gen dan Cheng, 1997].


BAB III ALGORITMA GENETIKA UNTUK PENJADWALAN JOB-SHOP

Pada skripsi ini akan dibuat sistem dengan menggunakan algoritma untuk membantu user dalam menyelesaikan masalah penjadwalan job-shop yang diharapkan dapat menyelesaikan masalah penjadwalan dengan waktu yang relatif singkat.

Penulis

membangun

sistem

ini

dengan

menggunakan

bahasa

pemrograman Matlab. Di bawah ini akan dituliskan secara rinci penggunaan algoritma genetika untuk menyelesaikan penjadwalan job-shop. A. Representasi Masalah Hal yang paling penting dalam menyelesaikan masalah optimasi adalah representasi atau pemodelan masalah ke dalam suatu model yang sesuai dengan algoritma yang digunakan. Untuk menyelesaikan penjadwalan job-shop dengan algoritma genetika, maka masalah harus direpresentasikan atau dimodelkan terlebih dahulu. Untuk

menyelesaikan

penjadwalan

job-shop

akan

digunakan

operation-based representation. Representasi ini mengkodekan jadwal sebagai urutan operasi dan setiap gen mewakili satu operasi. Kemudian digunakan simbol berupa angka untuk menamai masing-masing gen, dimana urutan dari angka merepresentasikan urutan operasi sedangkan angka itu

32


sendiri adalah nama dari job. Panjang dari kromosom terdiri dari n x m gen, dimana n = jumlah job, dan m = jumlah mesin. Contoh: 3 x 3 job mesin (tabel 2.2). Misal kromosomnya

[3 2

2 1 1 2 3 1 3], dimana 1 mewakili job1, 2 mewakili job2, dan 3

mewakili job3. Karena masing-masing job mewakili 3 operasi, berarti terdapat 3 simbol yang sama di dalam kromosom. Sebagai contoh terdapat 3 gen yang sama pada urutan kedua dari kromosom tersebut, dimana gen tersebut mewakili 3 operasi dari job2. 2 yang pertama merepresentasikan operasi pertama dari job2 akan diproses oleh mesin1, 2 yang kedua merepresentasikan operasi kedua dari job2 akan diproses oleh mesin3, dan 2 yang ketiga merepresentasikan operasi ketiga dari job2 akan diproses oleh mesin2. Relasi koresponden antara operasi dari job dan proses mesin dijelaskan pada gambar dibawah ini.

Kromosom

Mesin

[3 2

2 1 1 2 3 1 3]

12 (a)

3

[3 2

2 1 1 2 3 1 3]

1 3

2 (b)

[3 2

2 1 1 2 3 1 3]

2

1

3

(c)

Gambar 3.1 Operasi dari job dan korespondensi mesin (a) untuk job1, (b) untuk job2, dan (c) untuk job3

Berdasarkan relasi diatas, dapat memperoleh korespondensi daftar mesin yaitu

[2

1 3 1 2 2 1 3 3] yang diperlihatkan pada gambar dibawah ini.


Kromosom

[3

2 2 1 1 2 3 1 3]

Mesin

[2

1 3 1 2 2 1 3 3]

Gambar 3.2 Urutan proses dari job pada mesin1

Dari gambar 3.2 dapat dilihat bahwa urutan proses job untuk mesin1 adalah

2 − 1 − 3 , untuk mesin2 adalah 3 − 1 − 2 , dan untuk mesin3 adalah 2 − 1 − 3 . Dapat juga diringkas seperti pada gambar dibawah ini.

M1

J2

M2

J1

J3

J3

J1

M3

J2

J2 2

3

J1 5

7

8

J3 11

12

waktu

Gambar 3.3. Satu jadwal yang dikerjakan

B. Pembangkitan Kromosom Setelah dilakukan representasi atau pemodelan masalah, kemudian dilakukan

pembangkitan

kromosom.

Pembangkitan

kromosom dalam

penjadwalan job-shop akan dilakukan secara acak atau random. Semakin banyak job dan mesin yang akan dicari jadwal yang optimal maka semakin banyak pula kromosom yang dibangkitkan. Pada populasi awal akan dibangkitkan sepuluh kromosom secara acak. Setiap kromosom terdiri dari


gen-gen sebanyak jumlah job dikali jumlah mesin yang dimasukkan. Tabel 3.2 merupakan contoh inisialisasi populasi awal sebanyak 10 kromosom. Kromosom kek1 k2 k3 k4 k5 k6 k7 k8 k9 k10

Bentuk representasinya 3 3 2 3 1 3 3 3 3 3

2 1 1 1 2 1 1 3 3 3

1 2 1 3 2 1 3 3 2 2

3 1 2 1 1 2 1 2 1 2

2 3 2 3 2 1 3 2 1 3

2 3 3 2 1 3 2 1 1 2

3 2 3 2 3 3 1 1 2 1

1 1 3 2 3 2 2 2 2 1

1 2 1 1 3 2 2 1 3 1

Tabel 3.1. Contoh inisialisasi populasi awal sebanyak 10 kromosom

C. Pencarian nilai fitnes untuk masing-masing kromosom Kromosom yang telah dibangkitkan akan ditentukan berdasarkan nilai fitnesnya. Nilai fitnes disini merupakan solusi dari permasalahan penjadwalan job-shop yaitu makespan. Setiap kromosom yang telah dikodekan akan diterjemahkan untuk dicari nilai fitnesnya. Untuk menentukan fitnes terbaik adalah memilih dari seluruh kromosom yang memiliki fitnes terkecil, dan kromosom tersebutlah yang merepresentasikan sebuah jadwal. Nilai fitnes dari masing-masing kromosom diperoleh dari total waktu yang dihasilkan oleh masing-masing mesin dalam menyelesaikan sejumlah job. Kromosom yang mempunyai nilai fitnes terbaik adalah kromosom yang mempunyai total waktu minimum dalam mengerjakan semua job.


Secara matematis, fungsi fitnes untuk mencari waktu yang minimum untuk menyelesaikan job dapat dituliskan sebagai berikut: n Min ∑ max { C } ik 1 ≤ k≤m i =1 Dimana: Cik

= waktu penyelesaian job i pada mesin k

i

= 1, 2, 3, ... , n

k

= 1, 2, 3, ... , m

D. Pemilihan kromosom untuk dijadikan induk Pemilihan kromosom untuk dijadikan induk dilakukan berdasarkan nilai fitnes dari masing-masing kromosom. Induk dipilih melalui proses seleksi. Induk untuk proses persilangan / crossover dipilih dengan cara menghitung nilai fitnesnya, kromosom yang mempunyai nilai fitnes terbaik akan diambil untuk dijadikan induk untuk mendapatkan kromosom yang lebih baik daripada sebelumnya. Sedangkan pemilihan induk untuk proses mutasi dipilih dengan cara menghitung nilai fitnesnya juga dan kromosom yang mempunyai nilai fitnes terburuk diambil untuk dijadikan induk untuk mendapatkan kromosom yang lebih baik daripada sebelumnya. Tabel 3.1 merupakan contoh kromosom dengan nilai fitnes.


Kromosom kek1 k2 k3 k4 k5 k6 k7 k8 k9 k10

Bentuk representasinya 3 3 2 3 1 3 3 3 3 3

2 1 1 1 2 1 1 3 3 3

1 2 1 3 2 1 3 3 2 2

3 1 2 1 1 2 1 2 1 2

2 3 2 3 2 1 3 2 1 3

2 3 3 2 1 3 2 1 1 2

3 2 3 2 3 3 1 1 2 1

1 1 3 2 3 2 2 2 2 1

1 2 1 1 3 2 2 1 3 1

Fitnes 21 19 18 17 16 16 14 13 13 11

Tabel 3.2 merupakan contoh kromosom dengan nilai fitnes

Untuk proses persilangan / crossover, induk yang dipilih sebanyak dua. Dari tabel 3.2 terlihat bahwa kromosom k10 dan k9 yang mempunyai fitnes terbaik, oleh karena itu kedua kromosom tersebut mempunyai kemungkinan untuk melakukan proses persilangan / crossover. Sedangkan untuk proses mutasi, induk yang dipilih hanya satu dan yang dipilih adalah kromosom yang mempunyai fitnes terburuk. Dari tabel 3.2 terlihat bahwa kromosom k1 yang mempunyai fitnes terburuk, oleh karena itu kromosom k1 mempunyai peluang untuk melakukan proses mutasi.

E. Proses reproduksi untuk mendapatkan kromosom-kromosom baru Untuk mendapatkan jadwal dengan waktu yang seminimum mungkin, diperlukan modifikasi terhadap kromosom-kromosom. Modifikasi yang dilakukan adalah operasi persilangan dan operasi mutasi. Operasi persilangan adalah proses penggabungan dua kromosom (dua induk yang terpilih) untuk menghasilkan individu baru sedangkan operasi mutasi merupakan proses pengubahan sebuah kromosom yang terpilih untuk menghasilkan individu baru.


1. Operasi Persilangan / crossover Untuk mendapatkan individu baru salah satu cara yang dilakukan adalah dengan melakukan persilangan / crossover. Operasi persilangan / crossover melibatkan dua induk yang telah terpilih dan akan menghasilkan sebuah offspring. Dalam masalah ini yang digunakan adalah metode precedence preservation crossover (PPX). Langkah-langkahnya adalah sebagai berikut: i.

Random bilangan biner sepanjang jumlah gen pada kromosom.

ii.

Dimulai dari bilangan biner pertama paling kiri, jika bernilai 0 maka gen untuk offspring diambil dari gen pertama pada parent pertama yang belum terpakai. Dan pada parent kedua dicari gen yang paling kiri yang sama dengan gen yang diambil dari parent pertama yang belum dipakai kemuadian dicoret.

iii.

Jika bilangan biner bernilai 1 maka gen untuk offspring diambil gen paling kiri dari parent kedua yang belum terpakai. Dan pada parent pertama dicari gen paling kiri yang sama dengan gen yang diambil dari parent kedua yang belum terpakai kemudian dicoret.

iv.

Lakukan sampai gen bilangan biner terakhir.


Ilustrasi proses persilangan terlihat pada gambar 3.4. P1

3

2 2 3

1 1 3

1 2

H

0

1 1 1

0 0 0

1 1

P2

2

3

O

3

2 3 2

3 2

1 3 1 1 1 3

1 2 1 2

Gambar 3.4 Ilustrasi proses persilangan

2. Operasi mutasi Mutasi merupakan proses untuk menghasilkan individu baru dari sebuah kromosom melalui perubahan salah satu gen pada kromosom terpilih. Menurut Gen, Tsujimura, dan Kubota operasi mutasi yang digunakan adalah job-pair exchange mutation. Secara random diambil dua job yang tidak sama dan kemudian mengganti posisinya. Untuk Operation-Based representation, offspring / keturunan diperoleh dari mengganti dua job yang terdekat yang mungkin menghasilkan jadwal yang sama seperti parentnya. Metode ini memilih 2 generasi yang tidak identik dari kromosom, kemudian menukar posisi antara gen 1 dengan posisi gen kedua. Ilustrasi proses mutasi terlihat pada gambar 3.5 berikut.


p1 [ 3 2 1 2 3 4 1 2 4 4 1 3 4 1 2 3 ]

o1 [ 3 2 1 4 3 4 1 2 4 4 1 3 2 1 2 3 ] Gambar 3.5 Ilustrasi Operasi Mutasi

F. Proses pembentukan populasi baru Setelah melakukan proses persilangan / crossover dan mutasi yang menghasilkan kromosom keturunan / offspring yang baru, langkah selanjutnya adalah menghitung nilai fitnes masing-masing offspring tersebut. Kemudian dilakukan pembandingan nilai fitnes populasi awal sebelumnya dengan nilai fitnes offspring. Jika ada nilai fitnes yang berada pada populasi awal sebelumnya lebih buruk maka akan digantikan dengan offspring yang bernilai fitnes lebih baik. Dengan demikian diharapkan akan diperoleh kromosom dengan nilai lebih baik pada kromosom populasi baru.


BAB IV IMPLEMENTASI DAN ANALISA HASIL PROGRAM

A. Flowchart Suatu algoritma disusun dengan tujuan untuk menyusun tahap-tahap penyelesaian suatu masalah. Akan tetapi metode ini memiliki kelemahan, yaitu bahwa penyusunan algoritma sangat dipengaruhi oleh tata bahasa pembuatnya sehingga kadang-kadang akan sulit dipahami oleh orang lain. Untuk membantu kesulitan tersebut, maka diperlukan flowchart atau bagan alir. Secara garis besar flowchart penyelesaian masalah penjadwalan Job-Shop dengan algoritma genetika terlihat pada gambar 4.1 berikut.

41


Mulai

Input parameter Job-Shop dan Algoritma Genetika(jumlah job, mesin, operasi, ukuran populasi, Prob cross, Prob mutasi, dan generasi)

Inisialisasi populasi

k=1

Evaluasi populasi

Crossover

Mutasi

Evaluasi Populasi

Seleksi

k=jumlah generasi?

ya

tidak

k = k+1

Gambar 4.1. Flowchart penyelesaian masalah penjadwalan Job-Shop

Selesai


B. Analisis Hasil Program Program aplikasi yang dibuat berfungsi untuk mencari total waktu yang diperlukan dari mesin pertama mulai memproses pekerjaan hingga mesin terakhir selesai memproses pekerjaan (makespan) atau dapat dikatakan mendapat jadwal dengan makespan minimum. Di dalam program ini parameter yang diinputkan adalah: 1. Parameter Job-Shop. Parameter Job-shop diantaranya banyaknya jumlah job, mesin dan operasi. 2. Parameter algoritma genetika. Parameter algoritma genetika diantaranya: a. uk_pop,

merupakan

banyaknya

populasi

yang

akan

dibangkitkan dan bentuk populasi awal secara acak. b. Generasi,

merupakan

banyaknya

generasi

yang

akan

dihasilkan. Jumlah generasi besar berarti semakin banyak iterasi yang dilakukan, dan semakin besar pula domain solusi yang akn dieksplorasi. c. Pcross adalah probabilitas persilangan / crossover. Probabilitas ini menentukan peluang dari kromosom untuk melakukan persilangan / crossover. Tidak ada aturan yang pasti tentang berapa nilai parameter ini. d. Pmut adalah probabilitas mutasi. Probabilitas mutasi ini menentukan peluang dari gen pada setiap kromosom untuk


melakukan mutasi. Tidak ada aturan yang pasti tentang berapa nilai parameter ini. Tabel masalah penjadwalan 4 x 4 terlihat pada tabel 4.1 berikut.

Job1 Job2 Job3 Job4

1 4 2 4

Mesin 2 3 1 3 1 4 3 2

4 2 3 1

Job1 Job2 Job3 Job4

3 1 3 3

Waktu 3 3 2 3 2 3 2 3

2 4 2 4

Tabel 4.1. Tabel masalah penjadwalan 4 x 4

Contoh output masalah penjadwalan 4 x 4 (lampiran output) dilakukan dengan ukuran populasi = 10, banyaknya iterasi = 50, Pcross = 0.25 dan Pmut = 0.01, mencapai nilai minimum pada generasi ke-26 dengan nilai fitnes 14 satuan waktu. Proses persilangan / crossover terjadi pada generasi 5, 6, 7, 8, 10, 11, 13, 15, 19, 25, 31, 37 dan 43, sedangkan proses mutasi tidak terjadi. Dan salah satu jadwal yang dapat dikerjakan adalah 1 3 0 2

1 3 0 4

1 3 0 4

2 1 0 4

2 1 4 0

3 1 4 0

3 4 2 0

0 4 2 3

0 4 2 3

4 2 1 3

4 2 1 0

4 2 1 0

4 2 3 1

0 0 3 1

Didapatkan total waktu yang diperlukan untuk memproses seluruh job dari mulai diprosesnya job awal hingga job akhir selesai diproses adalah sebanyak 14 satuan waktu, dapat digambarkan dalam bentuk Gantt-Chart seperti pada gambar 4.2 berikut.


M1

J1

M2

J3

J2

J3

J4

J1

M3

J4

J4

M4 J 2

J2

J2

J1

J4

J3

3

2

1

J3

4

5

6

7

8

J1

9

10

11

12

13

14

waktu

Gambar 4.2. Representasi Gantt-Chart untuk masalah penjadwalan 4 x 4

Hasil penelitian dari program bila pengambilan parent untuk dikenai proses mutasi, dipilih yang mempunyai nilai fitnes terburuk. Tabel masalah penjadwalan 6 x 6 terlihat pada tabel 4.2 berikut.

Job1 Job2 Job3 Job4 Job5 Job6

3 2 3 2 3 2

1 3 4 1 2 4

Mesin 2 4 5 6 6 1 3 4 5 6 6 1

6 1 2 5 1 5

5 4 5 6 4 4

Job1 Job2 Job3 Job4 Job5 Job6

1 8 5 5 9 3

3 5 4 5 3 3

Waktu 6 7 1 5 8 9 5 3 5 4 9 10

3 5 1 8 3 4

6 4 7 9 1 1

Tabel 4.2. Tabel masalah penjadwalan 6 x 6

Penyelesaian masalah penjadwalan Job-Shop 6 x 6 dengan ukuran populasi = 10, banyaknya iterasi = 200 dan percobaan dirunning sebanyak 20 kali. Setelah melakukan pengujian untuk masalah penjadwalan Job-Shop 6x 6, didapatkan solusi optimum (waktu penyelesaian yang paling minimum) adalah 51 satuan waktu. Hasil yang diperoleh jika dirunning berdasarkan probabilitas crossover:


a. Probabilitas Crossover, Pcross=0.25

Cross

Mutasi

0.25

0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.1

Banyaknya Percobaan 3 3 6 8 6 1 4 6 5 5

Tabel 4.3 Hasil penelitian masalah 6x6, Pcross=0.25 dari 20 kali percobaan.

Grafik Probelm6, Pcross=0.25 10 8 Perco baan

Probabilitas

6 4 2 0 0

0.02

0.04

0.06

0.08

0.1

0.12

Probabilitas Mutasi

Grafik 4.1 Grafik hasil penelitian masalah 6 x 6, Pcross=0.25

Dari grafik 4.1 di atas terlihat bahwa percobaan terbanyak untuk mendapatkan solusi optimum terjadi jika Pcross=0.25 maka Pmut=0.04 b. Probabilitas Crossover, Pcross=0.30

Cross

Mutasi

0.3

0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.1



Grafik Problem6, Pcross=0.3 10 8 Perco b aan

Probabilitas

6 4 2 0 0

0.02

0.04

0.06

0.08

0.1

Probabilitas Mutasi


Dari grafik 4.2 di atas terlihat bahwa percobaan terbanyak untuk mendapatkan solusi optimum terjadi jika Pcross=0.3 maka Pmut=0.09 dan Pmut=0.1

0.12


c. Probabilitas Crossover, Pcross=0.35

Cross

Mutasi

0.35

0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.1



Grafik Problem6, Pcross=0.35 12 10 Perco baan

Probabilitas

8 6 4 2 0 0

0.02

0.04

0.06

0.08

0.1

0.12

Probabilitas Mutasi


Dari grafik 4.3 di atas terlihat bahwa percobaan terbanyak untuk mendapatkan solusi optimum terjadi jika Pcross=0.35 maka Pmut=0.09 d. Probabilitas Crossover, Pcross=0.40

Cross

Mutasi

0.4

0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.1



Grafik Problem6, Pcross=0.4

Percobaan

Probabilitas

14 12 10 8 6 4 2 0 0

0.02

0.04

0.06

0.08

0.1

0.12

Probabilitas Mutasi


Dari grafik 4.4 di atas terlihat bahwa percobaan terbanyak untuk mendapatkan solusi optimum terjadi jika Pcross=0.4 maka Pmut=0.08


e. Probabilitas Crossover, Pcross=0.45

Cross

Mutasi

0.45

0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.1




Probabilitas

10 8 6 4 2 0 0

0.02

0.04

0.06

0.08

0.1

0.12

Probabilitas Mutasi


Dari grafik 4.5 di atas terlihat bahwa percobaan terbanyak untuk mendapatkan solusi optimum terjadi jika Pcross=0.45 maka Pmut=0.09 f. Probabilitas Crossover, Pcross=0.50

Cross

Mutasi

0.5

0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.1



Grafik Problem6, Pcross=0.5

Perco baan

Probabilitas

16 14 12 10 8 6 4 2 0 0

0.02

0.04

0.06

0.08

0.1

0.12

Probabilitas Crossover




g. Probabilitas Crossover, Pcross=0.55

Cross

Mutasi

0.55

0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.1




Probabilitas

8 6 4 2 0 0

0.02

0.04

0.06

0.08

0.1

0.12

Probabilitas Mutasi


Dari grafik 4.7 di atas terlihat bahwa percobaan terbanyak untuk mendapatkan solusi optimum terjadi jika Pcross=0.55 maka Pmut=0.06 dan Pmut=0.07 h. Probabilitas Crossover, Pcross=0.60

Cross

Mutasi

0.6

0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.1




Probabilitas

6 4 2 0 0

0.02

0.04

0.06

0.08

0.1

0.12

Probabilitas Mutasi




i. Probabilitas Crossover, Pcross=0.65

Cross

Mutasi

0.65

0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.1



Grafik Problem6, Pcross=0.65 12 10 Perco b aan

Probabilitas

8 6 4 2 0 0

0.02

0.04

0.06

0.08

0.1

0.12

Probabilitas Mutasi


Dari grafik 4.9 di atas terlihat bahwa percobaan terbanyak untuk mendapatkan solusi optimum jika Pcross=0.65 maka Pmut=0.06 dan Pmut=0.1 j. Probabilitas Crossover, Pcross=0.7

Cross

Mutasi

0.7

0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.1




Probabilitas

10 8 6 4 2 0 0

0.02

0.04

0.06

0.08

0.1

0.12

Probabilitas Mutasi



Dari grafik 4.10 di atas terlihat bahwa percobaan terbanyak untuk mendapatkan solusi optimum terjadi jika Pcross=0.7 maka Pmut=0.09 dan Pmut=0.1 Dari grafik-grafik di atas terlihat bahwa percobaan terbanyak untuk mendapatkan solusi optimum terjadi pada Pmut=0.09 Hasil yang diperoleh jika diruning berdasarkan probabilitas mutasi: a. Probabilitas Mutasi, Pmut=0.01 Pcross

0.01

0.25 0.3 0.35 0.4 0.45 0.5 0.55 0.6 0.65 0.7


Tabel 4.13 Hasil penelitian masalah 6x6, Pmut=0.01 dari 20 kali percobaan.

Grafik Problem6, Pmut=0.01 8 Percobaan

Pmutasi

6 4 2 0 0

0.2

0.4

0.6

0.8


Grafik 4.11 Grafik hasil penelitian masalah 6 x 6, Pmut=0.01

Dari grafik 4.11 di atas terlihat bahwa percobaan terbanyak untuk mendapatkan solusi optimum terjadi jika Pmut=0.01 maka Pcross=0.5


b. Probabilitas Mutasi, Pmut=0.02 Pcross

0.02

0.25 0.3 0.35 0.4 0.45 0.5 0.55 0.6 0.65 0.7



Grafik Problem6, Pmut=0.02 10 8

Percobaan

Pmutasi

6 4 2 0 0

0.2

0.4

0.6

0.8



Dari grafik 4.12 di atas terlihat bahwa percobaan terbanyak untuk mendapatkan solusi optimum terjadi jika Pmut=0.02 maka Pcross=0.45 c. Probabilitas Mutasi, Pmut=0.03 Pcross

0.03

0.25 0.3 0.35 0.4 0.45 0.5 0.55 0.6 0.65 0.7




Pmutasi

6 4 2 0 0

0.2

0.4

0.6



Dari grafik 4.13 di atas terlihat bahwa percobaan terbanyak untuk mendapatkan solusi optimum terjadi jika Pmut=0.03 maka Pcross =0.25

0.8


d. Probabilitas Mutasi, Pmut=0.04 Pcross

0.04

0.25 0.3 0.35 0.4 0.45 0.5 0.55 0.6 0.65 0.7



Grafik Problem6, Pmut=0.04

Percobaan

Pmutasi

12 10 8 6 4 2 0 0

0.2

0.4

0.6

0.8



Dari grafik 4.14 di atas terlihat bahwa percobaan terbanyak untuk mendapatkan solusi optimum terjadi jika Pmut=0.04 maka Pcross=0.4 dan Pcross =0.7 e. Probabilitas Mutasi, Pmut=0.05 Pcross

0.05

0.25 0.3 0.35 0.4 0.45 0.5 0.55 0.6 0.65 0.7




Pmutasi

6 4 2 0 0

0.2

0.4

0.6

0.8

Probabilitas crossover




f. Probabilitas Mutasi, Pmut=0.06 Pcross

0.06

0.25 0.3 0.35 0.4 0.45 0.5 0.55 0.6 0.65 0.7




Percobaan

Pmutasi

12 10 8 6 4 2 0 0

0.2

0.4

0.6

0.8



Dari grafik 4.16 di atas terlihat bahwa percobaan terbanyak untuk mendapatkan solusi optimum terjadi jika Pmut=0.06 maka Pcross=0.55, Pcross =0.65 dan Pcross =0.7 g. Probabilitas Mutasi, Pmut=0.07 Pcross

0.07

0.25 0.3 0.35 0.4 0.45 0.5 0.55 0.6 0.65 0.7




Percobaan

Pmutasi

12 10 8 6 4 2 0 0

0.2

0.4

0.6

0.8





h. Probabilitas Mutasi, Pmut=0.08 Pcross

0.08

0.25 0.3 0.35 0.4 0.45 0.5 0.55 0.6 0.65 0.7




Pmutasi

10 5 0 0

0.2

0.4

0.6

0.8



Dari grafik 4.18 di atas terlihat bahwa percobaan terbanyak untuk mendapatkan solusi optimum terjadi jika Pmut=0.08 maka Pcross=0.4 i. Probabilitas Mutasi, Pmut=0.09 Pcross

0.09

0.25 0.3 0.35 0.4 0.45 0.5 0.55 0.6 0.65 0.7




Pmutasi

10 5 0 0

0.2

0.4

0.6

0.8





j. Probabilitas Mutasi, Pmut=0.1 Pcross

0.1

0.25 0.3 0.35 0.4 0.45 0.5 0.55 0.6 0.65 0.7




Pmutasi

10 5 0 0

0.2

0.4

0.6

0.8

Probabilitas crossover


Dari grafik 4.20 di atas terlihat bahwa percobaan terbanyak untuk mendapatkan solusi optimum terjadi jika Pmut=0.1 maka Pcross=0.7 Untuk mendapatkan solusi optimum jika Pmut=0.09 berdasarkan grafik 4.19 maka Pcross=0.5


BAB V PENUTUP

A.

KESIMPULAN Dari hasil penelitian Algoritma Genetika pada masalah penjadwalan Job-shop, terdapat beberapa kesimpulan yang dapat diambil, yaitu: 1.

Algoritma Genetika dirancang dan diimplementasi pada umumnya memberikan solusi yang mendekati optimal. Setelah melakukan pengujian dan memperoleh hasilnya, dapat dikatakan Algoritma Genetika bekerja dengan baik untuk mendapatkan solusi optimal (meminimumkan waktu penyelesaian).

2.

Setelah melakukan percobaan, diduga untuk menyelesaikan masalah penjadwalan Job-Shop jika menggunakan parameter uk_pop=10, banyaknya generasi = 100, maka probabilitas crossover dan mutasi yang tepat untuk dijadikan parameter adalah Pcross=0.5 dan Pmut=0.09. Hasil ini tidak mutlak karena penyelesaian menggunakan Algoritma Genetika pada prinsipnya menggunakan kaidah pemilihan secara random/acak.

B.

SARAN Dari hasil penelitian Algoritma Genetika pada masalah penjadwalan Job-Shop, terdapat beberapa saran yang dapat diambil, yaitu:

57


1.

Untuk penelitian selanjutnya, representasi kromosom dapat digunakan dalam bentuk lain, seperti Job-based representation, Preference-listbased

representation,

Priority-rule-based

Job-pair-relation-based representation,

representation,

Disjunctive-graph-based

representation, Completion-time-based representation,

Machine-

based representation atau Random key representation. Karena dimungkinkan dengan bentuk representasi yang lain jadwal yang dihasilkan

dapat

lebih

optimal

dibanding

operation-based

representation. 2.

Untuk penelitian selanjutnya, dapat digunakan operator persilangan / crossover metode lain, misalnya job-based order crossover, partialmapped crossover, atau yang lainnya. Dan operasi mutasi juga dapat dilakukan dengan metode lain, misalnya inversion, insersion, atau reciprocal exchange mutation.

3.

Untuk penelitian yang selanjutnya, input job, mesin dan operasi dapat dibuat tidak sama.


DAFTAR PUSTAKA

Gen, Mitsuo & Cheng, Runwei. (1997). Genetic Algorithms And Engingering Design. NewYork: John Wiley & Sons. Inc. http://bdg.centrin.netid/~budskman/ga.htm, diakses pada tanggal 1 September 2005. Kusumadewi,Sri. (2003). Artificial Intelligence (Teknik dan Aplikasinya). Yogyakarta: Graha Ilmu. Moon,I & Lee,J. (2000). Genetic Algorithm Application to the Job Shop Scheduling Problem with Alternative Routings.Brain Korea 21 Logistics Team Indusrial Engineering / Pusan National University. http://logistics.ie.pusan.ac.kr/bk21/pdf/jeLee,pdf Obitko, M.(1998).Introduction to Genetic Algorithms. http://cs.felk.cvut.cz/~xobitko/ga Saputro,Nico & Yento. (2004). Pemakaian Algoritma Genetika Untuk Penjadwalan Job Shop Dinamis Non Deterministik. Jurusan Ilmu Komputer Universitas Katolik Parahyangan. http://puslit.petra.ac.id/journals/industrial Sharma,Bhuvan & Yao,Xin. (2001). Characteristing Genetic Algorithm Approaches to Job Shop Scheduling. www.cems.uwe.ac.uk/~bsharma/papers/Bhuvan_Xin_Job_Shop_GA.pdf Suyanto. (2005). Algoritma Genetika dalam Matlab. Yogyakarta:Andi. Yamada,Takeshi & Nakano,Ryohei. (1997). Genetic Algorithms for Job-Shop Scheduling Problems. Proceedings of Modern Heuristic for Decision Support. London.

59


Procedure program untuk memanggil function-function function program clear; clc; fprintf('===============================================\n') fprintf('Program untuk menyelesaikan masalah penjadwalan JOB-SHOP dengan ALGORITMA GENETIKA\n') fprintf('

Jumlah job, mesin dan operasi sama\n')

fprintf('

Input populasi adalah 10 sampai 50\n')

fprintf('

Input generasi adalah 10 sampai 500\n')

fprintf('

1. Representasi kromosom menggunakan Operation based representation\n')

fprintf('

2. Crossover menggunakan Precedence Preservative Crossover (PPX) \n')

fprintf('

3. Mutasi menggunakan job-pair exchange mutation \n')

fprintf('===============================================\n') fprintf('\n')

iterasi=0; [inputan,mesin,waktu]=problem4 fprintf('jumlah job, mesin dan operasi adalah : %d\n',inputan) uk_pop=input('Masukkan banyaknya populasi = '); Pcross=input('Masukkan probabilitas crossover(0.0 sd 1.0) = '); Pmut=input('Masukkan probabilitas mutasi(0.0 sd 1.0) = '); generasi=input('Masukkan banyaknya generasi yang akan dihasilkan: ');

%Inisialisasi Populasi [kromosom_populasi_awal,kromosom_mesin_awal,kromosom_waktu_a wal]=inisialisasi_populasi(inputan,uk_pop,mesin,waktu);


[fungsi_fitnes,job_krom]=fungsi_fitness(uk_pop,inputan,kromo som_populasi_awal,kromosom_mesin_awal,kromosom_waktu_awal); minF=min(fungsi_fitnes);

while iterasi~=generasi [urut_kromosom]=urut_krom(uk_pop,fungsi_fitnes,kromosom_ populasi_awal); populasiUrutAwal=urut_kromosom;

acak_cross=rand; if acak_cross >= Pcross %CROSSOVER [offspring_crossover]=crossover(inputan,uk_pop,fung si_fitnes,kromosom_populasi_awal); else [offspring_crossover]=[]; End

acak_mut=rand; if acak_mut==Pmut %MUTASI [offspring_mutasi]=mutasi(inputan,uk_pop,fungsi_fit nes,kromosom_populasi_awal); %[offspring_mutasi]=mutasi_rand(inputan,uk_pop,krom osom_populasi_awal); else [offspring_mutasi]=[]; end [offspring_all]=[offspring_crossover;offspring_mutasi];

%SELEKSI [A,B]=size(offspring_all);


if A>=1 [off_all_mesin,off_all_waktu]=carimesin_waktu(input an,offspring_all,mesin,waktu); [fitnes_off_all]=fungsi_fitness(A,inputan,offspring _all,off_all_mesin,off_all_waktu);

t=find(fitnes_off_all<=minF); indek=t; [c,d]=size(t); if t==find(fitnes_off_all<=minF) populasiUrutAwal(1:c,:)=[offspring_all( indek,:)]; end kromosom_populasi_awal=[populasiUrutAwal]; else kromosom_populasi_awal=[populasiUrutAwal]; end

[krom_mesin,krom_waktu]=carimesin_waktu(inputan,kromosom _populasi_awal,mesin,waktu); kromosom_mesin_awal=krom_mesin; kromosom_waktu_awal=krom_waktu;

[fungsi_fitnes,job_krom]=fungsi_fitness(uk_pop,inputan,k romosom_populasi_awal,kromosom_mesin_awal,kromosom_waktu _awal); [krom_bantu]=urut_krom(uk_pop,fungsi_fitnes,kromosom_pop ulasi_awal); [kromBantu_mesin,kromBantu_waktu]=carimesin_waktu(inputa n,kromosom_populasi_awal,mesin,waktu); [fitnesKrom_bantu,job_krom_bantu]=fungsi_fitness(uk_pop, inputan,krom_bantu,kromBantu_mesin,kromBantu_waktu); krom_ambil=krom_bantu(uk_pop,:); minF=min(fungsi_fitnes);


bantu(iterasi+1)=minF; m=bantu'; iterasi=iterasi+1; end

minG=min(m); krom_ambil=krom_bantu(uk_pop,:); [kromAmbil_mesin,kromAmbil_waktu]=carimesin_waktu(inputan,kr om_ambil,mesin,waktu); [fitnesKrom_bantu,job_kromAmbil]=fungsi_fitness(uk_pop,input an,krom_bantu,kromBantu_mesin,kromBantu_waktu);

JADWAL = job_kromAmbil fprintf('\nDengan nilai fitness

: %d satuan waktu',minG)


Procedure untuk membuat populasi awal %=========================================================== %Membangkitkan sejumlah uk_pop kromosom %Jumlah job, mesin dan operasi sama % %Masukan: % inputan = jumlah job, mesin dan operasi % uk_pop = banyaknya kromosom awal atau banyaknya populasi % mesin = input mesin % waktu = input waktu % %Keluaran: % kromosom_populasi_awal = kromosom populasi awal % kromosom_mesin_awal = kromosom mesin % kromosom_waktu_awal = kromosom waktu %=========================================================== function [kromosom_populasi_awal,kromosom_mesin_awal,kromosom_waktu_a wal]=inisialisasi_populasi(inputan,uk_pop,mesin,waktu) panjang_kromosom=inputan*inputan; kromosom_populasi_awal=[]; kromosom_mesin_awal=[]; kromosom_waktu_awal=[]; for j=1:uk_pop jum_gen=zeros(1,inputan); k=1; while k<=panjang_kromosom job_krom=randint(1,1,[1 inputan]); if jum_gen(1,job_krom) < inputan kromosom_populasi(1,k)=job_krom; jum_gen(1,job_krom)=jum_gen(1,job_krom)+1; kromosom_mesin(1,k)=mesin(job_krom,jum_gen(1,jo b_krom)); kromosom_waktu(1,k)=waktu(job_krom,jum_gen(1,jo b_krom)); k=k+1; end end kromosom_populasi_awal=[kromosom_populasi_awal;kromosom_popu lasi]; kromosom_mesin_awal=[kromosom_mesin_awal;kromosom_mesin]; kromosom_waktu_awal=[kromosom_waktu_awal;kromosom_waktu]; end


Procedure untuk menghitung fungsi fitnes %=========================================================== %Mengevaluasi kromosom sehingga didapatkan nilai fitnesnya % %Masukan : % uk_pop = banyaknya kromosom awal atau banyaknya populasi % inputan = jumlah job, mesin dan operasi % mesin = input mesin % waktu = input waktu % %Keluaran : % fungsi_fitnes = nilai fitnes dari masing-masing kromosom % job_krom = jadwal yang mungkin belum optimal %=========================================================== function [fungsi_fitnes,job_krom]=fungsi_fitness(uk_pop,inputan,job_p opulasi,mesin,waktu) panjang_kromosom=inputan*inputan; min=10000; for i=1:uk_pop, Fitnes=[]; kendala_mesin=zeros(1,inputan); kendala_job=zeros(1,inputan); for j=1:panjang_kromosom, b=job_populasi(i,j); c=mesin(i,j); d=waktu(i,j); m=kendala_job(1,b); n=kendala_mesin(1,c); o=max(m,n); Fitnes(c,o+1:o+d)=b; kendala_mesin(1,c)=o+d; kendala_job(1,b)=o+d; end [p,q]=size(Fitnes); fungsi_fitnes(i,1)=q; if q<min, min=q; job_krom=Fitnes; end end


Procedure untuk melakukan proses persilangan / crossover %=========================================================== %Memindah-silangkan bagian kromosom parent yang telah dipilih secara acak untuk %menghasilkan kromosom baru, yaitu kromsom anak. %Proses persilangan ini menggunakan Precedence Preservative Crossover (PPX) % %Masukan: % inputan = job,mesin % uk_pop = banyaknya populasi % kromosom_populasi_awal = Populasi kromosom sebelumnya % %Keluaran: % offspring_crossover = Populasi baru kromosom setelah di crossover % %Contoh: % P1 : 3 2 2 3 1 1 3 1 2 % acak : 0 1 1 1 0 0 0 1 1 % P2 : 2 3 3 2 1 3 1 1 2 % Offspring : 3 2 3 2 1 1 3 1 2 %=========================================================== function [offspring_crossover]=crossover(inputan,uk_pop,fungsi_fitnes ,kromosom_populasi_awal) n=inputan*inputan; for i=1:uk_pop-1 for j=i+1:uk_pop if fungsi_fitnes(i,:) < fungsi_fitnes(j,:) temp_fitnes1=fungsi_fitnes(i,:); temp_krom=kromosom_populasi_awal(i,:); fungsi_fitnes(i,:)=fungsi_fitnes(j,:); kromosom_populasi_awal(i,:)=kromosom_populasi_a wal(j,:); fungsi_fitnes(j,:)=temp_fitnes1; kromosom_populasi_awal(j,:)=temp_krom; end end end urut_kromosom=[kromosom_populasi_awal]; orang_tua=urut_kromosom(uk_pop-1:uk_pop,:); parent=[orang_tua(1,:); orang_tua(2,:)]; acak=randint(1,n,[0 1]);


for a=1:n if (acak(1,a)==0) x=1; while (orang_tua(1,x)==0) x=x+1; end acak1=orang_tua(1,x); y=1; while (orang_tua(2,y)~=acak1) y=y+1; end orang_tua(1,x)=0; orang_tua(2,y)=0; anak(1,a)=acak1; else x=1; while (orang_tua(2,x)==0) x=x+1; end acak1=orang_tua(2,x); y=1; while (orang_tua(1,y)~=acak1) y=y+1; end orang_tua(2,x)=0; orang_tua(1,y)=0; anak(1,a)=acak1; end end offspring_crossover=anak;


Procedure untuk melakukan proses mutasi %=========================================================== %Skema Mutasi menggunakan Job-pair exchange mutation %Pengambilan parent untuk mutasi diambil kromosom yang mempunyai fitnes terbaik % %Masukan: % inputan = job,mesin % uk_pop = banyaknya populasi % kromosom_populasi_awal = populasi kromosom sebelumnya % fungsi_fitnes = nilai fitnes masing-masing kromosom % %Keluaran: % offspring = kromosom hasil mutasi % %Contoh: % Parent : 1 2 3 2 1 3 1 3 2 % posisi : 1 dan 4 % Offspring : 2 2 3 1 1 3 1 3 2 %=========================================================== function [offspring_mutasi]=mutasi(inputan,uk_pop,fungsi_fitnes,kromo som_populasi_awal) z=inputan*inputan; for i=1:uk_pop-1 for j=i+1:uk_pop if fungsi_fitnes(i,:) < fungsi_fitnes(j,:) temp_fitnes1=fungsi_fitnes(i,:); temp_krom=kromosom_populasi_awal(i,:); fungsi_fitnes(i,:)=fungsi_fitnes(j,:); kromosom_populasi_awal(i,:)=kromosom_populasi_a wal(j,:); fungsi_fitnes(j,:)=temp_fitnes1; kromosom_populasi_awal(j,:)=temp_krom; end end end urut=[kromosom_populasi_awal]; parent_mutasi=urut(1,:); pos=randint(1,2,[1 z]); if pos(1,1)==pos(1,2) pos=randint(1,2,[1 z]); end


a=parent_mutasi(1,pos(1,1)); parent_mutasi(1,pos(1,1))=parent_mutasi(1,pos(1,2)); parent_mutasi(1,pos(1,2))=a; offspring_mutasi=[parent_mutasi];

Procedure untuk mengurutkan kromosom berdasarkan nilai fitnesnya dari yang terbesar hinga terkecil %=========================================================== %Urutkan kromosom berdasarkan nilai fungsi fitnesnya % %Masukan: % uk_pop = banyaknya populasi % kromosom_populasi_awal = populasi kromosom sebelumnya % fungsi_fitnes = nilai fitnes masing-masing kromosom % %Keluaran: % urut_kromosom = kromosom yang telah diurutkan berdasarkan % nilai fitnesnya dari yang terbesar hingga yang terkecil % %=========================================================== function [urut_kromosom]=urut_krom(uk_pop,fungsi_fitnes,kromosom_popu lasi_awal) for i=1:uk_pop-1 for j=i+1:uk_pop if fungsi_fitnes(i,:) < fungsi_fitnes(j,:) temp_fitnes1=fungsi_fitnes(i,:); temp_krom=kromosom_populasi_awal(i,:); fungsi_fitnes(i,:)=fungsi_fitnes(j,:); kromosom_populasi_awal(i,:)=kromosom_populasi_awal(j,:); fungsi_fitnes(j,:)=temp_fitnes1; kromosom_populasi_awal(j,:)=temp_krom; end end end urut_kromosom=[kromosom_populasi_awal];


Procedure untuk mencari kromosom mesin dan kromosom waktu dari populasi baru %=========================================================== %Dari populasi yang dihasilkan akan dicari kromosom mesin dan kromosom waktunya % %Masukan : % inputan = jumlah job, mesin dan operasi % populasi_baru = input populasi baru % mesin = input mesin % waktu = input waktu % %Keluaran : % offspring_mesin = kromosom mesin dari populasi baru yang terbentuk % ofspring_waktu = kromosom mesin dari populasi baru yang terbentuk % %=========================================================== function [offspring_mesin,offspring_waktu]=carimesin_waktu(inputan,po pulasi_baru,mesin,waktu) [p,q]=size(populasi_baru); for b=1:p I=ones(1,inputan); for a=1:q temp=populasi_baru(b,a); K=I(1,temp); offspring_mesin(b,a)=mesin(temp,K); offspring_waktu(b,a)=waktu(temp,K); I(1,temp)=I(1,temp)+1; end end


Contoh Output untuk masalah penjadwalan 4 x 4 (Tabel 4.1) ============================================================ Program untuk menyelesaikan masalah penjadwalan JOB-SHOP dengan ALGORITMA GENETIKA Jumlah job, mesin dan operasi sama Input populasi adalah 10 sampai 50 Input generasi adalah 10 sampai 500 1. Representasi kromosom menggunakan Operation based representation 2. Crossover menggunakan Precedence Preservative Crossover (PPX) 3. Mutasi menggunakan job-pair exchange mutation ============================================================ jumlah job, mesin dan operasi adalah : 4 Masukkan banyaknya populasi = 50 Masukkan probabilitas crossover(0.0 sd 1.0) = 0.25 Masukkan probabilitas mutasi (0.0 sd 1.0) = 0.01 Masukkan banyaknya generasi yang akan dihasilkan: 50 GENERASI KE- 1 offspring_crossover = [] offspring_mutasi = [] minF = 17 GENERASI KE- 2 offspring_crossover = [] offspring_mutasi = [] minF = 17 GENERASI KE- 3 offspring_crossover = [] offspring_mutasi = [] minF = 17 GENERASI KE- 4 offspring_crossover = [] offspring_mutasi = []


minF = 17 GENERASI KE- 5 offspring_crossover = 1 3 2 2 2 4 3 4

1

3

4

1

3

4

2

1

2

1

3

1

4

3

1

2

4

1

1

4

3

1

3

2

4

1

1

4

3

1

3

2

2

1

1

4

3

3

2

1

offspring_mutasi = [] minF = 17 GENERASI KE- 6 offspring_crossover = 1 2 4 4 3 2 3 4 offspring_mutasi = [] minF = 17 GENERASI KE- 7 offspring_crossover = 1 2 3 4 2 2 4 3 offspring_mutasi = [] minF = 17 GENERASI KE- 8 offspring_crossover = 1 2 3 4 2 4 3 2 offspring_mutasi = [] minF = 17 GENERASI KE- 9 offspring_crossover = [] offspring_mutasi = [] minF = 17 GENERASI KE- 10 offspring_crossover = 1 3 2 4 2 4 3 4 offspring_mutasi = [] minF = 17


GENERASI KE- 11 offspring_crossover = 2 1 4 4 3 2 3 offspring_mutasi = [] minF = 17

2

4

1

1

4

3

1

3

2

4

1

3

3

1

4

2

1

GENERASI KE- 12 offspring_crossover = [] offspring_mutasi = [] minF = 17 GENERASI KE- 13 offspring_crossover = 1 2 3 4 4 2 3 2 offspring_mutasi = [] minF = 17 GENERASI KE- 14 offspring_crossover = [] offspring_mutasi = [] minF = 17 GENERASI KE- 15 offspring_crossover = 2 1 3 2 2 4 3 1 offspring_mutasi = [] minF = 17 GENERASI KE- 16 offspring_crossover = [] offspring_mutasi = [] minF = 17

4

4

3

3

1

4

1

2


GENERASI KE- 17 offspring_crossover = [] offspring_mutasi = [] minF = 17 GENERASI KE- 18 offspring_crossover = [] offspring_mutasi = [] minF = 17 GENERASI KE- 19 offspring_crossover = 2 1 4 4 3 2 3 4 offspring_mutasi = [] minF = 17 GENERASI KE- 20 offspring_crossover = [] offspring_mutasi = [] minF = 17 GENERASI KE- 21 offspring_crossover = [] offspring_mutasi = [] minF = 17 GENERASI KE- 22 offspring_crossover = [] offspring_mutasi = [] minF = 17 GENERASI KE- 23 offspring_crossover = []

2

1

1

4

3

3

1

2


offspring_mutasi = [] minF = 17 GENERASI KE- 24 offspring_crossover = [] offspring_mutasi = [] minF = 17 GENERASI KE- 25 offspring_crossover = 1 3 2 2 2 4 4 3 offspring_mutasi = [] minF = 17 GENERASI KE- 26 offspring_crossover = 2 4 1 4 3 2 3 2 offspring_mutasi = [] minF = 14

4

1

3

1

3

4

2

1

1

3

4

1

3

4

1

2

2

1

1

3

4

1

3

2

GENERASI KE- 27 offspring_crossover = [] offspring_mutasi = [] minF = 14 GENERASI KE- 28 offspring_crossover = [] offspring_mutasi = [] minF = 14 GENERASI KE- 29 offspring_crossover = 2 4 1 4 3 2 3 4 offspring_mutasi = []


minF = 14 GENERASI KE- 30 offspring_crossover = [] offspring_mutasi = [] minF = 14 GENERASI KE- 31 offspring_crossover = 2 4 1 4 3 2 3 2 offspring_mutasi = [] minF = 14 GENERASI KE- 32 offspring_crossover = [] offspring_mutasi = [] minF = 14 GENERASI KE- 33 offspring_crossover = [] offspring_mutasi = [] minF = 14 GENERASI KE- 34 offspring_crossover = [] offspring_mutasi = [] minF = 14 GENERASI KE- 35 offspring_crossover = [] offspring_mutasi = [] minF = 14

1

3

4

1

4

1

3

2


GENERASI KE- 36 offspring_crossover = [] offspring_mutasi = [] minF = 14 GENERASI KE- 37 offspring_crossover = 2 4 1 4 3 2 3 2 offspring_mutasi = [] minF = 14 GENERASI KE- 38 offspring_crossover = [] offspring_mutasi = [] minF = 14 GENERASI KE- 39 offspring_crossover = [] offspring_mutasi = [] minF = 14 GENERASI KE- 40 offspring_crossover = [] offspring_mutasi = [] minF = 14 GENERASI KE- 41 offspring_crossover = [] offspring_mutasi = [] minF = 14 GENERASI KE- 42 offspring_crossover = []

1

3

4

1

3

4

1

2


offspring_mutasi = [] minF = 14 GENERASI KE- 43 offspring_crossover = 2 4 1 4 3 2 3 2 offspring_mutasi = [] minF = 14 GENERASI KE- 44 offspring_crossover = [] offspring_mutasi = [] minF = 14 GENERASI KE- 45 offspring_crossover = [] offspring_mutasi = [] minF = 14 GENERASI KE- 46 offspring_crossover = [] offspring_mutasi = [] minF = 14 GENERASI KE- 47 offspring_crossover = [] offspring_mutasi = [] minF = 14 GENERASI KE- 48 offspring_crossover = [] offspring_mutasi = []

1

3

4

1

4

1

3

2


minF = 14 GENERASI KE- 49 offspring_crossover = [] offspring_mutasi = [] minF = 14 GENERASI KE- 50 offspring_crossover = [] offspring_mutasi = [] minF = 14

JADWAL = 1 3 0 2

1 3 0 4

1 3 0 4

2 1 0 4

2 1 4 0

3 1 4 0

3 4 2 0

Dengan nilai fitness

0 4 2 3

0 4 2 3

4 2 1 3

4 2 1 0

4 2 1 0

4 2 3 1

0 0 3 1

: 14 satuan waktu

IMPLEMENTASI ALGORITMA GENETIKA UNTUK MASALAH PENJADWALAN JOB-SHOP

Recommend Documents