Penerapan Algoritma Ant Colony Optimization (ACO) untuk Menyelesaikan Penjadwalan Flowshop dengan Tujuan Meminimumkan Makespan

Oleh:

Yuliana Vina Humira 25407044
Lisa Setyawati H. 25407052
Henry Rahardian S. 25407119
Yunita Hartanto 25408066

JURUSAN TEKNIK INDUSTRI

FACULTY OF INDUSTRIAL TECHNOLOGY

PETRA CHRISTIAN UNIVERSITY

SURABAYA

2011
Penerapan Algoritma Ant Colony Optimization (ACO) untuk Menyelesaikan Penjadwalan Flowshop dengan Tujuan Meminimumkan Makespan

1. Pendahuluan
Penjadwalan adalah proses pengambilan keputusan dimana melibatkan beragam sumber daya, antara lain manusia/pekerja, mesin, material, energy, uang, waktu, ruang, yang tersedia secara terbatas untuk menyelesaikan sekumpulan job dalam jangka waktu tertentu. Tujuan proses penjadwalan tergantung dengan apa yang ingin diminimalisasikan oleh perusahaan, misalnya meminimalkan keterlambatan, mean flow time, mean tardiness, makespan.
Di dalam permasalahan penjadwalan flowshop untuk karakteristik n jobs m machines adalah waktu penyelesaian job yang sangat panjang sehingga efisiensi perusahaan rendah. Laporan ini akan membahas ant colony algorithm, yang merupakan algoritma metaheuristik yang bersifat konstruktif dengan tujuan meminimalisasikan makespan.

2. Ant Colony Algorithm (M’Hallah & Alhajraf, 2008)
Ant Colony Optimization (ACO) algorithm merupakan salah satu algoritma kostruktif metaheuristik. ACO meniru perilaku koloni semut yang dikenal dengan perilaku sosialnya yang kompleks dan bekerja secara kooperatif dengan mengabaikan kebutaan yang dialami oleh semut. Semut mengidentifikasi jalur terpendek antara sarang mereka dengan sumber makanan tanpa menggunakan petunjuk visual. Mereka bertukar informasi tentang sumber makanan yang ada dengan mengeluarkan substansi kimia, yaitu pheromone di jalur antara sarang semut dan sumber makanan. Semut berbeda yang mencari makanan merasakan pheromone yang ditinggalkan oleh semut sebelumnya dan mengikuti jalur dengan konsentrasi pheromone yang kuat dengan harapan pheromone tersebut akan menuntun mereka ke sumber makanan dengan cepat. Mereka memilih jalur mereka dengan probabilitas keputusan bias dengan jumlah pheromone, yaitu semakin besar jumlah jejak pheromone maka semakin tinggi probabilitas semut akan mengikuti jalur tersebut. Pada keadaan absennya pheromone, semut akan bergerak secara random.Seiring berjalannya waktu, jaur terpendek antara sarang semut dan sumber makanan memiliki traffic density yang tinggi sedangkan pheromone berevaporasi sepanjang jalur dengan low-density. Perilaku ini mengarah kepada proses self-reinforcing, di mana sebagai gantinya mengarah kepada identifikasi jalur terpendek antara sarang semut dan sumber makanan.

3.1 Prinsip Dasar Ant Colony Algorithm
Ant Colony System (ACS) algorithm adalah salah satu algoritma metaheuristik untuk permasalahan optimisasi kombinasi. ACS terinspirasi oleh penelitian pada perilaku semut. Semut memiliki kemampuan untuk menemukan jalur terpendek dari sumber makanan ke sarang mereka tanpa menggunakan bantuan visual.
ACS menggunakan semut buatan dengan menggunakan beberapa asumsi, yaitu: * Setiap semut buatan memiliki beberapa memori. * Semut buatan tidak buta secara keseluruhan. * Semut buatan hidup di sebuah lingkungan, di mana satuan waktu diskret (Vlachos, 2006).
Prinsip umum untuk simulasi ACS dari perilaku semut sesungguhnya adalah setiap semut nantinya akan membawa satu solusi permasalahan. Nilai fungsi pheromone trail menunjukkan kualitas solusi yang telah dicapai oleh semut dari perjalanannya sebelumnya, sedangkan informasi heuristik sesuai dengan input data dari suatu permasalahan. Dalam hal ini fungsi objektif yang diinginkan adalah meminimumkan makespan.
Parameter pheromone trail dan informasi heuristic memiliki bobot yang digunakan untuk menunjukkan perbandingan tingkat kualitas antara kualitas semut sebelumnya dengan kualitas dari job itu sendiri. Parameter pheromone trail diberi bobot sebesar α, sedangkan parameter informasi heuristik diberi bobot sebesar β. Nilai dari parameter α dan β dapat dikombinasikan untuk menghasilkan solusi yang baik. Dalam menghasilkan solusi pada setiap tahapan, maka semut melakukan proses eksploitasi dan eksplorasi berdasarkan probabilitas tertentu. Apabila dilakukan proses eksploitasi, maka semut akan memilih nilai fungsi pheromone trail dan informasi heuristik yang paling baik. Apabila dilakukan proses eksplorasi, semut akan melakukan penyelidikan dengan memilih salah satu solusi berdasarkan nilai probabilitas dari fungsi pheromone trail dan informasi heuristik. Pengambilan keputusan untuk melakukan proses eksploitasi atau eksplorasi berdasarkan nilai random (q) yang berdistribusi U[(0,1)]. Jika q < q0 maka akan melakukan eksploitasi sebaliknya semut melakukan eksplorasi.
Solusi yang dipilih dari setiap semut akan dimasukkan ke dalam tabu list, yaitu daftar solusi yang tidak boleh dipilih pada tahapan berikutnya. Setelah semut memilih satu solusi dan dimasukkan ke dalam tabu list, maka nilai pheromone trail akan melakukan evaporasi. Kegiatan ini dilakukan oleh semua semut di dalam satu koloni. Setelah satu koloni semut menyusun suatu kombinasi, maka akan dilakukan pemilihan semut terbaik yang akan dibandingkan dengan semut terbaik secara global. Nilai pheromone trail dari job terbaik secara global akan mengalami evaporasi, sehingga mempengaruhi semut pada koloni berikutnya menyusun urutan job. Nilai pheromone trail mengalami evaporasi menghindari semut terlalu cepat mencapai konvergensi pada keadaan lokal optimum. (Pranata, 2006)

