1) Rizky Imansyah Putra adalah mahasiswa Jurusan Matematika Universitas Negeri Malang

2) Purwanto adalah dosen Jurusan Matematika Universitas Negeri Malang

Penerapan Algoritma Harmony Search pada

Resource-Constrained Project Scheduling Problem

(RCPSP) Rizky Imansyah Putra

1) dan Purwanto

2)

Jurusan Matematika

Universitas Negeri Malang

Email: rizky_ip20@yahoo.com

1. Pendahuluan

Penjadwalan proyek dengan menggunakan Critical Path Method (CPM)

hanya berfokus pada hubungan ketergantungan antar aktivitas dengan asumsi

ketersediaan sumberdaya yang tidak terbatas. Namun, dalam kenyataannya dalam

pengerjaan suatu proyek sumberdaya yang tersedia sangatlah terbatas guna

meminimalisasi pengeluaran sehingga manajer proyek sering sulit untuk

melakukan penjadwalan proyek. Maka akan ditemukan suatu masalah

penjadwalan kegiatan-kegiatan dengan kendala sumberdaya terbatas atau Resorce-

Constrained Project Scheduling Problem (RCPSP).

Beberapa metode heuristik yang dapat digunakan untuk menyelesaikan

Resource-Constrained Project Scheduling Problem seperti shortest task first, most

resource first, minimum slack first (gray-kidd algorithm), dan most successors.

Sedangkan metode metaheuristik untuk menyelesaikan RCPSP seperti algoritma

genetika, ant colony optimization, dan particle swarm optimization. Beberapa

ABSTRAK : Resource-Constrained Project Scheduling (RCPSP) adalah

perluasan dari project scheduling. Resource-Constrained Project Scheduling

berkembang untuk memperhitungkan durasi penjadwalan pengerjaan proyek

dengan kendala sumberdaya yang terbatas sehingga bisa ditentukan durasi

pengerjaan proyek yang minimum tanpa melebihi sumberdaya yang tersedia.

Algoritma Harmony Search pada RCPSP memiliki tujuh langkah, yaitu inisialisasi

masalah, memasukan data RCPSP, inisialisasi parameter Algoritma Harmony

Search, inisialisasi harmony memory (HM), membangkitkan vektor solusi baru,

meng-update harmony memory (HM), mengecek kriteria pemberhentian.

Kata kunci : algoritma harmony search, resource-constrained project scheduling,

penjadwalan.

ABSTRACT : Resource-Constrained Project Scheduling is an expansion of

project scheduling problem. Resource-Constrained Project Scheduling developed

for search the duration of the project scheduling with resource constraints so that it

can be determined that the minimum duration of the construction project without

exceeding available resources. Harmony Search Algorithm of RCPSP has seven

steps, they are initialization of the optimization problem, enter data of RCPSP,

initialization of algorithm parameters, initialization of harmony memory, generate

new vector solution, harmony memory update, check the termination criterion.

Keywords : harmony search algorithm, resource-constrained project scheduling,

scheduling.

algoritma metaheuristik GA, ACO, dan PSO telah diuji coba pada kasus RCPSP

seperti pada paper yang ditulis oleh Tchomte (2007) dan Goncalves (2004).

Oleh karena itu, bahwa penulisan skripsi kali ini akan dicoba metode

metaheuristik yang lain yaitu Harmony Search. Pada skripsi ini akan dijelaskan

langkah-langkah pengerjaan Algoritma Harmony Search dengan proses manual

dan hasilnya akan dibandingkan dengan hasil dari Algoritma CPM.

Tujuan dari penulisan skripsi ini adalah mengidentifikasi bagaimana

penyelesaian RCPSP menggunakan Algoritma Harmony Search dengan proses

manual dan bagaimana solusi yang diperoleh dari perhitungan menggunakan

Algoritma Harmony Search dibandingkan dengan Algoritma CPM.

2. Masalah RCPSP

Resource-Constrained Preoject Scheduling Problem atau RCPSP adalah

masalah penjadwalan aktivitas-aktivitas pada proyek harus memenuhi precedence

constraints dan resource constraints. Yang dimaksud dengan precedence

constraints adalah dimana aktivitas pendahulu harus sudah selesai dijadwalkan

