Jurnal Pengembangan Teknologi Informasi dan Ilmu Komputer e-issn: X

Jurnal Pengembangan Teknologi Informasi dan Ilmu Komputer Vol. 2, No. 3, Maret 2018, hlm. 958-967

e-ISSN: 2548-964X http://j-ptiik.ub.ac.id

Optimasi Penjadwalan Asisten Praktikum pada Laboratorium Pembelajaran Menggunakan Algoritme Genetika (Studi Kasus : Fakultas Ilmu Komputer Universitas Brawijaya) Nadia Natasa Tresia Sitorus1, Imam Cholissodin2 , Budi Darma Setiawan3 Program Studi Teknik Informatika, Fakultas Ilmu Komputer, Universitas Brawijaya Email: [email protected], [email protected], [email protected] Abstrak Penjadwalan merupakan hal yang penting untuk disusun secara matang demi berlangsungnya suatu kegiatan dengan baik. Penjadwalan yang baik dan efektif akan membuat kegiatan dapat berjalan dan terorganisir dengan baik. Praktikum merupakan kegiatan rutin yang dilakukan untuk penerapan materi yang telah diterima mahasiswa. Praktikum dapat berlangsung dengan baik jika jadwal mengajar asisten praktikum tidak bertabrakan dengan jadwal kuliah maupun kegiatan lainnya asisten praktikum. Algoritme genetika merupakan salah satu algoritme yang dapat menyelesaikan penjadwalan mengajar asisten praktikum melalui proses komputasi. Data dalam melakukan penelitian adalah data jadwal praktikum, data asisten praktikum dan jadwal kesediaan asisten. Kode asisten praktikum direpresentasikan pada kromosom dengan menggunakan metode permutasi. Urutan gen pada kromosom merepresentasikan kode jadwal praktikum. Metode crossover yang diterapkan adalah one-cut-point, dengan metode mutasi menggunakan reciprocal exchange, serta metode seleksi elitsm. Hasil pengujian mendapatkan nilai parameter algoritme genetika yang optimal yaitu dengan ukuran populasi 5000, generasi sebanyak 500, dengan nilai cr dan mr adalah 0,5 dan 0,5. Hasil keluaran sistem merupakan jadwal mengajar asisten praktikum laboratorium pembelajaran. Kata kunci: penjadwalan, algoritme genetika, asisten, praktikum Abstract Scheduling is an important thing to be prepared carefully for the sake of an activity doing well. Good and effective scheduling will make the activities work and be well organized. Practicum is a routine activity for the application of materials that have been accepted by students. Practicum can work well if the teaching schedule of the practicum assistant does not collide with the lecture schedule or their other activities. Genetic algorithm is one of algorithm that can complete the teaching schedule of practicum assistant through computation process. The data in conducting the research is the data from practicum schedule, practicum assistant and the schedule of the assistant's willingness. The code of the practicum assistant is represented on the chromosome using the permutation method. The sequence of genes on the chromosomes represents the code of the practicum schedule. The crossover method applied is one-cut-point, with mutation method using reciprocal exchange, and elitsm selection method. The test result obtained optimal genetic algorithm parameter with total population 5000, generation 500, with cr and mr value is 0,5 and 0,5. The output of the system is the teaching schedule of the laboratory teaching assistant. Keywords: scheduling, genetic algorithm, assistant, practicum membuat suatu kegiatan dapat berjalan dan terorganisir dengan baik. Ada beberapa aspek penting dan perlu diperhatikan dalam menyusun penjadwalan. Aspek-aspek ini merupakan parameter yang harus diperhatikan dan akan berpengaruh terhadap keberhasilan pelaksanaan kegiatan.

1. PENDAHULUAN Berdasarkan KBBI, penjadwalan merupakan proses mengatur urutan kegiatan dengan waktu yang detail. Penjadwalan merupakan hal yang penting untuk disusun secara matang demi berlangsungnya suatu kegiatan dengan baik. Penjadwalan yang baik dan efektif akan Fakultas Ilmu Komputer Universitas Brawijaya

958

Jurnal Pengembangan Teknologi Informasi dan Ilmu Komputer