3.2 Parameter Ant Colony Algorithm (Pranata, 2006)
Berikut merupakan parameter yang digunakan pada Ant Colony Algorithm: * Jumlah koloni semut(NCmax), yaitu jumlah siklus yang dibutuhkan dalam mencari solusi. Semakin banyak jumlah siklus, semakin optimal solusi yang dihasilkan. * Jumlah semut (m), yaitu jumlah semut pada setiap koloni yang mewakili jumlah kombinasi pada tiap siklus. Setiap semut dalam koloni mencari solusi dan meletakkannya dalam tabu list. Semakin banyak jumlah semut, semakin banyak kombinasi solusi yang dapat dipilih. * Pheromone trail (τij), yaitu zat kimia yang dikeluarkan oleh semut untuk menandai jalan dari sumber makanan ke sarangnya. Adanya pheromone trail agar menuntun semut lainnya untuk mencari jalan sependek mungkin. * Informasi heuristic (ηij), yaitu visibilitas suatu job dipilih pada tiap tahapan berdasarkan nilai fungsi secara matematis. * Tingkat kepentingan relative pheromone train (α), yaitu bobot yang diberikan pada pheromone trail (τij), sehingga solusi yang dihasilkan cenderung mengikuti sejarah masa lalu semut dari perjalanan sebelumnya. α ≥ 0 * Tingkat kepentingan relative informasi heuristic (β), yaitu bobot yang diberikan pada informasi heuristik (ηij), sehingga solusi yang dihasilkan cenderung berdasarkan nilai fungsi matematis. β ≥0 * Koefisien evaporasi (ρ), yaitu bobot penguapan untuk pheromone trail. Penguapan pheromone trail menyebabkan tidak semua semut mengikuti jalur sebelumnya.0 ≤ ρ ≤1 * Probabilitas semut melakukan eksploitasi pada tiap tahap (q0), 0 ≤ q0 ≤1

3.3 Prosedur Ant Colony Algorithm (Pranata, 2006)
Ant Colony Algorithm menggunakan cara kerja koloni semut untuk mencari jalur terpendek dalam pergi ke sumber makanan. Semua semut akan memilih nilai terbaik pada tiap tahapan. Hal tersebut dipengaruhi oleh pheromone trail sebelumnya dan informasi heuristic. Selama perjalanan, pheromone trail mengalami penguapan dengan koefisien tertentu sehingga tidak semua semut melewati jalur yang sama. Mekanisme pemilihan solusi oleh semut dilakukan melalui dua proses, yaitu: * Eksploitasi, semut memilih job yang memiliki nilai fungsi pheromone trail dan informasi heuristic tertinggi di antara kandidat job yang ada. Persamaan memilih job berdasarkan eksploitasi:
Job j=arrange maxh∈Ωτijαηijβ
Ω= himpunan job yang belum dimasukkan ke dalam tabu list (k) * Eksplorasi, semut melakukan penyelidikan terhadap suatu job dengan probabilitas pemilihan berdasarkan nilai fungsi pheromone trail dan informasi heuristic. Proses ini menghasilkan lebih banyak alternative solusi, sehingga mengurangi kemungkinan terjebak pada keadaan optimum local. Persamaan memilih job berdasarkan eksplorasi:
Pij=τijαηijβ0τijαηijβ jika j∈ Ω Setelah setiap semut memilih satu job ke dalam tabu list pada urutan tertentu, pheromone trail dari job pada urutan tersebut akan mengalami evaporasi yang disebut proses local trail update. Persamaan local trail update: τijt+1=1-ρτijt+ρτ0 τ0=1n.TSTP

τ0= pheromone trail awal
TSPT= nilai fungsi tujuan dari metode Shortest Processing Time Setelah semua job dimasukan dalam tabu list,nilai fungsi tujuan dari setiap semut dihitung. Semut terbaik dari tiap siklus dibandingkan dengan solusi terbaik secara global dari siklus sebelumnya. Pheromone trail solusi terbaik secara global akan mengalami evaporasi, yang dikenal dengan proses global trail update. Persamaan global trail update: τijt+1=1-ρτijt+ρ∆τij(t) ∆τijt=1T* untuk setiap i,j dari solusi terbaik0 selain itu
T*= nilai fungsi tujuan dari penerapan Ant Colony Algorithm

Proses pencarian solusi oleh setiap semut akan dilakukan secara berulang sampai jumlah siklus yang ditetapkan terpenuhi. Setelah terpenuhi, dipilihlah nilai fungsi tujuan terbaik secara keseluruhan yang merupakan solusi optimal.

Gambar 1. Flowchart Ant Colony Algorithm 3.4 Penerapan Ant Colony Algorithm untuk Penjadwalan Flowshop (Pranata, 2006)
Penjadwalan produksi merupakan salah satu permasalahan yang dapat dipecahkan menggunakan Ant Colony Algorithm, di mana penjadwalan produksi mencari kombinasi optimal penjadwalan dan Ant Colony Algorithm dapat menghasilkan solusi optimal dalam waktu relative singkat.
Parameter Ant Colony Algorithm disesuaikan dengan permasalahan penjadwalan produksi: * Pheromone trail (τij), menunjukkan banyaknya pheromone yang dikeluarkan semut pada job j urutan ke-i. Pada keadaan awal, pheromone trail dari semua job pada semua urutan adalah 1. * Informasi heuristic (ηij), menunjukkan tingkat visibilitas suatu solusi akan dipilih oleh semut dari job j pada urutan ke-i. dalam meminimumkan makespan, maka fungsi informasi heuristic yang digunakan: η ij=1Tj * Tunable (q0), Nilai tunable yang digunakan adalah 0,9 yang artinya probabilitas semut memilih job melalui proses eksploitasi sebesar 90% dan probabilitas semut memilih job melalui proses eksplorasi sebesar 10%. (Pranata, 2006)

