implementasi algoritma genetika untuk masalah … fileimplementasi algoritma genetika untuk masalah...

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

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

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.13 Hasil penelitian masalah 6 x 6, Pmut = 0.01............................ 51





xv






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.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








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


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 Job-

Shop, 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


3

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. Proses-

proses 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


4

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.


5

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.


6

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.


7

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 Job-

Shop. 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


9

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.


10

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.


11

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.


12

Teori dasar evolusi tersebut bila diimplementasikan dalam bentuk

algoritma genetika, maka diharapkan mampu menyelesaikan masalah-

masalah 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.


13

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

genetika

Keterangan.

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


14

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.


15

Ilustrasi Algoritma Genetika

mutation

0011011001

0011001001

crossover

1100101010

1011101110

1100101110 1011101010

solutions

evaluation

1100101110 1011101010 0011001001

offspring

fitness computation

decoding

1100101010 1011101110 0011011001 1100110001

chromosomes

selection

solutions encoding

new population

Gambar 2.1. Ilustrasi Algoritma Genetika


16

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.


17

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.


18

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

Kromosom 2

1 0 1 0 1 0 0 1

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


19

dalam suatu urutan. Gambar 2.3 merupakan contoh kromosom

dengan pengkodean permutasi.

Kromosom 1

Kromosom 2

1 3 4 2 6 5 7 8

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

Kromosom 2

1.2 5.6 0.3 2.6 4.5 3.7 1.4

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


20

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 /

y5

