PRESENTASI TUGAS AKHIR CF 1380 PENERAPAN ALGORITMA GENETIKA UNTUK MASALAH PENJADWALAN JOB SHOP PADA LINGKUNGAN INDUSTRI PAKAIAN

PRESENTASI TUGAS AKHIR – CF 1380

PENERAPAN ALGORITMA GENETIKA UNTUK MASALAH PENJADWALAN JOB SHOP PADA LINGKUNGAN INDUSTRI PAKAIAN

Penyusun Tugas Akhir : Fachrudin Afandi (NRP : 5204.100.017)

Dosen Pembimbing : Mahendrawathi, E.R, ST, MSc, Ph.D 14 Januari 2010

Tugas Akhir – CF1380

1

.:LATAR BELAKANG(1):. 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.

14 Januari 2010


2

.:LATAR BELAKANG(2):. 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.

14 Januari 2010


3

.:LATAR BELAKANG(3):. 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.

14 Januari 2010


4

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

14 Januari 2010


5

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

14 Januari 2010


6

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

14 Januari 2010


7

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

14 Januari 2010


8

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

14 Januari 2010


9

.:MASALAH PENJADWALAN JOB SHOP:. Job Shop Scheduling Problem (JSSP) melibatkan suatu tugas pada seperangkat kerja pada stasiunkerja (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

14 Januari 2010


10

.:Pemodelan JSSP(1):. Beberapa asumsi yang digunakan: 1.

2.

3.

Ketika sekali suatu operasi mulai dijalankan, maka tidak dapat disela. Tidak ada kasus kekurangan material, gangguan mesin dan ketidakhadiran operator mesin job shop dalam kerjanya. 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.

14 Januari 2010


11

.:Pemodelan JSSP(2):. Batasan-batasan dalam pemodelan: 1. Batasan waktu kedatangan

Ai  SPi

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

(1)

2. Batasan alokasi

X

ilkj

0

Setiap mesin (Mkj) harus memproses setidaknya satu operasi (Oil)

(2)

kj , M kj SM il

X X

ilkj

1

(3)

Setiap mesin harus memproses setidaknya satu operasi

ilkj

1

( 4)

Setiap operasi harus diproses

il

kj

3. Batasan operasi

Cil  ETil  1  Si 'l ' ,

Oil  P(Oi 'l ' )

4. Batasan waktu proses

Cil  Sil  STPil  Til  1 14 Januari 2010

( 6)

(5)

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)


12

.:Pemodelan JSSP(3):. Fungsi tujuan: p

min Z , dengan Z   ( i .TDi .i   i .ELi .(1  i ))

{ SPi },{ X ilkj }

(7)

i 1

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

14 Januari 2010


13

.: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 14 Januari 2010


14

.:METODA ALGORITMA GENETIKA:. Penghentian proses: Generasi dan operasi genetika Terpenuhi ?

Evaluasi kromosom: Evaluasi nilai fitness dalam populasi dengan fungsi fitness

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

14 Januari 2010

Kromosom dengan nilai fitness terbaik

Operator mutasi inversi

Pindah silang uniformorder (Davis, 1991)


Proses seleksi turnamen (Goldberg, Korb, & Deb, 1989)

15

.:ALGORITMA GENETIKA UNTUK 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

14 Januari 2010


16

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

14 Januari 2010


17


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

14 Januari 2010


18


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 kembali sifat 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 kembali sifat produk: berbaur dan multi produk

14 Januari 2010


19


Untuk melakukan evaluasi digunakan uji kebenaran pada setiap eksperimen. Uji kebenaran 





Setiap operasi hanya bisa dijalankan pada mesin yang mampu menanganinya Eksperimen 1 Setiap mesin setidaknya satu Mesin lockstitch 1 –harus 7 hanya memproses menampung operasi 2, 3, 4, 11 dan 12. Mesin overlock 8 – 14 hanya menampung operasi 1, 5, 6, 7, 8, 9 dan 10. operasi Eksperimen 2 Setiap operasi diprosesoperasi 1, 2, 3, 5, 6, 8, 9, 10, 11, Mesin lockstitch 1 – 9 harus hanya menampung dan 12. Mesin overlock 10 – 11 hanya menampung operasi 4, 7, dan 13.

14 Januari 2010


20

.:IMPLEMENTASI DAN UJI COBA PROGRAM:. 

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

C  ( S  STP  T )  ET 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) Pada uji coba eksperimen yang dilakukan waktu pengaturan mesin (STP) dianggap masuk dalam waktu proses (T)

14 Januari 2010


21


Uji coba pada eksperimen 1 

Kasus 1 Bobot tardiness

Bobot earliness

Jumlah order

Tenggat waktu

Order 1

5000

100

1200

15

Order 2

3000

100

1200

12

Mode 1 Mode 2

Uji coba pada eksperimen 2 

Kasus 1 Bobot tardiness

Bobot earliness