3. Penyelesaian Penjadwalan Flowshop Problem dengan Menggunakan Pendekatan Algoritma Ant Colony Optimization
Permasalahan terjadi pada penjadwalan flowhop untuk n jobs dengan dua mesin. Terdapat lima job dengan dua mesin masing-masing processing time untuk tiap job pada tiap mesin adalah sebagai berikut.

Tabel 1. Processing time untuk n jobs 2 machines Job | Mesin 1 | Mesin 2 | 1 | 29 | 27 | 2 | 23 | 31 | 3 | 34 | 12 | 4 | 21 | 22 | 5 | 22 | 17 |

Penyelesaian dilakukan dengan menggunakan algoritma ant colony. Berikut ini adalah tahap-tahap penyelesaian permasalahan di atas:
Step 1 nc = 1 k = 1 s = 1

Step 2: Input n, NCmax, m, α, β, ρ, q0 n = 5
NCmax = 2 m = 2 α = 1 β = 1 ρ = 0.1 q0 = 0.9

Step 3: Set τij, ηij ∈ i, j
Pheromone trail (τij) ij | 1 | 2 | 3 | 4 | 5 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 1 | 1 | 1 | 1 | 1 | 3 | 1 | 1 | 1 | 1 | 1 | 4 | 1 | 1 | 1 | 1 | 1 | 5 | 1 | 1 | 1 | 1 | 1 |

Informasi heuristik ηij untuk i = 1 η11 = | 0.01786 | η12 = | 0.01852 | η13 = | 0.02174 | η14 = | 0.02326 | η15 = | 0.02564 |

Step 4: Random q = U[0,1] q = 0.211603,
Karena q < q0 = 0,9 maka dilakukan proses eksploitasi.

Step 5: Pemilihan job dengan melakukan proses Eksploitasi
Ω = {1, 2, 3, 4, 5}
Job j=arrange maxh∈Ωτijαηijβ

Job | Nilai eksploitasi | 1 | 0.0178571 | 2 | 0.0185185 | 3 | 0.0217391 | 4 | 0.0232558 | 5 | 0.025641 |

Tabu list = {5}

Step 6: Local trail update
Pheromone trail yang diupdate untuk pheromone job 5 posisi ke-1 (τ15) dengan menggunakan rumus: τijt+1=1-ρτijt+ρτ0 τ0=1n.TSTP

ij | 1 | 2 | 3 | 4 | 5 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 1 | 1 | 1 | 1 | 1 | 3 | 1 | 1 | 1 | 1 | 1 | 4 | 1 | 1 | 1 | 1 | 1 | 5 | 0.90051 | 1 | 1 | 1 | 1 |

Step 7: s = 1 n = 5
Karena s ≠ n, maka s = s + 1 s = 2, kembali ke step 4

Step 4: Random q = U[0,1] q = 0.231204,
Karena q < q0 = 0,9 maka dilakukan proses eksploitasi.

Step 5: Pemilihan job dengan melakukan proses Eksploitasi
Ω = { 1,2,3,4}
Job j=arrange maxh∈Ωτijαηijβ
Dengan nilai informasi heuristic: η21 = | 0.01282 | η22 = | 0.01316 | η23 = | 0.01471 | η24 = | 0.01538 |

Maka nilai eksploitasi: Job | Nilai eksploitasi | 1 | 0.0128205 | 2 | 0.0131579 | 3 | 0.0147059 | 4 | 0.0153846 |

Tabu list = {5,4}

Step 6: Local trail update
Pheromone trail yang diupdate untuk pheromone job 4 posisi ke-2 (τ24) dengan menggunakan rumus: τijt+1=1-ρτijt+ρτ0 τ0=1n.TSTP

ij | 1 | 2 | 3 | 4 | 5 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 1 | 1 | 1 | 1 | 1 | 3 | 1 | 1 | 1 | 1 | 1 | 4 | 1 | 0.90031 | 1 | 1 | 1 | 5 | 0.90051 | 1 | 1 | 1 | 1 |

Step 7: s = 2 n = 5
Karena s ≠ n, maka s = s + 1 s = 3, kembali ke step 4

Step 4: Random q = U[0,1] q = 0.506323,
Karena q < q0 = 0,9 maka dilakukan proses eksploitasi.

Step 5: Pemilihan job dengan melakukan proses Eksploitasi
Ω = { 1,2,3}
Job j=arrange maxh∈Ωτijαηijβ
Dengan nilai informasi heuristic: η31 = | 0.0101 | η32 = | 0.01031 | η33 = | 0.01124 |

Maka nilai eksploitasi: Job | Nilai eksploitasi | 1 | 0.010101 | 2 | 0.0103093 | 3 | 0.011236 |

Tabu list = {5,4,3}

Step 6: Local trail update
Pheromone trail yang diupdate untuk pheromone job 3 posisi ke-3 (τ33) dengan menggunakan rumus: τijt+1=1-ρτijt+ρτ0 τ0=1n.TSTP

ij | 1 | 2 | 3 | 4 | 5 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 1 | 1 | 1 | 1 | 1 | 3 | 1 | 1 | 0.9002247 | 1 | 1 | 4 | 1 | 0.90031 | 1 | 1 | 1 | 5 | 0.90051 | 1 | 1 | 1 | 1 |

Step 7: s = 3 n = 5
Karena s ≠ n, maka s = s + 1 s = 4, kembali ke step 4

Step 4: Random q = U[0,1] q = 0.85836,
Karena q < q0 = 0,9 maka dilakukan proses eksploitasi.