( + 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:


21

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 Nilai Fitnes Probabilitas K1 1 0.25 K2 2 0.5 K3 0.5 0.125 K4 0.5 0.125

Jumlah 4 Gambar 2.6 Contoh penggunaan metode seleksi roda roulette.

K1 K3 K4

K2

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


22

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 Fitnes Fitnes Baru

B D E C A

5 5 5 10 15

1 2 3 4 5

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


23

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


24

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


25

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.


26

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.


27

1 1 0 0 1 1 Kromosom sebelum mutasi

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.


28

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.


29

Sebagai contoh penjadwalan 3 job dan 3 mesin (Yamada dan

Nakano, 1997)

Tabel 2.2: masalah 3 x 3

Mesin Waktu Job 1 1 2 3 Job 1 3 3 3 Job 2 1 3 2 Job 2 2 3 4 Job 3 2 1 3 Job 3 3 2 1

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.

M 1

J 1

J 2 J 3

M 2

J 3 J 1 J 2

M 3

J 2 J 1 J 3

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

10 waktu 8 12 6 4 2 0


30

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.


31

Hubungan jadwal Semiactive, Active dan Nondelay diperlihatkan

oleh diagram Venn pada gambar 2.11 berikut:

*opt

Semi-active

active

nondelay

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


33

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

, 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.

[ 3 1 3 2 1 1 2 2 3 ]

Kromosom [ ]3 1 3 2 1 1 2 2 3 [ ]3 1 3 2 1 1 2 2 3 [ ]3 1 3 2 1 1 2 2 3

Mesin 1 2 3 1 3 2 2 1 3 (a) (b) (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

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


34

Kromosom [ ]3 1 3 2 1 1 2 2 3

Mesin [ ]3 3 1 2 2 1 3 1 2

Gambar 3.2 Urutan proses dari job pada mesin1

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

, untuk mesin2 adalah 312 −− 213 −− , dan untuk mesin3 adalah .

Dapat juga diringkas seperti pada gambar dibawah ini.

312 −−

M1 J2 J1 J3

M2 J3 J1 J2

M3 J2 J1 J3

2 5 83 7 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


35

gen-gen sebanyak jumlah job dikali jumlah mesin yang dimasukkan. Tabel 3.2

merupakan contoh inisialisasi populasi awal sebanyak 10 kromosom.

Kromosom ke- Bentuk representasinya

k1 3 2 1 3 2 2 3 1 1 k2 3 1 2 1 3 3 2 1 2 k3 2 1 1 2 2 3 3 3 1 k4 3 1 3 1 3 2 2 2 1 k5 1 2 2 1 2 1 3 3 3 k6 3 1 1 2 1 3 3 2 2 k7 3 1 3 1 3 2 1 2 2 k8 3 3 3 2 2 1 1 2 1 k9 3 3 2 1 1 1 2 2 3 k10 3 3 2 2 3 2 1 1 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.


36

Secara matematis, fungsi fitnes untuk mencari waktu yang minimum

untuk menyelesaikan job dapat dituliskan sebagai berikut:

∑= ≤≤

n

1i}ikC {

mk1max Min

Dimana:

= waktu penyelesaian job i pada mesin k Cik

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.


37

Kromosom ke-

Bentuk representasinya Fitnes

k1 3 2 1 3 2 2 3 1 1 21 k2 3 1 2 1 3 3 2 1 2 19 k3 2 1 1 2 2 3 3 3 1 18 k4 3 1 3 1 3 2 2 2 1 17 k5 1 2 2 1 2 1 3 3 3 16 k6 3 1 1 2 1 3 3 2 2 16 k7 3 1 3 1 3 2 1 2 2 14 k8 3 3 3 2 2 1 1 2 1 13 k9 3 3 2 1 1 1 2 2 3 13 k10 3 3 2 2 3 2 1 1 1 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.


38

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.


39

Ilustrasi proses persilangan terlihat pada gambar 3.4.

P 3 2 2 3 1 1 3 1 2

Gambar 3.4 Ilustrasi proses persilangan

1

H 0 1 1 1 0 0 0 1 1

2 3 3 2 1 3 1 1 2 P2

O 3 2 3 2 1 1 3 1 2

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.


40

p [ 3 2 1 2 3 4 1 2 4 4 1 3 4 1 2 3 ] 1

o [ 3 2 1 4 3 4 1 2 4 4 1 3 2 1 2 3 ] 1

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


42

Mulai

Input parameter Job-Shop danAlgoritma Genetika(jumlah job,

mesin, operasi, ukuran populasi, Probcross, Prob mutasi, dan generasi)

k=1

Inisialisasi populasi

Evaluasi populasi

Crossover

Mutasi

k=jumlahgenerasi?

k = k+1

Selesaiya

tidak

Evaluasi Populasi

Seleksi

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

42

Mulai

Input parameter Job-Shop danAlgoritma Genetika(jumlah job,

mesin, operasi, ukuran populasi, Probcross, Prob mutasi, dan generasi)

Inisialisasi populasi

k=1

Evaluasi populasi

Crossover

Mutasi

k=jumlahgenerasi?

k = k+1

Selesaiya

tidak

Evaluasi Populasi

Seleksi


43

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


44

melakukan mutasi. Tidak ada aturan yang pasti tentang berapa

nilai parameter ini.

Tabel masalah penjadwalan 4 x 4 terlihat pada tabel 4.1 berikut.

Mesin Waktu Job1 1 2 3 4 Job1 3 3 3 2 Job2 4 1 3 2 Job2 1 2 3 4 Job3 2 1 4 3 Job3 3 2 3 2 Job4 4 3 2 1 Job4 3 2 3 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 1 1 2 2 3 3 0 0 4 4 4 4 0 3 3 3 1 1 1 4 4 4 2 2 2 2 0 0 0 0 0 4 4 2 2 2 1 1 1 3 3 2 4 4 4 0 0 0 3 3 3 0 0 1 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.


45

M1 J 1 J 2 J 3 J 4

M2 J 3 J 1 J 4 J 2

M3 J 4 J 2 J 1 J 3

M4 J 2 J 4 J 3 J 1

43 6 9 132 5 7 8 10 11 12 141 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.

Mesin Waktu Job1 3 1 2 4 6 5 Job1 1 3 6 7 3 6 Job2 2 3 5 6 1 4 Job2 8 5 1 5 5 4 Job3 3 4 6 1 2 5 Job3 5 4 8 9 1 7 Job4 2 1 3 4 5 6 Job4 5 5 5 3 8 9 Job5 3 2 5 6 1 4 Job5 9 3 5 4 3 1 Job6 2 4 6 1 5 4 Job6 3 3 9 10 4 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:


46

a. Probabilitas Crossover, Pcross=0.25

Probabilitas Cross Mutasi

BanyaknyaPercobaan

0.01 3 0.02 3 0.03 6 0.04 8 0.05 6 0.06 1 0.07 4 0.08 6 0.09 5

0.25

0.1 5

Grafik Probelm6, Pcross=0.25

0

2

4

6

8

10

0 0.02 0.04 0.06 0.08 0.1 0.12

Probabilitas MutasiPe

rcob

aan

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

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


BanyaknyaPercobaan

0.01 4 0.02 5 0.03 3 0.04 3 0.05 7 0.06 6 0.07 5 0.08 7 0.09 8

0.3

0.1 8

Grafik Problem6, Pcross=0.3

0

2

4

6

8

10

0 0.02 0.04 0.06 0.08 0.1 0.12

Probabilitas Mutasi

Perc

obaa

n




mendapatkan solusi optimum terjadi jika Pcross=0.3 maka Pmut=0.09 dan

Pmut=0.1


47

c. Probabilitas Crossover, Pcross=0.35


BanyaknyaPercobaan

0.01 6 0.02 4 0.03 3 0.04 4 0.05 4 0.06 5 0.07 8 0.08 7 0.09 10

0.35

0.1 3


0

2

4

6

8

10

12

0 0.02 0.04 0.06 0.08 0.1 0.12


rcob

aan





d. Probabilitas Crossover, Pcross=0.40


BanyaknyaPercobaan

0.01 3 0.02 3 0.03 4 0.04 10 0.05 1 0.06 5 0.07 2 0.08 12 0.09 8

0.4

0.1 6


02468

101214

0 0.02 0.04 0.06 0.08 0.1 0.12

Probabilitas Mutasi

Perc

obaa

n






48

e. Probabilitas Crossover, Pcross=0.45


BanyaknyaPercobaan

0.01 5 0.02 8 0.03 5 0.04 4 0.05 3 0.06 6 0.07 7 0.08 5 0.09 13

0.45

0.1 7


02468

101214

0 0.02 0.04 0.06 0.08 0.1 0.12

Probabilitas Mutasi

Perc

obaa

n





f. Probabilitas Crossover, Pcross=0.50


BanyaknyaPercobaan

0.01 7 0.02 4 0.03 2 0.04 4 0.05 3 0.06 5 0.07 8 0.08 7 0.09 14

0.5

0.1 5


02468

10121416

0 0.02 0.04 0.06 0.08 0.1 0.12

Probabilitas Crossover

Perc

obaa

n






49

g. Probabilitas Crossover, Pcross=0.55


BanyaknyaPercobaan

0.01 2 0.02 5 0.03 4 0.04 5 0.05 4 0.06 10 0.07 10 0.08 8 0.09 8

0.55

0.1 9


0

2

4

6

8

10

12

0 0.02 0.04 0.06 0.08 0.1 0.12

Probabilitas Mutasi

Perc

obaa

n





dan Pmut=0.07

h. Probabilitas Crossover, Pcross=0.60


BanyaknyaPercobaan

0.01 2 0.02 4 0.03 2 0.04 8 0.05 4 0.06 6 0.07 7 0.08 5 0.09 5

0.6

0.1 6


0

2

4

6

8

10

0 0.02 0.04 0.06 0.08 0.1 0.12

Probabilitas Mutasi

Perc

obaa

n






50

i. Probabilitas Crossover, Pcross=0.65


Banyaknya Percobaan

0.01 3 0.02 5 0.03 2 0.04 6 0.05 6 0.06 10 0.07 5 0.08 5 0.09 8

0.65

0.1 10


0

2

4

6

8

10

12

0 0.02 0.04 0.06 0.08 0.1 0.12


rcob

aan




mendapatkan solusi optimum jika Pcross=0.65 maka Pmut=0.06 dan

Pmut=0.1

j. Probabilitas Crossover, Pcross=0.7


BanyaknyaPercobaan

0.01 5 0.02 1 0.03 5 0.04 10 0.05 4 0.06 10 0.07 8 0.08 4 0.09 12

0.7

0.1 12


02468

101214

0 0.02 0.04 0.06 0.08 0.1 0.12

Probabilitas Mutasi

Perc

obaa

n




51


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

Pmutasi Pcross Banyaknya Percobaan

0.25 3 0.3 4 0.35 6 0.4 3 0.45 5 0.5 7 0.55 2 0.6 2 0.65 3

0.01

0.7 5

Grafik Problem6, Pmut=0.01

0

2

4

6

8

0 0.2 0.4 0.6 0.8


Perc

obaa

n

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

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


mendapatkan solusi optimum terjadi jika Pmut=0.01 maka Pcross=0.5


52

b. Probabilitas Mutasi, Pmut=0.02


0.25 3 0.3 5 0.35 4 0.4 3 0.45 8 0.5 4 0.55 5 0.6 4 0.65 5

0.02

0.7 1


02468

10

0 0.2 0.4 0.6 0.8

Probabilitas CrossoverP

erco

baan





c. Probabilitas Mutasi, Pmut=0.03


0.25 6 0.3 3 0.35 3 0.4 4 0.45 5 0.5 2 0.55 4 0.6 2 0.65 2

0.03

0.7 5


0

2

4

6

8

0 0.2 0.4 0.6 0.


Per

coba

an

8




mendapatkan solusi optimum terjadi jika Pmut=0.03 maka Pcross =0.25


53

d. Probabilitas Mutasi, Pmut=0.04


0.25 8 0.3 3 0.35 4 0.4 10 0.45 4 0.5 4 0.55 5 0.6 8 0.65 6

0.04

0.7 10


02468

1012

0 0.2 0.4 0.6 0.8


Per

coba

an




mendapatkan solusi optimum terjadi jika Pmut=0.04 maka Pcross=0.4 dan

Pcross =0.7

e. Probabilitas Mutasi, Pmut=0.05


0.25 6 0.3 7 0.35 4 0.4 1 0.45 3 0.5 3 0.55 4 0.6 4 0.65 6

0.05

0.7 4


0

2

4

6

8

0 0.2 0.4 0.6 0.8

Probabilitas crossover

Per

coba

an






54

f. Probabilitas Mutasi, Pmut=0.06


0.25 1 0.3 6 0.35 5 0.4 5 0.45 6 0.5 5 0.55 10 0.6 6 0.65 10

0.06

0.7 10


02468

1012

0 0.2 0.4 0.6 0.8

Probabilitas CrossoverPe

rcob

aan




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


0.25 4 0.3 5 0.35 8 0.4 2 0.45 7 0.5 8 0.55 10 0.6 7 0.65 5

0.07

0.7 8


02468

1012

0 0.2 0.4 0.6 0.8


Perc

obaa

n






55

h. Probabilitas Mutasi, Pmut=0.08


0.25 6 0.3 7 0.35 7 0.4 12 0.45 5 0.5 7 0.55 8 0.6 5 0.65 5

0.08

0.7 4


0

5

10

15

0 0.2 0.4 0.6 0.8

Probabilitas CrossoverPe

rcob

aan





i. Probabilitas Mutasi, Pmut=0.09


0.25 5 0.3 8 0.35 10 0.4 8 0.45 13 0.5 14 0.55 8 0.6 5 0.65 8

0.09

0.7 12


0

5

10

15

0 0.2 0.4 0.6 0.8


Per

coba

an






56

j. Probabilitas Mutasi, Pmut=0.1


0.25 5 0.3 8 0.35 3 0.4 6 0.45 7 0.5 5 0.55 9 0.6 6 0.65 10

0.1

0.7 12


0

5

10

15

0 0.2 0.4 0.6 0.8

Probabilitas crossoverPe

rcob

aan





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


58

1. Untuk penelitian selanjutnya, representasi kromosom dapat digunakan

dalam bentuk lain, seperti Job-based representation, Preference-list-

based representation, Job-pair-relation-based representation,

Priority-rule-based 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, partial-

mapped 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


60

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);


61

[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);


62

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);