Salah satu penjadwalan yaitu penjadwalan pendidikan merupakan penjadwalan yang dilaksanakan pada lembaga pendidikan atau universitas (Jha, 2014). Pada instansi pendidikan seperti universitas, penjadwalan akan selalu dilakukan setiap semester maupun untuk beberapa kegiatan lainnya. Sebagai contoh pengaturan jadwal mengajar dosen, penjadwalan mata kuliah, penjadwalan praktikum, penjadwalan dilaksanakannya ujian, maupun penjadwalan pengawas ujian, dan lain sebagainya. Praktikum merupakan kegiatan rutin yang dilakukan untuk penerapan materi yang telah diterima mahasiswa. Praktikum dapat berlangsung dengan baik jika jadwal mengajar asisten praktikum tidak bertabrakan dengan jadwal kuliah maupun kegiatan lainnya asisten praktikum. Agar kegiatan dapat berjalan secara optimal, maka diperlukan penjadwalan yang efektif untuk setiap sumber daya manusia (Eradipa, Rahman, dan Tantrika 2014). Dalam hal ini, sumber daya manusianya adalah asisten praktikum. Pada laboratorium pembelajaran FILKOM UB, penjadwalan mengajar asisten praktikum disusun berdasarkan jadwal praktikum yang telah ditentukan oleh akademik dengan mempertimbangkan jadwal kegiatan lain asisten secara manual. Proses penjadwalan secara manual terkadang menyebabkan adanya jadwal kegiatan yang saling bertabrakan. Sehingga asisten tidak dapat melakukan kegiatan mengajar dengan maksimal. Ada beberapa algoritme yang dapat digunakan dalam penyelesaian masalah penjadwalan. Salah satunya adalah penelitian oleh Wahyuningsih (2015) yang menggunakan algoritme max min ant system untuk menyusun penjadwalan akademik. Pada penelitian tersebut penulis berfokus untuk menghindari terjadinya bentrokan jadwal dan tempat yang sama pada proses belajar mengajar. Selain itu, algoritme lain yang sering diterapkan untuk menyelesaikan masalah penjadwalan antara lain, simulated annealing, vertex graph coloring, dan algoritme genetika (Zulfa, 2015). Algoritme yang paling sering diterapkan dalam permasalahan penjadwalan adalah algoritme genetika. Oleh karena itu, penulis menggunakan algoritme genetika untuk menyelesaikan permasalahan penjadwalan asisten praktikum. Pada skripsi ini, penjadwalan disusun berdasarkan jadwal praktikum yang telah ditentukan fakultas dan jadwal pribadi tiap asisten. Penelitian ini menggunakan algoritme Fakultas Ilmu Komputer, Universitas Brawijaya

959

genetika karena dapat diterapkan dalam masalah-masalah yang kompleks dalam berbagai bidang (Mahmudy, 2015). Algoritme genetika diterapkan berdasarkan ilmu genetika, sehingga menggunakan banyak istilah-istilah genetika. Algoritme genetika dapat mengerjakan permasalahan secara menyeluruh dengan hasil yang seoptimal mungkin (Fachrurrazi, 2014). Tujuan dari penelitian ini adalah untuk merancang dan mengimplementasikan algoritme genetika untuk menetukan jadwal mengajar asisten praktikum serta mengetahui kualitas solusi yang dihasilkan dengan menerapkan algoritme genetika terhadap penjadwalan asisten praktikum. Melalui penelitian ini diharapkan dapat meningkatkan keefektifitasan dan keefisienan penyusunan jadwal mengajar asisten praktikum. 2. TINJAUAN PUSTAKA 2.1. Penjadwalan Penjadwalan menurut Husen (2009) yakni, mengalokasikan waktu yang tersedia untuk melakukan setiap pekerjaan untuk menyelesaikan suatu kegiatan sehingga tercapai solusi yang optimal berdasakan batasan-batasan yang ada (dalam Devi, 2015). Penjadwalan meliputi alokasi sarana kegiatan dan mengenai hal yang diramalkan dalam waktu suatu kegiatan (Rifai dalam Zulfa, 2015). Penjadwalan yang baik seharusnya memiliki aturan-aturan penjadwalan yang cukup kuat dan memiliki tujuan yang realistis. Sehingga dapat fleksibel untuk memecahkan masalah yang tidak diprediksi sebelumnya dan memperbolehkan adanya suatu perencanaan ulang. Menurut Narasimhan dkk. (1985), suatu penjadwalan dapat dikategorikan baik jika jadwal yang dihasilkan sederhana, mudah dimengerti dan dapat dilaksanakan oleh siapa pun yang menggunakannya. 2.2. Penjadwalan Asisten Penjadwalan asisten praktikum mencakup masalah penempatan asisten pada tiap periode waktu mengajar. Penempatan atau pengalokasian asisten ini dijadwalkan berdasarkan jadwal asisten dan jadwal pelaksanaan praktikum sesuai dengan jadwal yang diberikan akademik dengan beberapa ketentuan yang disepakati antar asisten maupun dengan dosen pengampu mata kuliah.


