\
APLIKASI ALGORITMA GENETIK UNTUK OPfIMASI MASALAHPENJADWALAN
FLOW-SHOP
Oleh
HENDRA GUNAWAN F03498039
2003 JURUSAN TEKNOLOGI INDUSTRIPERTANIAN FAKULTAS TEKNOLOGIPERTANIAN INSTITUTPERTANIAN BOGOR BOGOR
'U'itliout new ideas, ... numanity woufi[not aavance. U'itliout goals. ... we Iiove no reason to tninli, . 'Witliout actino, ... we can not reacli our o6jectives. .
/I
•
On qjls... , I tmn�u are very
'smart".
• 'You can 'remem6er" wliot you've dOne 6efore. • 'You can 'kam"fromyour searcn-e:rperience. • jlna you can even 'cafl" tne name oftne 6eautiJufgin for tnefirst time at generation 476". Or. qjls..., justfor tne gin (ana my parents) I detf'tcate tfiis tnesis.
(Xenara qunawan, 9darcr. 2003)
Hendra Gunawan. F03498039. Aplikasi Algoritma.Genetik. ontuk Optimasi Masalah Penjadwalan Flow-Shop. Dibawah bimbingan Yandra Arkeman dan
Hartrisari
Hardjomidjojo.2003.
RINGKASAN Masalah penjadwalan mesin produksi telah menjadi
perhatian utama para
praklisi yang berkecimpung dalam dunia industri, baik industri manufaktur maupun industri berbasis pertanian (agroindustri). Salah satu penyebabnya. adalah adanya kesulitan menemukan teknik yang tepat untuk membuat jadwal produksi yang paling bail<., paling optimal, dan memenuhi segala kriteria-kriteria penjadwalan yang ditetapkan. Teknik-teknik penyusunan jadwal produksi yang sudah ada (teknik konvensional) tidak dapat
dipakai
karena
menangani masalah
teknik-teknik
tersebut
memiliki
banyak
kelemahan
dahim
berskala besar dan komplek. Salah satu masalah yang tergolong
kompJek dan sukar dipeeahkan adalah masalah penjadwalanfo l w Algoritma genetik, sebagai salah satu teknik dalam bidang ilmu Kecerdasan Buatan (Artificial Intelligence), termasuk teknik pencarian yang bersifat robust (tangguh), adaptif, dan efisien. Dalam pencariannya. aigoritma genetik meniru proses evolusi dan perubahan struktur genetik pada makhluk hidup. Algoritma genetik sangat eocok untuk memeeahkan masalah optimasi yang sukar atau kompJek (hDrd or complex optimization
problems) yang tidak dapat dipeeahkan dengan teknik-teknik penearian dan optimasi konvensional, seperti teknik kalkulus dan teknik enumeratif. Kesukaran terjadi karena teknik-teknik konvensional tersebut sangat tidak efisien, tergantung kepada adanya fungsi turunan, dan tidak dapat menangani masalah berskala besar. Penelitian ini bertujuan untuk mengaplikasikan algoriuna genetik dalam bidang penjadwalan produksi vaitu uotuk masalah flow-shop deterministik tanpa kendala
(unconstrained-deterministic flow-shop) berskala besar. Implementasi algoritma genetik dalam program komputer menggunakan bahasa pemrograman Borland Pascal 7.0. Program yang dikembangkan disebut FShop_GA. Representasi kromosom menggunakan order-based representation, penyilangan menggunakan Partially-Mapped Crossover (PMX), mutasi menggunakan swap mutation, dan seleksi menggunakan roulette-wheel selection. Studi kasus dari
literatur
digunakan
untuk mendemonstrasikan program
FShop_GA. Dalam penelitian ini digunakan dua kasus yaitu Kasus 1 (masalah 4 job 2 mesin) dan Kasus 2 (masalah 8 job 3 mesin ). Kedua kasus tersebut merupakan persoalan yang terdapat dalam buku Intelligent Manufacturing Systems (Kusiak, 1990). -
-
Masing-masing kasus memiliki besar ruang pencarian yang berbeda yang nilainya tergantung kepada jumlah permutasijob.
24 (4!=24) sedangkan Kasus 2 40320 (81=40320). Besamya ruang
Kasus 1 memiliki besar ruang penearian memiliki ruang pencarian yang lebih besar yaitu
penearian tersebut dinyatakan dalam banyaknya jumlah kromosom. Kasus 1 digunakan untuk menguji kebenaran program algoritma genetik yang dikembangkan. Hasil penditian m<:nunj:.lkkan bah.... a algoritma g�rletik .:;angat efi:;ier. dalam memecahkan masalah flow-shop deterministik umpa kendala berskala besar. Untuk Kasus
I, algoritma genetik dapat menemukan kromosom terbaik setelah mengekplorasi
83,33%
roang pencarian. Be:>amya persentase ruang pencarian yang dieksplorasi ini menunjukkan bahwa algoritma genetik tidak eoeok untuk diterapkan pada masalah dengan ruang penearian yang keeil. Sebaliknya, pada Kasus 2, algoritma genetik dapat menemukan kromosom terbaik hanya dengan mengekplorasi
1,09%
ruang pencarian. Hal ini
membuktikan bahwa algoritma genetik sangat efisien dan coeok untuk diterapkan pada masahh dengan roang pencarian yang besar.
SUMMARY
Machine scheduling problems have become an interest topic of discussiun for they who actively involved in industrial field, including agro-industrial sector. One of the main reasons is the difficulty in fmding the best and the most appropriate method for solving the problems. Conventional methods, like calculus-based or enumerative search, could not he used because of their weakness in solving large-scale and complex machine . scheduling problems. One of them is flow-shop problems. Genetic algorithms (GAs), as one of the Artificial Intelligence tool, have proved as one of searching and optimization method that can solve large-scale and complex optimization problems efficiently. In searching the best solution, GAs work by mimicking the process of evolution and natural genetics. GAs is appropriate for solving hard or complex optimization problems that could not be solved by using conventional methods like calculus-based or enumerative-scare&. The aims of this research is applying GAs for solving WlCOnstrained large-scale flow-shop problems. For its implementation, integer number (order representation) is used for chromosome representation, PMX methods is used for crossover, swap methods is used for mutation, and roulette wheel methods is used for selection. Case study taken from reference was conducted to demonstrate the software developed- called FShop_GA. Two case namely Case 1 (4 jobs- 2 machine) and Case 2 (8 jobs - 3 machine) were taken from Kusiak (1990). Case 1 has 24 (41-24) alternative schedules in its search space and Case 2 has 40320 (8!=40320) alternative schedules in its search space. In this research, Case 1 is used to check the validity of output of FShop_ GA compared with enumerative search. The experiment shows that GAs is very efficient in solving unconstrained large scale flow-shop problems. In Case 1, GAs could found the best sokltion by exploring 83,33% of search-space. This figures that GAs is inappropriate for solving small-scale flow-shop problems. Otherwise, in Case 2, GAs can found the best solution by exploring only 1,09% of search space. This shows that GAs is very efficient and appropriate for solving large-scale flow-shop problems.
FAKULTAS TEKNOLOGIPERTANlAN INSTlTUT PERTANIAN BOGOR
APLIKASIALGORITMA GENETIK UNTUK OPTIMASI MASALAH PENJADWALAN
FLOW-SHOP
SKRIPSI
Sebagai salah satu syarat uutuk memperoleh gelar SARJANA TEKNOLOGIPERTANIAN pada Fakultas Teknologi Pertaniao Institut Pertanian Bogor
Oleb
HENDRA GUNAWAN F03498039
Dilahirkao di Jakarta pada tanggal12 April 1980
Taoggal kelulusao: 20 Jaouari 2003
Pembimbing I
1
KATA PENGANTAR
Puji dan syukur penulis panjatkan kehadirat Allah SWT karena atas segala rahmat dan karunia-Nya, penulis dapat menyelesaikan skripsi ini. Terna yang dipilih dalam penelitian ini adalah Algoritma Genetik, dengan judul Aplikasi Algoritma Genetik untuk Optimasi Masalah Penjadwalan Flow-Shop. Penulis mengucapkan terima kasih kepada semua pihak yang telah banyak membantu dalam penyelesaian skripsi ini, antara lain kepada : 1.
Dr. Ir. Yanclra Arkeman. MEng., selaku dosen pembimbin� I yang tel� "membentuk" saya dengan memberikan pengar�an dan enlightment yang sangat berharga, baik. selama perkuliahan maupun dalam penyelesaian skripsi.
2.
Dr. Ir. Hartrisari Hardjomidjojo, DEA , selaku dosen pembimbing II yang telah memberi pemikiran-pemikiran berharga tentang dasar-dasar melakukan penelitian seeara ilmiah, khususnya dalam bidang manajemen sains.
3. Ir. Tauftk Djatna selaku dosen penguji yang telah memberi masukan berharga untuk kesempumaan penyajian skripsi ini. 4.
Kedua orangtua dan adik-adik penulis (Hendri, Nina, Taufik, Fikri) yang telah memberikan perhatian, semangat, dan do'a dengan tulus ikhlas.
5.
Rekan-rekan se-bimbingan (Neng Adi, Dian Eko, Torno, Amin, Dina, Agung) atas kekompakannya selama pembimbingan.
6: Rekan-rekan se-angkatan (TIN'35) yang telah memberikan bantuan, baik bantuan
moril
maupun
materil,
dan praktikan
mata kuliah Penerapan
Komputer (TIN'36 dan TIN'37) yang !elah menambah kesibukan penulis selama perkuliahan. 7.
Rekan-rekan kelja di LINK Computer - Darmaga (Mas Ariadi, Mbak Lia, Siska, Dadan. Sahadi, Didik, Gono, Asep, Agung, Rivol, Egie, Adi Kumis, Opik, Acung, Markus) atas segala bantuan dan kerjasamanya. Semoga skripsi ini bennanfaat.
Bogor, Maret 2003 Hendra Gunawan
II
RIWAYAT IllDU P
Penulis dilahirkan di Jakarta paela tanggal 12 April 1980 sebagai anak pertama dari lima bersaudara. anak dari pasangan Madroi dan Maskah Triana. Tahun 1998 penulis lulus dari SMU Negeri 1 Balaraja, Tangerang. Pada tahun yang sarna, penulis lu:us seleksi masuk IPB meh:1.lui jaiur Undangan Seleksi Masuk IPB (USMI) dan diterima di jurusan Teknologi lndustri Pertanian, Fakultas Teknologi Pertanian. Selama
mengikuti
perkuliahan.
penulis
sempat
menjadi
asisten
matakuliab Penerapan Komputer tabun ajaran 2000/200I dan 200112002, serta pemab mengikuti Praktek Lapang selama dua bulan (I Juli
-
30 Agustus 2002) di
PT. Charoen Pokphand htdonesia, Tangerang. Paela bulan September 1999, penulis mendapat beasiswa dari Yayasan Toyota-Astra untuk tahun ajaran 199912000. mengikuti
Pada
taoggai
program
Indonesia, Jakarta.
3
Oktober
2002,
IBM-StudeDt@Work
penulis
yang
mendapat
diadakan
oteh
kesempatan PT.
IBM
iii
DAFfARISI
Halaman KATA PENGANTAR .... . ..... .. .... .. ..................... .......... ........ .......... ...... .....
1
RIWAYAT mnup ........... ......... .. ................................. ........ . ................. ..
ii
.
..
.
.
.
DAFfAR lSI
.
.
.
.................................................................... . . . . . . .......................
DAFfAR TABEL
iii
.......... ....................... ................ . ...... ...........................
v
DAFfAR GAMBAR .... ....... ......... .................................... ..... ............ ......
VI
DAFfAR LAMPIRAN ... ....... ....... ....................... ........ .. . ...... ............ ....
IX.
..
.
.
.
.
.
.
.
..
.
.
.
..
.
.
..
PENDAHULUAN ........... ..... ...... ......... ...... .......... ..... .......... ...... ...... ..
I
A. LATARBELAKANG ........................................................................
1
B. TUJUAN .............................................................................................
3
C. RUANG LINGKUP ......... . ............. ........ ......... .... .... .. .............. .......
3
II. TINJAUAN PUSTAKA ........... ... .... . ........ .......................................... .
4
A. TIPE-TIPE PROSES PRODUKSI ......... ................ .. ....... . ....... ...... .
4
I.
Flow-Shop ... . .............................................................................
4
2.
Job-Shop ... ......... . ................. .....................................................
5
B. PENJADWALAN FLOW-SHOPTANPA KENDALA .....................
6
C. ALGORlTMA GENETIK .............. ............. ............ ...... .. ... .........
8
I.
.
.
.
..
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
:
.
.
.
.
..
.
.
1.
Kelahiran Algoritrna Genetik .... ........
.... .............. ............... ...
8
2.
Prosedur Urnum Algoritma Genetik ............. ...... ....... . .....-:......
9
3.
Kornponen-kornponen Algoritrna Genetik . ............ ............... .....
12
3.1 Representasi Kromosom ......... ........ ........ .......... ................
12
3.2 Operator-operator Algoritma Genetik ........... ...... . ................
13
3.2.1 Penyilangan (Crossover)..............................................
14
3.2.2 Mutasi (Mutation) ............ ..... ............. ............. .... .......
16
3.3 Fungsi Fitness . ........ ........ . .......... ... .... . .. . ... .... . . ......... .. .. . ..
18
3.4 Seleksi dan Reproduksi ................ ........... ..................... . ...
19
3.5 Kriteria Penghentian (Stopping Criteria)...............................
20
.
...
..
.
.
..
.
.
.
..
.
.
.
.
.
..
.
..
..
.
4.
..
.
.
Perbandingan Algoritrna Genetik dengan Teknik Pencarian dan Optimasi Konvensional ............ . ................. ....... ... ........ . ...... .
.
.
.
.
.
..
.
D. PENELlTIAN TERDAHULU . ..................................... .......... ........ ..
.
,
20 24
iv
III. METODOLOGI PENELITIAN . .
A. KERANGKA PEMIKIRAN .
...
....
....
.. .
....
..
.
...
.......
....
.......
B. PENDEKATAN METODEILMIAH IV.
.
.
........
. .... . ...
..
.....
...
.
....
....
.
..
..
.....
...
... .
.....
.
.
.
.
26
....
26
....
.....
.. . . ... ..
... ..
.....
.. .
......
....
..
..
.
.
..........
27
ALGORITMA GENETIK UNTUK OPTIMASI MASALAH PENJADWALAN FLOW-SHOP............................................................ A. REPR1lSENTASI KROMOSOM
.. . .... .. .. .....
B. FUNGSI FIINESS ..... .. ...
... . ..
.
C. PENYILANGAN D. MUTASI
..
...
...
.
.... . ..
..
. ... .
.....
.
...
.....
.
...
....... .. . .
...
.
..
..
...
..
..
.
.
..
..
...
....
.. . ... .... ..
..
... ... . .. . .. .. . .
.
.
.
.
......
.
.....
......
. .... .
.
....
....
. .. ... .
.
.. . ..
... .... .
.....
...
.
. .. .. ..
..
. .. . .... ... . ..
.....
..
..
..
..
.. . .
....
..
..
.
.......
..
.....
..
....
.
...
..
..
.
...
..... ..
...
..
E.
IMPLEMENTASI DALAM BAHASA PASCAL: FShop_GA . ...
F.
STIJDI KASUS
.
l . Kasus 1 1.1
:
....
.....
.
..
..
.
. ..
33 34
39
.......
...........
.....
...
.
l . 2 Populasi Awal ... .. .
..
...
. . ..
. .
....
..
....
.......
..
.. . ..
1.3
Proses Evaluasi dan Seleksi . ... . .. .. .
1.4
Proses Penyilangan dan Mutasi ... ... .
1.5
Hasil Running Program FShop_GA
..
.
.
.
.
..
..
..
.
.......
Masalah Penjadwalan 8 Job
..
..
1.6 Efisiensi Algoritma Genetik . :
33
Masalah Penjadwalan 4 Job - 2 Mesin............................
.....
-
.
...
Proses Evaluasi dan Seleksi
.
.
..
..
..
2.4 Proses Penyilangan dan Mutasi
.......
.
.
...
. .. ..
.
.... .. ..
....
.. ..
.
..
.
.
.....
.. ..
.
.
40 40
..
.....
.
........
45
... . ... . . ... .
51
.. .. . .......... .
52
... ......... ...
52
.. . .:......................
52
..
........
...
....
.....
...
.
.
...
. . ... ..
.
..
..
...
.
..
.
..
.
....
...
..
.
.
.
.
.
.
.
... . .
...
. . .. . . .
..
.
53
56
2.6
Efisiensi Algoritma Genetik....................................................
64
2.7
Variasi Tingkat Penyilangan (Pc) ..... .. .....
..
65
2.8 Variasi Tingkat Mutasi (Pm)...................................................
68
...
.
V. KESIMPULAN DAN SARAN
.. ... . .
...
A. KESIMPULAN .. . ....... .. ..
..
.....
...
...
.
....
... ...
.
.... . .. ...
...
..
.
..
.
.
....
....
....
..
...
.
...
..
..
..
.
....
..
...
.
.
........
...
....
.... .. .
.. .. .
.
.
...
....
..
. ..
.
...
.
71 71
76
...
.
..
...
..
...
...
....
.... ...
..
.. ..
.
...
LAMPIRAN
.
.......
.
...
.. ..
... .. .. . . . ..
.
.
73
.
.
.
.
DAFTAR PUSTAKA ....................................................................................
.
.. ...
..
.
...
72
..
.... ... ..
..
.. . . .. ...
..
.. . .. . . .... ...
B. SARAN
... . ... ....
..
..
....
.... . .
.
. .. . ...
2.5 Hasil Running Program FShop_GA .
.
.. ..
.
54
....
..... ..
......
.
......
..
.
...
...
42
..
......
...
.....
.
. .. .. .. ".................
. . ... ... ..
...
..
... . ..
...
3 Mesin
2.3
.. ..
..
40
.
Populasi Awal
....
.
..
...... .
...
2.2
.
....
. ..... .... .
..
Parameter-parameter Algoritma Genetik ... ..
.
....
...... ... ... ......
2.1
.
....
.....
...
...
..
. . . ..
..
32
39
...
Parameter-parameter Algoritma Genetik . .
2. Kasus 2
..
31
.
.......
.
.
31
.
......
.
.
..
.
.
.
..................................................................................................
v
DAFfAR TABEL
Halaman Tabel 1.
Perbandingan nilai makespan antara algoritma genetik dengan teknik heuristik 1ainnya (Gen dan Cheng, 1997)
..............................
Tabel 2.
Waktu pemrosesanjobdi setiap mesinWltukKasus 1
Tabel 3.
Daftar kromosom terbaik yang pemah dihasilkan dalam setiap generasi padaKasus 1
....................
......................................................................
Tabel-4.
Waktu pemrosesanjobdi setiap mesin untuk. Kasus 2 ....................
Tabel 5.
Daftar kromosom terbaik yang pernah dihasiJkan dalam setiap generasi padaKasus 2
....
.
.............................
,...................................
7 39
48 52·
63