63

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)


64

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_awal]=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,job_krom)); kromosom_waktu(1,k)=waktu(job_krom,jum_gen(1,job_krom));

k=k+1; end end kromosom_populasi_awal=[kromosom_populasi_awal;kromosom_populasi]; kromosom_mesin_awal=[kromosom_mesin_awal;kromosom_mesin]; kromosom_waktu_awal=[kromosom_waktu_awal;kromosom_waktu]; end


65

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_populasi,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


66

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_awal(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]);


67

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;


68

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,kromosom_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_awal(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


69

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_populasi_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];


70

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,populasi_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


71

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 = []


72

minF = 17 GENERASI KE- 5 offspring_crossover = 1 3 2 2 2 4 3 4 1 3 4 1 3 4 2 1 offspring_mutasi = [] minF = 17 GENERASI KE- 6 offspring_crossover = 1 2 4 4 3 2 3 4 2 1 3 1 4 3 1 2 offspring_mutasi = [] minF = 17 GENERASI KE- 7 offspring_crossover = 1 2 3 4 2 2 4 3 4 1 1 4 3 1 3 2 offspring_mutasi = [] minF = 17 GENERASI KE- 8 offspring_crossover = 1 2 3 4 2 4 3 2 4 1 1 4 3 1 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 2 1 1 4 3 3 2 1 offspring_mutasi = [] minF = 17


