its undergraduate 7801 presentasita 5204100017

8/17/2019 ITS Undergraduate 7801 PresentasiTA 5204100017

1/46

14 Januari 2010 Tugas Akhir – CF1380 1

PENERAPAN ALGORITMA GENETIKA UNTUK

MASALAH PENJADWALAN JOB SHOP PADA

LINGKUNGAN INDUSTRI PAKAIAN

PRESENTASI TUGAS AKHIR – CF 1380

Penyusun Tugas Akhir :

Fachrudin Afandi

(NRP : 5204.100.017)

Dosen Pembimbing :

Mahendrawathi, E.R, ST, MSc, Ph.D


2/46


Perusahaan diberbagai sektor industri dihadapkan pada

kompetisi pasar global yang terus meningkat dan fluktuasi

permintaan yang tidak dapat diramalkan.

Industri pakaian adalah salah satu yang terkena dampak dari

tekanan untuk dapat menghasilkan berbagai macam produk

yang sesuai dengan selera konsumen, dengan waktu yangsingkat dan biaya yang rendah.

Industri pakaian pada umumnya beroperasi dengan sistem job

shop dimana penjadwalan job shop untuk industri pakaianadalah suatu penjadwalan yang harus mengerjakan banyak

operasi menggunakan banyak mesin yang fleksibel.

.:.:LATAR BELAKANLATAR BELAKANG(1):.G(1):.


3/46



Berbagai macam penelitian telah dilakukan terhadapmasalah penjadwalan job shop pada industri pakaian.

Namun demikian, sebagian besar penelitian yang telahdilakukan sebelumnya hanya berkonsentrasi padapemecahan suatu masalah dengan metoda tertentu pada

lingkungan yang telah terdefinisikan jelas denganberbagai batasan.

Model matematika umum untuk masalah penjadwalan

job shop pada industri pakaian belum dibahas dan yangbertujuan meminimalkan penyelesaian pesanan lebihawal atau terlambat juga belum diselidiki.


4/46



Pada masalah penjadwalan produk berbaur, dua ataulebih pesanan produksi akan diproduksi dimanapunurutan produk. Sedangkan pada kasus penjadwalan multiproduk, dua atau lebih produk diproses secara terpisah.

Untuk mengisi celah ini, Guo et al. (2006)

mengembangkan metoda algoritma genetika untukpenjadwalan job shop yang bersifat berbaur dan multiproduk dalam industri pakaian.


5/46


Tujuan tugas akhir ini adalah

Mengimplementasikan algoritma genetika untukmelakukan penjadwalan job shop yang dapat

meminimalkan total pinalti E/T (Earliness/Tardiness).

.:.:TUJUANTUJUAN:.:.


6/46


Permasalahan yang terkait dalam tugas akhir ini adalah:

Bagaimana mengimplementasikan algoritma genetikadalam menyelesaikan masalah penjadwalan job shop

dengan tujuan meminimalkan total pinalti E/T

(Earliness/Tardiness)

Bagaimana solusi yang dihasilkan dapat membantu

industri pakaian dalam mengambil keputusan terkaitdengan masalah penjadwalan job shop

.:.:PERMASALAHANPERMASALAHAN:.:.


7/46


.:BATASAN MASALAH:..:BATASAN MASALAH:.

Algoritma yang digunakan adalah algoritma genetika

untuk masalah penjadwalan job shop.Data yang digunakan berasal dari data-data produksi

pada industri perakitan pakaian yang sesuai dengan

masalah penjadwalan job shop.

Pengembangan aplikasi menggunakan ruang lingkup

pemrograman Matlab


8/46


.:PENJADWALAN JOB SHOP:..:PENJADWALAN JOB SHOP:.

Penjadwalan merupakan suatu proses pengaturan sumber

daya untuk menyelesaikan tugas-tugas denganmelibatkan pekerjaan, sumber daya, dan waktu.

Tujuan dari masalah penjadwalan antara lainmeminimumkan waktu penyelesaian semua tugas

(makespan), meminimumkan keterlambatan pengerjaan,

meminimumkan waktu tunggu pada mesin,

meminimumkan biaya, dan lain-lain.


9/46