Step 5: Pemilihan job dengan melakukan proses Eksploitasi
Ω = { 1,2}
Job j=arrange maxh∈Ωτijαηijβ
Dengan nilai informasi heuristic: η41 = | 0.00752 | η42 = | 0.00763 |

Maka nilai eksploitasi: Job | Nilai eksploitasi | 1 | 0.0075188 | 2 | 0.0076336 |

Tabu list = {5,4,3,2}

Step 6: Local trail update
Pheromone trail yang diupdate untuk pheromone job 2 posisi ke-4 (τ42) dengan menggunakan rumus: τijt+1=1-ρτijt+ρτ0 τ0=1n.TSTP

ij | 1 | 2 | 3 | 4 | 5 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 1 | 1 | 1 | 0.90015 | 1 | 3 | 1 | 1 | 0.9002247 | 1 | 1 | 4 | 1 | 0.90031 | 1 | 1 | 1 | 5 | 0.90051 | 1 | 1 | 1 | 1 |

Step 7: s = 4 n = 5
Karena s ≠ n, maka s = s + 1 s = 5, kembali ke step 4

Step 4: Random q = U[0,1] q = 0.76815,
Karena q < q0 = 0,9 maka dilakukan proses eksploitasi.

Step 5: Pemilihan job dengan melakukan proses Eksploitasi
Ω = { 1}
Job j=arrange maxh∈Ωτijαηijβ
Dengan nilai informasi heuristic: η51 = | 0.00633 |

Maka nilai eksploitasi: Job | Nilai eksploitasi | 1 | 0.0063291 |

Tabu list = {5,4,3,2,1}

Step 6: Local trail update
Pheromone trail yang diupdate untuk pheromone job 1 posisi ke-5 (τ51) dengan menggunakan rumus: τijt+1=1-ρτijt+ρτ0 τ0=1n.TSTP

ij | 1 | 2 | 3 | 4 | 5 | 1 | 1 | 1 | 1 | 1 | 0.90013 | 2 | 1 | 1 | 1 | 0.90015 | 1 | 3 | 1 | 1 | 0.9002247 | 1 | 1 | 4 | 1 | 0.90031 | 1 | 1 | 1 | 5 | 0.90051 | 1 | 1 | 1 | 1 |

Step 7: s = 5, n = 5 s = n

Step 8 k = 1, m = 2
Karena k ≠ m, maka k = k + 1, s = 1 k = 2, s = 1 kembali ke step 4

Step 4: Random q = U[0,1] q = 0.791071,
Karena q < q0 = 0,9 maka dilakukan proses eksploitasi.

Step 5: Pemilihan job dengan melakukan proses Eksploitasi
Ω = {1, 2, 3, 4, 5}
Job j=arrange maxh∈Ωτijαηijβ
Dengan nilai informasi heuristic: η11 = | 0.01786 | η12 = | 0.01852 | η13 = | 0.02174 | η14 = | 0.02326 | η15 = | 0.02564 |

Maka nilai eksploitasi: Job | Nilai eksploitasi | 1 | 0.0178571 | 2 | 0.0185185 | 3 | 0.0217391 | 4 | 0.0232558 | 5 | 0.0230901 |

Tabu list = {4}

Step 6: Local trail update
Pheromone trail yang diupdate untuk pheromone job 4 posisi ke-1 (τ14) dengan menggunakan rumus: τijt+1=1-ρτijt+ρτ0 τ0=1n.TSTP

ij | 1 | 2 | 3 | 4 | 5 | 1 | 1 | 1 | 1 | 1 | 0.90013 | 2 | 1 | 1 | 1 | 0.90015 | 1 | 3 | 1 | 1 | 0.9002247 | 1 | 1 | 4 | 0.90047 | 0.90031 | 1 | 1 | 1 | 5 | 0.90051 | 1 | 1 | 1 | 1 |

Step 7: s = 1 n = 5
Karena s ≠ n, maka s = s + 1 s = 2, kembali ke step 4

Step 4: Random q = U[0,1] q = 0.208066,
Karena q < q0 = 0,9 maka dilakukan proses eksploitasi.

Step 5: Pemilihan job dengan melakukan proses Eksploitasi
Ω = { 1,2,3,5}
Job j=arrange maxh∈Ωτijαηijβ
Dengan nilai informasi heuristic: η21 = | 0.01282 | η22 = | 0.01316 | η23 = | 0.01471 | η25 = | 0.01639 |

Maka nilai eksploitasi: Job | Nilai eksploitasi | 1 | 0.0128205 | 2 | 0.0131579 | 3 | 0.0147059 | 5 | 0.0163934 |

Tabu list = {4,5}

Step 6: Local trail update
Pheromone trail yang diupdate untuk pheromone job 5 posisi ke-2 (τ25) dengan menggunakan rumus: τijt+1=1-ρτijt+ρτ0 τ0=1n.TSTP

ij | 1 | 2 | 3 | 4 | 5 | 1 | 1 | 1 | 1 | 1 | 0.90013 | 2 | 1 | 1 | 1 | 0.90015 | 1 | 3 | 1 | 1 | 0.9002247 | 1 | 1 | 4 | 0.90047 | 0.90031 | 1 | 1 | 1 | 5 | 0.90051 | 0.90033 | 1 | 1 | 1 |

Step 7: s = 2 n = 5
Karena s ≠ n, maka s = s + 1 s = 3, kembali ke step 4

Step 4: Random q = U[0,1] q = 0.675005,
Karena q < q0 = 0,9 maka dilakukan proses eksploitasi.

Step 5: Pemilihan job dengan melakukan proses Eksploitasi
Ω = { 1,2,3}
Job j=arrange maxh∈Ωτijαηijβ
Dengan nilai informasi heuristic: η31 = | 0.01 | η32 = | 0.0102 | η33 = | 0.01111 |

Maka nilai eksploitasi: Job | Nilai eksploitasi | 1 | 0.01 | 2 | 0.0102041 | 3 | 0.0100025 |