73

GENERASI KE- 11 offspring_crossover = 2 1 4 4 3 2 3 2 4 1 1 4 3 1 3 2 offspring_mutasi = [] minF = 17 GENERASI KE- 12 offspring_crossover = [] offspring_mutasi = [] minF = 17 GENERASI KE- 13 offspring_crossover = 1 2 3 4 4 2 3 2 4 1 3 3 1 4 2 1 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 4 4 3 3 1 4 1 2 offspring_mutasi = [] minF = 17 GENERASI KE- 16 offspring_crossover = [] offspring_mutasi = [] minF = 17


74

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 2 1 1 4 3 3 1 2 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 = []


75

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 4 1 3 1 3 4 2 1 offspring_mutasi = [] minF = 17 GENERASI KE- 26 offspring_crossover = 2 4 1 4 3 2 3 2 1 3 4 1 3 4 1 2 offspring_mutasi = [] minF = 14 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 2 1 1 3 4 1 3 2 offspring_mutasi = []


76

minF = 14 GENERASI KE- 30 offspring_crossover = [] offspring_mutasi = [] minF = 14 GENERASI KE- 31 offspring_crossover = 2 4 1 4 3 2 3 2 1 3 4 1 4 1 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


77

GENERASI KE- 36 offspring_crossover = [] offspring_mutasi = [] minF = 14 GENERASI KE- 37 offspring_crossover = 2 4 1 4 3 2 3 2 1 3 4 1 3 4 1 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 = []


78

offspring_mutasi = [] minF = 14 GENERASI KE- 43 offspring_crossover = 2 4 1 4 3 2 3 2 1 3 4 1 4 1 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 = []


79

minF = 14 GENERASI KE- 49 offspring_crossover = [] offspring_mutasi = [] minF = 14 GENERASI KE- 50 offspring_crossover = [] offspring_mutasi = [] minF = 14 JADWAL = 1 1 1 2 2 3 3 0 0 4 4 4 4 0 3 3 3 1 1 1 4 4 4 2 2 2 2 0 0 0 0 0 4 4 2 2 2 1 1 1 3 3 2 4 4 4 0 0 0 3 3 3 0 0 1 1 Dengan nilai fitness : 14 satuan waktu


implementasi algoritma genetika untuk masalah … fileimplementasi algoritma genetika untuk masalah...

Documents