sebelum kegiatan lain dijadwalkan. Sedangkan resource constraints adalah suatu

kendala dimana sumberdaya yang diperlukan oleh setiap aktivitas tidak boleh

melebihi sumberdaya yang tersedia. Berikut ini adalah formulasi matematika dari

RCPSP dengan fungsi tujuan untuk meminimasi durasi proyek (Setiawan;2010):

min{max 𝑓𝑖|𝑖 = 1,2,… ,𝑁} ………………. (1)

subject to : 𝑓𝑖 − 𝑓𝑗 ≥ 𝑑𝑖 ……………………(2)

∀𝑗∈ 𝑃𝑖 : 𝑖 = 1,2,… ,𝑁

𝐴𝑡𝑟𝑖𝑘 ≤ 𝑅𝑘 …………………….(3)

𝑘 = 1,2,… ,𝐾; 𝑡 = 𝑠1, 𝑠2,… , 𝑠𝑁 Dimana:

𝑁= jumlah aktivitas yang terdapat pada proyek

𝑓𝑖= waktu penyelesaian aktivitas 𝑖 (𝑖 = 1,2,… ,𝑁)

𝑑𝑖= durasi aktivitas 𝑖 𝑃𝑖= predecessor aktivitas 𝑖 𝑅𝑘= jumlah sumberdaya tipe 𝑘 yang tersedia (𝑘 = 1,2,… ,𝐾)

𝐾= jumlah tipe sumberdaya

𝑟𝑖𝑘= jumlah sumberdaya tipe 𝑘 yang diperlukan oleh aktivitas 𝑖 𝐴𝑡= sekelompok aktivitas yang berjalan pada waktu ke-𝑡 𝑠𝑖 = 𝑓𝑖 − 𝑑𝑖

𝑠𝑖= waktu mulai aktivitas 𝑖

Persamaan (1) merepresentasikan fungsi tujuan dari RCPSP. Persamaan (2)

merepresentasikan precedence constraints. Persamaan (3) merepresentasikan

resource constraints.

Untuk pembahasan kali ini, akan dibahas RCPSP dengan kebutuhan suatu

himpunan sumberdaya diasumsikan tetap. Atau lebih dikenal dengan Single-Mode

Resource-Constrained Project Scheduling Problem (SMPRCPSP).

Berikut ini adalah contoh visualisasi dari RCPSP:

Gambar 1 ilustrasi RCPSP

Apabila pada kasus Gambar 1 jumlah sumberdaya yang tersedia sebanyak 5 unit,

maka Gambar 2 merupakan salah satu bentuk pemjadwalan

Gambar 2 Visualisasi Bentuk Jadwal

3. Algoritma Harmony Search

Berikut ini adalah langkah-langkah dari algoritma Harmony Search secara

umum menurut konsep di atas (Hadwan;2013):

1. Inisialisasi optimalisasi masalah dan parameter algoritma.

2. Inisialisasi harmony memory.

3. Membangkitkan vektor solusi yang baru.

4. Meng-update harmony memory.

5. Ulangi langkah 3 dan 4 hingga kriteria pemberhentian.

Penjelasan untuk langkah-langkah Algoritma Harmony Search secara umum

adalah:

1) Inisialisasi Parameter Algoritma Harmony Search

Pada langkah pertama, optimalisasi masalah ditetapkan berdasarkan fungsi

tujuan dan parameter algoritma diinisialisasi sebagai berikut:

HMS (Harmony Memory Size) adalah banyak solusi yang disimpan pada

HM (Harmony Memory). HMS hampir sama seperti banyak populasi pada

Algoritma Genetika.

HMCR (Harmony Memory Considering Rate) digunakan selama proses

improvisasi untuk menentukan apakah variable dari solusi tersebut dapat

mengambil semua nilai tersebut pada HM. HMCR memilih suatu nilai

antara [0,1].

PAR (Pitch Adjusting Rate) juga digunakan selama proses improvisasi

untuk menentukan apakah variable dari solusi tersebut harus diganti ke

suatu nilai tetangga. PAR memilih suatu nilai antara [0,1].

2) Membangun Harmony Memory