.:PENJADWALAN JOB SHOP:..:PENJADWALAN JOB SHOP:.

Pada sistem perakitan produk berbaur: dua atau lebih

pesanan diproduksi dimanapun urutan berbaur

Sedangkan pada sistem perakitan multi produk: dua atau

lebih produk diproses secara terpisah didalam batch


10/46


.:MASALAH PENJADWALAN JOB SHOP:..:MASALAH PENJADWALAN JOB SHOP:.

Job Shop Scheduling Problem (JSSP) melibatkansuatu tugas pada seperangkat kerja pada stasiun-kerja (mesin) secara sekuensial

Saat mengoptimalkan satu atau lebih sasaran tanpamelanggar batasan-batasan yang diterapkan pada jobshop

(Guo et al, 2006)

Algoritma genetika merupakan salah satu teknikyang paling sering diterapkan dan telah terbukti di

beberapa penelitian dapat menemukan solusiheuristik dari suatu variasi yang luas pada aplikasi


11/46


.:.:PemodelanPemodelan JSSP(1):.JSSP(1):.

Beberapa asumsi yang digunakan:

1. Ketika sekali suatu operasi mulai dijalankan, makatidak dapat disela.

2. Tidak ada kasus kekurangan material, gangguanmesin dan ketidakhadiran operator mesin job shop

dalam kerjanya.

3. Job shop digunakan untuk memodelkan adalahdalam keadaan inisialisasi awal job shop kosong,

dengan kata lain tidak ada kerja yang menumpuksebelumnya (Work in Process / WIP) pada setiapstasiun-kerja.


12/46



Batasan-batasan dalam pemodelan:1. Batasan waktu kedatangan

2. Batasan alokasi

3. Batasan operasi

