PENERAPAN ALGORITMA HARMONY SEARCH DALAM PENYELESAIAN RESOURCE-CONSTRAINED PROJECT SCHEDULING PROBLEM Achmad Setiawan, Ir. Budi Santosa, M.Sc., Ph.D Jurusan Teknik Industri Institut Teknologi Sepuluh Nopember (ITS) Surabaya Kampus ITS Sukolilo Surabaya 60111 Email:
[email protected] ;
[email protected]
Abstrak Resource-Constrained Project Scheduling Problem (RCPSP) adalah masalah penjadwalan aktivitas pada proyek dengan kendala sumber daya terbatas dengan tujuan untuk meminimalkan durasi proyek. Masalah yang dihadapi pada proses penjadwalan ini adalah adanya keterbatasan sumber daya yang tersedia, kemudian tingkat kesulitan dalam menjadwalkan akan meningkat jika jumlah aktivitasnya banyak serta multi-resources. Oleh karena itu, pada penelitian ini dilakukan percobaan menggunakan algoritma Harmony Search (HS) untuk menyelesaikan permasalahan yang ada. Pada penelitian ini digunakan algoritma Particle Swarm Optimization (PSO) sebagai algoritma pembanding terhadap hasil algoritma HS pada penyelesaian RCPSP. Berdasarkan penelitian yang telah dilakukan maka terlihat bahwa kualitas solusi yang dihasilkan algoritma HS sama dengan algoritma PSO, namun dilihat dari sisi waktu komputasi, maka waktu komputasi algoritma HS lebih cepat daripada algoritma PSO. Oleh karena itu, apabila ditinjau dari segi waktu komputasi, maka performansi algoritma HS pada penyelesaian RCPSP lebih baik daripada algoritma PSO. Kata Kunci : Metaheuristik, Harmony Search, Resource-Constrained Project Scheduling Problem ABSTRACT Resource-Constrained Project Scheduling Problem (RCPSP) is the problem of scheduling activities on the project with limited resources in order to minimize the duration of the project. The problem faced in this scheduling process is the limited resources, then the level of difficulty in this scheduling will increase if there are so many activities to be scheduled and multi-resources. Therefore in this research, the experiment of using Harmony Search (HS) algorithm to solve existing problem is done. This research use the Particle Swarm Optimization (PSO) algorithm as a comparison algorithm of HS algorithm results on solving RCPSP. Based on research that has been done, it is known that the quality of HS algorithm solution is as good as the PSO algorithm, but in term of computing time, the HS algorithm is faster than the PSO algorithm. Therefore, in term of computing time, the HS algorithm performance on solving RCPSP is better than the PSO algorithm. Key Words : Metaheuristic, Harmony Search, Resource-Constrained Project Scheduling Problem
1.
Pendahuluan Pendekatan penjadwalan proyek secara tradisional seperti Critical Path Method (CPM) dan Program Evaluation and Review Technique (PERT) hanya berfokus pada hubungan ketergantungan antar aktivitas dengan menggunakan asumsi ketersediaan sumber daya yang tidak terbatas. Namun, dalam kenyataannya manajer proyek sering mengalami kesulitan dalam menjadwalkan suatu proyek dikarenakan keterbatasan sumber daya yang tersedia. Kemudian apabila dipaksakan adanya tambahan sumber daya, maka akan
menyebabkan adanya tambahan biaya yang cukup besar. Resource-Constrained Project Scheduling Problem (RCPSP) adalah masalah penjadwalan aktivitas-aktivitas pada proyek dengan kendala sumber daya terbatas. RCPSP termasuk masalah kombinatorial yang sulit untuk dipecahkan. Berbagai metode seperti metode analitis dan metode heuristik telah dicoba untuk menyelesaikan kasus RCPSP. Metode analitis seringkali mengadopsi modelmodel matematika seperti integer programming (Talbot, 1982) dan dynamic programming
(Gavish, 1991) untuk mencari solusi yang optimal. Namun demikian, metode analitis tidak memungkinkan untuk diterapkan apabila masalah yang menjadi obyek penelitian berukuran sangat besar dan sangat kompleks (Lee, 1996). Metode heuristik untuk penyelesaian kasus RCPSP bertujuan untuk mencari solusi yang optimal secara efisien (Boctor, 1990). Metode heuristik yang ada menggunakan aturan prioritas seperti Shortest Activity Duration (SAD), Minimum Late Finish Time (MILFT), atau Minimum Total Float (MITF) untuk menentukan aktivitas mana yang akan dijadwalkan terlebih dahulu. Namun demikian, tidak ada aturan prioritas yang mendominasi yang lain atau menunjukkan hasil yang lebih baik daripada yang lain secara konsisten (Davis, 1975). Selain itu, solusi yang dihasilkan dari penggunaan metode heuristik seringkali bersifat lokal optimal (Patterson, 1984). Seiring dengan berjalannya waktu, maka telah diterapkan beberapa metode metaheuristik untuk penyelesaian kasus RCPSP seperti genetic algorithm (Chan, 1996), ant colony optimization (Merkle, 2002), dan particle swarm optimization (Zhang, 2006). Genetic Algorithm (GA) melakukan pencarian solusi yang optimal dari kromosom-kromosom yang merepresentasikan jadwal dimana kromosomkromosom tersebut diproduksi melalui crossover dan mutation. Mekanisme updating kromosom membuat GA mampu keluar dari solusi yang bersifat lokal optimal. Oleh karena itu, GA lebih unggul daripada metode analitis dan metode heuristik. Namun demikian, terdapat kekurangan dalam performansi GA yaitu proses konvergensi yang lambat (Fogel, 1995). Penerapan Ant Colony Optimization (ACO) pada kasus RCPSP rata-rata menunjukkan hasil yang lebih baik dibandingkan dengan GA. Sedangkan performansi Particle Swarm Optimization (PSO) dilihat dari segi kualitas solusi menunjukkan hasil yang sama dengan GA. Beberapa metode metaheuristik seperti GA, ACO, dan PSO telah diuji cobakan pada kasus RCPSP. Oleh karena itu, pada penelitian kali ini akan dicoba metode metaheuristik yang lain yaitu Harmony Search (HS). Algoritma HS dipilih sebagai metode yang akan digunakan dalam penelitian ini karena algoritma ini menunjukkan hasil yang bagus ketika digunakan
untuk menyelesaikan beberapa masalah optimasi. Hal ini dikarenakan algoritma ini mempunyai beberapa kelebihan misalnya pitch adjustment yang dapat melakukan proses perbaikan pada solusi yang bersifat lokal optimal dan struktur algoritma HS relatif mudah (Geem, 2009). Selain itu, penelitian kasus RCPSP dengan menggunakan algoritma HS belum pernah dilakukan oleh peneliti-peneliti yang lain. Permasalahan dalam penelitian ini adalah sulitnya menjadwalkan aktivitas-aktivitas proyek dikarenakan keterbatasan sumber daya yang tersedia. Tingkat kesulitan dalam melakukan proses penjadwalan akan meningkat jika jumlah aktivitasnya banyak dan multiresources. Apabila proses penjadwalan ini dilakuakan secara manual, maka akan menyebabkan munculnya banyak alternatif jadwal yang sulit dicari yang optimal. Tujuan yang ingin dicapai dalam penelitian Tugas Akhir ini adalah untuk mengetahui performansi algoritma HS pada penyelesaian RCPSP dibandingkan dengan algoritma yang lain yaitu algoritma PSO. Selain itu, pada penelitian ini terdapat batasan dan asumsi yang digunakan untuk memperjelas ruang lingkup penelitian. Penelitian Tugas Akhir ini dibatasi pada kasus Single-Mode Resource-Constrained Project Scheduling Problem (SMRCPSP). Kemudian beberapa asumsi yang digunakan dalam penelitian Tugas Akhir ini antara lain: kapasitas sumber daya yang tersedia untuk tiap periode adalah tetap dan tidak ada preemption, artinya suatu aktivitas yang sedang berjalan tidak dapat dihentikan. 2.
Deskripsi RCPSP Masalah penjadwalan proyek dapat dilihat dari beberapa sudut pandang seperti tujuannya, bentuk-bentuk sumber daya yang diperlukan pada setiap aktivitas proyek, dan ada tidaknya kondisi preemption. Meminimasi durasi proyek seringkali digunakan sebagai fungsi tujuan secara umum dari masalah penjadwalan proyek. Sedangkan fungsi tujuan yang lain adalah minimasi total biaya proyek, maksimasi Net Present Value (NPV) dari cash flow, dan pelevelan penggunaan sumber daya. Sumber daya yang diperlukan oleh aktivitas proyek bisa bertipe satu jenis atau lebih dari satu jenis. Berdasarkan bisa atau tidaknya suatu
2
sumber daya untuk diperbarui, maka terdapat sumber daya yang dapat diperbarui dan sumber daya yang tidak dapat diperbarui. Sumber daya yang dapat diperbarui adalah sumber daya yang bisa digunakan kembali setelah diselesaikannya suatu aktivitas proyek seperti tenaga kerja. Sedangkan sumber daya yang tidak dapat diperbarui adalah sumber daya yang tidak bisa digunakan kembali setelah diselesaikannya suatu aktivitas proyek seperti uang. Kondisi preemption berarti suatu kondisi dimana aktivitas yang sedang berjalan dapat dihentikan dengan suatu alasan tertentu misalnya terdapat aktivitas lain yang ingin dijadwalkan pada periode tersebut. Sedangkan kondisi nonpreemption berarti suatu aktivitas yang sedang berjalan tidak dapat dihentikan. Resource-Constrained Project Scheduling Problem (RCPSP) adalah masalah penjadwalan aktivitas-aktivitas pada proyek dimana harus memenuhi precedence constraints dan resource constraints. Precedence constraints adalah suatu kendala dimana aktivitas pendahulu harus sudah selesai dijadwalkan sebelum aktivitas yang lain dijadwalkan. Resource constraints adalah suatu kendala dimana sumber daya yang diperlukan oleh setiap aktivitas pada setiap unit waktu tidak boleh melebihi kapasitas sumber daya yang tersedia. Berikut ini adalah formulasi matematika dari RCPSP dengan fungsi tujuan untuk meminimasi durasi proyek (Talbot, 1982; Patterson, 1984): minmax | 1,2, … , ………...………(1) subject to : ……………………..(2) ; 1,2, … , ∑ …………………….(3) ! 1,2, … , " ; # $% , $& , … , $' dimana N = jumlah aktivitas yang terdapat pada proyek = waktu penyelesaian aktivitas i ( 1,2, … , ) = durasi aktivitas i = predecessor aktivitas i = jumlah sumber daya tipe k yang tersedia (! 1,2, … , ") K = jumlah tipe sumber daya = jumlah sumber daya tipe k yang diperlukan oleh aktivitas i () =sekelompok aktivitas yang berjalan pada waktu ke-t $
$ = waktu mulai aktivitas i Persamaan (1) merepresentasikan fungsi tujuan dari RCPSP. Persamaan (2) merepresentasikan precedence constraints. Persamaan (3) merepresentasikan resource constraints. Berikut ini adalah contoh visualisasi dari RCPSP (Merkle, 2002):
Gambar 1. Visualisasi RCPSP
Apabila pada kasus diatas jumlah sumber daya yang tersedia sebanyak 4 unit, maka salah satu bentuk jadwal yang bisa dibuat akan diberikan sebagai berikut :
Gambar 2. Visualisasi Bentuk Jadwal
Berikut ini adalah beberapa variasi dalam RCPSP (Kolisch, 1996) : 1. Single-Mode Resource-Constrained Project Scheduling Problem (SMRCPSP) Pada SMRCPSP, setiap aktivitas proyek memiliki mode eksekusi tunggal. Durasi aktivitas dan kebutuhan terhadap suatu set sumber daya diasumsikan tetap. Fungsi tujuan secara umum pada SMRCPSP adalah meminimasi durasi proyek.
3
2. Multi-Mode Resource-Constrained Project Scheduling Problem (MMRCPSP) Pada MMRCPSP, setiap aktivitas proyek dapat dieksekusi dalam beberapa mode. Setiap mode menggambarkansuatu set sumber daya yang diperlukan oleh aktivitas proyek dan durasi aktivitas proyek tersebut. Fungsi tujuan secara umum pada MMRCPSP adalah meminimasi durasi proyek.
pengubahan frekuensi nada, hal itu berarti membangkitkan nilai yang sedikit berbeda pada algoritma HS. Berikut ini adalah formulasi penyesuaian nada: 6789 6:;< = 45 > ? ……………….…….(4) dimana 6789 = nada baru setelah dilakukan penyesuaian nada 6:;< = nada yang tersimpan pada harmony memory 45= bandwidth
3.
Prinsip Algoritma Harmony Search Algoritma Harmony Search (HS) pertama kali diperkenalkan oleh Zong Woo Geem pada tahun 2001. Ide dasar algoritma HS adalah meniru proses perbaikan harmoni musik yang dilakukan oleh kelompok paduan musik. Ketika kelompok paduan musik melakukan perbaikan pada harmoni musik yang dimainkan, maka akan terdapat tiga kemungkinan pilihan, antara lain memainkan harmoni musik yang terkenal berdasarkan ingatan mereka, memainkan harmoni musik yang serupa dengan harmoni musik yang terkenal namun ada sedikit penyesuaian, atau membuat harmoni musik yang baru. Geem (2001) memformulasikan ketiga pilihan ini pada proses optimasi secara kuantitatif. Ketiga komponen tersebut diformulasikan menjadi penggunaan harmony memory, penyesuaian nada, dan proses pembangkitan secara random. Penggunaan harmony memory sangat penting karena harmony memory tersebut bisa menjamin bahwa harmoni yang bagus akan dipertimbangkan sebagai elemen-elemen dari vektor solusi yang baru. Agar harmony memory dapat digunakan secara efektif, algoritma HS mengadopsi sebuah parameter yang disebut Harmony Memory Considering Rate (HMCR). Jika rate ini terlalu rendah, maka hanya sedikit harmoni elit yang terpilih dan juga dapat menyebabkan proses konvergensi terlalu lambat. Jika rate ini terlalu besar, maka akan menyebabkan nada-nada pada harmony memory banyak terpakai dan tidak sempat mengeksplorasi nada lain, dimana pada akhirnya sulit mencapai solusi yang bagus. Oleh karena itu, biasanya digunakan HMCR 0.7~0.95. Komponen kedua adalah penyesuaian nada dimana mempunyai beberapa parameter seperti bandwidth (45) dan Pitch Adjusting Rate (PAR). Penyesuaian nada musik berarti
? = bilangan random dengan interval @1,1A PAR yang bernilai rendah dengan bandwidth yang sempit dapat menyebabkan proses konvergensi lambat dikarenakan keterbatasan eksplorasi pada ruang pencarian yang besar. Pada sisi lain, PAR yang tinggi dengan bandwidth yang lebar dapat menyebabkan solusi-solusi yang ada terlalu menyebar dari potensi solusi optimal. Oleh karena itu, biasanya digunakan PAR 0.1~0.5. Berikut ini adalah langkah-langkah dari algoritma HS: 1. Inisialisasi masalah dan parameter algoritma. 2. Inisialisasi harmony memory. 3. Membangkitkan vektor solusi yang baru. 4. Meng-update harmony memory. 5. Mengecek kriteria pemberhentian. Langkah pertama dari algoritma HS adalah inisialisasi masalah dan parameter algoritma. Berikut ini adalah contoh masalah optimasi: min D6 E ………...………………………...(5) subject to 6 F …........................................(6) 1,2, … , ; G F H dimana D6 E = fungsi tujuan 6 = variabel keputusan ke-i F = interval variabel keputusan ke-i = jumlah variabel keputusan G = batas bawah variabel keputusan ke-i H = batas atas variabel keputusan ke-i Kemudian parameter algoritma HS terdiri dari Harmony Memory Size (HMS), HMCR, PAR, bandwidth, dan kriteria pemberhentian.
4
Langkah kedua dari algoritma HS adalah inisialisasi harmony memory. Pada tahap ini dibangkitkan matriks harmony memory secara random yang bersisi vektor-vektor solusi sebanyak HMS. Berikut ini adalah contoh matriks harmony memory:
x11 2 x1 .... HMS −1 x1 x HMS 1
x12
....
x 1N −1
x 22 ....
.... ....
x N2 −1 ....
−1 x 2HMS −1 .... x NHMS −1 x 2HMS .... x NHMS −1
x 1N x N2 .... x NHMS −1 x NHMS
Gambar 3. Matriks Harmony Memory
Langkah ketiga dari algoritma HS adalah membangkitkan vektor solusi yang baru (6 ′ ). Pembangkitan vektor solusi yang baru didasarkan pada tiga aturan antara lain penggunaan harmony memory, penyesuaian nada, dan proses pembangkitan secara random. Pada aturan pertama, vektor solusi yang baru diambil dari harmony memory apabila saat itu nilai dari bilangan random yang dibangkitkan untuk pertama kalinya dibawah HMCR dan bilangan random yang dibangkitkan untuk kedua kalinya diatas PAR. Nilai dari variabel keputusan pertama pada vektor solusi yang baru (6%′ ) diambil dari harmony memory dengan memilih salah satu nilai pada interval 6%% ~6%IJK. Nilai dari variabel keputusan yang lain (6&′ , 6L′ , … , 6'′ ) ditentukan dengan cara yang sama. Pada aturan kedua, pembangkitan vektor solusi yang baru dilakukan melalui proses penyesuaian nada. Apabila nilai bilangan random yang dibangkitkan untuk pertama kalinya dibawah HMCR dan bilangan random yang dibangkitkan untuk kedua kalinya dibawah PAR, maka akan dilakukan proses penyesuaian nada. Berikut ini adalah rumus penyesuaian nada: 6 ′ 6 = 45 > ? ………………………….(7) dimana
6 ′ = nada baru setelah dilakukan penyesuaian nada 6 = nada yang tersimpan pada harmony memory 45 = bandwidth ? = bilangan random dengan interval @1,1A
Pada aturan ketiga, vektor solusi yang baru dibangkitkan secara random dengan nilai interval yang memungkinkan (6 ′ F ). Hal terjadi apabila nilai dari bilangan random yang dibangkitkan untuk pertama kalinya diatas HMCR. Pada aturan ketiga tidak ada pembangkitan bilangan random untuk kedua kalinya karena nilai bilangan random yang dibangkitkan untuk pertama kalinya diatas HMCR. Langkah keempat dari algoritma HSadalah meng-update harmony memory. Apabila nilai vektor solusi yang baru lebih baik daripada nilai vektor solusi terjelek pada harmony memory dilihat dari sudut pandang nilai fungsi tujuan, maka vektor solusi yang baru akan dimasukkan ke dalam harmony memory dan vektor solusi terjelek pada harmony memory akan dikeluarkan. Apabila nilai vektor solusi yang baru lebih buruk daripada nilai vektor solusi terjelek pada harmony memory, maka tidak akan terjadi perubahan pada harmony memory. Langkah kelima dari algoritma HS adalah mengecek kriteria pemberhentian. Apabila kriteria pemberhentian telah tercapai maka iterasi dihentikan, apabila belum tercapai maka kembali ke langkah tiga. Terdapat beberapa macam kriteria pemberhentian antara lain jumlah iterasi maksimal, tidak terjadinya perubahan solusi setelah beberapa iterasi, dan lain-lain. 4.
Penerapan Algoritma HS pada Penyelesaian RCPSP Penerapan algoritma HS agar dapat menyelesaikan RCPSP ditunjukkan flowchart pada gambar 4. Berikut ini adalah penjelasan dari flowchart penerapan algoritma HS pada RCPSP:
1) Inisialisasi Masalah Pada tahap ini diperkenalkan masalah yang akan diselesaikan. Masalah dalam penelitian ini adalah RCPSP dengan fungsi tujuan meminimasi durasi proyek. Sedangkan kendala yang muncul adalah precedence constraints dan resource constraints.
2) Memasukkan Data RCPSP Data yang diperlukan untuk menyelesaikan kasus RCPSP adalah indeks aktivitas,
5
Gambar 4. Flowchart Penerapan Algoritma HS pada RCPSP
durasi aktivitas, kebutuhan sumber daya oleh tiap aktivitas, precedence constraints, dan jumlah sumber daya yang tersedia.
3) Inisialisasi Parameter Algoritma HS Beberapa parameter dari algoritma HS adalah HMS, HMCR, PAR, bandwidth, dan kriteria pemberhentian.
4) Inisialisasi HarmonyMemory •
Pada tahap ini dibangkitkan vektor solusi secara random. Vektor solusi pada algoritma HS merepresentasikan nilai prioritas
aktivitas proyek. Kemudian pada setiap iterasi, nilai prioritas aktivitas akan di-update melalui mekanisme algoritma HS. Berikut ini adalah penulisan vektor solusi yang merepresentasikan nilai prioritas aktivitas proyek: F @6% 6& … 6'M% 6' A …….(8) dimana X = vektor solusi i = indeks vektor solusi x = nilai prioritas aktivitas N = banyaknya aktivitas
6
• Setelah vektor solusi terbentuk, maka dilakukan transformasi vektor solusi kedalam bentuk jadwal yang feasible melalui skema paralel. Berikut ini adalah langkah-langkah yang diperlukan untuk menjadwalkan proyek dengan skema paralel: Menentukan waktu penjadwalan terbaru dimana waktu ini akan sama dengan waktu penyelesaian paling awal dari aktivitas-aktivitas yang telah dijadwalkan sebelumnya. Mengumpulkan aktivitasaktivitas yang feasible dimana aktivitas-aktivitas tersebut harus memenuhi precedence constraints dan resource constraints. Memilih sebuah aktivitas dari aktivitas-aktyivitas yang feasible dengan cara memilih aktivitas yang memiliki nilai prioritas yang lebih tinggi daripada yang lain. Menjadwalkan aktivitas yang terpilih. Apabila terdapat aktivitas-aktivitas yang belum dijadwalkan maka proses penjadwalan kembali ke langkah 1. • Setelah proses penjadwalan dilakukan maka durasi proyek dapat diketahui. • Vektor solusi dibangkitkan sebanyak HMS. Apabila semua vektor solusi telah dibangkitkan maka akan terbentuk matriks harmony memory.
x11 x12 2 x22 x1 .... .... HMS−1 HMS−1 x2 x1 x HMS x HMS 2 1
....
x1N −1
.... ....
xN2 −1 ....
−1 .... xNHMS −1 .... xNHMS −1
x1N xN2 .... HMS−1 xN xNHMS
Gambar 5. Matriks Harmony Memory
5) Membangkitkan Vektor Solusi yang Baru Proses pembangkitan vektor solusi yang baru melalui 3 cara, antara lain:
•
Apabila bilangan random yang dibangkitkan diatas HMCR maka akan dibangkitkan variabel keputusan yang baru secara random. VKB(i) = rand[BB(i),BA(i)] ...........(9) dimana VKB = variabel keputusan baru BB = batas bawah variabel keputusan BA = batas atas variabel keputusan
•
Apabila bilangan random yang dibangkitkan dibawah HMCR dan pembangkitan bilangan random berikutnya diatas PAR, maka variabel keputusan ke-i akan diambil dari harmony memory. D1 = int[1+(HMS-1)rand] ............(10) D2 = HM(D1,i) .............................(11) VKB(i) = D2 .................................(12) dimana D1 = nilai yang menyatakan pemilihan lokasi pada harmony memory secara random int = integer D2
•
=
nilai variabel keputusan yang diambil dari harmony memory
Apabila bilangan random yang dibangkitkan dibawah HMCR dan pembangkitan bilangan random berikutnya dibawah PAR, maka terdapat penyesuaian terhadap variabel keputusan ke-i yang telah diambil dari harmony memory. D3 = D2+bw*ε …………………….(13) VKB(i) = D3 .................................(14) dimana D3 = nilai variabel keputusan setelah dilakukan penyesuaian bw = bandwidth ? = bilangan random dengan interval @1,1A Kemudian setelah dilakukan proses penyesuaian maka akan dilakukan pengecekan terhadap batas atas dan
7
batas dari variabel keputusan. Apabila D3
BA, maka D3=BA. Batas bawah dari semua variabel keputusan adalah 0 dan batas atasnya adalah 1. Ketiga cara diatas dilakukan mulai dari i=1 hingga N, diamana N adalah banyaknya aktivitas. 6) Meng-update harmony memory Urutan langkah perbaikan harmony memory sebagai berikut: • Melakukan proses penjadwalan untuk vektor solusi baru yang telah dibentuk pada langkah 5. • Menghitung durasi proyek dari vektor solusi yang baru. • Melakukan pengecekan terhadap vektor solusi yang baru. Apabila nilai vektor solusi yang baru lebih baik daripada nilai vektor solusi terjelek pada harmony memory dilihat dari sudut pandang nilai fungsi tujuan, maka vektor solusi yang baru akan dimasukkan ke dalam harmony memory dan vektor solusi terjelek pada harmony memory akan dikeluarkan. Apabila nilai vektor solusi yang baru lebih buruk daripada nilai vektor solusi terjelek pada harmony memory, maka tidak akan terjadi perubahan pada harmony memory. 7) Mengecek kriteria pemberhentian Apabila kriteria pemberhentian telah tercapai maka proses komputasi dihentikan, apabila belum tercapai maka kembali ke langkah 5. 5.
Eksperimen Eksperimen dilakukan dengan bantuan kode program yang terdapat pada software Matlab untuk mengetahui efek perubahan parameter algoritma terhadap solusi yang dihasilkan dan performansi algoritma HS pada penyelesaian RCPSP.
Uji perubahan parameter algoritma digunakan untuk mengetahui efek perubahan parameter algoritma terhadap solusi yang dihasilkan. 5.1.1
Data Uji Perubahan Parameter Algoritma Data untuk uji perubahan parameter algoritma diambil dari International Journal of Project Management 24 (2006) 83–92. Tabel 1. Data Uji Perubahan Parameter Algoritma Sumber Daya Yang Akti Du Aktivitas Diperlukan vitas rasi Pendahulu 1 2 3 1
5
5
3
2
2
5
4
5
3
3
3
2
5
2
4
4
1
4
4
1
2
5
2
4
2
4
1
2
6
1
5
5
4
3
7
6
5
3
2
3
8
6
2
3
2
4
9
1
1
4
4
4
10
3
2
3
4
5
11
3
3
3
2
6
12
3
4
1
4
8
13
3
5
5
4
8
14
6
2
2
2
9
15
4
5
1
4
11
16
3
3
5
3
12
17
3
2
3
3
14
18
4
5
4
4
13
19
1
4
2
6
15
20
4
0
1
4
16
21
4
6
1
2
16
22
1
2
2
1
18
23
6
2
3
1
18
24
3
2
2
2
20
25
3
1
0
3
20
Uji Perubahan Parameter Algoritma
7
6
7
10
15
17 19 21
22
23
Tabel 2. Sumber Daya yang Tersedia Tipe 1
5.1
5
2 6
3 6
6
8
5.1.2
Hasil Uji Perubahan Parameter Algoritma Uji perubahan parameter algoritma dilakukan dengan cara melakukan kombinasi parameter HMCR dan PAR. Pada setiap kombinasi dilakukan replikasi running 10 kali, dimana setiap kali running digunakan HMS sebesar 15, bandwidth sebesar 0.1, dan iterasi sebanyak 80 kali.
Tabel 5. Output Uji Perubahan Parameter Algoritma Bagian 3 Repli kasi
Tabel 3. Output Uji Perubahan Parameter Algoritma Bagian 1 Repli kasi
HMCR=0.9
HMCR=0.9
PAR=0.1 Durasi Proyek
PAR=0.3 Durasi Proyek
PAR=0.5 Durasi Proyek
1
67
65
67
2
66
65
65
3
65
65
65
4
65
66
65
5
66
65
65
HMCR=0.7
HMCR=0.7
HMCR=0.7
6
65
65
65
PAR=0.1 Durasi Proyek
PAR=0.3 Durasi Proyek
PAR=0.5 Durasi Proyek
7
65
65
65
8
66
65
66
9
66
65
65
10 Durasi Proyek Terkecil
66
65
65
65
65
65
1
65
65
65
2
65
67
65
3
65
65
66
4
65
65
66
5
65
65
65
6
65
65
65
7
66
65
65
8
65
65
65
9
65
66
65
10 Durasi Proyek Terkecil
65
65
66
5.2
Uji Performansi Algoritma Uji performansi algoritma digunakan untuk mengetahui performansi algoritma HS pada penyelesaian RCPSP dibandingkan dengan algoritma yang lain yaitu algoritma Particle Swarm Optimization (PSO). 5.2.1
65
65
65
Tabel 4. Output Uji Perubahan Parameter Algoritma Bagian 2 Repli kasi
HMCR=0.9
HMCR=0.8
HMCR=0.8
HMCR=0.8
PAR=0.1 Durasi Proyek
PAR=0.3 Durasi Proyek
PAR=0.5 Durasi Proyek
Data Uji Performansi Algoritma Data untuk uji performansi algoritma diambil dari Project Scheduling Library (PSPLIB). Alamat website dari Project Scheduling Library (PSPLIB) adalah http://129.187.106.231/psplib/. Data ini terdiri dari 2 macam yaitu data pertama berisi 30 aktivitas proyek dan data kedua berisi 60 aktivitas proyek.
1
65
65
65
2
65
70
65
3
65
65
65
4
65
66
65
5
65
65
66
6
67
65
65
1
8
4
0
0
0
7
65
65
65
2
4
10
0
0
0
8
65
65
66
3
6
0
0
0
3
9
65
65
65
4
3
3
0
0
0
3
10 Durasi Proyek Terkecil
65
67
65
5
8
0
0
0
8
1
6
5
4
0
0
0
2
7
9
0
1
0
0
2
65
65
65
Tabel 6. Data Uji Performansi Algoritma untuk 30 Aktivitas Sumber Daya Akti Du Yang Diperlukan Aktivitas vitas rasi Pendahulu 1 2 3 4
9
Tabel 6. Data Uji Performansi Algoritma untuk 30 Aktivitas (Lanjutan) Sumber Daya Akti Du Yang Diperlukan Aktivitas vitas rasi Pendahulu 1 2 3 4
Tabel 8. Data Uji Performansi Algoritma untuk 60 Aktivitas (Lanjutan) Sumber Daya Akti Du Aktivitas Yang Diperlukan vitas rasi Pendahulu 1 2 3 4
8
2
6
0
0
0
3
6
8
10
0
0
0
2
9
7
0
0
0
1
3
7
9
0
0
6
0
3
10
9
0
5
0
0
1
8
1
0
0
0
8
7
11
2
0
7
0
0
7
9
9
0
6
0
0
1
12
6
4
0
0
0
2
10
8
0
0
0
3
9
13
3
0
8
0
0
8
11
3
0
7
0
0
3
14
9
3
0
0
0
1
12
6
8
0
0
0
8
15
10
0
0
0
5
9
13
2
0
0
0
1
2
16
6
0
0
0
8
12
14
5
0
0
0
9
1
17
5
0
0
0
7
12
15
1
6
0
0
0
3
18
3
0
1
0
0
7
16
3
2
0
0
0
5
19
7
0
10
0
0
4
17
10
0
0
2
0
12
20
2
0
0
0
6
15
18
9
7
0
0
0
13
21
7
2
0
0
0
15
16
19
1
5
0
0
0
7
22
2
3
0
0
0
19
21
20
3
0
0
8
0
11
23
3
0
9
0
0
18
22
21
6
0
4
0
0
4
24
3
4
0
0
0
9
14
22
3
0
0
4
0
6
25
7
0
0
4
0
10
23
3
0
5
0
0
4
26
8
0
0
0
7
6
7
24
7
0
0
1
0
14
27
3
0
8
0
0
20
26
25
6
9
0
0
0
10
28
7
0
7
0
0
18
26
10
0
7
0
0
11
19
29
2
0
7
0
0
5
23
27
9
3
0
0
0
17
18
30
2
0
0
2
0
25
27
28
8
0
0
3
0
2
29
4
0
0
7
0
26
30
3
6
0
0
0
19
31
3
0
0
0
4
16
32
6
0
7
0
0
17
33
1
0
0
0
4
13
34
9
0
0
1
0
8
35
9
9
0
0
0
34
36
1
0
7
0
0
10
37
2
5
0
0
0
5
11
13
10
17 17
19
24
Tabel 7. Sumber Daya yang Tersedia untuk 30 Aktivitas Tipe 1
2 12
3 13
4 4
12
Tabel 8. Data Uji Performansi Algoritma untuk 60 Aktivitas Sumber Daya Akti Du Aktivitas Yang Diperlukan vitas rasi Pendahulu 1 2 3 4
13
21
38
4
0
0
1
0
20
32
1
8
10
0
0
0
39
9
0
0
0
5
7
24
2
1
0
1
0
0
40
10
0
0
0
1
28
3
10
0
9
0
0
41
8
0
0
0
9
35
4
6
0
4
0
0
1
42
4
0
0
6
0
16
30
5
5
0
0
0
1
4
43
3
0
0
0
1
10
33
34
10
Tabel 8. Data Uji Performansi Algoritma untuk 60 Aktivitas (Lanjutan) Sumber Daya Akti Du Aktivitas Yang Diperlukan vitas rasi Pendahulu 1 2 3 4 44
6
0
0
0
9
9
45
6
0
0
0
7
40
46
7
4
0
0
0
27
47
3
0
8
0
0
23
Berikut ini adalah output hasil running uji performansi algoritma berupa durasi proyek untuk 30 aktivitas. Pada bagian tabel yang diberi shading warna biru menandakan durasi proyek terkecil dengan waktu komputasi tercepat untuk masing-masing algoritma. Tabel 11. Output Uji Performansi Algoritma untuk 30 Aktivitas
41 Repli kasi
48
2
0
2
0
0
25
49
10
0
0
7
0
37
43
50
4
0
5
0
0
22
26
51
2
2
0
0
0
46
52
1
0
1
0
0
38
39
53
4
0
0
6
0
25
42
PSO Waktu Durasi Komputasi Proyek (detik)
HS Waktu Durasi Komputasi Proyek (detik)
1
46
24.125
43
25.0625
2
46
25.109375
45
24.90625
3
43
25.59375
45
25.390625
51
4
46
25.6875
43
24.46875
43
25.015625
45
24.859375
44
54
10
0
0
0
7
15
47
53
5
55
8
0
0
3
0
29
45
52
6
43
25.140625
43
24.4375
56
6
0
4
0
0
28
31
54
7
46
25.625
45
25
57
10
0
0
9
0
15
36
42
8
43
25.140625
46
24.421875
58
3
0
0
0
7
14
56
57
9
45
25.75
45
25.5625
59
10
0
3
0
0
37
48
50
10
43
25
45
25.28125
60
1
0
0
0
1
27
49
55
Tabel 9. Sumber Daya yang Tersedia untuk 60 Aktivitas Tipe 1
2 13
3 11
4 12
Setelah diketahui output uji performansi algoritma, maka pada bagian dibawah ini akan disajikan grafik yang menggambarkan durasi proyek hasil running algoritma PSO dan HS selama 10 kali replikasi untuk problem 30 aktivitas.
13
Hasil Uji Performansi Algoritma Uji performansi algoritma dilakukan dengan cara melakukan running kedua algoritma yaitu HS dan PSO dimana setiap kali running dilakukan replikasi sebanyak 10 kali. Tabel 10. Parameter Algoritma 30 Aktivitas Proyek 60 Aktivitas Proyek PSO HS PSO HS Jumlah HMS=15 Jumlah HMS=30 Partikel Partikel =15 =30 c1=2 HMCR=0.8 c1=2 HMCR=0.8 c2=2 PAR=0.3 c2=2 PAR=0.3 bw=0.1 bw=0.1
Jumlah Iterasi= 80
Jumlah Iterasi= 80
Jumlah Iterasi= 120
Jumlah Iterasi= 120
Durasi Proyek
5.2.2
46.5 46 45.5 45 44.5 44 43.5 43 42.5 42 41.5
PSO HS
1
2
3
4
5
6
7
8
9
10
Replikasi
Grafik 1. Durasi Proyek PSO dan HS untuk 30 Aktivitas
Pada bagian dibawah ini akan ditampilkan tabel yang menggambarkan perbandingan hasil running algoritma HS dengan algoritma PSO untuk problem 30 aktivitas.
11
Tabel 12. Perbandingan Performansi Algoritma untuk 30 Aktivitas PSO HS Selisih Durasi Proyek 43 43 0 Terkecil Waktu 25 24.4375 0.5625 Komputasi Tercepat (detik)
Berikut ini adalah output hasil running uji performansi algoritma berupa durasi proyek untuk 60 aktivitas. Pada bagian tabel yang diberi shading warna biru menandakan durasi proyek terkecil dengan waktu komputasi tercepat untuk masing-masing algoritma. Tabel 13. Output Uji Performansi Algoritma untuk 60 Aktivitas PSO Waktu Durasi Komputasi Proyek (detik)
Repli kasi
HS Waktu Durasi Komputasi Proyek (detik)
1
80
391.5156
77
405.9844
2
80
406.5313
77
389.5625
3
79
420.7188
77
393.5625
4
77
400.1094
77
427.1875
5
77
394.1563
77
392.1094
6
81
405.5781
77
389.2813
7
77
400.9219
77
418.5
8
77
424.9219
77
395.2656
9
77
400.1094
77
388.6094
10
79
392.2969
77
395.6406
Setelah diketahui output uji performansi algoritma, maka pada bagian dibawah ini akan disajikan grafik yang menggambarkan durasi proyek hasil running algoritma PSO dan HS selama 10 kali replikasi untuk problem 60 aktivitas. 82
Durasi Proyek
81 80 79 78 PSO 77 HS 76 75 1
2
3
4
5
6
7
8
9
10
Replikasi
Pada bagian dibawah ini akan ditampilkan tabel yang menggambarkan perbandingan hasil running algoritma HS dengan algoritma PSO untuk problem 60 aktivitas. Tabel 14. Perbandingan Performansi Algoritma untuk 60 Aktivitas PSO HS Seli sih Durasi 77 77 0 Proyek Terkecil Waktu 394.1563 388.6094 5.5469 Komputasi Tercepat (detik)
6.
Analisa Berikut ini akan dijelaskan mengenai analisa hasil eksperimen yang telah dilakukan dari penelitian tugas akhir. 6.1
Analisa Uji Perubahan Parameter Algoritma Uji perubahan parameter algoritma digunakan untuk mengetahui efek perubahan parameter algoritma terhadap solusi yang dihasilkan. Uji perubahan parameter algoritma dilakukan dengan cara melakukan kombinasi dari parameter HMCR dan PAR. Penelitian sebelumnya menunjukkan bahwa penggunaan HMCR sebaiknya dalam rentang 0.7 sampai 0.95 dan PAR dalam rentang 0.1 sampai 0.5. Pada penelitian ini digunakan kombinasi nilai parameter HMCR dan PAR yang berbeda-beda, namun masih dalam rentang yang disarankan oleh penelitian sebelumnya. Setiap kombinasi parameter di-running sebanyak 10 kali, kemudian durasi proyek yang dihasilkan diambil dari durasi proyek terkecil dari 10 kali running. Hasil penelitian menunjukkan bahwa durasi proyek tidak mengalami perubahan meskipun nilai parameternya berubah. Hal ini dikarenakan RCPSP termasuk dalam kategori discrete optimization problem. Pada discrete optimization problem jumlah alternatif solusi tidak sebanyak pada continous optimization problem, sehingga solusi yang dihasilkan tetap sama walaupun parameter algoritma diubah. Dengan demikian jumlah alternatif solusi pada RCPSP yang tidak terlalu besar menyebabkan solusi yang dihasilkan algoritma HS tidak berubah, walaupun parameter algoritma diubah.
Grafik 2. Durasi Proyek PSO dan HS untuk 60 Aktivitas
12
6.2 Analisa Uji Performansi Algoritma Uji performansi algoritma digunakan untuk mengetahui performansi algoritma HS pada penyelesaian RCPSP dibandingkan dengan algoritma yang lain yaitu algoritma Particle Swarm Optimization (PSO). Pada pengujian ini data yang digunakan terdiri dari 2 macam yaitu data pertama berisi 30 aktivitas proyek dan data kedua berisi 60 aktivitas proyek. Running dilakukan dengan replikasi sebanyak 10 kali. Berdasarkan eksperimen yang telah dilakukan terlihat bahwa secara umum durasi proyek yang dihasilkan tiap replikasi tidak sama. Pada data pertama terlihat bahwa durasi proyek yang dihasilkan baik algoritma HS maupun PSO mengalami fluktuasi dari replikasi satu ke replikasi lainnya. Hal ini dikarenakan nilai bilangan random yang dibangkitkan, jika bilangan random yang dibangkitkan mendukung untuk terjadinya durasi proyek yang kecil maka akan dihasilkan durasi proyek yang kecil, namun jika bilangan random yang dibangkitkan tidak mendukung untuk terjadinya durasi proyek yang kecil maka akan sulit dihasilkan durasi proyek yang kecil. Pada data kedua terlihat bahwa durasi proyek yang dihasilkan algoritma HS stabil dari replikasi satu ke replikasi lainnya, sedangkan durasi proyek yang dihasilkan algoritma PSO mengalami fluktuasi dari replikasi satu ke replikasi lainnya. Hal ini juga dikarenakan nilai bilangan random yang dibangkitkan sebagaimana yang telah dijelaskan sebelumnya. Bilangan random yang dibangkitkan memiliki pengaruh terhadap solusi yang dihasilkan karena pembangkitan bilangan random bagian utama dari mekanisme algoritma. Durasi proyek hasil running diambil dari durasi proyek terkecil dari 10 kali replikasi. Pada pengujian data pertama, algoritma HS dan PSO menghasilkan durasi proyek yang sama yaitu 43 sedangkan waktu komputasi HS lebih cepat 0.5625 detik daripada PSO. Pada pengujian data kedua, algoritma HS dan PSO menghasilkan durasi proyek yang sama yaitu 77 sedangkan waktu komputasi HS lebih cepat 5.5469 detik daripada PSO. Hal ini menunjukkan bahwa kualitas solusi yang dihasilkan algoritma HS sama dengan algoritma PSO, namun apabila dilihat dari sisi waktu komputasi, maka waktu komputasi algoritma HS lebih cepat daripada algoritma PSO. Waktu komputasi algoritma HS lebih cepat daripada algoritma PSO dikarenakan mekanisme kerja
algoritma HS lebih efisien daripada algoritma PSO. Pada algoritma HS hanya ada satu kandidat solusi yang melakukan proses pencarian solusi, sedangkan pada algoritma PSO semua kandidat solusi melakukan proses pencarian solusi. Dengan demikian, apabila ditinjau dari segi waktu komputasi, maka performansi algoritma HS lebih baik daripada algoritma PSO. 7.
Kesimpulan dan Saran Berikut ini akan dipaparkan kesimpulan dan saran yang bisa diberikan dari hasil penelitian tugas akhir yang telah dilakukan. 7.1
Kesimpulan Berikut ini adalah beberapa kesimpulan yang bisa diberikan: 1. Perubahan parameter algoritma HS pada penyelesaian RCPSP tidak berpengaruh pada solusi yang dihasilkan. 2. Kualitas solusi yang dihasilkan algoritma HS sama dengan algoritma PSO, namun jika dilihat dari sisi waktu komputasi, maka waktu komputasi algoritma HS lebih cepat daripada algoritma PSO. Oleh karena itu, apabila ditinjau dari segi waktu komputasi, maka performansi algoritma HS untuk penyelesaian RCPSP lebih baik daripada algoritma PSO. 7.2
Saran Penelitian tugas akhir ini memiliki potensi untuk dikembangkan lebih lanjut. Pada penelitian berikutnya disarankan permasalahan yang akan diselesaikan adalah Multi-Mode Resource-Constrained Project Scheduling Problem (MMRCPSP) karena permasalahan MMRCPSP lebih mendekati kondisi dunia nyata daripada Single-Mode ResourceConstrained Project Scheduling Problem (SMRCPSP). 8. Daftar Pustaka Baker, K.R., dan Trietsch, D. (2009). Principles of Sequencing and Scheduling. John Wiley and Sons, New Jersey. Baker, K.R. (1974). Introduction to Sequencing and Scheduling. John Wiley and Sons, New York, Chichester, Brisbane, Toronto.
13
Boctor, F.F. (1990). Some efficient multiheuristic procedures for resourceconstrained project scheduling. Eur J Operat Res, Vol. 49, pp. 3–13. Brucker, P., Knust, S., Schoo, A., dan Thiele, O. (1998). A branch and bound algorithm for the resource-constrained project scheduling problem. European Journal of Operational Research, Vol. 107, pp. 272-288. Chan,
W.T., dan Chua, D.K.H. (1996). Construction resource scheduling with genetic algorithms. J Constr Eng Manage ASCE, Vol. 122, No. 2, pp. 125–32.
Davis, E.W., dan Patterson, J.H. (1975). A comparison of heuristic and optimum solutions in resource-constrained project scheduling. Manage Sci, Vol. 21, pp. 944–55. Eberhart, R.C., dan Shi, Y. (2001). Tracking and Optimizing Dynamic Systems with Particle Swarms. In: Proceedings of the IEEE congress on evolutionary computation (CEC 2001), Seoul, Korea, p. 94–7. Forsati, R., Haghighat, A.T., dan Mahdavi, M. (2008). Harmony search based algorithms for bandwidth-delayconstrained least-cost multicast routing. Computer Communications, Vol. 31, pp. 2505–2519. Gavish, B. dan Pirkul, H. (1991). Algorithms for multi-resource generalized assignment problem. Manage Sci, Vol. 37, No. 6, pp. 695–713. Geem, Z.W. (2009). Music-Inspired Harmony Search Algorithm. Springer, Verlag, Berlin, Heidelberg. Geem, Z.W., Lee, K.S., dan Park, Y. (2005). Application of Harmony Search to Vehicle Routing. American Journal of Applied Sciences, Vol. 2, No. 12, pp. 1552-1557. Geem, Z.W., Kim, J.H., dan Loganathan, G.V. A New Heuristic Optimization Algorithm: Harmony Search.
Fogel, D.B. (1995). Evolutionary computation toward a new philosophy of machine intelligence. IEEE Press, New York. Kennedy, J., dan Eberhart, R.C. (1995). Particle Swarm Optimization. In: Proceedings IEEE conference on neural networks, Vol. IV, Piscataway, NJ, p. 1942–48. Kolisch, R., dan Sprecher, A. (1996). PSPLIB A Project Scheduling Problem Library. European Journal of Operational Research, Vol. 96, pp. 205-216. Lee, J.K., dan Kim, Y.D. (1996). Search heuristics for resource constrained project scheduling. J Operat Res Soc, Vol. 47, No. 5, pp. 678–89. Mahdavi, M., Fesanghary, M., dan Damangir, E. (2007). An improved harmony search algorithm for solving optimization problems. Applied Mathematics and Computation, Vol. 188, pp. 1567–1579. Merkle, D., Middendorf, M., dan Schmeck, H. (2002). Ant Colony Optimization for Resource-Constrained Project Scheduling. IEEE Transactions on Evolutionary Computation, Vol. 6, No. 4. Patterson, J. (1984). A Comparison of Exact Procedures for Solving The Multiple Constrained Resource Project Scheduling Problem. Manage Sci, Vol. 30, pp.854–67. Saka, M.P. (2009). Optimum design of steel sway frames to BS5950 using harmony search algorithm. Journal of Constructional Steel Research, Vol. 65, pp. 36–43. Talbot, F.B. (1982). Resource-Constrained Project Scheduling with Time Resource Tradeoffs: The Nonpreemptive Case. Manage Sci, Vol. 28, No. 10, pp. 1197–210. Valls, V., Ballestin, F., dan Quintanilla, S. (2008). A hybrid genetic algorithm for the resource-constrained project scheduling problem. European Journal of Operational Research, Vol. 185, pp. 495–508. Zhang, H., Li, H., dan Tam, C.M. (2006). Particle Swarm Optimization for Resource-Constrained Project
14
Scheduling. International Journal of Project Management, Vol. 24, pp. 83– 92.
15