Pada langkah kedua, suatu himpunan inisial solusi dari ukuran HMS

dibangkitkan untuk membangun HM. HM digambarkan sebagai suatu matriks

2 dimensi. Baris menunjukan suatu himpunan solusi atau disebut vektor solusi

𝑋𝑖 , sedangkan kolom menunjukan variabel keputusan untuk tiap solusi. Setiap

solusi 𝑋𝑖 dapat dilihat sebagai salah satu susunan urutan. Berikut ini adalah

contoh matriks harmony memory :

2

2

1 1 1

1

2 2

1

11 1

1

21

2

2

...

...

... ... ... ...

...

...

HMS HMS

HMSH

N

N

HMS

N

MS HMS

N

x x x

x x x

xx

x

M

x

x

H

x

Gambar 4 Matriks Harmony Memory

3) Improvisasi Harmony Baru

Pada langkah ini, suatu vektor baru 𝑋′ = (𝑥1′ , 𝑥2

′ ,… , 𝑥𝑁′ ) dibangkitkan

berdasarkan pada tiga aturan, yaitu: (i) mempertimbangkan memory, (ii)

pencocokan nada, dan (iii) pemilihan acak. Membangkitkan suatu harmony

baru disebut improvisasi. Dalam mempertimbangkan memory, nilai dari

pemilihan pertama 𝑥1′ untuk vektor baru dipilih berdasarkan nilai yang tersedia

pada HM dari himpunan 𝑥11, 𝑥1

2 ,… , 𝑥1𝐻𝑀𝑆 , dengan kemungkinan HMCR

∈ [0,1]. Nilai keputusan dari 𝑥2′ , 𝑥3

′ ,… , 𝑥𝑁′ dipilih dengan cara yang sama. Jika

nilai acak yang terpilih dengan kemungkinan 1 − 𝐻𝑀𝐶𝑅, maka nilai vektor

solusi dipilih dari range yang mungkin dari nilai tersebut.

𝑥𝑖′ 𝑥𝑖 ∈ 𝑥𝑖

1 , 𝑥𝑖2 ,… , 𝑥𝑖

𝐻𝑀𝑆 dengan kemungkinan HMCR

𝑥𝑖 ∈ 𝑋𝑖 dengan kemungkinan (1 − HMCR)

Setiap komponen berdasarkan dari pertimbangan memory diuji untuk

menentukan apakan dapat dijadikan pencocokan nada. Langkah ini

menggunakan parameter PAR, dengan pemilihan sebagai berikut

𝑥𝑖′ 𝑥𝑖′ + 𝑟𝑎𝑛𝑑 −1,1 ∗ 𝑏𝑤 dengan kemungkinan PAR

𝑥𝑖′ dengan kemungkinan (1 − PAR)

Dimana 𝑏𝑤 (bandwidth) adalah suatu nilai sebarang.

4) 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 terjelek akan dikeluarkan dan digantikan oleh vektor solusi

baru. Jika nilai vektor solusi yang baru lebih buruk dari pada nilai vektor solusi

terjelek, maka tidak akan terjadi perubahan pada harmony memory.

5) Mengecek kriteria pemberhentian

Apabila kriteria pemberhentian telah tercapai, maka iterasi dihentikan.

Apabila belum tercapai maka ulangi langkah 3 dan 4 hingga kriteria

pemberhentian dipenuhi.

4. HASIL DAN PEMBAHASAN

Algoritma Harmony Search pada Penyelesaian Resource-Constrained Project

Scheduling Problem

Penerapan Algoritma Harmony Search supaya dapat menyelesaikan

RCPSP harus melalui beberapa langkah sebagai berikut:

1) Inisialisasi masalah.

2) Memasukan data RCPSP.

3) Inisialisasi parameter Algoritma HS.

4) Inisialisasi harmony memory.

5) Membangkitkan vektor solusi baru.

6) Meng-update harmony memory.

7) Mengecek kriteria pemberhentian.

Berikut penjelasan dari langkah-langkah tersebut (Setiawan;2010):

1) Inisialisasi Masalah

Pada tahap ini diperkenalkan masalah yang akan diselesaikan, masalah

dalam skripsi kali ini adalah RCPSP dengan fungsi tujuan meminimasi durasi