Batasan-batasan atau constraint pada penjadwalan digunakan sebagai tolak ukur kualitas jadwal yang dihasilkan, sehingga dapat memberikan jadwal yang optimal (Zaini dalam Zulfa, 2013). Jenis constraint ini yakni, hard constraint dan soft constraint. 1. Hard constraint merupakan batasan yang wajib dilakukan dalam penjadwalan. Jika batasan ini dilanggar, maka jadwal tidak layak untuk diimplementasikan (Qoiriah dalam Seisarrina, 2016). 2. Soft constraint merupakan batasan maupun ketentuan yang tidak wajib dilakukan atau boleh dilanggar. Akan tetapi untuk mencapai kualitas jadwal yang lebih maksimal, maka diharapkan untuk meminimalkan pelanggaran terhadap batasan ini (Perzina dan Remik, 2013). 2.3. Algoritme Genetika Algoritme genetika merupakan algoritme yang sangat populer serta sering digunakan untuk menyelesaikan masalah yang kompleks (Mahmudy dalam Zulfa, 2015).

960

tiap planggaran constraint. Rumus menghitung nilai fitness ditunjukkan pada Persamaan ((1). 𝐹𝑖𝑡𝑛𝑒𝑠𝑠 =

1 1+

𝑘 Σ𝑖=1 𝑤𝑖

. 𝑛𝑖

(1)

Keterangan: k = jumlah constraint i = indeks constraint bobot nilai penalti pada constraint wi = ke-i jumlah penalti pada tiap costraint ni = yang dilanggar 3. PERANCANGAN Diagram alir pada sistem dalam penelitian ini ditunjukkan pada Gambar 1. Mulai Generasi, popSize, cr, mr, data jadwal praktikum, data asisten, data kesediaan asisten Inisialisasi Kromosom For i=0 to generasi-1 Reproduksi

2.3.1. Proses Algoritme Genetika Pada algoritme genetika terdapat beberapa tahapan untuk mencari solusi terbaik sebagai berikut ini (Mahmudy, 2015). 1. Inisialisasi Pada tahap ini dilakukan pembangkitan populasi awal secara random.. 2. Reproduksi Tahapan ini bertujuan untuk membentuk individu baru dengan menggunakan operator crossover dan mutasi. 3. Evaluasi Tahap ini digunakan untuk menghitung nilai fitness tiap-tiap kromosom.. 4. Seleksi Tahap ini dilakukan untuk memilih individu yang layak untuk dipertahankan ke generasi berikutnya. 2.3.2. Fungsi Fitness Fitness pada algoritme genetika, digunakan untuk menentukan sifat reproduksi pada individu dan bertindak sebagai tolak ukur suatu individu semakin baik (Jha, 2014). Jika nilai fitness kromosom semakin besar, maka semakin besar peluang kromosom tersebut terpilih sebagai solusi (Mahmudy, 2015). Pada penelitian ini, nilai fitness dihitung berdasarkan nilai penalti yang diberikan pada Fakultas Ilmu Komputer, Universitas Brawijaya

Evaluasi Fitness Seleksi

i Solusi terbaik Selesai

Gambar 1 Diagram Alir Sistem Penjadwalan Asisten Praktikum

3.1. Formulasi Permasalahan Penelitian ini dilakukan untuk mencoba menyelesaikan permasalahan penjadwalan asisten praktikum Laboratorium Pembelajaran pada FILKOM UB. Perhitungan manual menggunakan sampel berupa data jadwal praktikum 2 kelompok mata kuliah dengan total sebanyak 13 jadwal. Masing-masing kelompok mata kuliah terdiri dari 9 dan 4 jadwal. Banyak jadwal akan merepresentasikan panjang kromosom yang diinisialisasikan dengan nilai bilangan berupa kode asisten. Parameter yang digunakan dalam perhitungan manual sebagai berikut yaitu, jumlah generasi sebanyak 2 generasi, 5 populasi, dengan cr dan mr 0,3 dan 0,2. Pada Tabel 1 ditunjukkan beberapa aturan penjadwalan asisten praktikum Laboratorium


Ilmu

Komputer

Tabel 1 Aturan dan Bobot Penalti Penjadwalan Asisten Praktikum Laboratorium Pembelajaran Fakultas Ilmu Komputer No.

Jadwal mengajar asisten tidak bentrok dengan jadwal kegiatan lain dan sesuai dengan jadwal kesediaan asisten. Setiap asisten minimal mengampu 1 kelas pratikum. Pemerataan jadwal mengajar disesuaikan dengan banyak kelas yang diampu dan jumlah asisten yang bersedia.

2.

3.

Tabel 3 Parent pada Proses Crossover Gen ke-i

Bobot Penalti

Constraint

1.

dihasilkan sejumlah hasil perkalian nilai popsize dengan crossover rate. Offspring= 5 x 0,3 = 1,5 ≈ 2.

1 2

0,005

0,005

0,001

Kelompok Mata Kuliah Sistem Informasi

Pembelajaran Fakultas Universitas Brawijaya.

961

3 4 5 6 7

3.2. Inisialisasi Kromosom Mata Kuliah Sistem Digital

8

Kromosom direpresentasikan seperti pada Gambar 2. Urutan gen menunjukkan kode jadwal kelas praktikum yang diampu asisten.

9 10 11 12 13

Gambar 2 Representasi Kromosom

Tabel 2 menunjukkan individu awal pada perhitungan manual.

1 2 3 4 5 6 7 8 9 10 11 12 13

P1 7 8 9 10 11 12 10 11 12 7 8 9 7 12 8 11 9 9 21 22 23 24 25 26 27 28

P2 1 2 3 4 5 6 1 4 2 5 3 6 2 5 1 6 3 3 13 14 15 16 17 18 19 20

9 10 11 12 7 8 9 11 7 10 8 12 9 12 7 11 8 8 19 20 23 24 15 16 27 28

P3 5 6 1 3 2 4 2 6 3 4 1 5 1 6 3 4 2 2 17 18 21 22 13 14 25 26

11 12 7 8 9 10 7 11 9 12 8 10 10 11 7 12 8 8 24 26 25 27 21 23 20 22

P4 2 6 3 5 1 4 2 3 1 6 3 5 2 6 4 5 1 1 17 19 18 28 14 16 13 15

7 9 8 11 10 12 7 12 8 10 9 11 11 12 9 10 7 7 23 25 21 26 22 28 24 27

7 8 9 10 11 12 10 11 12 7 8 9 7 12 8 11 9 9 21 22 23 24 25 26 27 28

P5 1 3 2 5 3 6 1 5 3 5 1 4 2 4 4 6 2 2 16 17 13 19 18 20 14 15

8 12 7 11 9 10 10 12 8 11 7 9 7 9 11 12 8 8 15 16 19 20 23 24 27 28

2 3 4 5 6 7 8 9 10 11 12 13

3.3. Crossover Pada proses crossover, offspring yang Fakultas Ilmu Komputer, Universitas Brawijaya

1 2 3 4 5 6 1 4 2 5 3 6 2 5 1 6 3 3 13 14 15 16 17 18 19 20

9 10 11 12 7 8 9 11 7 10 8 12 9 12 7 11 8 8 19 20 23 24 15 16 27 28

5 6 1 3 2 4 2 6 3 4 1 5 1 6 3 4 2 2 17 18 21 22 13 14 25 26

Cut Point 1

Cut Point 2

Tabel 4 Offspring pada Proses Crossover

1 3 4 2 6 1 5 4 5 1 6 2 3 3 6 2 5 1 1 13 14 17 18 21 22 25 26

P2

Tabel 4 menunjukkan hasil dari proses crossover dengan metode one cut point. Gen ke-i

Tabel 2 Individu Awal Gen ke-i

P1

C1 7 8 9 10 11 12 10 11 12 7 8 12 9 12 7 11 8 8 19 20 23 24 15 16 27 28

C2 1 2 3 4 5 6 1 4 2 5 1 5 1 6 3 4 2 2 17 18 21 22 13 14 25 26

9 10 11 12 7 8 9 11 7 10 8 9 7 12 8 11 9 9 21 22 23 24 25 26 27 28

5 6 1 3 2 4 2 6 3 4 3 6 2 5 1 6 3 3 13 14 15 16 17 18 19 20


3.4. Mutasi Pada proses mutasi offspring yang dihasilkan sejumlah hasil nilai popsize dengan mutation rate. Offspring= 5 x 0,2 = 1. Tabel 5 Parent pada Proses Mutasi Gen ke-i 1

Kelompok Mata Kuliah Sistem Informasi

2 3 4 5 6 7 8

Mata Kuliah Sistem Digital

9 10 11 12 13

P3 11 12 7 8 9 10 7 11 9 12 8 10 10 11 7 12 8 8 24 26 25 27 21 23 20 22

2 6 3 5 1 4 2 3 1 6 3 5 2 6 4 5 1 1 17 19 18 28 14 16 13 15

Titik Tukar 1

masing individu dan memberikan nilai penalti sesuai dengan bobot penalti yang telah dijelaskan pada Tabel 1. Tahap 1 Cek Constraint 1 Bagian yang diarsir merupakan bagian asisten yang jadwal mengajar dengan jadwal kesediaannya terjadi bentrok. Tabel 7 Hasil Cek Constraint 1 pada Individu 1 Gen ke-i 1 2

Titik Tukar 2

3 4 5 6

Titik Tukar 1

7 8

Titik Tukar 2

9 10

Tabel 6 menunjukkan hasil dari proses mutasi dengan reciprocal exchange mutation method.

11 12 13

Tabel 6 Offspring pada Proses Mutasi Gen ke-i 1 2 3 4 5 6 7 8 9 10 11 12 13

962

P1 7 8 9 10 11 12 10 11 12 7 8 9 7 12 8 11 9 9 21 22 23 24 25 26 27 28

1 2 3 4 5 6 1 4 2 5 3 6 2 5 1 6 3 3 13 14 15 16 17 18 19 20

P3 8 10 7 8 9 10 7 11 9 12 11 12 10 11 7 12 8 8 24 26 20 22 21 23 25 27

3 5 3 5 1 4 2 3 1 6 2 6 2 6 4 5 1 1 17 19 13 15 14 16 18 28

3.5. Evaluasi Fitness Pada proses evaluasi fitness, dilakukan pemeriksaan pelanggaran aturan dari asingFakultas Ilmu Komputer, Universitas Brawijaya

Tahap 2 Cek Constraint 2 Bagian yang diarsir merupakan asisten yang melakukan pelanggaran pada constraint 2 yaitu asisten yang tidak mendapatkan jadwal mengajar atau tidak mengampu kelas praktikum sama sekali. Tabel 8 Hasil Cek Constraint 2 pada Child 1 Kode Asisten 1 2 3 4 ... 12 13 ... 17 18 19 20 ... 27 28

Jumlah Kelas Diampu 4 3 2 3 ... 4 2 ... 0 0 0 0 ... 1 1

Tahap 3 Cek Constraint 3

Angka ini menunjukkan banyak kelas yang diampu oleh asisten berdasarkan kemunculannya dalam individu.


Bagian yang diarsir merupakan asisten yang melakukan pelanggaran pada constraint 3 yaitu asisten yang tidak memenuhi pemerataan pembagian jadwal mengajar. Pada praktikum kelompok mata kuliah Sistem Informasi, masing-masing asisten harus mendapatkan 3 kelas untuk diampu dan pada praktikum mata kuliah Sistem Digital, masing-masing asisten harus mendapatkan 1 kelas untuk diampu,

963

Individu Individu 5 Individu 1 Child 3 Individu 3 Individu 2 Child 1 Individu 4 Child 2

Nilai Fitness 0.952380952 0.947867299 0.943396226 0.938967136 0.930232558 0.926784059 0.909090909 0.900090009

Rank 1 2 3 4 5 6 7 8

Tabel 9 Hasil Cek Constraint 3 pada Child 1 Kode Asisten 1 2 3 4 5 6 7 8 9 10 11 12 ... 17 18 19 20 ... 27 28

Jumlah Kelas Diampu 4 3 2 3 4 2 3 3 2 3 3 4 ... 0 0 0 0 ... 1 1

4. IMPLEMENTASI Sistem mengimplementasikan dengan 4 bagian halaman yaitu bagian untuk menampilkan data jadwal praktikum, untuk menampilkan data asisten praktikum, bagian untuk menampilkan proses algoritma genetika, dan untuk menampilkan jadwal hasil sistem. 4.1. Antarmuka Halaman Data Jadwal Implementasi halaman load data jadwal praktikum bertujuan untuk menampilkan data jadwal praktikum semester ganjil T.A. 2016/2017.

Tahap Perhitungan Fitness Setelah melakukan pengecekan constraint, maka dilakukan perhitungan fitness masing-masing individu dengan menggunakan Persamaan (1). Berikut merupakan contoh perhitungan fitness pada pada individu 1. 𝐹𝑖𝑡𝑛𝑒𝑠𝑠 1 1 + (11(0,005) + 0(0,005) + 0(0,001)) 1 𝐹𝑖𝑡𝑛𝑒𝑠𝑠 = 1 + 0,055 𝐹𝑖𝑡𝑛𝑒𝑠𝑠 = 0,947867299 =

3.4. Seleksi Pada proses seleksi digunakan metode seleksi elitsm, dengan menggabungkan populasi awal dengan offspring. Lalu, mengurutkan nilai fitness-nya dari yang terbesar hingga yang terkecil. Kemudian, memilih sebanyak popSize untuk diloloskan untuk diproses pada generasi berikutnya. Tabel 10 Hasil Seleksi Fakultas Ilmu Komputer, Universitas Brawijaya

Gambar 3 Halaman Data Jadwal

4.2. Antarmuka Halaman Data Asisten Implementasi halaman load data asistem praktikum bertujuan untuk menampilkan data asisten praktikum semester ganjil T.A. 2016/2017.


964

Gambar 6 Halaman Hasil Jadwal Mengajar Asisten

Pada pengujian ukuran populasi digunakan ukuran populasi 500 sampai 5000 dengan kelipatan 500 sebanyak 50 generasi dengan nilai cr dan mr yaitu 0,9 dan 0,1.

5000

4500

4000

3500

3000

2500

2000

0,748 0,746 0,744 0,742 0,740 0,738 0,736 0,734 0,732

500

Rata-rata fitness

Implementasi halaman proses algoritme genetika bertujuan untuk menampilkan generasi dan nilai fitness terbaik dari proses dan memasukkan parameter algoritme genetika.

5.1. Pengujian Ukuran Populasi

1500

4.3. Antarmuka Halaman Proses Algoritme Genetika

5. PENGUJIAN DAN ANALISIS

1000

Gambar 4 Halaman Data Asisten

Populasi Gambar 7 Pengujian Ukuran Populasi

Gambar 5 Halaman Proses Algoritme Genetika

4.4. Antarmuka Halaman Hasil Jadwal Mengajar Asisten Implementasi halaman hasil bertujuan untuk menampilkan jadwal yang merupakan solusi terbaik dari proses algoritme genetika.

Berdasarkan Gambar 7 ditunjukkan peningkatan yang signifikan dari populasi 500 hingga 1500. Akan tetapi, terjadi penurunan rata-rata nilai fitness pada generasi 2000. Pada generasi 4000 hingga 5000 rata-rata nilai fitness yang dihasilkan mulai stabil. Peningkatan ratarata nilai fitness terjadi dengan ukuran populasi yang semakin besar pula. Hal ini disebabkan karena semakin besar ukuran populasi maka semakin banyak variasi gen yang dihasilkan, sehingga memungkinan untuk mendapatkan nilai fitness baru yang lebih baik. 5.2. Pengujian Jumlah Generasi Pada pengujian jumlah generasi digunakan kelipatan 50 sampai 500 generasi dengan ukuran populasi 5000, dan nilai cr dan mr bernilai 0,9

Fakultas Ilmu Komputer, Universitas Brawijaya


Rata-rata fitness

dan 0,1. 1,200 1,000 0,800 0,600 0,400

0,200 500

450

400

350

300

250

200

150

50

100

0,000

Generasi Gambar 8 Pengujian Jumlah Generasi

Berdasarkan Gambar 8 dapat dilihat bahwa terjadi peningkatan rata-rata nilai fitness yang signifikan dari generasi 50 hingga 250. Sementara itu peningkatan rata-rata nilai fitness setelah generasi 250 sudah konvergen dan stabil. Nilai popSize terbaik didapatkan pada generasi 500 dengan nilai fitness sebesar 0.973. Sehingga dapat disimpulkan semakin banyak generasi maka semakin baik rata-rata nilai fitness yang dihasilkan. Hal ini karena meningkatnya kemungkinan untuk mendapatkan nilai fitness yang lebih optimum pada generasi berikutnya. 5.3. Pengujian Nilai Cr dan Mr

Rata-rata fitness

Pengujian nilai cr dan mr dilakukan untuk mendapatkan nilai cr dan mr yang menghasilkan solusi teroptimal. Penelitian ini menggunakan pengujian nilai cr dan mr dengan rentang nilai 0,1 sampai 0,9. Parameter populasi dan generasi yang digunakan diambil dari hasil terbaik pengujian ukuran populasi dan jumlah generasi sebanyak 5000 dan 500 generasi.

terus terjadi, namun tidak lebih besar dari ratarata nilai fitness pada kombinasi nilai cr= 0,5 dan mr= 0,5. Hal ini membuktikan bahwa jika nilai crossover rate terlalu rendah, maka akan level eksplorasi meningkat dan menghasilkan generasi yang tidak dapat belajar dari generasi sebelumnya dengan efektif (Mahmudy, 2015). Hasil pengujian ini juga membuktikan bahwa penurunan nilai mr dapat meningkatkan kinerja algoritma genetika dalam mengeksploitasi pencarian lokal untuk mendapatkan nilai fitness yang lebih baik. 5.4. Analisi Global Pengujian Sistem penjadwalan asisten praktikum menggunakan algoritme genetika dengan parameter optimal hasil pengujian yakni sebanyak 5000 populasi, 500 iterasi, cr bernilai 0,5 dan mr bernilai 0,5 menghasilkan nilai fitness sebesar 0,9737≈0,974. Jadwal yang dihasilkan sistem sudah mendekati optimum, akan tetapi terdapat beberapa pelanggaran terhadap aturan penjadwalan. Namun jadwal yang dihasilkan sistem dapat diterapkan karena tidak terjadinya pelanggaran terhadap aturan yang paling penting, aturan nomer 1 dimana tidak terjadinya bentrok kegiatan pribadi asisten dengan kegiatan mengajar. Tabel 11 menunjukkan detail pelanggaran aturan penjadwalan dari jadwal yang dihasilkan oleh sistem. Tabel 11 Detail Pelanggaran Aturan pada Hasil Sistem No. 1

1,000 0,950 0,900

2

0,850 0,800 0,750 0,9 0,8 0,7 0,6 0,5 0,4 0,3 0,2 0,1 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9

Mr dan Cr Gambar 9 Pengujian Nilai Cr dan Mr

Berdasarkan Gambar 9, terjadi peningkatan rata-rata nilai fitness yang signifikan pada pengujian dengan menggunakan cr=0,1 dan mr=0,9 hingga nilai cr=0,5 dan mr=0,5. Peningkatan dan penurunan rata-rata nilai fitness Fakultas Ilmu Komputer, Universitas Brawijaya

965

3

Aturan Penjadwalan Asisten Praktikum Jadwal mengajar asisten tidak bentrok dengan jadwal kegiatan lain dan sesuai dengan jadwal kesediaan asisten. Setiap asisten minimal mengampu 1 kelas pratikum pada kelompok mata kuliah asisten tersebut. Pemerataan jadwal mengajar disesuaikan dengan banyak kelas yang diampu dan jumlah asisten yang bersedia. Total Pelanggaran Nilai Fitness

Jumlah Pelanggaran

0

1

17

18 0,9737

Berdasarkan jadwal manual dari 2 mata kuliah yang dibuat secara manual, terjadi beberapa pelanggaran, yakni pada aturan 1 dan 3. Jadwal yang dibuat secara manual memiliki


nilai fitness sebesar 0,973. Pelanggaran penjadwalan asisten praktikum manual pada 2 kelompok mata kuliah secara detail ditunjukkan pada Tabel 12. Tabel 12 Detail Pelanggaran Aturan pada Jadwal Manual No. 1

2

3

Aturan Penjadwalan Asisten Praktikum Jadwal mengajar asisten tidak bentrok dengan jadwal kegiatan lain dan sesuai dengan jadwal kesediaan asisten. Setiap asisten minimal mengampu 1 kelas pratikum pada kelompok mata kuliah asisten tersebut. Pemerataan jadwal mengajar disesuaikan dengan banyak kelas yang diampu dan jumlah asisten yang bersedia. Total Pelanggaran Nilai Fitness

Jumlah Pelanggaran

5

0

2

7 0,973

Ditinjau dari nilai fitness yang dihasilkan, maka jadwal manual dan hasil sistem memiliki nilai fitness yang sama-sama mendekati optimum. Akan tetapi, jika ditinjau dari waktu yang dibutuhkan untuk menyusun jadwal maka penjadwalan dengan sistem membutuhkan waktu lebih singkat yakni ± 20 sampai 30 menit. Sementara penjadwalan manual membutuhkan waktu sekitar 2-3 hari. Kesulitan mendapatkan nilai fitness yang optimum disebabkan oleh hal-hal berikut ini. Pertama, data yang dijadwalkan tergolong besar yakni 159 slot jadwal dengan 229 asisten dalam 10 mata kuliah. Kedua, nilai kromosom awal yang dibangkitkan bernilai acak yang tidak menjamin semua individu memiliki susunan kromosom yang baik. 6. KESIMPULAN Beberapa kesimpulan yang didapatkan dari pengujian dan analisis pada sistem penjadwalan asisten praktikum laboratorim pembelajaran menggunakan algoritme genetika adalah sebagai berikut. 1. Algoritme genetika dapat diterapkan pada penjadwalan asisten praktikum laboratorium pembelajaran. Implementasi algoritme genetika melalui tahap inisialisasi kromosom, reproduksi, evaluasi dan seleksi. Representasi kromosom yang diterapkan Fakultas Ilmu Komputer, Universitas Brawijaya

966

yakni dengan merempresentasikan kode asisten pada tiap slot jadwal praktikum. Solusi yang memiliki nilai fitness tertinggi merupakan solusi yang optimal dengan jumlah pelanggaran aturan penjadwalan yang paling sedikit. 2. Berdasarkan pengujian parameter algoritme genetika yang telah dilakukan maka diperoleh parameter terbaik adalah sebanyak 5000 populasi, 500 generasi, nilai cr= 0,5 dan mr= 0,5. Jadwal yang dihasilkan sistem sudah mendekati optimum, karena masih terjadi beberapa pelanggaran terhadap aturan penjadwalan. 7. DAFTAR PUSTAKA Devi, Okky C., 2015. Penerapan Algoritma Genetika Untuk Penjadwalan Asisten Praktikum. S1. Universitas Brawijaya. Eradipa, A.Y., Rahman, Arif, Tantrika, C.F.M., 2014. Penjadwalan Tenaga Kerja dengan Menggunakan Metode Goal Programming. Jurnal Rekayasa dan Manajemen Sistem Industri, Malang. Universitas Brawijaya. 2(6). pp. 12141225. Fachrurrazi, Sayed, 2013. Penerapan Algoritma Genetika Dalam Optimasi Pendistribusian Pupuk Di PT Pupuk Iskandar Muda Aceh Utara. JT-FTI, Aceh. Universitas Malikussaleh Reuleut. 2(1). pp. 47-66. Jha, S. K., 2014. Exam Timetabling Problem Using Genetic Algorithm. IJRET : International Journal of Research in Engineering and Technology, 03(05), pp. 649-654. Mahmudy, W. F., 2015. Dasar-Dasar Algoritma Evolusi. Malang: Program Teknologi Informasi dan Ilmu Komputer (PTIIK) Universitas Brawijaya. Mahmudy, W. F., Marian, R. M. & Luong, L. H. S., 2012. Solving Part Type Selection and Loading Problem Flexible Manufacturing System Using Real Code Genetic Algorithms - Part I : Modeling. World Academy of Science, Engineering and Technology, Volume 69, pp. 773-779. Narasimhan, S.L., McLeavey, D.W., Billington, P.J., 1985. Production Planning and Inventory Control, 2 ed. New Jersey: Prentice- Hall International, Inc.


Perzina, R. & Ramik, J., 2013. Self-Learning Genetic Algorithm for a Timetabling Problem with Fuzzy Constraints. International Journal of Innovative Computing, Information and Control, 9(11), pp. 4565-4582. Rifai, Ulisna A. 2011. Pengembangan Aplikasi Penjadwalan Kegiatan dengan Menggunakan Algoritma Genetika (Studi Kasus: Humas Kementrian Agama RI). Skripsi Fakultas Sains dan Teknologi 7 Universitas Islam Negeri Syarif Hidayatullah. Jakarta. Seisarinna, Maulidya L., 2016. Penjadwalan Pengawas Ujian Semester Menggunakan Algoritma Genetika (Studi Kasus: Fakultas Ilmu Komputer Universitas Brawijaya). S1. Universitas Brawijaya.. Suyanto, 2014. Artificial Intelegence Searching, Reasoning, Planning, dan Learning. 2nd ed. Bandung: Informatika Bandung. Wahyuningsih, Delpiah, 2015. Rancangan Sistem Penjadwalan Akademik Menggunakan Algoritma Max Min Ant System. JEPIN, Pangkalpinang. STMIK Atma Luhur Pangkalpinang. 1(2). pp. 72-75. Zulfa, Indana, 2015. Optimasi Jadwal Mengajar Asisten Laboratorium Menggunakan Algoritma Genetika. S1. Universitas Brawijaya.

Fakultas Ilmu Komputer, Universitas Brawijaya

967

Jurnal Pengembangan Teknologi Informasi dan Ilmu Komputer e-issn: X

Recommend Documents