4. Batasan waktu proses

)1(ii SP A

)2(0,

ilkj SM M kj

ilkj X

)3(1 il

ilkj X

)4(1 kj

ilkj X

)5()(,1 '''' liilliilil OPOS ET C

)6(1 ilililil T STPS C

Pemenuhan order Pi tidak dapat dimulai (SPi) sampaiwaktu kedatangan order Pi tiba ( Ai)

Setiap mesin (Mkj) harus memproses setidaknya satu

operasi (Oil)

Setiap mesin harus memproses setidaknya satu operasi

Setiap operasi harus diproses

Suatu operasi tidak dapat dimulai sebelum operasiyang terdahulu telah diselesaikan (Cil) dan diangkut

(ETil) sesuai dengan mesin kerjanya

Operasi Oil harus dijalankan dengan waktu proses (Til)

dan setup waktu (STPil)


13/46



Fungsi tujuan:

Meminimumkan total pinalti Earliness (ELi) atau Tardiness (TDi)

)7())1.(...(,min1

}{},{

p

i

iiiiii X SP

ELTD Z dengan Z ilkji


14/46


.:METODA ALGORITMA GENETIKA:..:METODA ALGORITMA GENETIKA:.

Pada umumnya suatu penerapan algoritma genetika

secara generasional sederhana terdiri dari 3 bagian,yaitu:

Memilih populasi awal

Evaluasi nilai fitness dari setiap individu didalam populasi

Ulangi sampai proses berhenti (nilai fitness terbaik

terpenuhi)

Pilih individu terbaik berdasar ranking untuk reproduksi

Bentuk generasi baru melalui pindah silang dan mutasi untukmenghasilkan keturunan baru (child )

Evaluasi nilai fitness keturunan yang dihasilkan

Setelah diatur terlebih dahulu, gantikan individu dengan nilai fitness

terburuk dengan keturunan yang dihasilkan


15/46


.:METODA ALGORITMA GENETIKA:..:METODA ALGORITMA GENETIKA:.

Inisialisasi populasi:

•menugaskan operasimasing-masing, kepadamesin yang mampu

menanganinya•Membangkitkankromosom yang feasibelhingga terbentuk populasi

Evaluasi kromosom:

Evaluasi nilai fitness dalam populasidengan fungsi fitness

Penghentian proses:

Generasi dan operasi genetika

Terpenuhi ?

Proses seleksi turnamen

(Goldberg, Korb, & Deb, 1989)Pindah silang uniform-

order (Davis, 1991)

Operator

mutasi inversi

Kromosom

dengan nilai

fitness terbaik


16/46


.:ALGORITMA GENETIKA UNTUK.:ALGORITMA GENETIKA UNTUK

MASALAH PENJADWALAN JOB SHOP:.MASALAH PENJADWALAN JOB SHOP:.

Langkah – langkah dalam menerapkan GA

pada masalah JSS, yaitu:1. Representasi kromosom

2. Inisialisasi populasi

3. Fitness dan seleksi

4. Operasi genetika

5. Ukuran penghentian proses


17/46


.:IMPLEMENTASI DAN UJI COBA PROGRAM:..:IMPLEMENTASI DAN UJI COBA PROGRAM:.

Implementasi program menggunakan Matlab 7.7

dalam lingkungan sistem operasi Windows XP.

Data yang digunakan adalah

data order produksi

data efisiensi operasi pada setiap stasiun-mesin

(sumber: ref. paper Guo et al, 2006)


18/46



Uji coba dilakukan dalam dua eksperimen

Eksperimen 1: setiap mesin hanya dapat menampung1 operasi dalam proses pengolahan order

Eksperimen 2: setiap mesin dapat menampungmaksimal dua operasi dalam proses pengolahan order


19/46



Setiap eksperimen terbagi menjadi 2 mode, yaitu

Mode 1: Pengolahan order 1 dijalankan kemudian saatwaktu tertentu ditunda untuk menjalankanpengolahan order 2 sampai selesai, kemudianpengolahan order 1 dijalankan kembali

sifat produk: multi produk

Mode 2: Pengolahan order 1 dijalankan kemudian saatwaktu tertentu pengolahan order 1 dan order 2dijalankan secara simultan sampai order 2 terpenuhi.

Setelah itu baru pengolahan order 1 dijalankankembali

sifat produk: berbaur dan multi produk


20/46



Untuk melakukan evaluasi digunakan uji

kebenaran pada setiap eksperimen.Uji kebenaran

Setiap operasi hanya bisa dijalankan pada mesin

yang mampu menanganinya

Setiap mesin harus memproses setidaknya satu

operasi

Setiap operasi harus diproses

Eksperimen 1Mesin lockstitch 1 – 7 hanya menampung operasi 2, 3, 4, 11 dan 12.Mesin overlock 8 – 14 hanya menampung operasi 1, 5, 6, 7, 8, 9 dan 10.

Eksperimen 2Mesin lockstitch 1 – 9 hanya menampung operasi 1, 2, 3, 5, 6, 8, 9, 10, 11,

dan 12.

Mesin overlock 10 – 11 hanya menampung operasi 4, 7, dan 13.


21/46



Operasi order harus dijalankan dengan waktu awal(start), waktu pengaturan mesin, dan waktu proses

operasi

Pada uji coba eksperimen yang dilakukan waktu pengaturan mesin (STP)dianggap masuk dalam waktu proses (T)

ET T STPS C )(

Dimana:

C = waktu penyelesaian order sepenuhnya (akan ditentukan)

S = waktu awal (start) operasi dijalankan (telah ditetapkan)

STP = waktu pengaturan mesin dilakukan (telah ditetapkan)

T = waktu order selesai dikerjakan (akan ditentukan)ET = waktu penundaan order dijalankan (telah ditetapkan)


22/46



Uji coba pada eksperimen 1

Kasus 1

Uji coba pada eksperimen 2

Kasus 1

Bobottardiness

Bobotearliness

Jumlahorder

Tenggatwaktu

Order 1 5000 100 1200 15

Order 2 3000 100 1200 12

Bobottardiness

Bobotearliness

Jumlahorder

Tenggatwaktu

Order 1 6000 100 1000 15

Order 2 4000 100 1000 12

Mode 1

Mode 2

Mode 1

Mode 2


23/46


.:SIMPULAN:..:SIMPULAN:.

GA dapat digunakan sebagai salah satu metodaalternatif dalam menyelesaikan penjadwalan job shop

karena memiliki kemampuan yang baik dalammembangkitkan solusi heuristik dari variasipermasalahan yang luas.

Metoda algoritma genetika mampu menyelesaikanmasalah penjadwalan job shop yang produknya bersifatberbaur dan multi produk dengan meminimalkan totalpinalti E/T (Earliness/Tardiness).

Waktu awal dan waktu pengaturan mesin sangatberpengaruh dalam efektifitas penjadwalan job shopyang dihasilkan.


24/46


.:SIMPULAN:..:SIMPULAN:.

Pada penjadwalan job shop dengan mode 2 dimana adasaat produksi dua order dijalankan secara bersamaan,

untuk produksi order 1 dapat dipaksakan produksinyadisaat pengolahan order 1 atau disaat pengolahan duaorder dijalankan ataupun order 1 dijalankan secaraberimbang disaat pengolahan order 1 dan pengolahan

dua order.Pinalti E/T dapat dikenakan pada pengolahan orderjika waktu awal produksi tidak tepat. Pinalti juga bisaterjadi jika susunan operasi yang dibuat tidak memiliki

efektifitas dan efisiensi didalam proses produksi order.Pinalti E/T pada produksi berarti total biaya produksijuga bertambah.


25/46


.:SARAN:..:SARAN:.

Pengembangan terhadap GA pada masalahpenjadwalan job shop dengan mempertimbangkanefek ketidakpastian, diantaranya:

Ketidakpastian permintaan konsumen

Gangguan mesin

Kekurangan bahan baku

Ketidakhadiran operator mesin

dll.


26/46


.:DAFTAR PUSTAKA:..:DAFTAR PUSTAKA:.

Watanabe, M., Ida, K., & Gen, M. (2005). A genetic algorithmwith modified crossover operator and search area adaption

for the jobshop scheduling problem. Computers andIndustrial Engineering, 48(4), 743-752.

Ventura, J. A., & Kim, D. (2003). Parallel machine schedulingwith earliness-tardiness penalties and additional resourceconstraints. Computers and Operations Research, 30(13),1945–1958.Seo, D. K., Klein, C. A., & Jang, W. (2005). Single machinestochastic scheduling to minimize the expected number oftardy jobs using mathematical programming models.

Computers and Industrial Engineering, 48(2), 153–161.Poon, P. W., & Carter, J. N. (1995). Genetic algorithmcrossover operators for ordering applications. Computersand Operations Research, 22(1), 135–147.


27/46



Park, B. J., Choi, H. R., & Kim, H. S. (2003). A hybrid geneticalgorithm for the job shop scheduling problems. Computers andIndustrial Engineering, 45(4), 597–613.

Gordon, V., Proth, J., & Chu, C. (2002). A survey of the state-of-the-art of common due date assignment and scheduling research.European Journal of Operational Research, 139(1), 1–25.

Guo, Z.X., Wong, W.K., Leung, S.Y.S., Fan, J.T., Chan, S.F. (2006).

Mathematical model and genetic optimization for the job shopscheduling problem in a mixed- and multi-product assemblyenvironment: A case study based on the apparel industry.Computers & Industrial Engineering 50 (2006) 202–219.

Cheng, R. W., Gen, M., & Tsujimura, Y. (1996). A tutorial survey of job-shop scheduling problems using genetic algorithms.1.Representation. Computers and Industrial Engineering, 30(4), 983–997.


28/46



Lauff, V., & Werner, F. (2004). Scheduling with common due

date, earliness and tardiness penalties for multimachine

problems: A survey. Mathematical and Computer Modeling,40(5–6), 637–655.

Brucker, P., Jurisch, B., & Sievers, B. (1994). A branch-and-

bound algorithm for the job-shop scheduling problem.Discrete Applied Mathematics, 49(1–3), 107–127.


29/46


TERIMA KASIH


30/46


.:.:RepresentasiRepresentasi KromosomKromosom:.:.

Langkah 1: Merepresentasikan kromosom

Penjelasan representasi kromosom sebagai berikut:

Mesin dibagi menjadi dua tipe, tipe 1 meliputi mesin 1-7 dan

tipe 2 meliputi mesin 8-12.

Operasi 1, 2, 3, dan 4 harus diproses pada mesin tipe 1

Sedangkan operasi 5 dan 6 harus diproses pada mesin tipe 2.


31/46


.:.:InisialisasiInisialisasi PopulasiPopulasi:.:.

Langkah 2: Inisialisasi populasi

1. Inisialisasi parameter

2. Membangkitkan kromosom string integer CHRi

3. Set i=i+1. jika i>u, STOP . Jumlah populasi terpenuhiiCHRPPN PPN

Indeks i

Ukuran populasi u

Populasi PPN


32/46


.:.:SeleksiSeleksi:.:.

Langkah 3: Proses seleksi dan fitness

Set ukuran turnamen k>=2Membangkitkan suatu permutasi acak didalam populasi

Bandingkan nilai fitness pada kromosom pertama pada

daftar permutasi, dan salin yang terbaik ke dalamgenerasi berikutnya

jika permutasi habis terpakai, bangkitkan permutasi lain

Ulangi langkah 3 dan 4 sampai tidak diperlukan seleksilagi untuk generasi berikutnya

p

i iiiiii ELTD Z

fitness

1 1))1.(...(

1

1

1


33/46


.:.:OperasiOperasi GenetikaGenetika:.:.

Langkah 4: Operasi genetika

Proses pindah silang

Proses mutasi


34/46


.:.:OperasiOperasi Genetika(1):.Genetika(1):.

Proses pindah silang

Acak beberapa string yang panjangnya sama dengan

kromosom

Isi beberapa posisi pada anak 1 dengan mencopi gen dariorang tua 1 dimana saja bit string yang memuat “1”

Buat daftar gen dari orang tua 1 dihubungkan dengan bitstring “0”

Mengubah urutan daftar gen sehingga urutannya sama

dengan urutan gen yang tampak pada orang tua 2

Salin urutan daftar gen ke dalam posisi kosong pada anak 1

Anak 2 diproduksi menggunakan proses serupa denganproses pada anak 1


35/46


.:.:ProsesProses PindahPindah SilangSilang:.:.

Ubah daftar gen 1 Daftar gen parent 1: (3,10) (6,12) (8) (1,11) (4,7)

Daftar gen parent 2: (5) (8) (1) (10) (11) (7,13)

Daftar gen parent 1: (8) (1,11) (3,10) (6,12) (4,7)

Daftar gen parent 2: (1) (10) (11) (5) (8) (7,13)Ubah daftar gen 2

Salin daftar gen 1

Salin daftar gen 2


36/46


.:.:OperasiOperasi Genetika(2):.Genetika(2):.

Proses mutasi

Ambil satu kromosom dari populasi sebagai kromosomasli.

Inversi kromosom dengan cara pada tipe mesin yang

sama, jika panjang kromosom n, maka tukar posisi

gen ke-2 dengan gen ke-n, gen ke-3 dengan gen ke (n-

1), dan seterusnya.

Mutasi kromosom dengan cara pada tipe mesin yang

sama, tukar secara acak posisi gen yang bersebelahan

antara gen ke-2 dan gen terakhir.


37/46


.:.:ProsesProses MutasiMutasi:.:.

5

Tipe 1 Tipe 2

Kromosom asli

Inversi kromosom

Mutasi kromosom

Tipe mesin

Titik mutasi

4,137,136,12112,6103189

5 4,137,13981310116,26,12

5 4,137,139813102,6116,12

1. Ambil satu kromosom dari populasi2. Menginversi kromosom3. Mutasi kromosom


38/46


.:.:PenghentianPenghentian ProsesProses:.:.

Langkah 5: Ukuran penghentian proses

Terpenuhinya 2 kriteria penghentian

Sejumlah generasi tertentu

Penggunaan keanekaragaman algoritma genetika

(Operasi genetika)


39/46


.:HASIL UJI COBA(1):..:HASIL UJI COBA(1):.

Eksperimen 1 kasus 1 mode 1

- Pada order 1 dengan waktu mulai hari ke 0, waktu penundaan 5,43 dantenggat waktu 15 hari

- Waktu rata-rata proses sistem operasi bottleneck 228 detik

- Sistem satu order 1125,5 detik

- Pada order 2 dengan waktu mulai hari ke 6,57 dan tenggat waktu 12 hari- Waktu rata-rata proses sistem operasi bottleneck 130 detik

- Sistem satu order 514,0001 detik

operasi Mesin no.

1 2 3 4 5 6 7 8 9 10 11 12 13 14

Order1 3 2 2 4 4 3 3 6 1 1 5 6 6 5

Order2 12 11 11 12 11 11 12 10 7 7 9 8 8 9


40/46


.:ANALISA HASIL(1):..:ANALISA HASIL(1):.

Hasil optimasi eks. 1 kasus 1 mode 1

Order 1 Order 2

Waktu Start 0 6,57

Waktu Pengolahan Order 9,53 5,43

Waktu Penundaan 5,43 0Waktu Penyelesaian Order 14,96 12

Tenggat Waktu 15 12

Pinalti $100*0,04=$4

0

Penjadwalan eks. 1 kasus 1 mode 1


41/46




- Pengolahan order 1 dengan waktu mulai hari ke 0 dan tenggat waktu 15 hari- Pada perakitan 798 pakaian, waktu sistem bottleneck 192 detik dan

sistem satu order 1056 detik.- Pengolahan dua order dengan waktu mulai hari ke 2,35

- Order 1: pada perakitan 402 pakaian, waktu sistem bottleneck 685,7143detik dan sistem satu order 2492,1 detik.

- Order 2: waktu sistem bottleneck 230,7692 detik dan sistem satu order1063,6 detik, dengan tenggat waktu 12 hari

operasi Mesin no.

1 2 3 4 5 6 7 8 9 10 11 12 13 14

Order1 2 4 2 3 4 3 3 1 1 1 5 5 6 6

2 order 11 3 2 12 4 4 11 8 1 7 5 6 9 10


42/46



Penjadwalan eks.1 kasus 1 mode 2

Order 1 Order 2

Waktu Start 0 2,35


Waktu Penyelesaian Order 14,98 11,99

Tenggat Waktu 15 12

Pinalti $100*0,02

=$2

$100*0,01

=$1

Hasil optimasi eks.1 kasus 1 mode 2


43/46




- Pada order 1 dengan waktu mulai hari ke 0, waktu penundaan 7 hari dan

tenggat waktu 15 hari- Waktu rata-rata proses sistem operasi bottleneck 228,8 detik.

- Sistem satu order 1523,1 detik.

- Pada order 2 dengan waktu mulai hari ke 5 dan tenggat waktu 12 hari- Waktu rata-rata proses sistem operasi bottleneck 201,2903 detik.

- Sistem satu order 526,4121 detik.

Op. Mesin no.

1 2 3 4 5 6 7 8 9 10 11

Order1

1,3 8 2,6 3 8 1 2,5 5 6 4,7 4,7

Order2

11 11,12 12 9,10 9,11 12 10,11 10,11 10,12 13 13


44/46




Order 1 Order 2

Waktu Start 0 5

Waktu Pengolahan Order 7,99 7

Waktu Penundaan 7 0Waktu Penyelesaian Order 14,99 12

Tenggat Waktu 15 12

Pinalti $100*0,01=$1

0


AS COBA


45/46




- Pengolahan order 1 dengan waktu mulai hari ke 0 dan tenggat waktu 15 hari- Pada perakitan 621 pakaian, waktu sistem bottleneck 277,6471 detik dan

sistem satu order 1537,2 detik.- Pengolahan dua order dengan waktu mulai hari ke 3,04

- Order 1: pada perakitan 379 pakaian, waktu sistem bottleneck 672,9412detik dan sistem satu order 3033,6 detik.

- Order 2: waktu sistem bottleneck 257,1429 detik dan sistem satu order

1107,7 detik, dengan tenggat waktu 12 hari

Op. Mesin no.

1 2 3 4 5 6 7 8 9 10 11

Order1

2 8 6 5,8 2 1 6 5 3 4 7

2order

1,12 10 2,11 9 5 11 3,6 1 8 4,7 13

ANALISA HASIL(4)ANALISA HASIL(4)


46/46




Order 1 Order 2

Waktu Start 0 3,04


Waktu Penyelesaian Order 14,97 12

Tenggat Waktu 15 12

Pinalti $100*0,03

=$3

0


its undergraduate 7801 presentasita 5204100017

Documents