penerapan algoritma genetika untuk masalah … fileoperasi menggunakan banyak mesin yang...

14 Januari 2010 Tugas Akhir – CF1380 1

PENERAPAN ALGORITMA GENETIKA UNTUKMASALAH 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


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 yang singkat dan biaya yang rendah.Industri pakaian pada umumnya beroperasi dengan sistem job shop dimana penjadwalan job shop untuk industri pakaian adalah suatu penjadwalan yang harus mengerjakan banyak operasi menggunakan banyak mesin yang fleksibel.

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



Berbagai macam penelitian telah dilakukan terhadap masalah penjadwalan job shop pada industri pakaian.Namun demikian, sebagian besar penelitian yang telah dilakukan sebelumnya hanya berkonsentrasi pada pemecahan suatu masalah dengan metoda tertentu pada lingkungan yang telah terdefinisikan jelas dengan berbagai batasan.Model matematika umum untuk masalah penjadwalan job shop pada industri pakaian belum dibahas dan yang bertujuan meminimalkan penyelesaian pesanan lebih awal atau terlambat juga belum diselidiki.



Pada masalah penjadwalan produk berbaur, dua atau lebih pesanan produksi akan diproduksi dimanapun urutan produk. Sedangkan pada kasus penjadwalan multi produk, dua atau lebih produk diproses secara terpisah.Untuk mengisi celah ini, Guo et al. (2006) mengembangkan metoda algoritma genetika untuk penjadwalan job shop yang bersifat berbaur dan multi produk dalam industri pakaian.


Tujuan tugas akhir ini adalahMengimplementasikan algoritma genetika untuk melakukan penjadwalan job shop yang dapat meminimalkan total pinalti E/T (Earliness/Tardiness).

.:.:TUJUANTUJUAN:.:.


Permasalahan yang terkait dalam tugas akhir ini adalah:Bagaimana mengimplementasikan algoritma genetika dalam 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 terkait dengan masalah penjadwalan job shop

.:.:PERMASALAHANPERMASALAHAN:.:.


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


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

Penjadwalan merupakan suatu proses pengaturan sumber daya untuk menyelesaikan tugas-tugas dengan melibatkan pekerjaan, sumber daya, dan waktu.

Tujuan dari masalah penjadwalan antara lain meminimumkan waktu penyelesaian semua tugas (makespan), meminimumkan keterlambatan pengerjaan, meminimumkan waktu tunggu pada mesin, meminimumkan biaya, dan lain-lain.


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


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

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

Saat mengoptimalkan satu atau lebih sasaran tanpa melanggar batasan-batasan yang diterapkan pada job shop

(Guo et al, 2006)Algoritma genetika merupakan salah satu teknik yang paling sering diterapkan dan telah terbukti di beberapa penelitian dapat menemukan solusi heuristik dari suatu variasi yang luas pada aplikasi


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

Beberapa asumsi yang digunakan:1. Ketika sekali suatu operasi mulai dijalankan, maka

tidak dapat disela.2. Tidak ada kasus kekurangan material, gangguan

mesin dan ketidakhadiran operator mesin job shop dalam kerjanya.

3. Job shop digunakan untuk memodelkan adalah dalam keadaan inisialisasi awal job shop kosong, dengan kata lain tidak ada kerja yang menumpuk sebelumnya (Work in Process / WIP) pada setiap stasiun-kerja.



Batasan-batasan dalam pemodelan:1. Batasan waktu kedatangan

2. Batasan alokasi

3. Batasan operasi

