LOGO
“PENGEMBANGAN METODE HYBRID TABU SEARCH-CROSS ENTROPY UNTUK PENJADWALAN FLOWSHOP”
Oleh : Muhammad Fahmi L. 2506 100 080 Pembimbing : Ir. Budi Santosa, M.Sc., Ph.D Ko-Pembimbing : Stefanus Eko Wiratno, S.T., M.T.
Contents 1
Pendahuluan
2
Tinjauan Pustaka
3
Metodologi Penelitian
4
Perancangan dan Pengujian Algoritma
5
Analisa dan Pembahasan
6
Kesimpulan dan Saran
Pendahuluan
Perumusan Masalah
Ruang Lingkup
Latar Belakang
Tujuan Manfaat
Latar Belakang
Penjadwalan Produksi
NP-hard Problem
Combinatorial Problem
Cont… Metode Umum
Flowshop Scheduling Problem
• Branch and Bound Algorithm
• CDS Algorithm
Mixed-Integer Linear Programming
Metaheuristik
• Ant Colony Optimization • Particle Swarm Optimization • Differential Evolution
Cont… sequence generating heuristics (Tabu Search)
Hybrid Tabu Search-Cross Entropy improvement heuristics (Cross Entropy)
www.themegallery.com
Perumusan Masalah
Permasalahan yang akan dibahas pada penelitian ini yaitu bagaimana menggunakan kombinasi metode Tabu Search dan Cross Entropy untuk menyelesaikan permasalahan penjadwalan produksi flowshop
Ruang Lingkup Penelitian
Batasan
• Menggunakan data dari jurnal penelitian Taillard (1993) • Kombinasi job dan mesin yang digunakan yang digunakan yaitu 20 dan 50 untuk job dan 5, 10, 20 untuk mesin
Asumsi
• Semua job sudah tersedia dan siap diproses pada waktu ke-0 • Set-up time untuk setiap operasi dan mesin dimasukkan dalam waktu proses • Produksi berjalan tanpa adanya preempt
Tujuan Penelitian
Mendapatkan algoritma Hybrid Tabu Search-Cross Entropy untuk penyelesaian kasus penjadwalan Flowshop
Menghasilkan program komputer untuk implementasi Hybrid Tabu Search-Cross Entropy untuk penyelesaian Flowshop Scheduling Problem
Membandingkan performansi Hybrid Tabu Search-Cross Entropy untuk penyelesaian permasalahan produksi flowshop dibandingkan dengan hasil yang telah ada pada jurnal penelitian Taillard (1993)
Manfaat Penelitian Manfaat yang bisa diperoleh dari penelitian ini dalam bidang keilmuan adalah adanya pendekatan baru yang merupakan implementasi metode Hybrid Tabu Search-Cross Entropy untuk penyelesaian kasus penjadwalan flowshop.
Tinjauan Pustaka Scheduling Problem
B
Macam-macam Industri
A
C
Flowshop Scheduling Problem
Concept
Critical Review
E
D
Cross Entropy
Macam-macam Industri
Fixed Site/Project
Industri ditinjau dari strategi process design
Job Shop
Flow Shop
Gambar 2. 1 Jenis-jenis Industri ditinjau dari aliran proses (Fogarty, et al.,1991)
Scheduling Problem
Constraint
Jumlah mesin, jumlah pekerjaan dan waktu proses
Fungsi tujuan
component of scheduling problem
Cont… Production Planning, master scheduling
Orders, demand forecast
Quantities, due dates
Capacity status
Material requirements, planning, capacity planning Scheduling constraints
Material requirements
Shop orders, release dates
Scheduling and rescheduling Schedule performance
Schedule
Detailed scheduling
Dispatching
Shop status
Shopfloor management Data collection
Job loading Shopfloor
Gambar 2.2 Diagram alir informasi dalam sistem manufaktur (Pinedo,2008)
Flowshop Scheduling Problem Formulasi Flowshop Scheduling Problem : Minimize Cmax(π) = C(πn, m) C(π1, 1) = pπ1,1 C(πj, 1) = C(πj-1, 1) + pπj,1, j = 2,3,……….,n, k = 2,3,……….,m, C(π1, k) = C(π1, k-1) + pπ1,k, C(πj, k) = max{ C(πj-1, k), C(πj, k-1) } + pπj,k, j = 2,3,……….,n; k = 2,3,……….,m.
Gantt chart hasil eksekusi Flowshop Scheduling Problem :
Gambar 2.3 Gantt Chart Penjadualan Flowshop
Tabu Search Tabu search yang ditemukan oleh Glover (1989), menurut Ben-Daya, et al. (1998) adalah sebuah metode optimasi berdasarkan local search dimana yang telah sukses diaplikasikan untuk memecahkan banyak permasalahan kombinatorial.
Algoritma sederhana dari tabu search yaitu :
(Sumber : http://priyandari.staff.uns.ac.id/files/2009/09/image025.gif)
Cross Entropy Generate sampel data random (χ) berdasarkan mekanisme spesifik
Cross Entropy Memperbaharui parameter (v) berdasarkan data sampel elite
Critical Review Tabel 4.1 critical review menurut sudut pandang penulis Peneliti (Tahun)
Judul Penelitian
Metode
Tasgetiren, et. Al., A discrete differential evolution algorithm for Metode Discrete differential evolution(DDE) dan the permutation flowshop scheduling problem metode Iterated greedy(IG) (2008)
Sahputra, et. Al., (2009)
Tabu search sebagai local search pada algoritma Ant Colony untuk penjadwalan Flowshop
Rera., (2010)
Penerapan Metode Cross Entropy D alam Penyelesaian Capacitated Vehicle Routing Problem
Hasil Untuk makespan criterion metode DDE memiliki performa yang sama dengan PSOvns, akan tetapi metode DDE memiliki waktu komputasi yang lebih cepat daripada PSOvns
Ant Colony Optimization(ACO) digabungkan dengan metode Tabu Search(TS)
Algoritma ACO yang di-hybrid dengan tabu search ternyata mempu menghasilkan makespan yang tidak jauh berbeda dengan metode ACO, akan tetapi waktu komputasi yang dihasilkan ACO-Tabu lebih singkat.
Cross Entopy(CE)
Metode Cross Entropy dapat menyelesaikan problem kombinatorial seperti CVRP dengan cepat dan kualitasnya lebih baik jika dibandingkan dengan metode Tabu Search, akan tetapi metode Cross Entropy ini kurang baik pada jumlah simpul yang besar.
Metodologi Penelitian Identifikasi Permasalahan
Perumusan Masalah dan Penetapan Tujuan Penelitian
Observasi dan Analisa Algoritma Tabu Search dan Cross Entropy
Studi Bahan Pustaka dan Literatur Tahap Persiapan
Pengumpulan Data : • • • • • •
Matriks Waktu untuk 20 Job 5 Mesin Matriks Waktu untuk 20 Job 10 Mesin Matriks Waktu untuk 20 Job 20 Mesin Matriks Waktu untuk 50 Job 5 Mesin Matriks Waktu untuk 50 Job 10 Mesin Matriks Waktu untuk 50 Job 20 Mesin
Mengembangkan Algoritma Tabu Search untuk Flowshop Scheduling Problem
Mengembangkan Algoritma Cross Entropy untuk Flowshop Scheduling Problem
Mengembangkan Algoritma Tabu Search-Cross Entropy untuk Flowshop Scheduling Problem
Validasi Model
Model Valid ?
Tidak
Ya Bandingkan hasil dengan metode lain dan hasil dari jurnal
Tahap Pengembangan dan Pengujian Model
Analisa Hasil Performansi
Kesimpulan dan Saran
Tahap Kesimpulan dan Analisa Model
Perancangan dan Pengujian Algoritma
Pengembangan Algoritma START
Pengumpulan data yang berupa matriks waktu proses job ke-j pada mesin ke-k
Menentukan parameter rho, alpha, jumlah mesin dan job, jumlah sampel yang akan dibangkitkan, maksimal jadwal dalam tabu list, dan maksimal iterasi tabu search Melakukan perhitungan dengan Model Algoritma Tabu Search Menghasilkan beberapa jadwal dalam tabu list Pembangkitan matriks transisi awal P yang pengaruhi dari jadwal-jadwal terbaik dari tabu list Membangkitkan sejumlah N jadwal sebagai kandidat solusi awal dari matriks transisi yang ada
Menghitung completion time job ke-j dikerjakan pada mesin ke-k berdasarkan constrain-nya : C(πj, k) = max{ C(πj-1, k), C(πj, k-1) } + pπj,k, j = 2,3,……….,n; k = 2,3,……….,m.
Menghitung nilai makespan yang dihasilkan oleh setiap jadwal yang dibangkitkan : Cmax(π) = C(πn, m)
Pengurutan jadwal terbaik sesuai dengan makespan yang paling minimum
Pengambilan sampel elite yaitu pengambilan sebanyak rho*N sampel jadwal terbaik
Mengupdate matriks transisi dengan acuan sampel elit
Tidak Apakah stopping criterion terpenuhi ?
Ya STOP ITERASI
Algoritma Cross Entropy untuk penjadwalan produksi flowshop
Cont… START
Pengumpulan data yang berupa matriks waktu proses job ke-j pada mesin ke-k
Menentukan parameter tabu list dan maksimum iterasi
Pembangkitan jadwal inisialisasi
Menghitung nilai makespan yang dihasilkan oleh jadwal yang dibangkitkan : Cmax(π) = C(πn, m)
Memasukkan jadwal inisialisasi kedalam tabu list
Membangkitkan sejumlah N jadwal yang didapat dari pertukaran tetangga jadwal terbaik tiap iterasinya
Menghitung nilai makespan yang dihasilkan oleh setiap jadwal yang dibangkitkan : Cmax(π) = C(πn, m)
Memilih jadwal terbaik sesuai dengan makespan yang paling minimum
Membandingkan jadwal terbaik sekarang dengan jadwal terbaik dari tabu list
Tidak Apakah stopping criterion terpenuhi ?
Ya
STOP ITERASI
Algoritma Tabu Search untuk penjadwalan produksi flowshop
Algoritma Hybrid Tabu Search-Cross Entropy
Modifikasi
A
B
Menghitung nilai makespan yang dihasilkan oleh setiap jadwal yang dibangkitkan : Cmax(π) = C(πn, m)
Pengurutan jadwal terbaik sesuai dengan makespan yang paling minimum
Pengambilan sampel elite yaitu pengambilan sebanyak rho*N sampel jadwal terbaik
Mengupdate matriks transisi dengan acuan sampel elit
Tidak Apakah stopping criterion terpenuhi ?
Ya STOP ITERASI
Algoritma Tabu Search-Cross Entropy untuk penjadwalan produksi flowshop
Contoh Numerik
job
1 2 3
1 27 18 23
2 39 19 5
mesin 3 19 13 14
4 14 22 17
5 28 43 22
Matriks Waktu Proses Produksi job i pada mesin k pada uji validasi
Contoh satu perhitungan manual : Jadwal = 1-2-3 C(π1, 1) = 27 C(π2, 1) = 18 + 27 = 45 C(π1, 2) = 39 + 27 = 66 C(π2, 2) = max{ 66 , 45 } + 29 = 66 + 29 = 85 C(π3, 1) = 45 + 23 = 68 C(π3, 2) = max{ 68 , 85 } + 5 = 85 + 5 = 90 C(π1, 3) = 66 + 19 = 85 C(π2, 3) = max{ 85 , 85 } + 13 = 85 + 13 = 98 C(π3, 3) = max{ 90 , 98 } + 14 = 98 + 14 = 112 C(π1, 4) = 85 + 14 = 99 C(π2, 4) = max{ 99 , 98 } + 22 = 99 + 22 = 121 C(π3, 4) = max{ 112 , 121 } + 17 = 121 + 17 = 138 C(π1, 5) = 99 + 28 = 127 C(π2, 5) = max{ 121 , 127 } + 43 = 127 + 43 = 170 C(π3, 5) = max{ 138 , 170 } + 22 = 170 + 22 = 192 Makespan : C(π3, 5) =192
Rekap Hasil Contoh Numerik
Pengujian data Pengujian data 20 job 5 mesin
Parameter Cross Entropy : N= 30000, rho = 0.005, alpha = 0.9 Parameter Tabu Search : max.Iterasi = 1000000, ukuran tabu list = 3 Parameter Tabu-CE : N= 5000, rho = 0.005, alpha = 0.9, max.Iterasi = 1000, ukuran tabu list = 3
Cont… Pengujian data 20 job 10 mesin
Cont… Pengujian data 20 job 20 mesin
Pengujian data 50 job 5 mesin
Pengujian data 50 job 10 mesin
Pengujian data 50 job 20 mesin
Analisa dan Pembahasan Analisa Contoh Numerik Pada pengujian contoh numerik, dilakukan empat metode yaitu enumerasi, metode Cross Entropy, Tabu Search, dan Tabu Search-Cross Entropy sebagai cara penyelesaiannya. ketiga metode utama yang digunakan ini mempunyai solusi jadwal optimum yang sama dengan hasil metode enumerasi, hal ini dikarenakan ukuran dari data yang digunakan pada contoh numeric merupakan set data kecil, jadi semua metode dengan sangat mudah mendapatkan nilai global optimal Hasil contoh numerik ini bisa dibuktikan bahwa metode Tabu Search, Cross Entropy dan Hybrid Tabu Search-Cross Entropy dapat digunakan untuk menyelesaikan permasalahan penjadwalan produksi flowshop.
Cont… Analisa data 20 job 5 mesin Ketiga metode yang ada memiliki nilai makespan minimum yang sama. Hal ini bisa disebabkan karena ada kemungkingan data set uji yang digunakan memiliki dimensi yang belum cukup besar, sehingga semua metode memiliki nilai solusi yang sama. Ketiga metode tersebut juga memiliki kemungkinan untuk terjebak pada local optimal sehingga hasil yang didapatkan berada pada titik yang sama. Perubahan terhadap parameter jumlah sampel yang dibangkitkan pada bagian Cross Entropy dari metode Hybrid Tabu Search-Cross Entropy maupun perubahan parameter maksimum iterasi pada bagian Tabu Search dari metode Hybrid Tabu Search-Cross Entropy memiliki hasil yang tidak berbeda secara signifikan. Hal ini bisa disebabkan karena hasil yang didapat terjebak pada local optimal dari jumlah solusi yang sebanyak 20! (20 faktorial).
Cont… Analisa data 20 job 10 mesin Flowshop untuk 20 job 10 mesin didapatkan hasil bahwa metode Cross Entropy memiliki nilai makespan yang paling minimum diantara dua metode yang lain termasuk metode Hybrid Tabu Search-Cross Entropy. Hal ini bisa disebabkan karena metode Hybrid Tabu Search-Cross Entropy tidak mendapatkan inisial solusi yang baik dari metode Tabu Search. Pada setting parameter yang berbeda pada metode Hybrid Tabu Search-Cross Entropy dihasilkan bahwa pengaruh peningkatan jumlah sampel yang dibangkitkan juga akan mempengaruhi hasil makespan, begitu juga yang terjadi pada pengaruh nilai maksimum iterasi yang ditetapkan. Jika dibandingkan antara keduanya maka pengaruh kenaikan jumlah sampel yang dibangkitkan lebih besar dampaknya terhadap hasil makespan daripada pengaruh maksimum iterasi.
Cont… Analisa data 20 job 20 mesin Pada data uji 20 job 20 mesin menghasilkan bahwa metode Cross Entropy memiliki nilai makespan yang lebih baik jika dibandingkan dengan dua metode yang lain Hasil ini bisa saja disebabkan karena metode ini lebih cepat konvergen dengan menemukan hasil yang sudah bagus karena sudah menemukan hasil minimum pada waktu men-generate jadwal secara random. Perubahan parameter yang dilakukan untuk metode Hybrid Tabu Search-Cross Entropy justru menghasilkan nilai makespan yang lebih baik daripada hasil makespan metode Cross Entropy. Ini mengindikasikan bahwa peningkatan jumlah yang dibangkitkan pada metode Hybrid Tabu SearchCross Entropy sangat besar pengaruhnya terhadap nilai makespan.
Cont… Analisa data 50 job 5 mesin Metode Hybrid Tabu Search-Cross Entropy menghasilkan nilai makespan dan waktu komputasi yang lebih baik daripada metode yang lain. Hal ini bisa terjadi karena metode ini dibantu dengan adanya hasil inisialisasi dari metode Tabu Search, sehingga konvergensi dari metode ini sangat cepat dan hasilnya sudah terarah ke nilai yang optimal. Perubahan terhadap parameter jumlah sampel yang dibangkitkan pada bagian Cross Entropy dari metode Hybrid Tabu Search-Cross Entropy maupun perubahan parameter maksimum iterasi pada bagian Tabu Search dari metode Hybrid Tabu Search-Cross Entropy memiliki hasil yang berbeda.
Cont… Analisa data 50 job 10 mesin Metode Hybrid Tabu Search-Cross Entropy memiliki nilai makespan yang lebih baik jika dibandingkan dengan dua metode yang lain Hasil ini bisa saja disebabkan karena metode ini lebih cepat konvergen karena dengan bantuan hasil inisialisasi dari metode Tabu Search. Perubahan parameter yang dilakukan untuk metode Hybrid Tabu Search-Cross Entropy justru menghasilkan nilai makespan yang lebih baik daripada hasil makespan metode Hybrid Tabu Search-Cross Entropy dengan parameter awal. Ini mengindikasikan bahwa peningkatan jumlah yang dibangkitkan pada metode Hybrid Tabu Search-Cross Entropy sangat besar pengaruhnya terhadap nilai makespan.
Cont… Analisa data 50 job 20 mesin Metode Hybrid Tabu Search-Cross Entropy menghasilkan nilai makespan dan waktu komputasi yang lebih baik daripada metode yang lain. Hal ini bisa terjadi karena metode ini tingkat konvergensinya cepat yang berasal dari adanya hasil inisialisasi dari metode Tabu Search, sehingga hasilnya sudah terarah ke nilai yang optimal tanpa harus melebar ke solusi yang local optimal. Perbandingan terhadap perubahan parameter jumlah sampel yang dibangkitkan pada bagian Cross Entropy dari metode Hybrid Tabu Search-Cross Entropy maupun perubahan parameter maksimum iterasi pada bagian Tabu Search dari metode Hybrid Tabu SearchCross Entropy memiliki hasil yang kurang baik jika dibandingkan terhadap hasil metode Hybrid Tabu Search-Cross Entropy dengan parameter awal. Penyebabnya bisa saja karena pengaruh random jadwal yang dikeluarkan oleh metode Tabu Search maupun Cross Entropy kurang bagus.
Cont… Analisa Performa Keseluruhan Nilai makespan yang dihasilkan oleh ketiga metode jika dibandingkan terhadap hasil optimal yang didapatkan dari jurnal masih kurang baik. Hal ini bisa disebabkan karena ketiga metode tersebut sangat rentan terjebak pada local optimal, sehingga sangat besar peluangnya untuk tidak mendapatkan hasil yang global optimal. Sebenarnya metode Hybrid Tabu Search-Cross Entropy sudah dibuat untuk mengurangi adanya local optimal yang dibuat oleh metode Tabu Search dan Cross Entropy, akan tetapi metode ini ternyata masih kurang bagus jika dibandingkan dengan hasil jurnal yang ada.
Cont… Perbandingan Error Hasil Running Terhadap Hasil Optimal Jurnal 14.00%
Tingkat Error
12.00% 20x5
10.00%
20x10
8.00%
20x20
6.00%
50x5
4.00%
50x10
2.00%
50x20
0.00% CE
Tabu
CE-Tabu
Gambar 5.1 Perbandingan Error Hasil Running Terhadap Hasil Optimal Jurnal
Kesimpulan dan Saran Kesimpulan
Metode Cross Entropy, Tabu Search, dan Hybrid Tabu Search-Cross Entropy dapat diaplikasikan untuk penyelesaian Flowshop Scheduling Problem. Metode Hybrid Tabu Search-Cross Entropy dalam penyelesaian Flowshop Scheduling Problem menghasilkan nilai makespan dan waktu komputasi lebih baik daripada metode Tabu Search dan Cross Entropy untuk sebagian besar data uji. Perubahan jumlah sampel yang dibangkitkan pada metode Hybrid Tabu Search-Cross Entropy berpengaruh signifikan pada hasil makespan yang didapatkan daripada perubahan yang dilakukan pada maksimum iterasi. Dibandingkan dengan jurnal penelitian Taillard (1993), metode Tabu SearchCross Entropy kurang dapat menunjukan performansi yang lebih baik pada permasalahan yang ada.
Saran Penelitian selanjutnya bisa dilakukan dengan menerapkan algoritma Tabu Search-Cross Entropy unutk menyelesaikan kasus yang ada didunia nyata, bukan data sekunder..
Daftar Pustaka Baker, K. R., (1974), Introduction to Sequencing and Scheduling. Duke University: John Wiley&Sons. Ben-Daya, M., and Al-Fawzan, M. A., 1998. “A Tabu Search Approach for the Flowshop Scheduling Problem.” European Journal of Operational Research, Vol. 109, pp. 8895. Campbell, H. G., Dudek, R. A., & Smith, M. L., (1970), A Heuristic Algorithm for the njob, m-machine Sequencing Problem, Management Science, No. 16, B630-B637. Caserta, M., & Rico, E. Q., (2007). A Cross Entropy-Lagrangean Hybrid Algorithm for the Multi-Item Capacitated Lot-Sizing Problem with Setup Times, Journal of Computers and Operations Research. De Boer, P. T., Kroese, D.P., Mannor, S., & Rubinstein, R. Y., (2005), A Tutorial on the Cross-entropy method, Annals of Operations Research, vol. 134, No. 1, pp. 19-67. Fogarty, D. W., Blackstone, J. H., & Hoffman, (1991), Production and Inventory Management, South-Western Publishing Co., Cincinnati. Glover, F., (1989), Tabu Search part-I, Journal on Computing, vol 1, no.33. Glover, F., (1980), Tabu Search part-II, Journal on Computing, vol 2, no.1 Krone, M. J., & Steiglitz, K., (1971), Heuristic-Programming Solution of a FlowshopScheduling Problem, Operations Research, vol. 22, No. 3, pp. 629-638. Nawaz, M., Enscore, E. E., & Ham, I., (1983), A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem, International Journal of Management Science, vol. 11, No. 1, pp. 91-95. Pan, Q. K., Tasgetiren, M. T., & Liang, Y. C., (2008). A Discrete Differential Evolution Algorithm For The Permutation Flowshop Scheduling Problem, Journal of Computers and Industrial Engineering. Pinedo, M. L., (2008), “Scheduling : Theory, Algorithms, and Systems”, 3rd edition, USA: Springer.
Cont… Rajendran, C., & Ziegler, H., (2004). Ant-Colony Algorithms for Permutation Flowshop Scheduling to Minimize Makespan/Total Flowtime of Jobs, Journal of Computers and Industrial Engineering. Rera, G. F., (2010), Penerapan Metode Cross Entropy Dalam Penyelesaian Capacitated Vehicle Routing Problem, Tugas Akhir, Jurusan Teknik Industri ITS, Surabaya. Rubinstein, R.Y., (1999), The Cross-Entropy Method for Combinatorial and Continuous Optimization, Methodology and Computing in Applied Probability, vol 1, 127-190, Boston. Rubinstein, R. Y., & Kroese, D. P., (2004), The Cross Entropy; A Unified Approach to Combinatorial Optimiztion, Monte Carlo Simulation and Machine Learning, USA: Springer. Sahputra, I. H., Octavia, T., & Chandra, A. S., (2009), Tabu Search Sebagai Local Search Pada Algoritma Ant Colony Untuk Penjadwalan Flowshop, Jurnal Teknik Industri, vol. 11, No. 2, pp. 188-194. Sevkli, M., Tasgetiren, M. F., Liang, Y. C., & Gencyilmaz, G., (2006). A Particle Swarm Optimization Algorithm For Makespan And Total Flowtime Minimization In The Permutation Flowshop Sequencing Problem, European Journal of Operational Research. Taillard, E., (1993), Benchmarks of Basic Scheduling Problems, European Journal of Operational Research, vol. 64, pp. 278-285. Tseng, F. T., & Stafford, E. F., (2007), New MILP models for the permutation flowshop problem, Journal of the Operational Research Society.
LOGO