Tabu list = {4, 5, 2}

Step 6: Local trail update
Pheromone trail yang diupdate untuk pheromone job 2 posisi ke-3 (τ32) dengan menggunakan rumus: τijt+1=1-ρτijt+ρτ0 τ0=1n.TSTP

ij | 1 | 2 | 3 | 4 | 5 | 1 | 1 | 1 | 1 | 1 | 0.90013 | 2 | 1 | 1 | 0.9002041 | 0.90015 | 1 | 3 | 1 | 1 | 0.9002247 | 1 | 1 | 4 | 0.90047 | 0.90031 | 1 | 1 | 1 | 5 | 0.90051 | 0.90033 | 1 | 1 | 1 |

Step 7: s = 3 n = 5
Karena s ≠ n, maka s = s + 1 s = 4, kembali ke step 4

Step 4: Random q = U[0,1] q = 0.528814,
Karena q < q0 = 0,9 maka dilakukan proses eksploitasi.

Step 5: Pemilihan job dengan melakukan proses Eksploitasi
Ω = { 1,3}
Job j=arrange maxh∈Ωτijαηijβ
Dengan nilai informasi heuristic: η41 = | 0.008 | η43 = | 0.00885 |

Maka nilai eksploitasi: Job | Nilai eksploitasi | 1 | 0.008 | 3 | 0.0088496 |

Tabu list = {4,5,2,3}

Step 6: Local trail update
Pheromone trail yang diupdate untuk pheromone job 3 posisi ke-4 (τ43) dengan menggunakan rumus: τijt+1=1-ρτijt+ρτ0 τ0=1n.TSTP

ij | 1 | 2 | 3 | 4 | 5 | 1 | 1 | 1 | 1 | 1 | 0.90013 | 2 | 1 | 1 | 0.9002041 | 0.90015 | 1 | 3 | 1 | 1 | 0.9002247 | 0.90018 | 1 | 4 | 0.90047 | 0.90031 | 1 | 1 | 1 | 5 | 0.90051 | 0.90033 | 1 | 1 | 1 |

Step 7: s = 4 n = 5
Karena s ≠ n, maka s = s + 1 s = 5, kembali ke step 4

Step 4: Random q = U[0,1] q = 0.096894,
Karena q < q0 = 0,9 maka dilakukan proses eksploitasi.

Step 5: Pemilihan job dengan melakukan proses Eksploitasi
Ω = { 1}
Job j=arrange maxh∈Ωτijαηijβ
Dengan nilai informasi heuristic: η51 = | 0.00637 |

Maka nilai eksploitasi: Job | Nilai eksploitasi | 1 | 0.0057333 |

Tabu list = {4,5,2,3,1}

Step 6: Local trail update
Pheromone trail yang diupdate untuk pheromone job 1 posisi ke-5 (τ15) dengan menggunakan rumus: τijt+1=1-ρτijt+ρτ0 τ0=1n.TSTP

ij | 1 | 2 | 3 | 4 | 5 | 1 | 1 | 1 | 1 | 1 | 0.81024 | 2 | 1 | 1 | 0.9002041 | 0.90015 | 1 | 3 | 1 | 1 | 0.9002247 | 0.90018 | 1 | 4 | 0.90047 | 0.90031 | 1 | 1 | 1 | 5 | 0.90051 | 0.90033 | 1 | 1 | 1 |

Step 7: s = 5, n = 5 s = n

Step 8 k = 2, m = 2 k = m

Step 9: Menghitung Fitness Value untuk masing-masing semut
Semut ke-1
Sequence 5-4-3-2-1 Job | Mesin 1 | Flow Time 1 | Mesin 2 | Flow Time 2 | 5 | 22 | 22 | 17 | 39 | 4 | 21 | 43 | 22 | 65 | 3 | 34 | 77 | 12 | 89 | 2 | 23 | 100 | 31 | 131 | 1 | 29 | 129 | 27 | 158 |
Makespan: 158

Semut ke-2
Sequence 4-5-2-3-1 Job | Mesin 1 | Flow Time 1 | Mesin 2 | Flow Time 2 | 4 | 21 | 22 | 22 | 43 | 5 | 22 | 44 | 17 | 61 | 2 | 23 | 67 | 31 | 98 | 3 | 34 | 101 | 12 | 113 | 1 | 29 | 130 | 27 | 157 |
Makespan: 157

Step 10: Memilih semut terbaik dari tiap siklus
Semut ke-2
Sequence 4-5-2-3-1

Step 11: Memilih solusi global terbaik
Sequence 4-5-2-3-1

Step 12: Global Trail Update
Pheromone trail mengalami evaporasi dengan menggunakan rumus: τijt+1=1-ρτijt+ρ∆τij(t) ∆τijt=1T* untuk setiap i,j dari solusi terbaik0 selain itu

ij | 1 | 2 | 3 | 4 | 5 | 1 | 0.9 | 0.9 | 0.9 | 0.9 | 0.72985 | 2 | 0.9 | 0.9 | 0.8112041 | 0.81014 | 0.9 | 3 | 0.9 | 0.9 | 0.8102022 | 0.81104 | 0.9 | 4 | 0.81274 | 0.81028 | 0.9 | 0.9 | 0.9 | 5 | 0.81046 | 0.81193 | 0.9 | 0.9 | 0.9 |

Step 13 nc = 1, NCmax =2
Karena nc ≠ NCmax maka nc = nc + 1, k = 1, s = 1 nc = 2, kembali ke step 4

Step 4: Random q = U[0,1] q = 0.716059,
Karena q < q0 = 0,9 maka dilakukan proses eksploitasi.

Step 5: Pemilihan job dengan melakukan proses Eksploitasi
Ω = {1, 2, 3, 4, 5}
Job j=arrange maxh∈Ωτijαηijβ
Dengan nilai informasi heuristic: η11 = | 0.01786 | η12 = | 0.01852 | η13 = | 0.02174 | η14 = | 0.02326 | η15 = | 0.02564 |