proyek (Csebfalvi;2009)

𝐦𝐢𝐧 𝑓 𝑥 𝑥 = {𝑥𝑖 ≤ 𝑥𝑖 ≤ 𝑥𝑖 , 𝑖 = 1,2,… ,𝑁 }}

Jika dianalogikan pada musik, 𝑥 adalah melodi yang nilai keindahannya

ditunjukan oleh 𝑓(𝑥). Dengan kata lain, semakin rendah nilai 𝑓(𝑥), semakin

tinggi kualitas melodi tersebut. Pada band, jumlah musisi ditunjukan oleh 𝑁

sedangkan dalam RCPSP menunjukan banyaknya kegiatan dalam proyek

tersebut, dan musisi 𝑖 bertanggung jawab untuk bunyi 𝑥𝑖 . Misal 𝑥𝑖 , 𝑥𝑖 ≤ 𝑥𝑖 ≤

𝑥𝑖 menyatakan waktu mulai pengerjaan aktivitas 𝑖. 𝑥𝑖(𝑥𝑖) menyatakan waktu

paling cepat (lambat) suatu aktivitas 𝑖 dapat dimulai pengerjaannya.

2) Memasukan Data RCPSP

Untuk memodelkan RCPSP, dimisalkan sebagai berikut: Suatu proyek

terdiri dari 𝑁 aktivitas 𝑖 ∈ {1,2,… ,𝑁} dengan durasi tiap aktivitas 𝐷𝑖 .

Selanjutnya, aktivitas 𝑖 = 0 (𝑖 = 𝑁 + 1) didefinisikan menjadi aktivitas

dummy dengan tidak memerlukan sumberdaya dan lama durasi 0. Aktivitas-

aktivitas tersebut berhubungan dengan precedence dan resource constraints.

Misal 𝐼𝑃𝑆 = 𝑖 → 𝑗|𝑖 ≠ 𝑗, 𝑖 ∈ 0,1,… ,𝑁 , 𝑗 ∈ 1,2,… ,𝑁 + 1 merupakan

himpunan hubungan kegiatan sebelum dan sesudah.Pada proses pengerjaan,

aktivitas 𝑖 membutuhkan 𝑅𝑖𝑟 unit sumberdaya tipe 𝑟 ∈ {1,2,… ,𝑅} selama

durasi pengerjaan. Karena sumberdaya 𝑟 hanya tersedia 𝑅𝑟 unit pada suatu

periode pengerjaan.

3) Inisialisasi Parameter Algoritma HS

Algoritma Harmony Search (HS) telah dikembangkan oleh Lee dan Geem

(2004) pada suatu analogi dengan proses improvisasi musik dimana para

pemain alat music mengiprovisasi nada dari masing-masing alat musik yang

mereka kuasai sehinggga mendapatkan harmoni yang baik. Harmoni-harmoni

tersebut kemudian disimpan ke dalam harmony memory (HM) supaya dapat

dibandingkan dan dicari harmoni yang lebih baik. Banyak HM disebut sebagai

harmony memory size (HMS).

Agar harmony memory dapat digunakan secara efektif, Algoritma HS

mengadopsi suatu parameter harmony memory considering rate (HMCR).

Seperti yang telah dibahas pada Bab II, jika rate ini terlalu rendah, maka hanya

sedikit harmoni elit yang terpilih dan dapat menyebabkan proses konvergensi

terlalu lambat. Jika rate terlalu besar, maka akan menyebabkan nada-nada pada

HM banyak terpakai dan tidak sempat mengeksplorasi nada lain, sehingga sulit

mencapai solusi yang bagus. Oleh karena itu, menurut Setiawan (2010)

biasanya digunakan HMCR = 0.7 − 0.95.

Parameter berikutnya adalah bandwidth (bw). Bandwidth ini berguna

untuk mengubah frekuensi nada, berikut adalah formulasi penyesuaian nada:

𝑥𝑛𝑒𝑤 = 𝑥𝑜𝑙𝑑 + 𝑏𝑤 ∗ 𝜀

Keterangan:

𝑥𝑛𝑒𝑤 = variabel keputusan yang baru

𝑥𝑜𝑙𝑑 = variabel keputusan yang lama