Jumlah order

Tenggat waktu

Order 1

6000

100

1000

15

Order 2

4000

100

1000

12

14 Januari 2010


Mode 1 Mode 2

22

.: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. 14 Januari 2010


23

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

14 Januari 2010


24

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

14 Januari 2010


25

.: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. 14 Januari 2010


26

.:DAFTAR PUSTAKA:. 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-ofthe-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.

14 Januari 2010


27

.:DAFTAR PUSTAKA:. 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-andbound algorithm for the job-shop scheduling problem. Discrete Applied Mathematics, 49(1–3), 107–127.

14 Januari 2010


28

TERIMA KASIH

14 Januari 2010


29

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

14 Januari 2010


30

.:Inisialisasi Populasi:. Langkah 2: Inisialisasi populasi 1. Inisialisasi parameter Indeks i  Ukuran populasikromosom u Membangkitkan  Populasi PPN  CHR PPN  PPN 

2.

string integer CHRi

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

14 Januari 2010


31

.:Seleksi:.

Langkah 3: Proses seleksi dan fitness Set ukuran turnamen k>=2 Membangkitkan suatu permutasi acak didalam populasi Bandingkan nilai fitness pada kromosom pertama pada daftar permutasi, dan salin yang terbaik ke dalam generasi berikutnya 1 1 jika permutasi habis terpakai, bangkitkan permutasi lain fitness   p Z  1  ( i .TDi .i   i .ELi .(1  i ))  1 Ulangi langkah 3i 1dan 4 sampai tidak diperlukan seleksi lagi untuk generasi berikutnya

14 Januari 2010


32

.:Operasi Genetika:.

Langkah 4: Operasi genetika Proses pindah silang Proses mutasi

14 Januari 2010


33

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

14 Januari 2010


34

.:Proses Pindah Silang:.

Salin daftar Ubah daftar gen gen 11 Salin Ubah daftar daftar gen gen 22 14 Januari 2010

Daftar gen parent 1: (8) (3,10) (1,11) (6,12) (3,10) (8) (6,12) (1,11) (4,7) Daftar gen parent 2: (5) (1) (8) (10)(1) (11) (10) (5)(11) (8) (7,13) Tugas Akhir – CF1380

35

.:Operasi 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 (n1), 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.

14 Januari 2010


36

.:Proses Mutasi:. Titik mutasi Kromosom asli

5

9

8

1

3

10

2,6

11

Inversi kromosom

5

6,12

11

2,6

10

3

1

8

9

7,13 4,13

Mutasi kromosom

5

6,12

6,2

11

10

3

1

8

9

7,13 4,13

Tipe mesin

Tipe 1

6,12 7,13 4,13

Tipe 2

1. 2. 3. Ambil Menginversi Mutasisatu kromosom kromosom kromosomdari populasi 14 Januari 2010


37

.:Penghentian Proses:.

Langkah 5: Ukuran penghentian proses Terpenuhinya 2 kriteria penghentian  

Sejumlah generasi tertentu Penggunaan keanekaragaman algoritma genetika (Operasi genetika)

14 Januari 2010


38

.:HASIL UJI COBA(1):. Eksperimen 1 kasus 1 mode 1 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

- 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

14 Januari 2010


39

.:ANALISA HASIL(1):. Hasil Penjadwalan optimasieks. eks.11kasus kasus11mode mode11 Order 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

14 Januari 2010


40

.:HASIL UJI COBA(2):. Eksperimen 1 kasus 1 mode 2 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

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

-

14 Januari 2010


41

.:ANALISA HASIL(2):. Penjadwalan Hasil optimasieks.1 eks.1kasus kasus1 1mode mode2 2 Order 1

Order 2

Waktu Start

0

2,35


14,98

9,64


14,98

11,99

Tenggat Waktu

15

12

Pinalti

$100*0,02 =$2

$100*0,01 =$1

14 Januari 2010


42

.:HASIL UJI COBA(3):. Eksperimen 2 kasus 1 mode 1 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

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

14 Januari 2010


43


Order 2

Waktu Start

0

5


7,99

7

Waktu Penundaan

7

0


14,99

12

Tenggat Waktu

15

12

Pinalti

$100*0,01 =$1

0

14 Januari 2010


44

.:HASIL UJI COBA(4):. Eksperimen 2 kasus 1 mode 2 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

2 order

1,12

10

2,11

9

5

11

3,6

1

8

4,7

13

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

-

14 Januari 2010


45


Order 2

Waktu Start

0

3,04


14,97

8,96


14,97

12

Tenggat Waktu

15

12

Pinalti

$100*0,03 =$3

0

14 Januari 2010


46

PRESENTASI TUGAS AKHIR CF 1380 PENERAPAN ALGORITMA GENETIKA UNTUK MASALAH PENJADWALAN JOB SHOP PADA LINGKUNGAN INDUSTRI PAKAIAN

Recommend Documents