IMPLEMENTASI ALGORITMA GENETIKA UNTUK OPTIMASI PENJADWALAN PERKULIAHAN DI D-3 KOMSI SEKOLAH VOKASI UGM

NINDYA ANGGITA AZIS, Faizah, S.Kom., M.Kom.

2017 | Skripsi | S1 ILMU KOMPUTER

Proses penjadwalan perkuliahan merupakan agenda penting yang dilakukan secara rutin setiap semester. Hal yang sama juga terjadi di lingkungan Program Studi D-3 KOMSI Sekolah Vokasi UGM. Selama ini, jadwal yang digunakan, dihasilkan melalui 2 tahap, yaitu proses penjadwalan perkuliahan, kemudian proses penempatan asisten praktikum. Dengan adanya 2 tahap proses penjadwalan yang dilakukan, tentunya memberi pengaruh terhadap lamanya waktu yang dibutuhkan untuk menghasilkan jadwal. Salah satu cara untuk mereduksi waktu yang dibutuhkan untuk melakukan penjadwalan perkuliahan dan penempatan asisten adalah dengan menggabungkannya dalam satu tahapan algoritma genetika. Dengan penyajian data (solusi) yang tepat, algoritma genetika diharapkan mampu mengarahkan sistem untukmenghasilkan solusi, dalam waktu yang lebih singkat. Penelitian ini diawali dengan membuat desain solusi yang direpresentasikan dalam model representasi bilangan bulat. Kemudian menerapkan metode seleksi ranking (Rank-based selection) untuk memilih pasangan parent. Langkah selanjutnya adalah menerapkan metode multiple-cut-point crossover, random mutation dan metode Steady State dengan Elitism pada tahapan seleksi survivor. Tahap-tahap algoritma genetika ini akan diulang hingga kondisi dari stopping criteria terpenuhi. Penelitian ini mengembangkan sebuah program berbasis desktop yang mampu melakukan proses penjadwalan perkuliahan dan penempatan asisten dalam satu tahapan algoritma genetika. Selain ditemukannya solusi optimal, lamanya waktu pengujian juga menjadi objek perhatian pada penelitian ini. Keberhasilan proses pencarian solusi bergantung terhadap parameter yang digunakan. Berikut ini adalah parameter optimal, atau parameter yang dapat menghasilkan solusi dalam waktu yang lebih singkat : Pc = 70%, Pm = 9,5%, dan popsize = 20 individu. Setelah melakukan pengujian tahap kedua, dapat diketahui bahwa 2 pengujian yang dapat menghasilkan jadwal yang memenuhi 5 tingkat prioritas batasan, adalah pengujian dengan menggunakan 50 kelas dan 100 kelas. Sementara pengujian dengan menggunakan 152 kelas, program mampu menghasilkan jadwal yang memenuhi 4 tingkat prioritas batasan.

Course scheduling is an important task to do when a new semester begins in an educational institution, like Program Studi D-3 KOMSI Sekolah Vokasi UGM. Course scheduling used in Program Studi D-3 KOMSI Sekolah Vokasi UGM has been generated through two phases, scheduling of course only and scheduling of asisstant of practical work class. Two phases of course scheduling which have been doing, absolutely took more times. One of alternatives that can be implemented to reduce times took by doing those two phases is merging them into one phase. An optimum solution can be found briefly with the suitable data representation. The process of genetic algorithms in this study will be started by designing a solution in an integer-representation-model. Then, the following steps are implementing Rank-based selection to gather parents will be crossovered, implementing multiple-cut-point crossover, implementing random mutation method, and implementing Steady State with Elitism as an approach in survivor selection phase. Those genetic algorithm steps will be executed repeatedly until the conditioned of stopping criteria is fulfilled. This study develops a desktop program which is able to perform scheduling of course only and scheduling of asisstant of practical work class in a single run. Not only the ability to find the best solution which become the main focus in this study, but also the running time needed too. The success of solution-searching-process, depends on the value of parameter given. The combination of parameter which is able to get the best result in a fewer running time are : Pc = 70%, Pm = 9,5%, and popsize = 20 chromosomes. After doing the second phase experiment, it can be concluded that two experiment which successfully found a schedule fulfilling 5 level priority of constraints are the experiment using 50 classes and the experiment using 100 classes. While another experiment only successfully found a solution fulfilling 4 level of constraints defined.

Kata Kunci : penjadwalan, kuliah, asisten, optimasi, algoritma genetika, course scheduling, lecture, asisstant, optimization, genetic algorithm