𝑏𝑤 = bandwidth

𝜀 = nilai random antara [-1,1]

Parameter yang berhubungan dengan bw adalah PAR. Untuk PAR yang

bernilai rendah bw yang sempit dapat menyebabkan proses konvergensi lambat

dikarenakan keterbatasan eksplorasi pada ruang pencarian yang besar.

Sebaliknya, jika PAR yang tinggi dan bw yang lebar dapat menyebabkan

solusi-solusi yang ada terlalu menyebar dari potensi maksimal. Sehingga,

biasanya digunakan PAR = 0.1 − 0.5.

4) Inisialisasi Harmony Memory

Pada bagian ini dibangkitkan vektor solusi secara random. Vektor solusi

pada Algoritma HS merepresentasikan nilai prioritas aktivitas proyek.

Kemudian pada setiap iterasi dilakukan pembaruan sesuai dengan mekanisme

Algoritma HS. Vektor solusi dituliskan sebagai berikut

𝑋𝑖 = [𝑥1𝑖 𝑥2

𝑖 … 𝑥𝑁−1𝑖 𝑥𝑁

𝑖 ].

Keterangan:

𝑋𝑖=vektor solusi

𝑖=indeks vektor solusi

𝑥𝑁𝑖 =nilai prioritas aktivitas

𝑁=banyak aktivitas

Vektor solusi dibangkitkan sebanyak HMS. Bila vektor solusi telah

dibangkitkan maka akan terbentuk matriks harmony memory seperti pada

penjelasan sebelumnya.

5) Membangkitkan Vektor Solusi yang Baru

Membangkitkan vektor solusi yang baru dilakukan melalui 3 cara, yaitu:

Apabila bilangan random 𝑟1 yang dibangkitkan lebih besar dari HMCR

maka akan dibangkitkan variabel keputusan yang baru secara random

𝑉𝐾𝐵 𝑖 = 𝑟𝑎𝑛𝑑[𝐵𝐵 𝑖 ,𝐵𝐴 𝑖 ] Dengan 𝑉𝐾𝐵(𝑖) = variabel keputusan baru

𝐵𝐵(𝑖) = irisan batas bawah variabel keputusan 𝑖 𝐵𝐴(𝑖) = irisan batas atas variabel keputusan 𝑖

Apabila bilangan random 𝑟1 yang dibangkitkan lebih kecil dari HMCR dan

pembangkitan bilangan random 𝑟2 lebih besar dari PAR, maka variabel

keputusan 𝑖 akan diambil dari HM.

𝐷1 = 𝑖𝑛𝑡 1 + 𝐻𝑀𝑆 − 1 𝑟𝑎𝑛𝑑 𝐷2 = 𝐻𝑀 𝐷1, 𝑖 𝑉𝐾𝐵 𝑖 = 𝐷2

Dengan 𝐷1 = nilai yang menyatakan pemilihan lokasi pada HM secara

random dan 𝑖𝑛𝑡 adalah bilangan bulat.

𝐷2 = nilai variabel keputusan yang diambil dari HM.

Apabila bilangan random 𝑟1 yang dibangkitkan lebih kecil dari HMCR dan

pembangkitan bilangan random 𝑟2 lebih kecil dari PAR, maka variabel

keputusan 𝑖 akan diambil dari HM.

𝐷3 = 𝐷2 + 𝑏𝑤 ∗ 𝜀

𝑉𝐾𝐵 𝑖 = 𝐷3

Dengan 𝐷3 = nilai variabel keputusan setelah dilakukan penyesuaian.

𝑏𝑤 = bandwidth

𝜀 = bilangan random dengan interval [−1,1] Kemudian dilakuakn pengecekan batas dari variabel keputusan. Apabila

𝐷3 < 𝐵𝐵, maka 𝐷3 = 𝐵𝐵. Apabila 𝐷3 > 𝐵𝐴, maka 𝐷3 = 𝐵𝐴.

Ketiga cara tersebut dilakukan mulai 𝑖 = 1 hingga 𝑁.

6) Meng-update Harmony Memory

Langkah-langkah pemilihan HM sebagai berikut:

Melakukan proses penjadwalan untuk vektor solusi baru yang telah dibentuk