Maka nilai eksploitasi: Job | Nilai eksploitasi | 1 | 0.0160714 | 2 | 0.0166667 | 3 | 0.0195652 | 4 | 0.018901 | 5 | 0.0207811 |

Tabu list = {5}

Step 6: Local trail update
Pheromone trail yang diupdate untuk pheromone job 5 posisi ke-1 (τ15) dengan menggunakan rumus: τijt+1=1-ρτijt+ρτ0 τ0=1n.TSTP

ij | 1 | 2 | 3 | 4 | 5 | 1 | 0.9 | 0.9 | 0.9 | 0.9 | 0.72985 | 2 | 0.9 | 0.9 | 0.8112041 | 0.81014 | 0.9 | 3 | 0.9 | 0.9 | 0.8102022 | 0.81104 | 0.9 | 4 | 0.81274 | 0.81028 | 0.9 | 0.9 | 0.9 | 5 | 0.72993 | 0.81193 | 0.9 | 0.9 | 0.9 |

Step 7: s = 1 n = 5
Karena s ≠ n, maka s = s + 1 s = 2, kembali ke step 4

Step 4: Random q = U[0,1] q = 0.126112,
Karena q < q0 = 0,9 maka dilakukan proses eksploitasi.

Step 5: Pemilihan job dengan melakukan proses Eksploitasi
Ω = { 1,2,3,4}
Job j=arrange maxh∈Ωτijαηijβ
Dengan nilai informasi heuristic: η21 = | 0.01282 | η22 = | 0.01316 | η23 = | 0.01471 | η24 = | 0.01538 |

Maka nilai eksploitasi: Job | Nilai eksploitasi | 1 | 0.0115385 | 2 | 0.0118421 | 3 | 0.0132353 | 4 | 0.0124658 |

Tabu list = {5,3}

Step 6: Local trail update
Pheromone trail yang diupdate untuk pheromone job 3 posisi ke-2 (τ23) dengan menggunakan rumus: τijt+1=1-ρτijt+ρτ0 τ0=1n.TSTP

ij | 1 | 2 | 3 | 4 | 5 | 1 | 0.9 | 0.9 | 0.9 | 0.9 | 0.72985 | 2 | 0.9 | 0.9 | 0.8112041 | 0.81014 | 0.9 | 3 | 0.9 | 0.81029 | 0.8102022 | 0.81104 | 0.9 | 4 | 0.81274 | 0.81028 | 0.9 | 0.9 | 0.9 | 5 | 0.72993 | 0.81193 | 0.9 | 0.9 | 0.9 |

Step 7: s = 2 n = 5
Karena s ≠ n, maka s = s + 1 s = 3, kembali ke step 4

Step 4: Random q = U[0,1] q = 0.652091,
Karena q < q0 = 0,9 maka dilakukan proses eksploitasi.

Step 5: Pemilihan job dengan melakukan proses Eksploitasi
Ω = { 1,2,4}
Job j=arrange maxh∈Ωτijαηijβ
Dengan nilai informasi heuristic: η31 = | 0.00893 | η32 = | 0.00909 | η34 = | 0.0101 |

Maka nilai eksploitasi: Job | Nilai eksploitasi | 1 | 0.0080357 | 2 | 0.0073746 | 4 | 0.0090909 |

Tabu list = {5,3,4}

Step 6: Local trail update
Pheromone trail yang diupdate untuk pheromone job 4 posisi ke-3 (τ34) dengan menggunakan rumus: τijt+1=1-ρτijt+ρτ0 τ0=1n.TSTP

ij | 1 | 2 | 3 | 4 | 5 | 1 | 0.9 | 0.9 | 0.9 | 0.9 | 0.72985 | 2 | 0.9 | 0.9 | 0.8112041 | 0.81014 | 0.9 | 3 | 0.9 | 0.81029 | 0.8102022 | 0.81104 | 0.9 | 4 | 0.81274 | 0.81028 | 0.810202 | 0.9 | 0.9 | 5 | 0.72993 | 0.81193 | 0.9 | 0.9 | 0.9 |

Step 7: s = 3 n = 5
Karena s ≠ n, maka s = s + 1 s = 4, kembali ke step 4

Step 4: Random q = U[0,1] q = 0.5575,
Karena q < q0 = 0,9 maka dilakukan proses eksploitasi.

Step 5: Pemilihan job dengan melakukan proses Eksploitasi
Ω = { 1,2}
Job j=arrange maxh∈Ωτijαηijβ
Dengan nilai informasi heuristic: η41 = | 0.00752 | η42 = | 0.00763 |

Maka nilai eksploitasi: Job | Nilai eksploitasi | 1 | 0.0067669 | 2 | 0.0061843 |

Tabu list = {5,3,4,1}

Step 6: Local trail update
Pheromone trail yang diupdate untuk pheromone job 1 posisi ke-4 (τ41) dengan menggunakan rumus: τijt+1=1-ρτijt+ρτ0 τ0=1n.TSTP

ij | 1 | 2 | 3 | 4 | 5 | 1 | 0.9 | 0.9 | 0.9 | 0.81015 | 0.72985 | 2 | 0.9 | 0.9 | 0.8112041 | 0.81014 | 0.9 | 3 | 0.9 | 0.81029 | 0.8102022 | 0.81104 | 0.9 | 4 | 0.81274 | 0.81028 | 0.810202 | 0.9 | 0.9 | 5 | 0.72993 | 0.81193 | 0.9 | 0.9 | 0.9 |

Step 7: s = 4 n = 5
Karena s ≠ n, maka s = s + 1 s = 5, kembali ke step 4

Step 4: Random q = U[0,1] q = 0.149963,
Karena q < q0 = 0,9 maka dilakukan proses eksploitasi.