4. Batasan waktu proses

)1(ii SPA

)2(0,

ilkj SMMkjilkjX

)3(1 il

ilkjX

)4(1 kj

ilkjX

)5()(,1 '''' liilliilil OPOSETC

)6(1 ilililil TSTPSC

Pemenuhan order Pi tidak dapat dimulai (SPi) sampai waktu 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 operasi yang terdahulu telah diselesaikan (Cil) dan diangkut (ETil) sesuai dengan mesin kerjanya

Operasi Oil harus dijalankan dengan waktu proses (Til) dan setup waktu (STPil)



Fungsi tujuan:

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

)7())1.(...(,min1}{},{

p

iiiiiiiXSP

ELTDZdenganZilkji


.: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 untuk menghasilkan keturunan baru (child)

Evaluasi nilai fitness keturunan yang dihasilkan

Setelah diatur terlebih dahulu, gantikan individu dengan nilai fitness terburuk dengan keturunan yang dihasilkan


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

Inisialisasi populasi:•menugaskan operasi masing-masing, kepada mesin yang mampu menanganinya•Membangkitkan kromosom yang feasibel hingga terbentuk populasi

Evaluasi kromosom:Evaluasi nilai fitness dalam populasi dengan fungsi fitness

Penghentian proses:Generasi dan operasi genetikaTerpenuhi ?

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

order (Davis, 1991)Operator mutasi inversi

Kromosom dengan nilai fitness terbaik


.: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 kromosom2. Inisialisasi populasi3. Fitness dan seleksi4. Operasi genetika5. Ukuran penghentian proses


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



Uji coba dilakukan dalam dua eksperimen

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

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



Setiap eksperimen terbagi menjadi 2 mode, yaitu

Mode 1: Pengolahan order 1 dijalankan kemudian saat waktu tertentu ditunda untuk menjalankan pengolahan order 2 sampai selesai, kemudian pengolahan order 1 dijalankan kembalisifat produk: multi produk

Mode 2: Pengolahan order 1 dijalankan kemudian saat waktu tertentu pengolahan order 1 dan order 2 dijalankan secara simultan sampai order 2 terpenuhi. Setelah itu baru pengolahan order 1 dijalankan kembalisifat produk: berbaur dan multi produk



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.



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)

ETTSTPSC )(

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)



Uji coba pada eksperimen 1

Kasus 1

Uji coba pada eksperimen 2

Kasus 1

Bobot tardiness

Bobot earliness

Jumlah order

Tenggat waktu

Order 1 5000 100 1200 15

Order 2 3000 100 1200 12

Bobot tardiness

Bobot earliness

Jumlah order

Tenggat waktu

Order 1 6000 100 1000 15

Order 2 4000 100 1000 12

Mode 1Mode 2

Mode 1Mode 2


.:SIMPULAN:..:SIMPULAN:.

GA dapat digunakan sebagai salah satu metoda alternatif dalam menyelesaikan penjadwalan job shop karena memiliki kemampuan yang baik dalam membangkitkan solusi heuristik dari variasi permasalahan yang luas. Metoda algoritma genetika mampu menyelesaikan masalah penjadwalan job shop yang produknya bersifat berbaur dan multi produk dengan meminimalkan total pinalti E/T (Earliness/Tardiness).Waktu awal dan waktu pengaturan mesin sangat berpengaruh dalam efektifitas penjadwalan job shop yang dihasilkan.


.:SIMPULAN:..:SIMPULAN:.

Pada penjadwalan job shop dengan mode 2 dimana ada saat produksi dua order dijalankan secara bersamaan, untuk produksi order 1 dapat dipaksakan produksinya disaat pengolahan order 1 atau disaat pengolahan dua order dijalankan ataupun order 1 dijalankan secara berimbang disaat pengolahan order 1 dan pengolahan dua order. Pinalti E/T dapat dikenakan pada pengolahan order jika waktu awal produksi tidak tepat. Pinalti juga bisa terjadi jika susunan operasi yang dibuat tidak memiliki efektifitas dan efisiensi didalam proses produksi order. Pinalti E/T pada produksi berarti total biaya produksi juga bertambah.


.:SARAN:..:SARAN:.

Pengembangan terhadap GA pada masalah penjadwalan job shop dengan mempertimbangkan efek ketidakpastian, diantaranya:

Ketidakpastian permintaan konsumen

Gangguan mesin

Kekurangan bahan baku

Ketidakhadiran operator mesin

dll.


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

Watanabe, M., Ida, K., & Gen, M. (2005). A genetic algorithm with modified crossover operator and search area adaption for the jobshop scheduling problem. Computers and Industrial Engineering, 48(4), 743-752.Ventura, J. A., & Kim, D. (2003). Parallel machine scheduling with earliness-tardiness penalties and additional resource constraints. Computers and Operations Research, 30(13), 1945–1958.Seo, D. K., Klein, C. A., & Jang, W. (2005). Single machine stochastic scheduling to minimize the expected number of tardy jobs using mathematical programming models. Computers and Industrial Engineering, 48(2), 153–161.Poon, P. W., & Carter, J. N. (1995). Genetic algorithm crossover operators for ordering applications. Computers and Operations Research, 22(1), 135–147.



Park, B. J., Choi, H. R., & Kim, H. S. (2003). A hybrid genetic algorithm for the job shop scheduling problems. Computers and Industrial 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 shop scheduling problem in a mixed- and multi-product assembly environment: 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.



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.


TERIMA KASIH


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


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

Indeks i

Ukuran populasi u

Populasi PPN


.:.:SeleksiSeleksi:.:.

Langkah 3: Proses seleksi dan fitnessSet ukuran turnamen k>=2Membangkitkan suatu permutasi acak didalam populasiBandingkan nilai fitness pada kromosom pertama pada daftar permutasi, dan salin yang terbaik ke dalam generasi berikutnyajika permutasi habis terpakai, bangkitkan permutasi lainUlangi langkah 3 dan 4 sampai tidak diperlukan seleksi lagi untuk generasi berikutnya

p

i iiiiii ELTDZfitness

11))1.(...(

11

1


.:.:OperasiOperasi GenetikaGenetika:.:.

Langkah 4: Operasi genetika

Proses pindah silang

Proses mutasi


.:.: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 dari orang tua 1 dimana saja bit string yang memuat “1”

Buat daftar gen dari orang tua 1 dihubungkan dengan bit string “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 dengan proses pada anak 1


.:.: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 1Salin daftar gen 2


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

Proses mutasi

Ambil satu kromosom dari populasi sebagai kromosom asli.

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.


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


.:.:PenghentianPenghentian ProsesProses:.:.

Langkah 5: Ukuran penghentian prosesTerpenuhinya 2 kriteria penghentian

Sejumlah generasi tertentu

Penggunaan keanekaragaman algoritma genetika (Operasi genetika)


.: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 dan tenggat 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


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

Hasil optimasi eks. 1 kasus 1 mode 1Order 1 Order 2

Waktu Start 0 6,57

Waktu Pengolahan Order 9,53 5,43

Waktu Penundaan 5,43 0

Waktu Penyelesaian Order 14,96 12

Tenggat Waktu 15 12

Pinalti $100*0,04=$4

0

Penjadwalan eks. 1 kasus 1 mode 1




- 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,7143 detik dan sistem satu order 2492,1 detik.

- Order 2: waktu sistem bottleneck 230,7692 detik dan sistem satu order 1063,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



Penjadwalan eks.1 kasus 1 mode 2Order 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




- 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

Order 1

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

Order 2

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




Waktu Start 0 5

Waktu Pengolahan Order 7,99 7

Waktu Penundaan 7 0


Tenggat Waktu 15 12

Pinalti $100*0,01=$1

0





- 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,9412 detik 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

Order 1

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




Waktu Start 0 3,04



Tenggat Waktu 15 12

Pinalti $100*0,03=$3

0


penerapan algoritma genetika untuk masalah … fileoperasi menggunakan banyak mesin yang...

Documents