pada langkah 5.

Menghitung durasi proyek dari solusi baru.

Jika vektor solusi baru lebih baik daripada vektor solusi yang terjelek pada

HM, maka vektor solusi terjelek akan dikeluarkan dan digantikan oleh

vektor solusi yang baru.

7) Mengecek Kriteria Pemberhentian

Apabila kriteria pemberhentian telah tercapai maka proses penghitungan

selesai, jika belum tercapai maka kembali ke langkah 5.

Contoh: Akan dilakukan pengerjakan proyek dengan jumlah sumberdaya dalam

bahasan kali ini diartikan sebagai pekerja yang tersedia sebanyak 5 orang dan

aktivitas-aktivitas sebagai berikut:

Tabel 1 Daftar Aktivitas Proyek

Aktivitas Durasi Sumberdaya

(Pekerja)

Aktivitas

Pendahulu

A 2 1 -

B 3 3 1

C 4 2 1

D 3 3 2

E 5 2 4

F 7 3 3

G 4 3 6

H 3 2 5,7

Dari data yang terdapat pada tabel 1, akan dibuat salah satu model penjadwalan

dalam diagram precedence seperti di bawah ini

Gambar 5 Bentuk Penjadwalan 1 Proyek

Pada interval [5,7] sumberdaya yang diperlukan melebihi sumberdaya

yang tersedia, sehingga proses pengerjaan tidak dapat dilanjutkan. Dengan

menggunakan Algoritma CPM yang telah dimodifikasi (Seda;2009) sehingga

dapat menyelesaikan masalah RCPSP, diperoleh lama pengerjaan proyek selama

23 hari dan penjadwalan baru dengan diagram precedence sebagai berikut:

Gambar 6 Bentuk Penjadwalan Baru Proyek

Akan dicari solusi lain dengan menggunakan Algoritma Harmony Search.

Iterasi 1:

Langkah 1

Mencari solusi minimum untuk permasalahan penjadwalan proyek 1

dengan fungsi tujuan 𝐦𝐢𝐧 𝑓 𝑥 𝑥 = {𝑥𝑖 ≤ 𝑥𝑖 ≤ 𝑥𝑖 , 𝑖 = 1,2,… ,𝑁 }}, jumlah

pekerja yang tersedia adalah 5 orang selama proses pengerjaan.

Langkah 2

Data Resouce-Constrained Project Scheduling Problem yang dibutuhkan

untuk mencari solusi minimum dapat diperoleh dari tabel 1.

Langkah 3

Akan dipilih secara random parameter untuk Algoritma HS dengan

menggunakan Ms Excel, diperoleh:

HMS dipilih antara [1,3], terpilih HMS = 3

HMCR dipilih antara [0.5,0.93], terpilih HMCR = 0,7

PAR dipilih antara [0.1,0.5], terpilih PAR= 0,3

bw (Bandwidth) = 10

Kriteria pemberhentian dipilih 2 iterasi. Solusi baru dipilih dari durasi pengerjaan

proyek terkecil atau terpendek.

Langkah 4

Dibangkitkan vektor solusi sebanyak HMS, dengan vektor solusi pertama

mengambil solusi dari Algoritma CPM

Dengan vektor solusi pertama 𝑋1 = [0 2 5 5.5 9 9 16 20]. Dibangkitkan vektor solusi kedua 𝑋2 = [0 2.5 2 6 16 9 16.5 21] dengan lama

pengerjaan 24 hari.

Dibangkitkan vektor solusi ketiga 𝑋3 = [0 2.5 2 6 10 9 16 20] dengan lama

pengerjaan 23 hari.

Langkah 5

Mencari vektor solusi baru 𝑋′ dari Harmony Memory berikut

𝐻𝑀 = 0 2 5 5.5 9 9 16 20

0 2.5 2 6 16 9 16.5 210 2.5 2 6 10 9 16 20

Dicari vektor solusi baru sesuai langkah-langkah Algoritma Harmony Search

untuk RCPSP sehingga pada iterasi 1 diperoleh vektor solusi baru 𝑋′ = 0 2 2 5 9 9 16 20 dengan durasi pengerjaan proyek selama 23 hari. Dengan

