PENERAPAN ALGORITMA CODEQ UNTUK MENYELESAIKAN PERMASALAHAN J OB SHOP SCHEDULING Dosen Pembimbing: 1. Yudha Prasetyawan, S.T. M.Eng 2. Ir. Budi Santosa, M.S., Ph.D.
Oleh: M Bisyrul Jawwad 2507100069
Pendahuluan Industri/perusahaan
penjadwalan yang baik akan dapat meningkatkan efektivitas serta efisiensi sistem produksi industri
untuk dapat melakukan suatu proses penjadwalan (scheduling) yang baik sangat sulit untuk dibuat karena terkendala batasan(constraint)
Begitu pula dengan model penjadwalan job shop
Tidak begitu rumit ketika pekerjaan yang diselesaikan hanya sedikit , namun ketika ada sejumlah m machine (mesin) berbeda dan n job (pekerjaan) berbeda untuk dijadwalkan akan menjadi rumit.
Pendahuluan Differential Evolution
Omran
Chaotic Search
CODEQ Oposition Based Laerning
Quantum Mechanism
Pendahuluan Alasan Memilih CODEQ untuk Permasalahan Job
Shop Scheduling 1. Algoritma ralatif baru (baru ditemukan tahun 2008) dan belum pernah digunakan untuk menyelesaikan Job Shop Scheduling 2. Permasalahan Job Shop Scheduling sudah pernah diselesaikan dengan algoritma Differential Evolution, yang hampir mirip dengan CODEQ 3. Tidak memerlukan parameter
Perumusan Masalah • Bagaimana menentukan urutan pekerjaan sehingga diperoleh makespan yang optimum pada permasalahan Job Shop Scheduling dengan metode CODEQ
Tujuan Penelitian • Mengembangkan algoritma CODEQ untuk kasus Job shop Scheduling. • Mengimplementasikan metoda CODEQ untuk penyelesaian problem Job shop Scheduling pada suatu program komputer sehingga program yang dibuat dapat menyelesaikan permasalahan Job shop Scheduling yang lebih rumit.
Ruang Lingkup Penelitian • Suatu pekerjaan diproses hanya sekali dalam suatu mesin • Suatu operasi tidak dapat di sela • Operasi dalam suatu pekerjaan harus diproses secara berurutan yaitu setelah operasi sebelumnya selesai dilakukan • Setiap mesin hanya dapat memproses satu pekerjaan pada suatu waktu
Manfaat Penelitian • Adanya pendekatan baru yang merupakan aplikasi metoda CODEQ dalam menyelesaikan Job shop Scheduling Problem. • Merupakan perluasan aplikasi metoda CODEQ yang sebelumnya hanya ditunjukkan pada penyelesaian kasus
routing.
Contoh Data Penelitian ukuran kasus job
mesin
ft06
6
6
la01 la02 la03 la04
10 10 10 10
5 5 5 5
la05 ft10 orb01 orb02 la22 la23 la24 la25
10 10 10 10 15 15 15 15
5 10 10 10 10 10 10 10
Urutan proses
Waktu proses
Sumber data: OR-Library
Job Shop Scheduling resource
constraint
precedence
• Konsep penjadwalan job shop adalah waktuoperasi suatumelanggar operasi mulai Jikamenentukan penjadwalan suatu salah satu constraint , makadan penjadwalan operasi tersebut harusuntuk dikerjakan mengalokasikan resource dialihkan waktunya,operasi dimana pengalihan waktu saat ini bisa mengerjakan tersebut. Pada membuat proses penyelesaian job dapat berlangsung menjadwalkan suatu operasi selain menentukan lebih lama dan bahkan membuat proses mengalami kapan operasi tersebut mulai dikerjakan juga keterlambatan ditentukan resource mana yang dipakai oleh operasi tersebut.
Job Shop Scheduling Formulasi Job Shop • Himpunan pekerjaan M={m1,m2,m3,…mm} • Himpunan mesin J={j1,j2,j3….jn} • Himpunan operasi per pekerjaan I Oi={Oi1,Oi2,….Oim} • Waktu proses tiap operasi {ti1,ti2,…….tim} • Untuk setiap O terdapat himpunan A, relasi biner urutan operasi. Jika , maka v harus dikerjakan sebelum w. • Untuk setiap operasi v didefinisikan waktu mulai S(v)
•
Panjang suatu jadwal S adalah
Ilustrasi Job Shop 58
• Kotak berwarna menunjukan mesin tempat operasi • Panah berarah menunjukkan urutan suatu operasi diproses dalam suatu job • Garis putus-putus (sisi tak berarah) menunjukkan bahwa kedua operasi berada dalam mesin yang sama dan salah satu dari kedua operasi itu harus mendahului yang lain
CODEQ Langkah metoda algoritma CODEQ (Omran dan Salman) untuk Job Shop Scheduling : 1. Pemeberian indeks untuk matriks urutan pekerjaan 2. Inisialisasi • Pembentukan vektor solusi (xi)urutan secara random permutasi sebesar jumlah operasi, sebanyak yang diinginkan • Pengurutan berdasarkan kegiatan pendahulu • Perhitungan makespane untuk masing-masing urutan solusi yang sudah terbentuk
CODEQ 3. Mutasi • mencari vektor baru(mutan). Pilih tiga individu(xi, xi1, xi2) secara random sebagai induk, dengan ketentuan xi ≠ xi1 ≠ xi2. Selanjutnya dicari nilai vi untuk mendapatkan mutan Persamaan tersebut diturunkan dari persamaan Quantum Mechanic yaitu : •
Diasumsikan bahwa g induk yang akan dicari mutannya (g = xi), sedangkan sebagai perbedaan vektor .
•
Selanjutnya mutan yang terbentuk diurutkan berdasarkan kegiatan pendahulu, lalu dihitung nilai waktu operasinya seperti pada tahap inisialisasi
CODEQ 4. Crossover: nilai υi yang baik akan menggantikan xi 5. Penentuan Nilai W(t) xb(t): vektor dengan nilai terburuk xg(t):vektor dengan nilai terbaik c adalah variable chaotic yang diperoleh dari persamaan berikut:
Selanjutnya Nilai W(t) yang terbentuk diurutkan berdasarkan kegiatan pendahulu, lalu dihitung nilai waktu operasinya seperti pada tahap inisialisasi
CODEQ 6. Jika makespan dari nilai w(t) lebih baik daripada x(t), maka w(t) menggantikan posisi x(t), jika tidak, maka sebaliknya 7. Ulangi langkah 2-5 sampai terpenuhinya
stoping criteria
Critical Review Constraint Optimization using CODEQ (Omran,2009)
Algoritma Genetik Hibrida dalam Penyelesaian Job Shop Scheduling Problem (Samsu sampena, 2009)
Penggunaan Metode CODEQ Untuk Menyelesaikan Permasalahan Capacited
Vehicle routing Problem (Giri,2010)
Metodologi Penelitian Mulai
Perumusan Masalah
Studi Literatur Codeq & JSP
Pengumpulan Data (dari OR-Library)
A
A
Pengembangan Algoritma Codeq untuk permasalahan jobshop
Pengujian Algoritma
Perbandingan Algoritma
Kesimpulan & Saran
Selesai
Algoritma Usulan mulai
B
Penentuan nilai W untuk masing-masing sampel Wi(t) = LB + UB - r * x(b) untuk r<0.5 Wi(t) = x(g) + Ix1-x2I * (2c-1) untuk r>0.5
Input Data yang akan diproses, meliputi data urutan permesinan dan waktu permesinan
Dimana: Wi(t): individu w ke-i pada iterasi ke-t LB:nilai vektor paling rendah pada iterasi tersebut UB:nilai vektor paling tinggi pada iterasi tersebut C:variabel chaotic X(b):vektor dengan nilai terendah pada iterasi tersebut X(g):vektor dengan nilai terendah pada iterasi tersebut
Inisialisasi sampel awal (X) dengan cara random permutasi jumlah operasi sebanyak yang diinginkan(n), beserta nilai makespan
Membandingkan nilai makespan Wi dan Xi
Tentukan mutan (V) pada masing-masing sampel awal dengan cara Vi(t)=Xi(t)+(Xi1(t)-X12(t))ln(1/u) Dimana: Vi(t):Vektor mutan I pada iterasi ke-t Xi:Vektor solusi i pada iterasi ke-t i=1,2,…..,n
Crssover Membandingkan nilai makspane sampel awal dengan mutan
A
Nilai makespan yang lebih baik akan mengantikan solusi sebelumnya ke-i tidak
Populasi baru sudah terkumpul
Stopping criteria terpenuhi ya
B
Nilai mutan(Vi) yang lebih baik akan menggantikan sampel awal(Xi)
Ambil SolusiTerbaik sebagai hasil akhir Akhir
A
selesai
Contoh Pengerjaan Manual item
job
operation time
j1 j2 j3 j1 j2 j3
Machine Sequence
Machine Sequence
operation sequence 1 2 3 3 3 2 1 5 3 3 2 3 m1 m2 m3 m1 m3 m2 m3 m1 m2
j1 j2 j3
1 4 7
2 5 8
3 6 9
Contoh Pengerjaan Manual • Inisialisasi sampel x1 x2 x3 x4
1 9 8 6
5 4 3 3
urutan operasi 3 7 2 8 6 3 7 2 4 6 9 1 1 5 4 8
9 8 2 2
6 1 5 9
4 5 7 7
x1 x2 x3 x4
1 4 4 1
7 7 1 4
2 8 2 5
urutan operasi 3 8 9 9 1 2 3 5 6 6 2 3
4 3 7 7
5 5 8 8
makespane 6 19 6 21 9 15 9 14
• Mutasi v1 1 10 5.1 6.06 5.96 v2 5.53 5.5 6.5 7.47 2.53 v3 4 -0.5 3.5 4.53 1.94 v4 -1 0.4 0.9 1.4 1.49
mutan v1 v2 v3 v4
7 2 4 3 3 8.5 2 5.5
1 1 1 1
7 2 4 2
mutan v1 v2 v3 v4
3.5 4.5 5 6 9.5 11 5.4 5.9
8 3 5 3
9 4 6 4
2 5 2 5
3 6 3 6
4 7 7 7
5 8 8 8
1 6 5 1
6 9 9 9
9 5 1 2
makespane 18 16 14 16
5 8 4 3
7 9 6 4
6 1 2 5
8 3 3 6
2 2 7 8
3 4 8 7
4 7 9 9
Contoh Pengerjaan Manual • Crossover
x1 x2 x3 x4
1 6 5 6
9 5 1 3
5 8 4 1
7 9 6 5
• Penentuan Nilai W w1 w2 w3 w4
6 6 7 5
3 2 3 4
• Seleksi
1 1 1 2
5 4 6 7
4 5 5 3
7 8 4 8
2 3 2 1
9 9 9 9
8 7 8 6
6 1 2 4
8 3 3 8
2 2 7 2
3 4 8 9
4 7 9 7
Validasi • Quantum
Genetic Algorithm memperoleh hasil 11
Gu et al (2009)
• Dengan menghitung semua kemungkinan, Nilai optimal yang bisa diperoleh sebesar 11
• Hasil yang diperoleh dengan 3 pembangkitan sampel dan 3 iterasi diperoleh hasil 11
Enumerasi
Algoritma usulan
Hasil Percobaan • Kasus 6 x 6 ukuran
makespan
referensi PSO MA terbaik
kasus job mes TSSA SA ft06
6
6
55
GA 55
IA 55
codeq GAP% 55 55 0
55
• Kasus 10 x 5 ukuran
makespan
kasus la01 la02 la03 la04 la05
job mes TSSA SA 10 5 10 5 10 5 10 5 10
5
GA IA PSO 666 666 666 655 655 655 597 597 597 590 590 590 593
593
referensi MA terbaik codeq GAP% 666 666 670 0.6 655 655 655 0 597 597 614 2.85 590 590 592 0.34
593 593
593
592 -0.17
Hasil Percobaan • Kasus 10 x 10 ukuran
makespan
kasus ft10 orb01 orb02 orb03 orb04 orb05 orb06 orb07 orb08 orb09 orb10 la16 la17 la18 la19 la20
job 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
mes TSSA SA GA IA PSO MA 10 930 930 930 930 930 10 1059 1149 10 888 929 10 1005 1129 10 1005 1062 10 887 936 10 1010 1060 10 397 416 10 899 1010 10 934 994 10 944 10 945 945 945 945 945 10 784 784 784 784 10 848 848 848 848 10 842 842 842 844 10 907 902 902 907
referensi terbaik 930 1059 888 1005 1005 887 1010 397 899 934 944 945 784 848 842 902
codeq GAP% 938 0.86 1079 1.89 898 1.13 1018 1.29 1009 0.4 893 0.68 1029 1.88 398 0.25 913 1.56 942 0.86 1009 6.89 949 0.42 791 0.89 859 1.3 844 0.24 912 1.11
Hasil Percobaan • Kasus 15 x 5 ukuran
makespan
kasus la06 la07 la08 la09 la10
job mes TSSA SA 15 5 15 5 15 5 15 5 15 5
GA IA PSO 926 926 926 890 890 890 863 863 863 951 951 951 958 958 958
• Kasus 20 x 5 ukuran
referensi MA terbaik codeq GAP% 926 926 926 0 890 890 908 2.02 863 863 863 0 951 951 959 0.84 958 958 990 3.34
makespan
kasus la11 la12 la13
job mes TSSA SA 20 5 20 5 20 5
GA 1222 1039 1150
IA 1222 1039 1150
PSO 1222 1039 1150
MA 1222 1039 1150
referensi terbaik
codeq GAP% 1222 1260 3.11 1039 1174 13 1150 1174 2.09
Hubungan Performansi CODEQ dengan Jumlah Total Operasi 2.5
% GAP 2
1.5
1
0.5
Jumlah total operasi
0 36
50
75
100
Analisis Faktor penyebab buruknya performansi • bilangan random yang dibangkitkan saat melakukan tahapan mutasi dan tahan penentuan nilai w jika bilangan random yang dibangkitkan mendukung untuk membuat makespan pekerjaan kecil maka akan dihasilkan makespan yang kecil pula, begitu juga sebaliknya. • Hal yang sama juga terjadi ketika tahap inisialisasi dimana pembangkitan individu awal juga dibangkitan dengan cara random permutasi • Jumlah penyaringan 2 kali untuk setiap iterasi yang dimiliki metode ini tidak menjadi jaminan akan membuat iterasi lebih cepat optimal • Jumlah operasi yang semakin besar akan membuat kemungkinan untuk membentuk individu awal semakin besar. Dan membuat pembentukan solusi optimal menjadi lebih lama.
Kesimpulan 1
Algoritma CODEQ bisa digunakan untuk menyelesaikan permasalahan penjadwalan job shop , dengan mengurutkan solusi yang terbentuk sesuai kegiatan atau operasi pendahulu
2
Algoritma CODEQ mampu menghasilkan solusi yang kompetitif untuk problem dengan skala 6 pekerjaan x 6 mesin , sedangkan untuk kasus dengan skala 10 pekerjaan x 10 mesin dan 20 pekerjaan x 5 mesin menghasilkan makespan yang lebih besar dibanding solusi yang sudah ada
3
Semakin besar jumlah operasi akan membuat algoritma CODEQ semakin sulit menentukan nilai optimal.
Saran 1
2
3
Modifikasi algoritma untuk bisa menghasilkan solusi awal yang berbeda dan tidak berulang
Melakukan pembangkitan sampel awal yang lebih banyak dan jumlah iterasi yang lebih banyak pula
Menggunakan metode CODEQ untuk permasalahan yang lain
Daftar Pustaka •
•
• •
•
•
•
•
Betrianis & Aryawan, P T. 2003. Penerapan Algoritma Tabu Search dalam Penjadwalan Job Shop . Departemen Teknik Industri, Fakultas Teknik, Universitas Indonesia, Jakarta Budiman, A 2010, Pendekatan Cross Entropy-Genetic Algorithm untuk Permasalahan Penjadwalan Job shop tanpa Waktu Tunggu Pada Banyak Mesin. Institut Teknologi Sepuluh Nopember, Surabaya Bedworth, D D & Bailey, J E. 1987. Integrated Production and Control System . John Willey & Sams, Singapore Chao, Y Z;Li P G; Rao, Y Q; Guan, Z L.2006. Avery fast TS/SA algorithm for the job shop scheduling problem. School of Mechanical Science & Engineering, Huazhong University of Science & Technology, Wuhan, China Dini, M. 2009. Optimasi Penjadwalan Job Shop dengan Metode Algoritma Defferential Evolution untuk Meminimumkan Total Biaya Lembur pada Kegiatan Pemuatan Barang Kontainer Ekspor, Universitas Indonesia, Jakarta Fachrudin, A & Mahendrawati, E R. 2010. Penerapan Algoritma Genetika untuk Masalah Penjadwalan Job Shop pada Lingkungan Industri Pakaian. Institut Teknologi Sepuluh Nopember, Surabaya Gamma. 2006. Implementasi Model Penjadwalan Job -Shop dalam Masalah Penjadwalan Kereta Api Jalur Tunggal dengan Pendekatan Constraint Programming. Institut Teknologi Bandung. Ginting, R. 2007. Sistem Produksi, Graha Ilmu, Yogyakarta
Daftar Pustaka •
•
Giri, YN. 2010. Penggunaan Metoda Codeq Untuk Menyelesaikan permasalahan Capacited Vehicle Routing Problem , Institut Teknologi Sepuluh Nopember. Surabaya Gu, Jinwei; Gu, Manzhan; Ca, Cuiwen, Gu, Xingsheng. 2009. A novel
competitive co-evolutionary quantum genetic algorithm for stochastic job shop scheduling problem. Research Institute of Automation, East China University of • • •
• •
Science and Technology, Shanghai, China Http://people.brunel.ac.uk/mastjjb/jeb/orlib/jobshopinfo.html , (diakses pada 22 maret 2011) Laguna, M; Barnes, J; Glover, F. 1991. Journal of International Manufacturing : 2 vol 63. Lin, T L; Horng, S J; Kao, T W; Chen, Y H; Run, R S. 2010. An efficient job-shop scheduling algorithm based on particle swarm optimization . Department of Electrical Engineering, National Taiwan University of Science and Technology, Taipei, Taiwan Pinedo, M & Chao, X. 1999. Operations Scheduling with Applications in Manufacturing and Services . McGraw-Hill, Singapore. Omran, G H & Salman, M A. 2009. Constrained optimization using CODEQ. Elsevier-ScienceDirect. Departmen of Computer Sciene. Gulf University for Science and Technology, Kuwait
Daftar Pustaka • •
•
•
Sempena, S. 2008. Algoritma Genetik Hibrida dalam Penyelesaian Job-Shop Scheduling Problem . Jurusan Teknik Informatika ITB, Bandung Xing, L N; Chen, W Y; Wang, P; Zhao, Q S; Xiong, A J 2010, Knowledge-Based Ant Colony Optimization for Flexible Job shop Scheduling Problems . ElsevierScienceDirect. Yang, J H; Sun, L; Lee, H P; Qian, Y; Liang, Y. 2008. Clonal Selection Based Memetic Algorithm for Job Shop Scheduling Problem . Institute of Electric and Information Engineering, Beihua University, Jilin , P. R. China Zhang, R & Wu, C. 2007. A Hybrid immune simulated annealing algorithm for the job shop scheduling problem , Department of Automation, Tsinghua University, Beijing , PR China.
Sekian TERIMA KASIH