Step 5: Pemilihan job dengan melakukan proses Eksploitasi
Ω = {2}
Job j=arrange maxh∈Ωτijαηijβ
Dengan nilai informasi heuristic: η52 = | 0.00694 |

Maka nilai eksploitasi: Job | Nilai eksploitasi | 2 | 0.0050684 |

Tabu list = {5,3,4,1,2}

Step 6: Local trail update
Pheromone trail yang diupdate untuk pheromone job 2 posisi ke-5 (τ52) dengan menggunakan rumus: τijt+1=1-ρτijt+ρτ0 τ0=1n.TSTP

ij | 1 | 2 | 3 | 4 | 5 | 1 | 0.9 | 0.9 | 0.9 | 0.81015 | 0.72985 | 2 | 0.9 | 0.9 | 0.8112041 | 0.81014 | 0.81012 | 3 | 0.9 | 0.81029 | 0.8102022 | 0.81104 | 0.9 | 4 | 0.81274 | 0.81028 | 0.810202 | 0.9 | 0.9 | 5 | 0.72993 | 0.81193 | 0.9 | 0.9 | 0.9 |

Step 7: s = 5, n = 5 s = n

Step 8 k = 1, m = 2
Karena k ≠ m, maka k = k + 1, s = 1 k = 2, s = 1 kembali ke step 4

Step 4: Random q = U[0,1] q = 0.667405766,
Karena q < q0 = 0,9 maka dilakukan proses eksploitasi.

Step 5: Pemilihan job dengan melakukan proses Eksploitasi
Ω = {1, 2, 3, 4, 5}
Job j=arrange maxh∈Ωτijαηijβ
Dengan nilai informasi heuristic: η11 = | 0.01786 | η12 = | 0.01852 | η13 = | 0.02174 | η14 = | 0.02326 | η15 = | 0.02564 |

Maka nilai eksploitasi: Job | Nilai eksploitasi | 1 | 0.0160714 | 2 | 0.0166667 | 3 | 0.0195652 | 4 | 0.018901 | 5 | 0.0187161 |

Tabu list = {3}

Step 6: Local trail update
Pheromone trail yang diupdate untuk pheromone job 3 posisi ke-1 (τ13) dengan menggunakan rumus: τijt+1=1-ρτijt+ρτ0 τ0=1n.TSTP

ij | 1 | 2 | 3 | 4 | 5 | 1 | 0.9 | 0.9 | 0.9 | 0.81015 | 0.72985 | 2 | 0.9 | 0.9 | 0.8112041 | 0.81014 | 0.81012 | 3 | 0.81043 | 0.81029 | 0.8102022 | 0.81104 | 0.9 | 4 | 0.81274 | 0.81028 | 0.810202 | 0.9 | 0.9 | 5 | 0.72993 | 0.81193 | 0.9 | 0.9 | 0.9 |

Step 7: s = 1 n = 5
Karena s ≠ n, maka s = s + 1 s = 2, kembali ke step 4

Step 4: Random q = U[0,1] q = 0.600742,
Karena q < q0 = 0,9 maka dilakukan proses eksploitasi.

Step 5: Pemilihan job dengan melakukan proses Eksploitasi
Ω = { 1,2,4,5}
Job j=arrange maxh∈Ωτijαηijβ
Dengan nilai informasi heuristic: η21 = | 0.01282 | η22 = | 0.01299 | η24 = | 0.01471 | η25 = | 0.01587 |

Maka nilai eksploitasi: Job | Nilai eksploitasi | 1 | 0.0115385 | 2 | 0.0116883 | 4 | 0.0119158 | 5 | 0.0128878 |

Tabu list = {3,5}

Step 6: Local trail update
Pheromone trail yang diupdate untuk pheromone job 5 posisi ke-2 (τ25) dengan menggunakan rumus: τijt+1=1-ρτijt+ρτ0 τ0=1n.TSTP

ij | 1 | 2 | 3 | 4 | 5 | 1 | 0.9 | 0.9 | 0.9 | 0.81015 | 0.72985 | 2 | 0.9 | 0.9 | 0.8112041 | 0.81014 | 0.81012 | 3 | 0.81043 | 0.81029 | 0.8102022 | 0.81104 | 0.9 | 4 | 0.81274 | 0.81028 | 0.810202 | 0.9 | 0.9 | 5 | 0.72993 | 0.73106 | 0.9 | 0.9 | 0.9 |

Step 7: s = 2 n = 5
Karena s ≠ n, maka s = s + 1 s = 3, kembali ke step 4

Step 4: Random q = U[0,1] q = 0.535701,
Karena q < q0 = 0,9 maka dilakukan proses eksploitasi.

Step 5: Pemilihan job dengan melakukan proses Eksploitasi
Ω = { 1,2,4}
Job j=arrange maxh∈Ωτijαηijβ
Dengan nilai informasi heuristic: η31 = | 0.01 | η32 = | 0.0102 | η34 = | 0.01149 |

Maka nilai eksploitasi: Job | Nilai eksploitasi | 1 | 0.009 | 2 | 0.0082776 | 4 | 0.0093127 |

Tabu list = {3,5,4}

Step 6: Local trail update
Pheromone trail yang diupdate untuk pheromone job 4 posisi ke-3 (τ34) dengan menggunakan rumus: τijt+1=1-ρτijt+ρτ0 τ0=1n.TSTP

ij | 1 | 2 | 3 | 4 | 5 | 1 | 0.9 | 0.9 | 0.9 | 0.81015 | 0.72985 | 2 | 0.9 | 0.9 | 0.8112041 | 0.81014 | 0.81012 | 3 | 0.81043 | 0.81029 | 0.8102022 | 0.81104 | 0.9 | 4 | 0.81274 | 0.81028 | 0.7294117 | 0.9 | 0.9 | 5 | 0.72993 | 0.73106 | 0.9 | 0.9 | 0.9 |

Step 7: s = 3 n = 5
Karena s ≠ n, maka s = s + 1 s = 4, kembali ke step 4