bentuk penjadwalan seperti Gambar 7

Gambar 7 Bentuk Penjadwalan Solusi Iterasi 1 Proyek 1

Langkah 6

Solusi ini lebih baik dari vektor solusi 𝑋2 pada HM yang membutuhkan waktu

24 hari, sehingga vektor solusi baru 𝑋′ menggantikan vektor solusi 𝑋2. Jadi

Harmony Memory yang baru adalah

𝐻𝑀 = 0 2 5 5.5 9 9 16 200 2 2 5 9 9 16 20

0 2.5 2 6 10 9 16 20

Langkah 7

Karena kriteria pemberhentian belum terpenuhi, maka ulangi langkah 5

dengan HM yang baru.

Iterasi 2:

Iterasi 2 dilakukan dengan cara mengulangi langkah 5 dengan parameter

yang tetap seperti iterasi 1. Diperoleh vektor solusi baru

𝑋′ = 0 2 2 5 8 8.7 15 19 yang mempunyai durasi selama 22 hari. Karena

kriteria pemberhentian telah terpenuhi, maka iterasi selesai. Sehingga diperoleh

solusi pengerjaan proyek dengan waktu selama 22 hari.

5. Analisa

Pada contoh di atas solusi dari Algoritma HS lebih minimum

dibandingkan menggunakan CPM. Karena pada Algoritma HS solusi

dibangkitkan secara random dari gabungan solusi-solusi pada Harmony Memory

yang telah memenuhi syarat dari RCPSP termasuk solusi dari perhitungan dengan

CPM, sedangkan pada CPM solusi diperoleh dari penjadwalan proyek biasa yang

belum ditentukan batas sumberdaya yang tersedia dan menggunakan dasar earliest

start dan lastest finish. Pada Algoritma HS terdapat beberapa iterasi yang telah

ditentukan pada kriteria pemberhentian. Untuk contoh di atas ditetapkan dua

iterasi sebagai kriteria pemberhentian, pada iterasi pertama diperoleh vektor solusi

dengan lama pengerjaan proyek selama 23 hari, vektor solusi ini menggantikan

vektor solusi pada HM karena solusi lebih baik. Solusi inilah yang mengakibatkan

Algoritma HS dapat membangkitkan solusi yang lebih minimum pada iterasi

kedua.

6. Kesimpulan

Untuk menyelesaikan Resouce-Constrained Project Scheduling Problem

dengan menggunakan Algoritma Harmony Search harus dilakukan tujuh langkah

berikut: inisialisasi masalah, memasukan data RCPSP, inisialisasi parameter

Algoritma HS, Inisialisasi harmony memory, membangkitkan vektor solusi baru,

Meng-update harmony memory, mengecek criteria pemberhentian.

Pada langkah inisialisasi harmony memory vektor solusi dibangkitkan dari

solusi dari perhitungan dengan menggunakan CPM dan vektor solusi yang lain

dibangkitkan secara random dengan memenuhi syarat RCPSP yaitu precedence

constraints dan resource constraints. Vektor-vektor solusi tersebut digabungkan

sebanyak 𝑁 kolom dengan 𝑁 adalah banyak aktivitas pada proyek dan baris

sebanyak HMS yang berguna untuk langkah berikutnya yaitu membangkitkan

vektor solusi baru. Variabel keputusan untuk membangkitkan vector solusi baru

ini diperoleh dari iterasi-iterasi hingga memenuhi kriteria pemberhentian.

Jika dibandingkan dengan Algoritma Critical Path Method, solusi

Algoritma Harmony Search tidak selalu merupakan solusi terbaik, karena

pencarian solusi dilakukan secara random, sehingga solusi yang diperoleh sangat

beragam. Pencarian solusi RCPSP menggunakan Algoritma HS lebih memerlukan

waktu yang lebih lama daripada pencarian soslusi menggunakan Algoritma CPM.

Namun, lama waktu yang diperlukan untuk mendapatkan solusi menggunakan

Algoritma HS tergantung pada kriteria pemberhentian yang dipilih.

7. Saran

Dalam skripsi ini, masih disajikan RCPSP dengan hanya dibatasi satu tipe

sumberdaya dan suatu aktivitas tidak dapat dihentikan pada tengah-tengah

