Tesis
Algoritma Differential Evolution -Variable Neighborhood Search untuk Minimasi Makespan dan Maximum Lateness Pada Penjadwalan Job Hybrid Flowshop with Job-sequence Dependent Setup-time
Oleh:
Ong Andre Wahyu Riyanto (2508 202 007)
Pembimbing: Prof. Ir. Budi Santosa, M.Sc., PhD
Hybrid Flowshop
Model lantai produksi, dimana sejumlah n job yang diproses dalam m seri tahap operasi dalam rangka mengoptimalkan fungsi tujuan tertentu. Setidaknya pada salah satu seri tahap operasi memiliki lebih dari satu unit mesin paralel. Keseluruhan n job diproses dalam aliran operasi satu arah: tahap operasi -1, tahap operasi-2, …, tahap operasi-m. Suatu job diperbolehkan melompati tahap operasi manapun (stage skipping). Setidaknya suatu job melompati satu tahap operasi. Setiap job j memiliki waktu pemrosesan pij di tahap operasi i.
Hybrid Flowshop with Job-sequence Dependent Setup-time (HFFS/SDST) Model Hybrid Flowshop yang mempertimbangkan adanya waktu setup mesin yang tergantung pada urutan langsung job yang diproses di mesin tersebut. Model Hybrid Flowshop yang mempertimbangkan adanya stage skipping. Terdapat job yang melompati tahap operasi (karena job tidak memerlukan operasi di suatu tahap).
LATAR BELAKANG (1) Penjadwalan operasi di lantai produksi merupakan salah satu persoalan kritis dalam perencanaan dan pengelolaan proses manufaktur (Pezella, dkk, 2008)
- Hybrid flow shop: setidaknya pada salah satu seri tahap operasi memiliki lebih dari satu unit mesin paralel
Penjadwalan operasi pada kondisi praktikal sering dihadapkan pada kebutuhan optimasi multi-tujuan Penjadwalan operasi pada hybrid flow shop kebanyakan berorentasi pada optimasi tujuan-tunggal
Penjadwalan operasi flow shop adalah salah satu diantara persoalan penjadwalan yang paling sering dikaji, tetapi flow shop sering dikritik karena model ini mengandung terlalu banyak penyederhanaan (Naderi, dkk, 2010)
- Flow shop: setiap tahap operasi hanya menggunakan satu unit mesin - Kondisi praktikal lantai produksi: jarang pada suatu tahap operasi hanya menggunakan satu unit mesin saja
Masih diperlukan penelitian tentang permasalahan optimasi penjadwalan job pada hybrid flow shop yang mempertimbangkan multi-tujuan
LATAR BELAKANG (2) Weighting Objective Approach Memberikan kombinasi pembobotan secara linier pada masing-masing fungsi tujuan untuk memperoleh satu nilai fungsi tunggal Lebih ke persoalan yang pragmatis, tetapi kurang dapat menghasilkan beberapa solusi efesien (Loukil, dkk, 2005)
Pendekatan yang lebih umum yang dapat menghasilkan beberapa solusi efesien (Loukil, dkk, 2005)
Pendekatan Minimasi Multi-tujuan
Simultaeous Optimization (Pareto) approach Menemukan satu himpunan solusi takterdominasi optimal yang dikenal sebagai pareto front
Prosedur bersifat subyektif, mengabaikan perbedaan mendasar antara optimasi tujuan-tunggal dengan optimasi multi-tujuan, (Santosa & Willy, 2011)
FORMULASI MASALAH Kondisi praktikal lini produksi membutuhkan kriteria multitujuan (Hoogevenen, 2005)
DE & VNS sering digunakan sebagai metode minimasi tujuan untuk permasalahan optimasi kombinatorial
Bagaimana meminimasi makespan dan maximum lateness pada penjadwalan job HFFS/SDST menggunakan algoritma differential evolution (DE) dan variable neighborhood structure (VNS) ?
VNS local search dengan dua atau lebih
struktur neighborhood (Tasgetiren, dkk, 2004)
DEglobal search dengan struktur sederhana dan mudah diimplementasikan (Qian, dkk, 2009)
ASUMSI PENELITIAN (1) 1. 2. 3. 4. 5.
6.
Selama periode penjadwalan job tidak terjadi kerusakan mesin maupun break down karena aktifitas perawatan. Keseluruhan mesin siap memproses job di titik waktu ke nol. Keseluruhan job bersifat independent dan siap diproses di titik waktu ke nol. Keseluruhan job memiliki prioritas pemrosesan yang sama. Pada suatu titik waktu setiap mesin paralel di suatu tahap operasi hanya dapat memproses satu job, begitu juga setiap job hanya diproses sekali di satu mesin paralel. Urutan (permutasi) penjadwalan job di permulaan setiap tahap operasi tidak harus selalu sama.
ASUMSI PENELITIAN (2) 7. 8.
9. 10.
11. 12. 13.
Job sequence dependent setup time tidak termasuk dalam waktu proses job. Besar waktu job sequence dependent setup time urutan langsung antara job j dan job k, tidak sama dengan besar waktu job sequence dependent setup time urutan langsung antara job k dan job j. Setiap job dapat mulai diproses di mesin paralel yang tersedia ( mesin tidak sedang memproses job lain). Daya tampung antar tahap operasi (intermediate buffer) tidak terbatas. Job dapat menunggu diantara dua tahapan operasi sampai dengan tersedia mesin paralel di tahap operasi berikutnya. Setiap job yang sedang diproses di suatu mesin tidak boleh diinterupsi (memproses job lain). Tidak terdapat waktu transportasi antar tahapan operasi. Data mengenai waktu proses job, waktu setup, maupun job due date bersifat deterministik dan diketahui dengan baik.
Membuat dan mengimplementasikan hibridasi DE-VNS untuk meminimasi makespan dan maximum lateness secara simultan
Menemukan himpunan solusi takterdominasi (non-dominated solutions)
Tujuan Penelitian
Mengukur metrik performansi himpunan solusi tak-terdominasi yang dihasilkan oleh metode hibridasi DE-VNS.
Membandingkan antara himpunan solusi tak-terdominasi yang dihasilkan oleh DE-VNS dengan himpunan solusi takterdominasi yang dihasilkan oleh DEinsert maupun oleh PSO-VNS.
Memberikan sebuah penerapan metode metaheuristik untuk menyelesaikan permasalahan optimasi multi-tujuan penjadwalan job HFFS/SDST
KONTRIBUSI PENELITIAN
Memberikan alternatif metode metaheuristik yang kompetitif untuk menyelesaikan permasalahan optimasi kombinatorial multitujuan yang lebih nyata.
Ilustrasi Contoh Problem n=8 m=3 mi=2 Job yang tidak diproses di tahap operasi i tahap operasi-i job stage skipping jumlah 1 8 1 2 3 1 3 2 1
Pekerjaan (job) yang diproses di tahap operasi i tahap operasi-i 1 1 2 3 4 5 6 7 1 2 4 5 6 7 8 2 3 1 3 4 5 6 7 8
job sequence dependent setup time
jumlah 7 7 7
Sjki tahap operasi 1 job k
tahap operasi, i 1 2 3 due date
Waktu setup mesin jika job j dikerjakan di mesin paralel pada urutan pertama tahap operasi, i 1 2 3
1 39 24 32
2 37 29 22
pekerjaan (job) j 3 4 5 6 32 22 29 20 39 36 25 20 28 24 29 34
7 26 23 20
8 27 38 37
1 0 36 26 27 34 33 23 26
job j
1 2 3 4 5 6 7 8
Waktu pemrosesan pekerjaan (job) pekerjaan (job) j 1 2 3 4 5 6 7 8 64 70 99 92 68 71 95 78 95 64 77 56 87 65 56 76 99 83 93 63 100 63 60 62 442 393 627 659 595 615 692 421
Sjki tahap operasi 2
2 20 0 39 30 20 28 25 21
3 37 29 0 23 35 34 26 36
4 24 40 31 0 31 29 20 34
job k
5 23 31 33 22 0 37 33 34
6 21 32 27 38 34 0 35 34
7 24 27 30 35 40 30 0 36
Sjki tahap operasi 3 job k job j
1 2 3 4 5 6 7 8
1 0 39 30 28 23 31 38 35
2 28 0 27 34 30 28 33 26
3 36 30 0 21 36 31 22 25
4 38 38 31 0 35 40 23 34
5 31 26 23 32 0 28 37 37
6 20 26 26 23 40 0 28 33
7 31 34 21 22 23 38 0 27
8 40 25 39 40 27 31 32 0
8 25 32 21 25 36 32 33 0
job j
1 2 3 4 5 6 7 8
1 0 27 27 35 40 32 26 31
2 32 0 21 31 24 20 23 32
3 24 35 0 33 23 38 36 31
4 33 29 40 0 36 20 32 26
5 24 29 32 39 0 22 24 20
6 36 25 37 24 21 0 35 23
7 40 30 39 37 26 38 0 32
8 39 28 35 24 33 21 40 0
Penyelesaian Menggunakan Algoritma DE-VNS Langkah-0, penentuan nilai parameter : NP=50, Xmax =4 , Xmin=0, F=0,5, Cr=0,8 dan Gmax=50
Langkah-1a, inisialisasi pop. awal dengan pembangkitan random: Xi,0 = rand(0,1)* (Xmax - Xmin) + Xmin Xi(0) X1 X2 X3 . . . X49 X50
1 3,801 0,925 2,427 . . . 1,219 0,759
2 0,774 2,729 1,211 . . . 0,259 3,953
3 2,331 1,694 2,062 . . . 1,482 2,301
dimensi j 4 1,806 0,176 0,109 . . . 0,683 3,977
5 1,759 1,360 1,257 . . . 2,501 2,934
6 1,504 0,040 1,679 . . . 3,847 0,235
7 1,441 2,194 1,047 . . . 1,636 1,896
konversikan Xi,0 menjadi individu solusi permutasi job dengan aturan smallest parameter value (SPV) ϕ (0) urutan job (permutasi) ι
ϕ1
2
7
6
5
4
3
1
ϕ2
6
4
1
5
3
7
2
ϕ3 . . .
4 . . .
7 . . .
2 . . .
5 . . .
6 . . .
3 . . .
1 . . .
ϕ49
2
4
1
3
7
5
6
ϕ50
6
1
7
3
5
2
4
Langkah-1b, inisialisasi populasi awal dengan teknik LPT-EDD :
ϕι
urutan job (permutasi)
ϕ1
4
1
2
6
5
3
7
ϕ2
7
5
1
3
6
4
2
ϕ3 . . .
7 . . .
2 . . .
1 . . .
5 . . .
6 . . .
3 . . .
4 . . .
ϕ49
7
2
1
5
6
4
3
ϕ50
2
1
4
6
3
5
7
Langkah-2, Menghitung fungsi multi-tujuan individu populasi awal (Po ), - fi,0 maupun individu populasi kombinasi LPT-EDD (PLPT-EDD), fi,LPT-EDD : f i (0) f1 f2 f3 . . . f 49 f 50
Cmax 422 433 414 . . . 430 440
Lmax -20 40 -28 . . . -185 -45
f i,LPT-EDD(0) f1 f2 f3 . . . f 49 f 50
Dimana: Cmax=makespan , Lmax=maximum lateness
Cmax 427 385 420 . . . 432 450
Lmax -200 -8 -235 . . . -195 -242
scalar fitness function
f1 f2 f3 . . .
f 49 f 50
fi (0) 316,2321 276,6025 146,7639 . . . -36,7612 215,1520
fi,LPT-EDD(0) f1 276,9627 228,6025 f2 f3 23,9826 . . . . . . f 49 -43,8687 f 50 129,1859
Perbandingan Himpunan Solusi Tak-terdominasi: DE-VNS, DE-Insert, PSO-VNS n=50, m=4, m1=3 m2=2 m3=2 m4=2 n=50, m=4, mi =2
1000
800
700
DE-VNS DE-Insert PSO-VNS
800 700 Maximum Lateness
600
Maximum Lateness
DE-VNS DE-Insert PSO-VNS
900
500
400
600 500 400 300
300
200 200
100
100 2750
2800
2850 Makespan
2900
n=50, m=8, mi =2 2000
DE-VNS DE-Insert PSO-VNS
2650
2700
2750 2800 2850 Makespan
2900
2950
3000
3050
DE-VNS DE-Insert PSO-VNS
1600 1400 Maximum Lateness
1800
Maximum Lateness
2600
n=50, m=8, m1=4 m2=2 m3=4 m4=2 m5=3 m6=3 m7=3 m8=2 1800
2400 2200
0 2550
2950
1600 1400 1200
1200 1000 800
1000 600
800 400
600 400 3600
3800
4000
4200 Makespan
4400
4600
4800
200 3400
3500
3600
3700
3800 3900 4000 Makespan
4100
4200
4300
4400
Kesimpulan
Algoritma DE-VNS mampu menghasilkan jumlah himpunan solusi yang tidak terdominasi oleh himpunan solusi algoritma DE-Insert maupun algoritma PSO-VNS yang lebih banyak. Algoritma DE-VNS mampu menghasilkan jumlah himpunan solusi yang lebih mendekati himpunan pareto dibandingkan dengan algoritma DE-Insert maupun algoritma PSO-VNS. Walaupun nilai metrik jumlah titik solusi tak-terdominasi algoritma PSO-VNS lebih besar dibandingkan dengan dua algoritma lain, tetapi titik solusi algoritma PSO-VNS secara umum terdominasi semua oleh himpunan solusi algoritma DE-VNS.
Kesimpulan Berdasarkan hasil performansi nilai metrik NNDS dan D1R dapat dikatakan bahwa teknik kombinasi LPT-EDD untuk memperbaiki inisialisasi populasi awal mampu memberikan himpunan solusi awal yang lebih baik dibandingkan dengan dua algoritma lain. Efektivitas algoritma DE-VNS lebih baik dibandingkan dengan algoritma DE-Insert maupun PSO-VNS. Maka algoritma DEVNS dapat digunakan untuk meminimasi makespan dan maximum lateness penjadwalan job pada hybrid flexible flow shop with job sequence dependent setup time (HFFS/SDST). Solusi kompromistis himpunan solusi tak-terdominasi yang dihasilkan oleh algoritma DE-VNS dapat memberikan alternatif solusi bagi pengambilan keputusan di lantai produksi.
Saran Menambah satu kriteria tujuan yaitu, minimasi number of tardy job (jumlah job yang terlambat). Himpunan solusi tak-terdominasi dari tiga tujuan yang saling konflik akan lebih merepresentasikan kondisi praktikal penjadwalan job. Diusulkan setiap mesin paralel di tiap tahap operasi memiliki kecepatan waktu pemrosesan yang tidak sama (tidak identik). Hal ini akan lebih merepresentasikan kondisi praktikal penjadwalan job di lini produksi. .
REFERENSI UTAMA Allahverdi, A, C.T. Ng b, T.C.E. Cheng , Mikhail Y. Kovalyov,“A Survey Of Scheduling Problems With Setup Times Or Costs” , International Journal of Production Research, 2008. Li, B-B, Wang, L.,Liu, B., “An Effective PSO-Based Hybrid Algorithm for Multiobjective Permutation Flow Shop Scheduling“, IEEE Transaction on System Manufacturing and Cybernetics, 2008. Babu, B.,V., Mathew M., Jehan, Lenus, “Differential Evolution for MultiObjective Optimization”, India, 2003. Hoogeveen, H., “Multiciteria Scheduling”, European Journal of Operational Research, 2005. Hartanto, Fredy, “Penerapan Multi Objective Gentic Algorithm (MOGA) pada Penjadwalan Dynamic-Mulit Objective dan Sequence Dependent Setup Time Compound Flow Shop di PT X”, Tesis, 2010. Hansen, Piere, Mladenovic, Nenad, “Invited Variable Review: Neigborhood Search:Principles & Aplications”, EJOR, 2001. Ishibuci, H, Murata T.A, “Balance Between Genetic Search and Local Search in Memetic Algorithm for Multiobjective Permutation Flowshop Scheduling “, IEEE Transaction on Evolutionary Computattion, Volume 7, No.2, 2003. Jungwattanakit, J., Reodecha, M., Chaovalitwongse, P., Werner, F., “Algorithms for Flexible Flow Shop roblems with Unrelated Parallel Machines, Setup Times, and Dua Criteria, International Jounal od Advanced Manufacturing Technology, 2008. Kurz, M.E., R.G. Askin, “Scheduling Flexible Flow Lines with Sequence Dependent Setup TImes”, European Journal of Operational Research, 2004. Loukil, T., J., Teghem and D. Tuyttents, “Solving Multi-Objectives Production Scheduling Problems Using Metaheuristics, European Journal of Operations Research, 161, pp. 42-61 Montes, E., M., Sierra, M., R., Coella. C., , “Multi-Objective Optimization using Differential Evolution: A Survey of the State-of-the-Art:”, Laboratorio Nacional de Inform´atica Avanzada (LANIA A.C.) R´ebsamen 80, Centro, Xalapa, Veracruz, 91000, Mexico, 2005. Naderi,B., R.Ruiz, M. Zandieh, “Algorithms for a Realistic Variant of Flow Shop Scheduling”, Computer & Operations Research, 2010.
REFERENSI UTAMA Onwubolu, G, Donald Davendra, D, ”Scheduling Flow Shops using Differential Evolution Algorithm”, European Journal of Operational Research 171, pp. 674–692, 2006. Pinedo M. ,”Scheduling: Theory, Algorithms And Systems”. New York: Springer; 2002. Pezella F., Morganti G., Ciaschetti G., ”A Genetic Algorithm for Flexible Job-shop Scheduling Problem”, Computer & Operations Research, 2008: 3202-3212. Price V. Kenneth, Storn M. Rainer, Lampinen A. Jouni, ”Differential Evolution: A Practical Approach to Global Optimization”, Springer, 2005. Qian, B, Wang, L, Huang, D, Wang, Wang, X, “An Effective Hybrid DE-based Algorithm for Multi-objective Flow Shop Scheduling with Limited Buffers”, Computers & Operations Research 36, pp.209 – 233, 2009. Quadt, D., Kuhn, H., “A Taxonomy Of Flexible Flow Line Scheduling Procedures”, European Journal of Operation Research, pp. 686-698, 2007. Ribas, I., R. Leisten, J.M. Framinan, “Review and Classification of Hybrid Flow Shop Scheduling Problem form a Production and a Solution Procedure Perspective”, Computer & Operations Research, 2010. Ruiz, R., Jose Antonio, V.Rodriquez, “Invited Review: The Hybrid Flow Shop Scheduling Problem”, European Journal of Operational Research, 2010. Santosa B., Willy, P., “Metode Metaheuristik: Konsep dan Implementasi”, Cetakan pertama, Penerbit Guna Widya, 2011. Tasgetiren, M.F, Liang, Y.C, Sevkli, M, Gencyilmaz, G, “Particle Swarm Optimization Algorithm for Makespan and Maximum Lateness in Permutation Flowshop Sequencing Problem”, Dept. of Management, Fatih University, Istambul-Turkey, 2004.
