OPTIMASI MULTI-OBJECTIVE UNTUK DISTRIBUSI BEBAN KERJA PEGAWAI MENGGUNAKAN NSGA-II AHMAD KHAIDIR 2210206725 TELEMATIKA CIO - TEKNIK ELEKTRO - ITS
LATAR BELAKANG • Perbaikan kinerja aparatur pemerintah • Optimasi distribusi beban kerja • Optimasi multi-objective : distribusi berdasarkan kompetensi; dan keadilan kerja pegawai • Penelitian sebelumnya : 1. Optimasi penugasan hanya berdasarkan kompetensi ataupun integrasi optimasi biaya (NSGA-II); 2. Eiselt dkk (2008), optimasi beban kerja dan kepuasan kerja kedalam sebuah fungsi aggregat (AOF).
PERUMUSAN MASALAH Analisa apakah NSGA-II memberikan solusi optimal untuk distribusi beban kerja berdasarkan keberhasilan dan keadilan kerja PNS di lingkungan BKD Kota Medan ?
TUJUAN dan MANFAAT • Analisa solusi yang dihasilkan optimasi multi-objective distribusi beban kerja menggunakan NSGA-II terhadap PNS BKD Kota Medan ; • Mengatasi kejenuhan akibat pekerjaan monoton dan ketidakhadiran akibat tidak diberi pekerjaan; • Bermanfaat menciptakan lingkungan kerja yang kondusif sehingga meningkatkan kinerja PNS BKD Kota Medan.
METODA PENELITIAN Pemodelan Sistem
Ukur Optimasi Sistem Lama
Terapkan Optimasi AOF
Terapkan Optimasi MultiObjective : NSGA-II
Ukur Optimasi AOF
Ukur Optimasi MultiObjective : NSGA-II
Perbandingan Pengukuran Kesimpulan
PEMODELAN SISTEM • Modifikasi Model Eiselt dkk (2008) • Dinotasikan :
Pekerjaan i = 1 .. m, Pegawai j = 1 .. n , Keahlian k= 1 .. p
• Didefinisikan parameter : rik = tingkat keahlian k yang dibutuhkan pekerjaan i ajk ti fi xij
= tingkat keahlian k yang dimiliki pegawai j = durasi waktu yang dibutuhkan untuk menyelesaikan pekerjaan i = frekuensi pekerjaan i = jumlah pekerjaan i yang diselesaikan pegawai j
• Solusi :
solusi x dapat dinyatakan sebagai himpunan parameter xij x = {x11, x12, …, x1n, x21, …, x2n, …, xi1, …, xmn}
PEMODELAN SISTEM • Agar pekerjaan dapat diselesaikan dengan baik dan efisien dengan tingkat kebosanan rendah maka diminamilisasi ratarata relatif dari tingkat keahlian pegawai yang tidak terpakai • Rata-rata relatif dari tingkat keahlian pegawai yang tidak terpakai : • Fungsi Tujuan ke-1 : Min
PEMODELAN SISTEM • Untuk meningkatkan keadilan kerja, maka diminimalisasi deviasi beban kerja pegawai dengan beban kerja rata-rata • Beban kerja pegawai j : • Beban kerja rata-rata
:
• Deviasi beban kerja
:
• Sehingga, Fungsi Tujuan ke-2 : Min
TAHAPAN NSGA-II • Inisialisasi Populasi xij diberi nilai bilangan bulat positif secara acak, namun tetap memenuhi pembatas :
(Jumlah total pekerjaan i dikerjakan oleh seluruh pegawai harus sama dengan frekuensi pekerjaan)
TAHAPAN NSGA-II • Non Dominated Sort • Populasi diurutkan berdasarkan non domination menggunakan algoritma Fast Non-dominated Sorting (Deb,2002) • Populasi terbagi atas beberapa tingkatan front yang berbeda. • Solusi pada front pertama mendominasi solusi front berikutnya.
TAHAPAN NSGA-II • Non Dominated Sort Definisi dominasi : Sebuah solusi x(1) mendominasi solusi yang lain x(2), jika : • Solusi x(1) tidak lebih buruk dari x(2) untuk semua fungsi tujuan • Solusi x(1) lebih baik dari x(2) minimal pada satu fungsi tujuan.
TAHAPAN NSGA-II • Crowding Distance • Pembanding antara dua individu dalam front yang sama, agar solusi yang dihasilkan dapat mewakili keseluruhan solusi pareto-optimal • Perhitungan keliling cuboid yang dibentuk oleh solusi terdekat (Deb,2002)
TAHAPAN NSGA-II • Seleksi Tournament Selection dengan Seleksi individu (Deb,2002) berdasarkan : • Peringkat non-domination (front) • Jika berasal dari front yang sama, pilih individu dengan crowding distance (Ƒi) yang lebih besar.
TAHAPAN NSGA-II • Operator Genetika a. Simulated Binary Crossover (SBX) (Deb & Agrawal,1995; Deb & Kumar, 1995) 1. Tentukan bilangan acak u antara 0 s.d 1 2. Cari nilai b :
dengan hc = index distribusi crossover
TAHAPAN NSGA-II • Operator Genetika a. Simulated Binary Crossover (SBX) (sambungan) 3. Hasil crossover :
dimana ci,k adalah variabel ke-k dari anak ke-i, dan pi,k adalah parent yang dipilih
TAHAPAN NSGA-II • Operator Genetika b. Polynomial Mutation (Deb, 2001) 1. Tentukan bilangan acak r antara 0 s.d 1 2. Cari nilai d :
dengan h m = index distribusi mutasi
TAHAPAN NSGA-II • Operator Genetika b. Polynomial Mutation (sambungan) 3. Hasil mutasi : dimana ck adalah variabel ke-k dari anak mutasi, dan pk adalah parent yang dipilih
TAHAPAN NSGA-II • Rekombinasi Gabungan populasi induk dengan hasil crossover dan mutasi kemudian dipilih dengan Non-Dominated Sort dan Crowding Distance untuk mendapatkan populasi generasi berikutnya.
DIAGRAM ALIR NSGA-II Mulai Seleksi Inisialisasi Populasi
Crossover
Non Dominated Sort Mutasi Crowding Distance Rekombinasi
Selesai
Ya
Kondisi berhenti terpenuhi ?
Tidak
HASIL PENELITIAN • Data penelitian • Diperoleh melalui kuesioner yang diisi pejabat eselon IV pada Badan Kepegawaian Daerah (BKD) Kota Medan. • BKD Kota Medan terdiri dari 32 orang PNS jabatan staf dengan 51 jenis pekerjaan yang membutuhkan 29 jenis keahlian.
HASIL PENELITIAN • Optimasi AOF • Kedua fungsi tujuan digabung menjadi fungsi tujuan baru dengan operator penjumlahan (+) dan bobot a antara 0..1 • Fungsi Tujuan Baru : Min • Diselesaikan menggunakan algoritma genetika, dengan operator genetika SBX dan Polynomial Mutation • Dilakukan penelitian untuk menentukan nilai a antara 0.1, 0.5 dan 0.9 yang memberikan nilai Z terbaik
HASIL PENELITIAN • Optimasi AOF (sambungan) • Untuk setiap nilai a dilakukan 5 kali percobaan untuk menghitung nilai Z • Menggunakan Uji Statistik (Uji Kolmogorov Smirnov dan Uji Shapiro Wilk untuk Uji Normalitas, Uji Levene untuk Uji Homogenitas, Uji ANOVA atau Uji Welch atau Uji Kruskal Wallis untuk membandingkan nilai rata-rata Z) • Hasil Uji Statistik menunjukkan bahwa nilai rata-rata Z untuk ketiga nilai a adalah sama
HASIL PENELITIAN • Optimasi AOF (sambungan) • Perubahan populasi setiap generasi :
Populasi Awal
Populasi Generasi Ke-5
Populasi Generasi Ke-10
Populasi Generasi Ke-15
HASIL PENELITIAN • Optimasi NSGA-II • Dilakukan penelitian untuk menentukan jumlah generasi terkecil untuk mendapatkan solusi pareto-optimal • Membandingkan kualitas beberapa kumpulan solusi paretooptimal menggunakan indikator hypervolume • Indikator hypervolume diestimasi dengan pendekatan Monte Carlo (While dkk, 2006), yaitu : • Menormalisasi nilai semua fungsi tujuan antara 0 dan 1 • Membangkitkan sekumpulan nilai acak • Menguji setiap nilai acak tersebut apakah didominasi salah solusi pareto-optimal
HASIL PENELITIAN • Optimasi NSGA-II (sambungan) • Menggunakan Uji Statistik (Uji Kolmogorov Smirnov dan Uji Shapiro Wilk untuk Uji Normalitas, Uji Levene untuk Uji Homogenitas, Uji ANOVA atau Uji Welch atau Uji Kruskal Wallis untuk membandingkan estimasi rata-rata Hypervolume) • Hasil Uji Statistik menunjukkan bahwa estimasi rata-rata nilai hypervolume terbagi atas 2 kelompok generasi yang sama, yaitu kelompok 1 : generasi 100 dan 1000, sedangkan kelompok 2 : generasi 3000, 5000, 7000 dan 10000
HASIL PENELITIAN • Optimasi NSGA-II (sambungan) • Perubahan populasi (generasi = 3000):
Populasi Awal
Populasi Generasi ke-1500
Populasi Generasi ke-300
Populasi Generasi ke-2250
Populasi Generasi ke-750
Populasi Generasi ke-3000
KESIMPULAN • Model matematis pendistribusian beban kerja dimodifikasi dari model Eiselt (2008). • Solusi pareto-optimal yang terbaik telah didapatkan pada populasi generasi ke-3000. • Solusi pareto-optimal NSGA-II lebih baik dengan mendominasi 100 % solusi dari sistem yang lama dan solusi yang dihasilkan Algoritma Genetika dengan Aggregat of Function (AOF).
SARAN • Penelitian terhadap parameter yang mempengaruhi solusi NSGA-II seperti Probabilitas Crossover, Pobabilitas Mutasi, Index Distribusi Crossover dan Index Distribusi Mutasi. • Penelitian terhadap operator genetika lain yang dapat diterapkan pada permasalahan pendistribusian beban kerja PNS dengan NSGA-II. • Pengembangan lebih lanjut untuk permasalahan pendistribusian beban kerja lebih kompleks, seperti pendistribusian beban kerja PNS mempertimbangkan perubahan kompetensi dan pembelajaran.