pengerjaan. Permasalahan suatu proyek pada kenyataannya memiliki keterbatasan

sumberdaya yang beragam tipe dan suatu kegiatan dapat dihentikan jika ada suatu

kegiatan yang lebih penting diselesaikan terlebih dahulu. Hal ini dapat dijadikan

bahan penelitian yang lebih lanjut sehingga solusi yang diperoleh mendekati

permasalahan pada dunia proyek sesungguhnya.

Daftar Pustaka

Aldous, J.M dan Wilson, R.J. 1990. Graph and Applications, an Introductory

Approach. London: Springer-Verlag.

Badri, Sofwan. 1987. Dasar-dasar Network Planning. Jakarta : Rineka Cipta.

Chakraborty, P., Ghosh, G., Das, S., Jain, D. 2009. An Improve Harmony Search

Algorithm with Differential Mutation Operator. Fundamental Informaticae

Vol. 95 No. 1-26.(online) (http://academic-work.googlecode.com/).

Diakses 2 Februari 2013.

Csebfalvi, Gyorgy. Csebfalvi, Aniko. Szendroi, Etelka. 2008. A Harmony Search

Metaheuristic for the Resource-Constrained Project Scheduling Problem

and its Multi-mode Version. Dari notice university of pecs PhD student

goverment. (Online) (http://www.gphd.ktk.pte.hu/), diakses pada 2

Februari 2013.

Goncalves, Jose F., Mendes, Jorge J., Resende, Mauricio. 2004. A Genetic

Algorithm for the Resource Constrained Multi-Project Scheduling

Problem. AT&T Labs Techinal Report TD-668LM4.

Hadwan, M., Ayob, M., Sabar, N.R., Qu, Roug. 2013.A harmony search

algorithm for nurse rostering problem. Information Science. (online)

(http://www.elsevier.com/locate/ins), diakses 26 Februari 2013.

Kolisch, R., dan Sprecher, A. 1996. PSPLIB-A Project Scheduling Problem

Library. European Journal of Operational Research. (http://www.om-

db.wi.tum.de/psplbi), diakses 26 Februari 2013.

Lee, Kang Seok dan Geem, Zong Woo. 2004. A new meta-heuristic algorithm for

continuous engineering optimization: harmony search theory dan practice.

Dari full-text scientific database offering journal, articles, dan book

chapter (online) (http://www.sciencedirect.com/) diakses pada 6

September 2012.

Petterson, J.H., Sowinski, R., Talbot, F.B., Weglarz, J. 1989. An algorithm for a

general class of precedence and resource constrained scheduling problem.

Dari The European digital mathematics library

(https://www.eudml.org/doc), diakses 2 Februari 2013.

Sastrohadiwiryo, B. Siswanto. 2007. Pengantar Manajemen. Jakarta : Bumi

Aksara.

Seda, M., Matousek, R., Osmera, P., Pivonka, P., Sandera, C. 2009. A Flexible

Heuristic Algorithm for Resource-Constrained Project Scheduling. Dari

full-text scientific database offering journal, articles, dan book chapter

(online) (http://www.sciencedirect.com/) diakses pada 6 September 2012.

Setiawan, Achmad dan Santosa, Budi. 2010. Penerapan Algoritma Harmony

Search dalam Penyelesaian Resource-Constrained Project Scheduling

Problem. Dari digital repository (online) (http://www.digilib.its.ac.id/),

diakses 5 September 2012.

Soeharto, Iman. 1990. Manajemen Proyek dari Konseptual sampai Operasional.

Jakarta : Erlangga.

Stanimirovic, Ivan., Petrkovic, Marko., Stanimirovis, Predrag., dan Ciric,

Miroslav. 2009. Heurustic Algorithm For Single Resource Constrained

Project Scheduling Problem Based On The Dynamic Programming.

Yugoslav Journal of Operation Research Vol. 19, No. 2.

(http://core.kmi.open.ac.uk/), diakses 2 Februari 2013.

Tchomte, Sylverin K., Gourgand, M., Quilliot, A. 2007. Solving Resource-

Constrained Project Scheduling Problem with Partical Swarm

Optimization. Regular Papers.