BAB 4 HASIL DAN PEMBAHASAN
4.1. Hasil Implementasi Pembahasan untuk penerapan algoritma harmony search yang dilakukan dalam penjadwalan asisten ini, akan dijabarkan dengan ulasan hasil dari inputan parameterparameter yang berbeda. Untuk hasil penjadwalan, dapat dipastikan berbeda dari percobaan yang pertama hingga yang terakhir walaupun parameter yang diinput sama, hal ini karena adanya random value yang digunakan dalam algoritma. Untuk hasil-hasil yang dijabarkan di sini, adalah hasil-hasil selama penulis melakukan percobaan. Dari hasil inisialisasi matriks penampung yang dibaca dari file excel, ada beberapa parameter tetap yang perlu diketahui: 1.
81.
adalah jumlah asisten pengajar untuk dialokasikan.
2.
26.
adalah jumlah ruangan praktikum yang tersedia untuk alokasi transaksi
praktikum. 3.
35.
adalah jumlah periode yang digunakan dalam transaksi praktikum.
Untuk tiga tetapan di atas, akan digunakan secara konstan dalam melakukan algoritma penjadwalan ini. Dalam melakukan implementasi untuk pengujian algoritma ini pada program, akan dilakukan secara bertahap dan terbagi menjadi tiga langkah utama:
1.
Konversi raw data ke matriks penampung Langkah ini akan mengubah data-data mentah (raw data) yang didapatkan dari tim Resources M anagement dan Database Administrator menjadi data olahan dasar, berupa matriks biner 0,1 dan bipolar
1,1 .
Contoh data mentah untuk data kualifikasi yang akan diolah datanya dilampirkan pada lampiran. Berikut sample yang diambil untuk keterangan:
G ambar 1 Contoh raw data kualif ikasi
Keterangan: a.
Kolom “A” mewakili asisten pengajar.
b.
Setiap kolom mewakili kode-kode matakuliah yang dilayani oleh Software Laboratory Center.
c.
Nilai “Q” menandakan asisten memiliki kualifikasi untuk matakuliah pada kolom yang diwakilinya.
d.
Nilai selain “Q” menandakan asisten tidak memiliki kualifikasi untuk matakuliah pada kolom yang diwakilinya. Pada contoh nilai tersebut adalah “PT”.
Hasil konversi dari data di atas, akan dituliskan dalam file “qualification_t.xlsx”, sebagai contoh:
G ambar 2 Hasil konversi data kualifikasi
Keterangan: a.
Setiap kolom dan baris akan terproyeksi sama seperti data mentah.
b.
Nilai hasil konversi akan berbentuk biner, nilai 1 akan mewakili status “Q”, sedangkan 0 untuk lainnya.
Contoh data mentah untuk data asisten pengajar yang akan diolah datanya dilampirkan pada lampiran. Berikut sample yang diambil untuk keterangan:
G ambar 3 Contoh raw data asisten pengajar
Keterangan: a.
Data yang dibutuhkan ada pada kolom “INISIAL” dan “SHIFT”.
b.
Untuk nilai pada kolom “SHIFT” terdiri dari pagi dan malam.
Hasil konversi dari data di atas, akan dituliskan dalam file “resources_t.xlsx”, sebagai contoh:
G ambar 4 Hasil konversi data asisten pengajar
Keterangan: a.
Kolom “A” mewakili asisten pengajar.
b.
Setiap kolom mewakili periode praktikum yang ada pada transaksi.
c.
Nilai -1 mengindikasikan pada periode tersebut, asisten yang diwakili kolom “A” tidak bisa dialokasikan untuk mengajar, karena asisten yang bersangkutan berada di luar shift kerja.
d.
Nilai 0 mengindikasikan pada periode tersebut, asisten yang diwakili kolom “A” available untuk dialokasikan mengajar. Bila pada tahapan selanjutnya ada alokasi yang terjadi, maka nilai 0 akan berubah menjadi 1 atau 0,5 sesuai dengan bobot matakuliah yang dialokasikan.
Contoh data mentah untuk data transaksi yang akan diolah datanya dilampirkan pada lampiran. Berikut sample yang diambil untuk keterangan:
G ambar 5 Contoh raw data transaksi praktikum
Keterangan: a.
Data dikonversi menjadi matriks dua dimensi dengan Kode M tk sebagai nilai.
b.
Nilai pada kolom ruang, akan menjadi baris. Nilai pada kolom hari dan shift akan menjadi kolom, pada hasil konversi.
Hasil konversi dari data di atas, akan dituliskan dalam file “transaction_t.xlsx”, dan disimpan sebagai matriks
,
, sebagai contoh:
G ambar 6 Hasil konversi data transaksi praktikum
Keterangan: a.
Setiap baris mewakili ruangan praktikum.
b.
Setiap kolom mewakili periode praktikum.
c.
Setiap matakuliah yang diwakili pada nilai matriks, akan terkorespondensi dari data asal.
2.
Inisialisasi HM Pada langkah ini, data-data hasil konversi yang tersimpan dalam masingmasing excel ([nama_file]_t.xlsx) akan digunakan untuk diisikan pada harmoni memori, yang merupakan matriks cerminan matriks
,
. Untuk matriks
,
,
sendiri merupakan
yang juga hasil konversi data transaksi praktikum, namun
dengan nilai berupa asisten pengajar. Untuk mengisi matriks
, dilakukan
,
perulangan sesuai dengan jumlah baris dan kolom pada matriks matakuliah pada matriks
,
,
. Nila i
digunakan sebagai referensi untuk mendapatkan
asisten yang memiliki kualifikasi matakuliah tersebut dan available pada shift sesuai dengan kolom pada matriks
,
. Contoh untuk matriks
,
dalam file
excel:
G ambar 7 Contoh matriks
Jumlah matriks
,
, pada file excel
yang dihasilkan akan sebanyak jumlah parameter HM S yang
akan dimasukkan dalam array multi-dimensi, dengan susunan array berupa array 3 dimensi [$HM S][$r][$p].
Bila matriks
,
sejumlah HM S sudah didapatkan, maka dilanjutkan untuk
mendapatkan nilai objektif untuk masing-masing HM . Untuk mewakili nilai objektif, dalam penerapan digunakan variabel tValues yang merupakan array 2 dimensi [$HM S][$penalty]. Untuk $penalty = 0, mewakili penalti untuk batasan C3. $penalty = 1, mewakili penalti untuk batasan C2. $penalty = 2, mewakili penalti untuk batasan C1. Dari hasil tValues yang didapatkan, nilai objektif akan didapat dengan menjumlahkan nilai penalty yang ada untuk masing-masing HM S. ∑ $ 3.
,
1…
.
Improvisasi harmoni baru Untuk mendapatkan harmoni baru, dilakukan cara yang sama dalam melakukan inisialisasi disertai dengan kemungkinan kondisi pengisian dengan nilai pada harmoni memori yang sudah ada (HM CR), dan nilai neighbourhood pada harmoni memori yang sudah ada (PAR). Bagian yang penting dalam langkah ini adalah mengupdate data harmoni memori dan nilai objektif dari harmoni memori yang sudah ada dengan nilai objektif harmoni memori baru yang lebih baik. Bila hal ini dilakukan berulan g (dalam hal ini sesuai dengan parameter NI), maka akan ada kemungkinan terjadi perbaikan harmoni memori, maksimal sebanyak NI. Dari semua langkah yang dilakukan dalam menerapkan algoritma, nantinya akan
menghasilkan sebuah
dengan nilai objektif yang diharapkan (minimal). Hasil
akhir dari algoritma program yang digunakan dalam membantu penerapan algoritma akan dijabarkan dalam tiga bentuk matriks, matrik , , dan sebuah file excel.
, dan akan disimpan dalam
Berikut akan ditampilkan hasil dari percobaan untuk penjadwalan asisten pengajar dengan menggunakan parameter-parameter HSA dan parameter permasalahan sebagai berikut: HM S = 5, M inimum Weight = 4,5, M aximum Weight = 5,5, Variation M ax = 5, HM CR = 90, PAR = 20, dan NI = 75. Sedikit tampilan hasil dalam file excel:
G ambar 8 Contoh matriks w hasil algoritma
G ambar 9 Contoh matriks t hasil algoritma
G ambar 10 Contoh matriks e hasil algoritma
4.2. Pembahasan 4.2.1
Perbandingan Hasil Implementasi Perbandingan hasil dari penjadwalan asistensi asisten pengajar secara manual
dengan penerapan atau implementasi algoritma harmony search bisa dilihat dalam bentuk tabel. Perbandingan ini dilakukan untuk mengetahui efektivitas dari parameter HM S terhadap nilai objektif, dengan asumsi parameter lain tetap. Kolom-kolom pada tabel mewakili nilai penalti yang didapat untuk masing-masing batasan, untuk penalti bobot asisten pengajar diwakili kolom C3, untuk penalti mengajar lebih dari dua shift dalam satu hari diwakili kolom C2, dan untuk penalti mengajar matakuliah lebih dari variasi yang ditentukan diwakili kolom C3. Data pada tabel diambil berdasarkan data terbaik dari masing-masing 10 kali percobaan:
Tabel 1 Perbandingan nilai objective dengan perbedaan parameter pada HMS
HMS
C3
C2
C1
Objective
5 7 10
50 54 51
27 28 27
14 8 10
91 90 88
Berdasarkan tabel 1, bisa dilihat bahwa parameter HM S tidak terlalu efektif untuk meminimalkan nilai objektif, dengan distribusi penalti yang relatif sama. Dari hasil tersebut untuk penalti pada bobot asisten pengajar yang diwakili C3, C2, dan C1 terlihat merata dan tidak mengalami banyak perubahan, meskipun terjadi perubahan pada jumlah memori harmoni yang digunakan dalam perbaikan harmoni. Nilai objektif yang didapat dengan meningkatkan jumlah memori harmoni pun tidak mengalami perubahan yang signifikan, dengan nilai objektif minimum yang didapatkan 90. Tabel 2 Perbandingan nilai objektif dengan perbedaan parameter pada HMCR
HMCR 80 85
C3 53 51
C2 29 27
C1 10 13
Objective 92 91
90
50
26
12
88
Berdasarkan tabel 2, bisa dilihat bahwa parameter HM CR yang besar memiliki kecenderungan untuk perbaikan yang lebih baik. Dari tabel, untuk nilai HM CR sebesar 85 mendapatkan hasil objektif sebesar 93, lebih besar dibandingkan dengan nilai HM CR 80. Sedangkan untuk nilai HM CR 90, terjadi penurunan yang signifikan, dengan nilai objektif menjadi 88. Hal ini membuat inkonsistensi pada peningkatan parameter HM CR, karena bergantungnya parameter HM CR pada harmoni memori yang sudah ada sebelumnya.
Tabel 3 Perbandingan nilai objektif dengan perbedaan parameter pada PAR
PAR 20
C3 47
C2 32
C1 13
Objective 92
25 30
50 50
31 29
10 10
91 89
Berdasarkan tabel 3, bisa dilihat bahwa parameter PAR yang besar memiliki kecenderungan untuk perbaikan yang lebih baik, dengan distribusi penalti yang relatif random. Dari tabel, untuk nilai PAR sebesar 20, terjadi penurunan nilai penalti untuk C3 menjadi 47, yang merupakan titik terendah penalti C3 dari semua percobaan yang dilakukan, namun penurunan ini tidak diimbangi dengan penurunan nilai objektif. Berkurangnya nilai C3 mengakibatkan meningkatnya nilai penalti pada C2, sehingga nilai objektif cenderung tidak berubah secara signifikan. Pada percobaan, untuk nilai parameter PAR sebesar 30, bisa menekan nilai objektif pada nilai 89. Tabel 4 Perbandingan nilai objektif dengan perbedaan parameter pada NI
NI
C3
C2
C1
Objective
50 75 100
51 57 51
31 25 29
12 10 9
94 92 89
Berdasarkan tabel 4, bisa dilihat bahwa nilai pada parameter NI yang besar memiliki kecenderungan untuk perbaikan yang lebih baik, dengan distribusi penalti yang relatif random. Untuk penambahan nilai pada NI, nilai objektif yang dihasilkan pun membaik, terbukti dengan adanya penurunan nilai objektif seiring dengan bertambahnya parameter NI. Untuk nilai NI yang besar, yang dalam percobaan ini adalah 100, akan memperbesar kemungkinan untuk mendapatkan hasil yang lebih optimal.
Keterangan parameter yang digunakan untuk 4 tabel yang dijabarkan di atas: a.
M in Weight = 4,5
b.
M ax Weight = 5,5
c.
Variation M ax = 5
d.
HM S = 10 (selain pada tabel 1)
e.
HM CR = 90 (selain pada tabel 2)
f.
PAR = 30 (selain pada tabel 3)
g.
NI = 100 (selain pada tabel 4) Dari 4 perbandingan di atas, bila diambil yang terbaik dan dibandingkan dengan
nilai objektif pada hasil penjadwalan manual, maka akan didapatkan tabel perbandingan yang mengukur keefektifan dari algoritma harmony search: Tabel 5 Perbandingan algoritma harmony search dan manual
Harmony Manual
C3 54 46
C2 26 1
C1 9 8
Objective 89 55
Pada tabel 5, digunakan parameter pada harmony search, HM S = 10, M in Weight = 4,5, M ax Weight = 5,5, Variation M ax = 5, HMCR = 90, PAR = 30, dan NI = 100, dan dilakukan selama 10 kali percobaan untuk mendapatkan nilai objektif yang terbaik. Dari tabel 5, dapat dilihat bahwa hasil untuk penjadwalan manual masih memiliki nilai objektif yang jauh lebih baik dibandingkan dengan menggunakan algoritma harmony search. Hal ini dikarenakan penjadwalan manual yang dihasilkan sudah diminimalisasi sebaik mungkin dan sudah digunakan pada praktikum semester genap
10/11, jadi nilai penalti yang didapat pastinya sudah minimal. Bila dibandingkan per parameter, untuk setiap pelanggaran pada batasan, digambarkan dalam diagaram:
Nilai Rata‐rata Penalti HMS 100 90 80 70 60 50 40 30 20 10 0
52
52
50
HMCR
PAR
NI
53
29
31
28
29 11
C1
C2
12
12
11
C3
Nilai Penalti
G ambar 11 Chart hasil perbandingan nilai rata-rata penalti per parameter
Dari diagaram di atas, bisa dilihat untuk setiap parameter yang diubah secara independen memiliki kecenderungan untuk menghasilkan nilai yang relatif sama pada setiap pelanggaran batasan. Perbandingan pada tabel-tabel di atas, belum disertai dengan dimensi waktu. Bila dimensi waktu diikutsertakan, maka algoritma harmony search akan secara mutlak mengalahkan waktu dari manual. Perkiraan untuk waktu proses manual kurang lebih selama 1 minggu hari kerja, sedangkan dengan melakukan implementasi algoritma harmony search bisa diselesaikan dalam waktu yang relatif singkat (kurang dari 15 menit). Oleh karena itu sebagai usulan solusi dari permasalahan ini, bisa menggunakan algoritma harmony search ini untuk membuat prototype penjadwalan, yang selanjutnya
bisa diperbaiki dan disesuaikan oleh tim Resources M anagement secara manual dengan melihat data yang direpresentasikan pada matriks-matriks excel hasil algoritma. 4.2.2 Kompleksitas Algoritma Dari hasil menjalankan algoritma optimasi harmony search, penulis mencoba menguraikan kapasitas dari algoritma tersebut dalam sebuah notasi kompleksitas algoritma. Berdasarkan pseudocode yang terlampir pada bab 3, bisa dilihat bahwa untuk melakukan inisialisasi harmoni memerlukan perulangan yang berdasarkan pada besarnya harmoni memori dan jumlah dari harmoni memori, dan untuk melakukan perbaikan pada harmoni, dilakukan perulangan sebanyak NI dengan melakukan perulangan di dalamnya untuk mendapatkan dan menghitung harmoni memori baru. Pada proses membaca data dari file excel sampai pada inisialisasi harmoni memori besar kompleksitasnya dinotasikan dengan
.
untuk jumlah asisten
pengajar dan untuk jumlah periode. Pada proses melakukan improvisasi harmoni baru sampai kondisi NI terpenuhi, besar kompleksitasnya dinotasikan dengan
.
untuk jumlah asisten
pengajar dan untuk jumlah periode. Kompleksitas algoritma secara keseluruhan dapat dihitung dengan membandingkan kedua proses di atas dengan cara:
Bisa disederhanakan dengan hanya membandingkan: |
cara
Karena untuk penelitian yang dilakukan penulis menggunakan nilai untuk kompleksitas algoritma ini adalah 81
35
2835. Sehingga kompleksitas algoritm:
, maka
. Dengan nilai 2835 .
Dengan kompleksitas yang diketahui, bisa dicermati bahwa ukuran jumlah asisten akan mempengaruhi besaran dari kompleksitas algoritma harmony search yang digunakan. Semakin besar nilai kompleksitas akan menandakan kecilnya efektivitas dari algoritma tersebut, dan akan mempengaruhi waktu proses algoritma.