Step 4: Random q = U[0,1] q = 0.917901,
Karena q < q0 = 0,9 maka dilakukan proses eksplorasi.

Step 5: Pemilihan job dengan melakukan proses Eksploitasi
Ω = { 1,2}
Pij=τijαηijβh∈Ωτijαηijβ ,jika j ∈ Ω0 ,selain itu
Dengan nilai informasi heuristic: η41 = | 0.00826 | η42 = | 0.0084 |

Maka probabilitas eksplorasi: P41 = | 0.4958373 | P42 = | 0.5041627 | P43 = | 0 | P44 = | 0 | P45 = | 0 |

Tabu list = {3,5,4,2}

Step 6: Local trail update
Pheromone trail yang diupdate untuk pheromone job 2 posisi ke-4 (τ42) dengan menggunakan rumus: τijt+1=1-ρτijt+ρτ0 τ0=1n.TSTP

ij | 1 | 2 | 3 | 4 | 5 | 1 | 0.9 | 0.9 | 0.9 | 0.81015 | 0.72985 | 2 | 0.9 | 0.9 | 0.8112041 | 0.72929 | 0.81012 | 3 | 0.81043 | 0.81029 | 0.8102022 | 0.81104 | 0.9 | 4 | 0.81274 | 0.81028 | 0.7294117 | 0.9 | 0.9 | 5 | 0.72993 | 0.73106 | 0.9 | 0.9 | 0.9 |

Step 7: s = 4 n = 5
Karena s ≠ n, maka s = s + 1 s = 5, kembali ke step 4

Step 4: Random q = U[0,1] q = 0.127726,
Karena q < q0 = 0,9 maka dilakukan proses eksploitasi.

Step 5: Pemilihan job dengan melakukan proses Eksploitasi
Ω = { 1}
Job j=arrange maxh∈Ωτijαηijβ
Dengan nilai informasi heuristic: η51 = | 0.00685 |

Maka nilai eksploitasi: Job | Nilai eksploitasi | 1 | 0.004999 |

Tabu list = {3,5,4,2,1}

Step 6: Local trail update
Pheromone trail yang diupdate untuk pheromone job 1 posisi ke-5 (τ15) dengan menggunakan rumus: τijt+1=1-ρτijt+ρτ0 τ0=1n.TSTP

ij | 1 | 2 | 3 | 4 | 5 | 1 | 0.9 | 0.9 | 0.9 | 0.81015 | 0.65701 | 2 | 0.9 | 0.9 | 0.8112041 | 0.72929 | 0.81012 | 3 | 0.81043 | 0.81029 | 0.8102022 | 0.81104 | 0.9 | 4 | 0.81274 | 0.81028 | 0.7294117 | 0.9 | 0.9 | 5 | 0.72993 | 0.73106 | 0.9 | 0.9 | 0.9 |

Step 7: s = 5, n = 5 s = n

Step 8 k = 2, m = 2 k = m

Step 9: Menghitung Fitness Value untuk masing-masing semut
Semut ke-1
Sequence 5-4-3-2-1 Job | Mesin 1 | Flow Time 1 | Mesin 2 | Flow Time 2 | 5 | 22 | 22 | 17 | 39 | 3 | 34 | 56 | 12 | 68 | 4 | 21 | 77 | 22 | 99 | 1 | 29 | 106 | 27 | 133 | 2 | 23 | 129 | 31 | 164 |
Makespan: 164

Semut ke-2
Sequence 4-5-2-3-1 Job | Mesin 1 | Flow Time 1 | Mesin 2 | Flow Time 2 | 3 | 34 | 22 | 12 | 46 | 5 | 22 | 44 | 17 | 63 | 4 | 21 | 65 | 22 | 87 | 2 | 23 | 88 | 31 | 119 | 1 | 29 | 117 | 27 | 146 |
Makespan: 146

Step 10: Memilih semut terbaik dari tiap siklus
Semut ke-2
Sequence 3-5-4-2-1

Step 11: Memilih solusi global terbaik
Sequence 3-5-4-2-1

Step 12: Global Trail Update
Pheromone trail mengalami evaporasi dengan menggunakan rumus: τijt+1=1-ρτijt+ρ∆τij(t) ∆τijt=1T* untuk setiap i,j dari solusi terbaik0 selain itu

ij | 1 | 2 | 3 | 4 | 5 | 1 | 0.81 | 0.81 | 0.81 | 0.72914 | 0.59199 | 2 | 0.81 | 0.81 | 0.7300837 | 0.6572 | 0.72911 | 3 | 0.73157 | 0.72926 | 0.729182 | 0.72994 | 0.81 | 4 | 0.73147 | 0.72925 | 0.65762 | 0.81 | 0.81 | 5 | 0.65694 | 0.65954 | 0.81 | 0.81 | 0.81 |

Step 13 nc = 2, NCmax =2 nc = NCmax

Step 14: Print solusi
Sequence 3-5-4-2-1 dengan makespan 146

4. Kesimpulan
Penyelesaian permasalahan penjadwalan untuk n jobs 2 mesin dengan menggunakan 2 semut di dalam satu koloni dan 2 siklus menghasilkan urutan job 3-5-4-2-1 dengan makespan sebesar 146. Nilai makespan ini dapat lebih minimal lagi dengan menjalankan algoritma ini dengan jumlah semut dan siklus yang lebih banyak.

DAFTAR REFERENSI

Vlachos, A. (2006). Ant colony system solving capacitated location-allocation problems on a line. Journal of Information & Optimization Sciences. Vol. 27 No. 1, pp. 81 – 96.
M’Hallah, R. & Alhajraf, A. (2008). Ant colony optimization for the single machine total earliness tardiness scheduling problem. New Frontiers in Applied Artificial Intelligence. Springer: German
Pranata, O. (2006). Penjadwalan produksi dengan algortima ant colony di FSCM Manufacturing Indonesia Plant 4. Universitas Kristen Petra: Surabaya.