PENDEKATAN CROSS ENTROPY-GENETIC ALGORITHM PADA PERMASALAHAN MULTI OBJECTIVE JOB SHOP SCHEDULING Liliek Nurkhalida, Budi Santosa Jurusan Teknik Industri Insitut Teknologi Sepuluh Nopember (ITS) Surabaya Kampus ITS Sukolilo Surabaya 60111 Email:
[email protected] ;
[email protected] Abstrak Multi Objective Job Shop Scheduling Problem (MOJSP) merupakan permasalahan penentuan urutan operasi dari beberapa job dengan mempertimbangkan lebih dari satu tujuan yang ingin dicapai.Hal ini menjadikan penyelesaiannya tidak mudah karena kompleksitas masalah yang tinggi.Perkembangan metoda optimasi untuk mencapai solusi permasalahan ini mendorong munculnya banyak metode penyelesaian baru.Penelitian ini menawarkan pendekatan alternatif Cross Entropy-Genetic Algorithm untuk menyelesaikan kasus job shop dengan multi objektif.Metoda ini merupakan sintesa dari algoritma Cross Entropy dan Genetic Algorithm. Algoritma hibrid ini telah berhasil diterapkan pada kasus job shop scheduling dengan objektif tunggal.Untuk mengakomodasi perhitungan multi objektif, digunakan pendekatan fungsi utilitas (pembobotan).Dari hasil eksperimen yang dilakukan, tampak Cross Entropy-Genetic Algorithm dapat menghasilkan solusi yang kompetitif dibanding metoda Simulated Annealing. Kata kunci: Multi Objective, Job Shop Scheduling, Cross Entropy-Genetic Algorithm.
ABSTRAK Multi Objective Job Shop Scheduling Problem (MOJSP) is a problem in defining optimal operation sequences of some jobs according to more than one goal to achieve. The problems get harder to solve because of its complexity. The development on optimization method has led many new methods to solve this problem. This research offers an approach of Cross EntropyGenetic Algorithm method to solve job shop scheduling problem with multi objectives. The method was born from recombination of Cross Entropy method with Genetic Algorithm. This algorithm has been successfully applied on single objective job shop scheduling. The weighted objective approach was proposed to accommodate multi objective calculation. From the experiment result shows that generally, Cross Entropy-Genetic Algorithm has competitive solution to Simulated Annealing. Keywords: Multi Objective, Job Shop Scheduling, Cross Entropy, Genetic Algorithm.
1. Pendahuluan Permasalahan job shop schedulingtermasuk kategori kasus NP-hard.Karena semakin besar ukuran problem, maka waktu komputasi yang diperlukan untuk menyelesaikan problem akan semakin lama. Membutuhkan waktu yang sangat lama untuk mendapatkan solusi optimal jika menggunakan pendekatan eksak.Sedangkan jumlah jobyang ditemukan dilapangan berjumlah hingga puluhan bahkan ratusan job. Disamping itu, kondisi real dilapangan lebih banyak dihadapkan pada pengambilan keputusan yang melibatkan banyak tujuan. Demikian halnya dengan penelitian pada job shop scheduling yang lebih condong pada pencapaian optimal dari beberapa objektif
(Multi Objective Job shop Scheduling Problem MOJSP). Oleh karenanya permasalahan menjadi semakin kompleks. Dibutuhkan suatu teknik khusus untuk mendapatkan penyelesaian yang memuaskan pada semua objektif. Tujuan dari penelitian ini adalah optimalisasi dua objektif yang umum ditemukan pada perusahaan manufaktur yaitu minimasi makespan dan Total Weighted Tardiness (TWT) (Fattahi P.,et.al. 2006). Dengan meminimumkan Total Weighted Tardiness akan menjamin tercapainya just-in-time pada sistem produksi. Sedangkan meminimumkan makespan dapat meningkatkan efisiensi utilitas resources produksi (Gao J. 2010). Berdasarkan hasil penelitian dari Fattahi P. et.al (2006) makespan
1
dan total weighted tardiness memiliki hubungan trade-off. Dimana upaya memperbaiki nilai suatu fungsi tujuan dalam waktu yang bersamaan akan memperburuk nilai fungsi tujuan lainnya. Cross Entropy merupakan algoritma metaheuristik yang cukup baru. Algoritma ini memiliki mekanisme pemilahan sampel elit yang akandigunakan sebagai dasar penentuan pembangkitan populasi sampel pada iterasi berikutnya. Dengan mekanisme ini, populasi sampel baru yang terbentuk akan terjaga dalam konvergensi ke arah solusi optimal. Cross Entropy telah berhasil diterapkan pada contoh kasus NP-hard lain seperti pada penyelesaian Generalized Orienteering Problem (Hardiansyah N. 2010), desain reliable networks (Altiparmak F., Dengiz B. 2008) dan penjadwalan diskrit-kontinyu dengan diskretisasi resource kontinyu (Jedrzejowicz P., Skakovski A. 2009). Metoda ini nantinya akan dihibridasi dengan Genetic Algorithm yang memiliki mekanisme pindah silang dan mutasi. Konsep ini berfungsi sebagai diversifikasi solusi optimal. Sehingga menghindari kemungkinan pencarian solusi terjebak di area lokal optimal. Selain itu, mekanisme elitisme yang tidak dapat dilakukan pada algoritma Cross Entropy dapat diperoleh dari Genetic Algorithm ini. Dengan elitisme, sampel dengan nilai solusi terbaik akan disimpan agar dapat muncul pada populasi sampel diiterasi berikutnya. Algoritma hibrid Cross Entropy-Genetic Algorithm ini telah berhasil diterapkan pada kasus job shop scheduling dengan objektif tunggal (Budiman M.A. 2010). Diharapkan algoritma hibrid Cross Entropy-Genetic Algorithmini dapat memberikan performansi yang baik pada kasus job shop dengan multi objektif. Yaitu berupa pendekatan solusi optimal minimal sama dengan referensi pembanding. Pada referensi pembanding menyelesaikan kasus yang sama menggunakan algoritma metaheuristik Simulated Annealing (Fattahi P., et.al. 2006). Pembanding ini dipilih karena menggunakan parameter objektif yang sama, yaitu meminimasi makespan dan Total Weighted Tardiness. 2. Deskripsi Permasalahan 2.1 Job Shop Scheduling Permasalahan penjadwalan sering kali menjadi aspek penting dilihat dari faktor
ekonomi. Problem mengerucut kepada bagaimana alokasi sumber daya yang ada dapat maksimal untuk memenuhi kebutuhan produksi. Permasalahan penjadwalan biasanya sulit ditemukan solusinya karena memiliki batasan yang beragam, dengan struktur produk yang akan diproduksi cukup kompleks, dan kemungkinan alur proses produksi yang sangat beragam (Fogel D.B. 2000). Job shop scheduling problem merupakan salah satu dari sekian banyak permasalahan penjadwalan yang ada. Baik dengan asumsi penyelesaian terhadap mono-objective problem atau multi-objective problem. Ataupun pertimbangan asumsi mengenai fleksibilitas proses dan asumsi-asumsi terkait lainnya. Dalam kondisi realnya, multiobjective problem dengan karakteristik proses yang fleksibel lebih banyak terjadi dalam industri manufaktur. Permasalahan Job Shop Scheduling dapat digambarkan dalam beberapa poin berikut: (Xu Q. 2001) οΌ Problem terdiri dari sejumlah n job, dimana setiap job terdiri dari serangkaian operasi yang berbeda. οΌ Untuk melakukan job ini, terdapat m mesin yang dapat digunakan, dengan syarat setiap mesin hanya dapat mengerjakan satu operasi dalam satu waktu. οΌ Setiap operasi akan diproses pada mesin yang telah ditentukan, dalam jangka waktu operasi tertentu, tanpa ada interupsi seperti mesin breakdown, kehabisan material dan lain sebagainya. οΌ Tujuannya adalah untuk mendapatkan jadwal, yang mana jadwal ini dapat mengalokasikan setiap operasi pada mesin yang tepat dengan mempertimbangkan interval waktu, sehingga didapatkan waktu penyelesaian job tercepat. Untuk kasus Multi-objective Job Shop Scheduling, objektif yang sering digunakan dalam penelitian-penelitian sebelumnya antara lain (Moslehi G., Mahnam M. 2010; Ramesh S., Cary J. M. 1989; Zhang G., et.al., 2009; Gao J., et.al., 2007): 1. 2. 3. 4. 5.
Meminimumkan makespan, Meminimumkan workload tiap mesin, Meminimumkan total workload mesin, Meminimumkan Total Weighted Tardiness , Meminimumkan keterlambatan,
2
6. Meminimumkan cost, dan 7. Meminimumkan total weighted completion time. 2.2 Cross Entropy Cara kerja dari algoritma Cross Entropy dapat digambarkan sebagai berikut: strategi perolehan informasi oleh algoritma ini adalah bagaimana mengambil sampel yang tepat dari ruang lingkup permasalahan dan mendapatkan gambaran distribusi dari solusi yang bagus. Dengan distribusi ini akan di-generate kandidat solusi baru. Distribusi ini akan terus di-update berdasarkan kandidat solusi yang lebih baik. Selanjutnya sampel akan dibangun berdasarkan rata-rata distribusi yang muncul dari solusi yang bagus. Algoritma akan terus mengulang skenario yang sama hingga distribusi sampel mengarah pada area solusi optimal. Secara garis besar, Cross Entropy akan melewati dua fase penting penyusun algoritmanya, yaitu: 1) Membangkitkan sampel dari data random, yang mengacu pada mekanisme random tertentu (sesuai dengan permasalahannya), dan 2) Meng-update parameter berdasarkan data sampel terbaik (sampel elit), dengan tujuan akan mampu menghasilkan sampel yang lebih baik pada iterasi berikutnya. 2.3 Genetic Algorithm Cara kerja dari Genetic Algorithm secara umum dapat dijelaskan sebagai berikut. Langkah awal adalah mendapatkan populasi dengan individu yang dibangkitkan secara random. Hal ini akan berlaku dalam setiap iterasi algoritma, yang dalam kasus Genetic Algorithm diistilahkan sebagai generasi populasi sampel. Pada setiap generasi, fitness dari masing-masing individu acak tadi di evaluasi, kemudian dipilih individu dengan nilai fitness terbaik. Individu terpilih ini (kromosom induk) selanjutnya akan dimodifikasi untuk membentuk populasi baru. Modifikasi terdiri dari dua jenis mekanisme, yaitu crossover (kawin silang) dan mutasi. Dari crossover dan mutasi akan didapatkan kromosom anak dengan jumlah sama dengan induknya. Populasi baru yang terdiri dari kromosom anak dan induk kemudian digunakan dalam generasi berikutnya. (www.wikipedia.com)
Tiga operasi dasar pada Genetic Algorithm adalah reproduksi, crossover, dan mutasi. Masing-masing operasi tersebut akan dijelaskan lebih lanjut pada poin-poin berikut. (Rao S.S. 2009): a) Reproduksi Merupakan operasi pertama yang diterapkan pada populasi untuk memilih kromosom terbaik sebagai pembentuk mating pool. Kromosom dipilih berdasarkan proporsi nilai fitness yang dimilikinya. Metoda yang terkenal adalah dengan mekanisme roda putar atau roulette wheel. Roda putar terdiri dari n yang sama dengan jumlah kromosom, dengan besarnya bagian itu bergantung pada proporsi fitness dari masing-masing kromosom. Roda akan diputar dan kromosom yang terpilih adalah yang bagiannya berada tepat dibawah anak panah penunjuk hasil ketika roda berhenti berputar. Semakin besar proporsi fitness yang dimiliki oleh sebuah kromosom, kemungkinan terpilih akan semakin besar. b) Crossover Crossover dilakukan setelah tahap reproduksi, dengan tujuan menghasilkan kromosom baru (kromosom anak) dengan menukar informasi antar kromosom yang ada dalam mating pool. Operator crossover yang digunakan pada penelitian ini adalah order crossover (OX). Dipilih dua kromosom induk secara acak dari mating pool, kemudian memilih dua crossover site (garis vertikal) secara random. c) Mutasi Operator mutasi akan merubah digit/gen dalam satu kromosom dengan nilai tertentu. Contoh metoda mutasi adalah single-point mutation. Dimana mutation site akan diperoleh secara random dan digit/gen pada site tersebut akan dirubah nilainya. Sebuah angka random akan dibangkitkan dengan batasan 0 hingga 1. Jika angka random tersebut lebih kecil dari operator mutasi Pm, maka digit gen diganti, namun jika tidak maka digit gen tidak dirubah. Tujuan dari mutasi adalah (1) untuk membangkitkan kromosom baru dengan tetap menjaga nature kromosom pada populasi awalnya, dengan demikian dapat mengoptimalkan pencarian di area solusi lokal. (2) mutasi hanya mengganti satu unit gen pada tiap kromosom untuk menghindari penggantian
3
terhadap gen yang sudah bagus, dan (3) untuk menjaga keragaman dalam populasi, sehingga masih terdapat beberapa alternatif solusi sebagai pilihan. 2.4 Permasalahan Multi Objektif Fungsi utilitas membantu mengkonversi permasalahan multiobjective menjadi permasalahan objektif tunggal. Caranya adalah dengan memberikan bobot preferensi tertentu pada masing-masing objektif. Dengan demikian beberapa objektif dapat dijadikan objektif tunggal dan mempermudah perhitungan tujuan yang ingin diselesaikan pada penelitian ini memiliki satuan yang berbeda, yaitu makespan dengan satuan waktu dan Total Weighted Tardiness dengan satuan mata uang. Sehingga untuk dapat menjumlahkannya perlu dilakukan normalisasi. Formula normalisasi yang akan digunakan berdasarkan persamaan pada penelitian Low C., et.al. (2005): distance =
π π€π
π π π₯ βππβ
(1)
ππβ βππβ
dimana π€π merupakan bobot dari objektif ke-i dari total K objektif, dan ππ=1 π€π = 1, ππβ sebagai solusi optimal dari objektif ke-i dan ππβ sebagai solusi terburuk dari objektif ke-i. 3. Algoritma yang Diusulkan Algoritma CEGA yang diusulkan pada penerapan dalam permasalahan multi objective job shop scheduling dapat dijelaskan sebagai berikut: Langkah I: Inisialisasi Kasus sederhana yang digunakan tampak pada Tabel 1 sebagai berikut: Tabel 1 Tabel Data Kasus 3 Job-3 Operasi-3 Mesin job
due date
1 2 3
17 15 11
weigh operasi 1 notasi ted mesin waktu
1 1 1
1 1 3
4 2 1
1 4 7
operasi 2 mesin waktu
3 2 1
2 5 3
notasi
2 5 8
operasi 3 mesin waktu
2 3 2
1 3 2
notasi
3 6 9
Parameter algoritma Cross Entropy-Genetic Algorithm yang digunakan pada contoh perhitungan ini yaitu: οΌ jumlah sampel (N) = 6 οΌ rho (Ο) = 0.02 οΌ alpha (Ξ±) = 0.8 οΌ parameter pindah silang (Pps) = 1 οΌ parameter pemberhentian (Ξ²) = 0.001 οΌ bobot fungsi tujuan makespan (bMS) = 0.5
οΌ bobot fungsi tujuan TWT (bTWT) = 0.5 Langkah II: Pembangkitan Sampel Bentuk sampel berupa notasi yang mewakili prioritas urutan operasi dari seluruh job. Sampel ini dibangkitkan secara random. Untuk keperluan validasi, maka dilakukan pembangkitan bilangan random yang membentuk sampel hingga sebanyak 6 sampel sebagai berikut: X1 X2 X3 X4 X5 X6
ο 4-5-7-6-1-2-3-8-9 ο 4-7-3-9-8-1-5-6-2 ο 1-9-7-8-4-6-5-2-3 ο 4-5-6-1-7-8-9-2-3 ο 6-3-7-8-5-1-2-4-9 ο 5-7-8-3-6-1-2-4-9
Sebagaimana diketahui pada Tabel 1, angka 4 pada sampel mewakili operasi pertama dari job 2, angka 8 merepresentasikan operasi kedua dari job 3 dan seterusnya. Langkah III: Penghitungan Fungsi Tujuan Untuk perhitungan fungsi tujuan, akan diberikan contoh perhitungan satu sampel, dan untuk sampel lain dihitung dengan langkah yang sama. Sampel yang digunakan dalam contoh adalah sampel pertama (X1) = 4-5-7-6-1-2-3-8-9. 1. Urutan pertama dari sampel 4-5-7-6-1-2-38-9 adalah operasi 4. Cek mesin yang digunakan oleh operasi 4 pada Tabel 1 dan posisi operasi tersebut pada gantt chart penjadwalan: a) Jika operasi tersebut tidak memiliki operasi prasyarat dan operasi pendahulu, maka letakkan operasi dengan waktu mulai = 0. b) Jika tidak terdapat operasi prasyarat namun terdapat operasi pendahulu, maka waktu mulai operasi = waktu selesai operasi pendahulu. c) Jika tidak terdapat operasi pendahulu namun terdapat operasi prasyarat, maka waktu mulai operasi = waktu selesai operasi prasyarat. d) Jika terdapat operasi prasyarat dan operasi pendahulu, maka waktu mulai operasi = waktu selesai terlama diantara operasi prasyarat dan operasi pendahulu.
4
X
4
5
1
7
8
2
3
9
didapat gantt chart akhir seperti pada Gambar 4 berikut:
6
m
2 6 mesin3 7 5 9 mesin2 3 mesin1 4 1 8 t 0 1 2 3 4 5 6 7 8 9 10 11 Gambar 1 Contoh Gantt Chart Penjadwalan Optimal
m mesin3 7 mesin2 mesin1 4 1 2
4
m mesin3 mesin2 mesin1
4 1
2
3
4
5
6
7
8
9 10 11 12 13 14 15
t
Gambar 2 Tahap 1 Penjadwalan Operasi pada Sampel X1
2. Untuk urutan berikutnya yaitu operasi 5 pada job 2, memiliki operasi prasyarat yaitu operasi 4 dan tidak memiliki operasi pendahulu pada mesin 2. Dengan menggunakan peraturan penempatan operasi seperti dijelaskan sebelumnya, maka waktu mulai operasi 5 adalah tepat setelah operasi 4 namun diletakkan pada baris mesin kedua, yaitu: X1
4
3
4
9
3
1 5
6
8 8
7
t
9 10 11 12 13 14 15
4. Kemudian tetapkan nilai makespan, yaitu dengan melihat waktu selesai dari operasi yang paling akhir dijadwalkan. Pada sampel X1 operasi terakhir yang dijadwalkan adalah 9 dengan waktu selesai = 15. Maka makespan untuk sampel X1 adalah 15 satuan waktu. m mesin3 7 mesin2 mesin1 4 1 2
6
2
5
3
1 3
4
5
6
7
8 8
9 t
9 10 11 12 13 14 15
Gambar 5 Penentuan Makespan
5. Langkah berikutnya adalah menghitung waktu keterlambatan pengerjaan suatu job (dari due date-nya), dikali dengan denda per satuan waktu keterlambatan. Kemudian Total Weighted Tardiness diperoleh dengan menjumlah total denda yang dikenakan pada semua job. Contoh perhitungan TWT untuk sampel X1 terdapat pada Tabel 2. Diketahui TWT sebesar 4. m mesin3 7 mesin2 mesin1 4 1 2
6
2
5
3
1 3
4
5
6
7
8 8
9
9 10 11 12 13 14 15
t
Gambar 6 Penentuan Waktu Selesai Tiap Job Tabel 2 Tabel Perhitungan TWT untuk Sampel X1 job1 job2 job3
due date
waktu selesai
weigthed
total weighted
17 15 11
13 10 15
1 1 1
max(0,(13-17)*1) max(0,(10-15)*1) max(0,(15-11)*1) 4
TWT
5
m mesin3 mesin2 mesin1 4 1 2
2
Gambar 4 Tahap Akhir Penjadwalan Operasi pada Sampel X1
Operasi prasyarat memiliki hubungan dalam satu job. Sedangkan operasi pendahulu memiliki hubungan dalam satu mesin. Contoh operasi prasyarat dan operasi pendahulu sebagaimana tampak pada Gambar 1. Operasi 2 dikatakan sebagai operasi prasyarat bagi operasi 3 (pada job 1) dan sebagai operasi pendahulu bagi operasi 6 pada mesin 3. Atau contoh lain, operasi 1 memiliki operasi pendahulu pada mesin 1 yaitu operasi 4, namun tidak memiliki operasi prasyarat (pada job 1). Sehingga, berdasarkan ketentuan penempatan operasi pada gantt chart, operasi ke-4 diletakkan pada baris mesin 1 dengan waktu mulai = 0, sebagaimana tampak pada Gambar 2. X1
6 5
Lakukan prosedur yang sama mulai proses 1 sampai 5 untuk sampel lainnya. 7. Setelah terhitung makespan dan TWT dari seluruh sampel, selanjutnya hitung nilai Z masing-masing sampel. Nilai Z sebagaimana persamaan (2), merupakan normalisasi nilai fungsi tujuan makespan dan TWT dari setiap sampel. Sehingga nilai objektif dapat ditampilkan dalam bentuk tunggal dan lebih mudah digunakan untuk keperluan evaluasi performansi antar sampel.
6. 5 3
4
5
6
7
8
9 10 11 12 13 14 15
t
Gambar 3 Tahap 2 Penjadwalan Operasi pada Sampel X1
3. Lakukan prosedur yang sama pada operasi lain yang belum terjadwalkan. Namun perlu diberi catatan. Ketika ditemukan operasi yang prasyarat-nya belum terjadwalkan, maka operasi tersebut tidak dapat dijadwalkan. Demikian seterusnya hingga seluruh operasi terjadwalkan. Sehingga akan
5
π=
πππππ πππ π βπππππ πππ πππ πππππ ππ π πππ₯ βπππππ πππ πππ
ππππ βππππππ ππππππ₯ βππππππ
β πππππ‘πππππ πππ
+
(2)
β πππππ‘πππ
Hasil perhitungan nilai makespan, TWT dan Z dari semua sampel direkap dalam Tabel 3 berikut: Tabel 3 Hasil Perhitungan Makespan, TWT, Z sampel makespan TWT Z X1 15 4 0.150 X2 18 1 0.300 X3 20 5 0.700 X4 17 5 0.400 X5 19 11 0.900 X6 19 11 0.900
Langkah IV: Penentuan Sampel Elit Nilai Z dari semua sampel kemudian di urutkan dari yang terkecil hingga terbesar. Dengan rho sebesar 0.02, maka jumlah sampel elit adalah N*rho = 6*0.02 = 0.12 β 1. Dari Tabel 4, diambil satu sampel teratas sebagai sampel elit. Yaitu sampel ke-1 (X1) dengan urutan prioritas operasi 4-5-7-6-1-2-3-8-9.
Karena proses ini merupakan iterasi pertama dan hanya terdapat 1 sampel elit, maka bobot sampel elit tersebut = 1. Langkah VII: Penghitungan Linear Fitness Rangking (LFR) Nilai LFR akan digunakan dalam pemilihan induk untuk proses pindah silang. LFR diperoleh melalui rumus: LFR(I(N-i+1)) = Fmax-(Fmax-Fmin)*((i-1)/(N1)) (3) dengan Fmax = 1/Z(1) = 6.67 dan Fmin = 1/Z(N) = 1/Z(6) = 1.11, maka LFR untuk semua sampel adalah: X1 ο LFR = 6.67-((6.67-1.11)*((1-1)/(6-1))) = 6.67 X2 ο LFR = 6.67-((6.67-1.11)*((2-1)/(6-1))) = 5.56 X3 ο LFR = 6.67-((6.67-1.11)*((3-1)/(6-1))) = 3.33 X4 ο LFR = 6.67-((6.67-1.11)*((4-1)/(6-1))) = 4.44 X5 ο LFR = 6.67-((6.67-1.11)*((5-1)/(6-1))) = 2.22 X6 ο LFR = 6.67-((6.67-1.11)*((6-1)/(6-1))) = 1.11
Tabel 4 Hasil Pengurutan Berdasarkan Nilai Z
sampel X1 X2 X3 X4 X5 X6
makespan 15 18 17 20 19 19
TWT 4 1 5 5 11 11
Z 0.150 0.300 0.400 0.700 0.900 0.900
Langkah V: Update Parameter Pindah Silang Setiap iterasi akan dilakukan update parameter pindah silang, dimana semakin banyak iterasi maka parameter pindah silang akan semakin kecil. Hal ini diperlukan untuk mendapatkan nilai parameter yang update untuk evaluasi kriteria pemberhentian. ππ
π’ = 2βπ Pps(1)
πππ π‘
=
0.143 2β0.143
= 0.5
= (1- πΌ)*u + (Pps(0)*πΌ) = (1-0.8)*0.5 + (1*0.8) = 0.9
Langkah VI: Pembobotan Sampel Elit Bobot untuk sampel elit diperoleh dari evaluasi terhadap nilai terbaik pada iterasi sebelumnya.
Langkah VIII: Elitisme Tujuan dari adanya mekanisme elitisme adalah untuk menyimpan sampel dengan nilai fungsi tujuan terbaik pada setiap iterasi. Sampel ini nantinya akan muncuk kembali pada populasi sampel di iterasi berikutnya. Jumlah sampel yang di elitisme sebanyak satu sampel. Pada kasus ini, maka sampel yang di elitisme adalah X1 ο 4-5-7-6-1-2-3-8-9 Langkah IX: Pemilihan Induk untuk Pindah Silang Dengan menggunakan mekanisme roulettee wheel, dilakukan pemilihan induk 1 dari sampel elit dan induk 2 dari sampel keseluruhan. a. Pemilihan induk 1 ο untuk setiap sampel dilakukan pengambilan nilai random, dan untuk sampel X1 didapatkan angka random 0.6948. Nilai kumulatif bobot dari sampel dibagi dengan total bobot dibandingkan dengan nilai random. Apabila nilai pembagian tersebut lebih besar dari nilai random, maka sampel tersebut diambil sebagai induk 1. Karena hasil pembagian bernilai 1, maka sampel X1 ditetapkan sebagai induk 1. 6
b. Pemilihan induk 2 ο dengan prosedur yang hampir sama dengan pemilihan induk 1, induk 2 dipilih. Yang membedakan adalah nilai evaluasi. Pada proses ini, menggunakan nilai LFR dari sampel yang sedang dievaluasi. Apabila nilai perbandingan antara kumulatif LFR dan total LFR lebih besar dari nilai random, maka sampel tersebut menjadi induk 2. Total LFR = 6.67+5.56 +3.33 +4.44 + 2.22 +1.11 = 23.33 Untuk X1 = 6.67/23.33 = 0.29 < 0.6227 X2 = (6.67+5.56)/23.33 = 0.52 < 0.6227 X3 = (6.67+5.56+3.33)/23.33=0.71> 0.6227 Berdasarkan prosedur dan hasil perhitungan diatas, diketahui sampel X3 ditetapkan sebagai induk 2. Langkah X: Pindah Silang (Cross Over) Dari langkah sebelumnya diperoleh X1 sebagai induk 1 dan X3 sebagai induk 2. Apabila dalam pembangkitan bilangan random diperoleh bilangan random lebih kecil dari parameter pindah silang, maka dilakukan pindah silang terhadap kedua induk tersebut. Namun jika bilangan random lebih besar dari parameter pindah silang, maka tidak terjadi pindah silang. Hasil bilangan random yang dibangkitkan sebesar 0.015, lebih kecil dari Pps (0.9) sehingga dilakukan pindah silang antara X1 dan X3. Untuk menentukan bagian dari sampel induk yang akan ditukar, maka dilakukan mekanisme sebagai berikut: dengan membangkitkan dua bilangan random, diperoleh bilangan 0.6948 dan 0.8491. Nilai random tersebut kemudian dikonversi menjadi nilai bulat, dan digunakan sebagai pembatas bagian sampel yang akan di pindah antar induk. ri = ceil (random*n) r1 = ceil(0.4387*9) = 4 ο p1 = 4 r2 = ceil(0.8491*9) = 8 ο p2 = 8
(4)
induk1 = 4 5 7 6 π π π π 9 induk2 = 1 9 7 8 π π π π 3 Kemudian angka yang didalam kurung dan tebal ditukar antar induk menjadi seperti berikut: calon_anak_1 = β¦ β¦ β¦ β¦ 4 6 5 2 β¦ calon_anak_2 = β¦ β¦ β¦ β¦ 1 2 3 8 β¦
Untuk mengisi titik-titik pada calon_anak_1, maka diperiksa satu per satu operasi pada induk1. Jika terdapat operasi pada induk 1 yang belum tercantum pada calon_anak_1, maka operasi tersebut akan mengisi titik-titik. Hal ini dilakukan secara berurutan. Sehingga sampel anakan hasil pindah silang menjadi: anak1 = 7 1 3 8 4 6 5 2 9 ο menggantikan X2 anak2 = 9 7 4 6 1 2 3 8 5 ο menggantikan X3 Kemudian ulangi dengan mengevaluasi sampel ke-5 dan sampel ke-6. Dengan perhitungan yang sama dengan awal, diketahui induk1 = X1 dan induk2 = X3. Dengan random 0.9841 yang lebih besar dari Pps (0.9), maka tidak terjadi pindah silang. Induk1 dan induk2 digunakan untuk mengganti sampel ke-5 dan ke-6, sehingga populasi baru menjadi X1 ο 4-5-7-6-1-2-3-8-9 X2 ο 7-1-3-8-4-6-5-2-9 X3 ο 9-7-4-6-1-2-3-8-5 X4 ο 4-5-6-1-7-8-2-3-9 X5 ο 5-7-8-4-6-1-2-3-9 X6 ο 7-3-8-6-1-4-5-2-9 Langkah XI: Mutasi Parameter mutasi menggunakan setengah dari nilai parameter pindah silang, yaitu 0.9/2 = 0.45. Berikut perhitungan mutasi untuk contoh kasus ini: Untuk X3, dimana i = 1 dan r = 0.1174 (< Pm), maka dilakukan mutasi pada gen ke-a dan gen ke-b dimana a = ceil(r*n) = ceil(0.1174*9) = 2 dan b = X3(1,i) = X3(1,1) = 7. X3 = 9-7-4-6-1-2-3-8-5ο 9-3-4-6-1-2-7-8-5 Dan untuk X3, dimana i = 2 dan r = 0.7757 (> Pm), maka tidak dilakukan mutasi. Prosedur ini dilakukan berulang hingga seluruh operasi dalam suatu sampel terevaluasi dan seluruh sampel dalam populasi terevaluasi kecuali sampel elitisme. Hasil akhir dari mutasi untuk semua sampel yang dimutasi adalah X2 ο 7-8-5-6-4-2-3-1-9 X3 ο 9-3-6-8-1-2-4-7-5 X4 ο 1-7-6-3-4-8-2-5-9 X5 ο 3-9-5-4-6-1-2-8-7 X6 ο 2-9-8-6-1-3-5-7-4
7
Langkah XII: Menghitung Nilai Fungsi Tujuan Populasi Baru Setelah melakukan proses pindah silang dan mutasi, diperoleh populasi sampel dengan anggota yang baru. Dimana anggota ini terdiri dari sampel hasil elitisme, sampel hasil pindah silang, dan sampel hasil mutasi. Rekap hasil perhitungan nilai fungsi tujuan terdapat dalam Tabel 5. Tabel 5 Hasil Perhitungan Makespan, TWT, Z Populasi Iterasi 1
sampel ke- makespan 1 15 2 19 3 20 4 15 5 18 6 20
TWT 4 8 6 3 7 6
Z 0.1 0.9 0.8 0.00 0.70 0.8
4. Eksperimen Data Uji Untuk menguji performansi algoritma pada permasalahan penjadwalan job shop ini, digunakan data yang sudah memiliki hasil sehingga dapat dibandingkan secara langsung. Data uji tersebut berasal dari jurnal penelitian Fattahi P et.al. (2006). Algoritma yang digunakan dalam jurnal tersebut adalah Simulated Annealing. Eksperimen dilakukan pada software Matlab 7.10 (r2010a).
date untuk setiap job. Untuk keterlambatan (weighted) diberi nilai 1.
denda
Tabel 7. Data Input Eksperimen MOJ 1
Tabel 8. Data Input Eksperimen MOJ 2
Tabel 9. Data Input Eksperimen MOJ 3
Tabel 10. Data Input Eksperimen MOJ 4
4.1 Pengumpulan Data Data uji berupa tabel yang berisi informasi mesin dan waktu yang dibutuhkan masingmasing operasi dari beberapa job. Terdapat empat tipe soal dengan ukuran permasalahan yang berbeda. Deskripsi secara singkat ditampilkan pada Tabel 6 berikut: Tabel 6. Deskripsi Problem MOJSP Fattahi P et.al (2006)
tipe problem
jumlah job
jumlah operasi
jumlah mesin
MOJ 1 MOJ 2 MOJ 3 MOJ 4
4 6 10 15
3 4 4 4
3 4 6 7
4.2 Hasil Uji Eksperimen Berikut tabel perbandingan hasil eksperimen data uji antara algoritma Simulated Annealing dengan Cross Entropy-Genetic Algortihm.
Tabel data uji terdiri dari informasi jenis job, operasi tiap job, mesin yang digunakan oleh tiap operasi, waktu proses tiap operasi dan due
8
Tabel 11. Tabel Perbandingan Solusi SA dan CEGA
Untuk lebih memperjelas performansi yang dimiliki CEGA, berikut tabel yang menunjukkan gap antara solusi makespan SA-makespan CEGA dan TWT SA-TWT CEGA. Tabel 12. Perbandingan GAP Solusi MOJ 1
Tabel 13. Perbandingan GAP Solusi MOJ 2
Tabel 14. Perbandingan GAP Solusi MOJ 3
Tabel 15. Perbandingan GAP Solusi MOJ 4
5. Analisa Hasil Eksperimen Angka merah pada Tabel 11 menunjukkan terdapat gap antara hasil SA dan CEGA.Namun dapat dilihat bahwa angka merah hanya berada pada kolom TWT. Atau dengan kata lain, seluruh solusi makespan dari CEGA berhasil diperoleh tanpa ada gap dengan solusi makespan dari SA. Hal ini memungkinkan karena pada faktanya solusi CEGA diambil dari sejumlah N solusi makespan-TWT. Dengan nilai N yang besar, kemungkinan untuk menemukan solusi yang mendekati atau bahkan sama juga besar. Nilai makespan untuk beberapa kombinasi urutan prioritas operasi bisa sama. Karena makespan hanya memperhitungkan waktu total penyelesaian dari keseluruhan job. Sedangkan nilai TWT dapat berbeda pada urutan yang memiliki makespan yang sama. Karena TWT memperhitungkan waktu penyelesaian dari tiap job.Dimana kombinasinya bisa cukup banyak. Untuk kasus MOJ 1, murni tidak terdapat gap antara SA dan CEGA, baik makespan maupun TWT. Dengan demikian CEGA dapat dikatakan cukup efektif untuk menyelesaikan permasalahan skala kecil. Begitu pula dengan kasus MOJ 2. Hanya terdapat satu angka merah dengan gap sebesar 5.3%. Dengan pencapaian maksimal dari alternatif solusi lain, maka gap dari satu solusi ini dapat dianggap tidak terlalu signifikan. Sehingga CEGA dapat dikatakan cukup efektif pada skala permasalahan 2 kali lebih besar dari MOJ 1. Keberhasilan ini dapat dicapai karena banyaknya solusi optimal alternatif yang dihasilkan oleh CEGA. Dengan bobot preferensi yang sama antara kedua objektif, CEGA mampu memberikan solusi optimal sekaligus nondominated pada kasus MOJ 1 dan MOJ 2. Untuk kasus MOJ 3, tampak hampir semua solusi TWT alternatif berwarna merah.Dengan gap paling besar adalah 33.53% pada solusi alternatif ke-4.Hal ini disebabkan CEGA tidak memiliki mekanisme penyimpanan solusi nondominated.Sehingga dibutuhkan usaha yang lebih besar untuk menghasilkan alternatif solusi yang lebih banyak. Dengan banyaknya solusi tersebut akan muncul kemungkinan solusi optimal lain yang lebih mendekati nilai TWT SA. Untuk kasus MOJ 4, tampak sama dengan performansi pada kasus MOJ 3, yaitu hanya satu angka yang tidak berwarna merah diantara solusi alternatif lainnya. Namun gap TWT pada MOJ 4 adalah gap negatif. Artinya solusi TWT
9
CEGA lebih baik dari SA. Hal ini menunjukkan bahwa proses pencarian solusi pada CEGA lebih luas dari SA. Seperti telah disebutkan sebelumnya, SA mengevaluasi solusi berdasarkan local search. Sehingga peluang untuk mendapatkan kemungkinan solusi diluar area pencarian cukup kecil. Sedangkan CEGA terus mengalami diversifikasi melalui proses pindah silang dan mutasi. Proses diversifikasi ini memungkinkan pencarian solusi yang belum tereksplor sebelumnya. Dalam hal ini, CEGA lebih unggul daripada SA. Disamping itu, algoritma SA yang diusulkan dalam jurnal tersebut memiliki kriteria pemberhentian yang diatur sedemikian rupa. Kriteria pemberhentian tambahan dimasukkan kedalam algoritma untuk mengurangi waktu komputasi.Sehingga kemungkinan perluasan pencarian solusi menjadi terbatas. Namun demikian, TWT CEGA pada alternatif solusi 1 lebih kecil dari TWT CEGA pada alternatif 2 dan 3. Dilihat dari nilai makespan juga, menjadikan alternatif solusi 2 dan 3 terdominasi oleh alternatif solusi 1. Hal ini bertentangan dengan salah satu konsep pareto yang menyatakan bahwa solusi dalam set
solusi pareto tidak saling mendominasi satu sama lain. Fenomena ini muncul dikarenakan mekanisme CEGA yang memperhitungkan pengambilan solusi berdasarkan nilai pada fungsi tunggal, bukan pada konsep pareto.
7. Daftar Pustaka
De Boer, Pieter-Tjerk, Kroese Dirk P., Mannor S., Rubinstein R.Y. 2003, βA tutorial on the Cross-Entropyβ, Haifa: Department of Industrial Engineering, Technion β Israel Institute of Technology. Dreo J., Petrowski A., Siarry P., Taillard E. 2006, Metaheuristics for Hard Optimization, Springer, Heidelberg. Esquivel S., Ferrero S., Gallard R., Salto C., Alfonso H., Schutz M. 2002, βEnhanced evolutionary algorithms for single and multiobjective optimization in the jobshopschedulingproblemβ, Knowledge Based System, vol.15, pp.13-25. Fattahi P., Mehrabad M.S., Aryanezhad M.B. 2006, βAn algorithn for multi objective job shop schedulingβ, Journal of Industrial Engineering International, vol.2, no.3, pp.43-53. Fogel D.B. 2000, βWhat is evolutionary computation?β,IEEE Spectrum, pp.26-32. Gao J. 2010, βA novel artificial immune system for solving multi objective scheduling problems subject to special process contraintβ, Computers & Industrial Engineering, vol.58, pp.602-609.
Altiparmak F., Dengiz B. 2008, βA cross entropy approach to design of reliable networksβ, European Journal of Operational Research, vol.199, pp.542-552. Anonim. Pareto Optimality, Optimization in Engineering Design, System Realization Laboratory, Georgia Institute of Technology, handout lecturer. Baker K.R., Trietsch D. 2009, Principles of sequencing and scheduling, A John Willey & Sons, Inc. Publication, New Jersey. Budiman M.A. 2010, βPendekatan Cross Entropy-Genetic Algorithm untuk permasalahan penjadwalan job shop tanpa waktu tunggu pada banyak mesinβ, Surabaya: Institut Teknologi Sepuluh Nopember. Ciptomulyono U. 2011, Goal Programming, Basics, Handout lecturer,p.30. Doerner K.F., Gendreau M., Greistorfer P., Gutjahr W.J., Hartl R.F., Reimann Marc.(eds) 2007, Metaheuristics, Progress in Complex Systems Optimization, Springer Science+Business Media, New York.
6. Kesimpulan Dari hasil eksperimen maupun analisis yang telah dilakukan, maka dapat disimpulkan bahwa hibridasi Cross Entropy-Genetic Algorithm terbukti efisien. Karena dapat menghasilkan solusi yang kompetitif terutama pada problem skala kecil. Namun demikian algoritma ini memiliki kekurangan dan kelebihan. Cross Entropy-Genetic Algorithm lebih unggul dari segi diversifikasi solusi dibanding Simulated Annealing yang menggunakan mekanisme neighborhood search. Namun, Cross EntropyGenetic Algorithm lebih buruk dari sisi penentuan solusi non-dominated karena hanya melakukan evaluasi solusi berdasarkan nilai objektif tunggal.
10
Gao J., Gen M., Sun L., and Zhao X. 2007, βA hybrid of genetic algorithm and bottleneck shifting for multiobjective flexible job shop scheduling problemsβ, Computers & Industrial Engineering, vol.53, pp.149-162. Glover F., Kochenberger G.A. 2003, Handbook of Metaheuristics, Kluwer Academic Publishers, New York. Hardiansyah N. 2010, βPenerapan metode cross entropy dalam penyelesaian generalized orienteering problem (studi kasus: best tour in China)β Jedrzejowicz P., Skakovski A. 2009, βA crossentropy-based population-learning algorithm for discrete-continuous scheduling with continuous resource discretisationβ, Neurocomputing, vol.73, pp.655-660. Kroese, Dirk P. 2009, βCross-Entropy Methodβ, Brisbane: Mathematics Department, Univerisity of Queensland. _____, βCross-entropy methodβ, http://iew3.technion.ac.il/CE/tutor.php, diakses pada 2 Maret 2011 Low C., Wu T.H., Ming Hsu C. 2005, βMathematical modelling of multi-objective job shop scheduling with dependent setups and re-entrant operationsβ, International Journal Advanced Manufacturing Technology, vol.27, pp.181-189. Moghaddam R.T., Azarkish M., Barkousaraie A.S. 2010, βSolving a multi objective job shop scheduling problem with sequencedependent setup times by a pareto archive PSO combined with genetic operators and VNSβ, International Journal Advance Manufacturing Technology. Moslehi G., Mahnam M. 2010, βA pareto approach to multi-objective flexsible jobshop scheduling problem using particle swarm optimization and local searchβ, International Journal Production Economics,vol.129, pp.14-22. Ramesh S., Cary J. M. 1989, βMulticriteria job shop schedulingβ, Computer Industrial Engineering, vol.17, no.1-4, pp.597-602. Rao S.S. 2009, Engineering Optimization: Theory and Practice, Fourth Edition, John Willey & Sons, Inc., New Jersey. Santosa B., Willy P. 2011, Metoda Metaheuristik Konsep dan Implementasi, Guna Widya, Surabaya. Sakawa M., Kubota R. 2000, βFuzzy programming for multi objective job shop
scheduling with fuzzy processing time and fuzzy due date through genetic algorithmsβ, European Journal of Operational Research, vol.120, pp.393-407. Vilcot G., Billaut J. 2008, βA tabu search and a genetic algorithm for solving a bicriteria general job shop scheduling problemβ, European Journal of Operational Research, vol.190, pp.398-411. Xu Q. 2001, βIntroduction to job shop scheduling problemβ. Handout lecturer Yen G.G. and Ivers B. 2008, βJob shop scheduling optimization through multiple independent particle swarmsβ, International Journal of Intelligent Computing and Cybernetics, vol.2, no.1, pp.5-33. Zhang G., Shao X., Li P., and Gao L. 2009, βAn effective hybrid particle swarm optimization algorithm for multi objective flexiblejob shop scheduling problemβ, Computers& Industrial Engineering, vol.56, pp.13091318. http://www.en.wikipedia.org/wiki/Crossentropy_method, diakses pada 21 Februari
2011. http://iew3.technion.ac.il/CE/,
diakses
pada
3
Februari 2011. http://lancet.mit.edu/%7Embwall/presentations/Intro ToGAs/, diakses pada 3 Februari 2011.
11
