TEKNIK PENJADWALAN KULIAH MENGGUNAKAN METODE ALGORITMA GENETIKA
Oleh 1
Dian Sari Reski , Asrul Sani2, Norma Muhtar3
ABSTRACT Scheduling problem is one type of allocating resources problem that exist to time slots available. There is constraint filling to determine a scheduling the lecture becomes so complicated. This study aims to determine a scheduling the lecture using genetic algorithm methods. Genetic algorithm is algorithm form finding the optimal solution based on the mechanism of natural selection and natural genetic traits. To find a good solution, genetic algorithm will be looking for a combination of genes on a chromosome in order to provide the most superior individuals based on fitness function. The fitness value of individual is higher, it possible to survive and produce a descendant for an individual. On genetic algorithm processing happen of a variation caused by genetic operator or crossover and mutation. The result of this research after doing crossover process and mutation is good individual forming a schedule based on constraint determined. Key words: Scheduling the Lecture, Genetic Algorithm, Fitness Function. PENDAHULUAN Jadwal merupakan daftar kegiatan berdasarkan waktu, tempat dan pelaksana dari kegiatan tersebut. Jadwal harus bisa memenuhi beberapa hal yang disesuaikan dengan kebutuhan pelaksana dari kegiatan tersebut. Waktu pelaksanaan dari suatu kegiatan harus dibuat sedemikian rupa sehingga tidak ada lebih dari suatu kegiatan pada waktu yang bersamaan [1]. Pembuatan jadwal adalah sebuah masalah periodik yang selalu dihadapi oleh sekolah dan universitas. Dengan banyaknya faktor yang mempengaruhi penyusunan suatu jadwal seperti jumlah ruangan, daya tampung ruangan, dan slot waktu yang sedikit menjadikan penyusunan jadwal perkuliahan lebih rumit serta yang harus diperhatikan juga dari sisi dosen, yaitu beberapa kemungkinan dosen akan mengajar lebih dari satu matakuliah yang ada, sehingga harus ditemukan solusi yang terbaik untuk menyelesaikannya. Di samping faktor-faktor diatas, dalam penyusunan jadwal kuliah ini pun terdapat sangat banyak kemungkinan yang selayaknya dicoba untuk menemukan penjadwalan yang terbaik. Karena itu dibutuhkan metode yang dapat diterapkan untuk mengerjakan penjadwalan mata kuliah ini. Salah satu metode yang dapat digunakan untuk menyelesaikan permasalahan tersebut adalah dengan menggunakan algoritma. Salah satu algoritma yang akan digunakan yaitu algoritma genetika. Algoritma genetika cukup baik untuk digunakan dalam penjadwalan mata kuliah disebuah perguruan tinggi.
Untuk kasus yang kompleks suatu algoritma tidak selalu menghasilkan solusi yang optimal, namun setidaknya bisa diperoleh solusi yang cukup baik untuk kebutuhan tertentu tergantung kriteria yang telah ditentukan. Selain itu masalah penjadwalan juga sangat kompleks, tergantung dari kebutuhan individu dan institusi yang terkait. Sehingga untuk mengatasi masalah jadwal matakuliah ini, penulis menggunakan algoritma genetika sebagai salah satu metode dalam menyelesaikan masalah ini. Pada penelitian ini akan dibahas bagaimana menentukan penjadwalan kuliah menggunakan metode algoritma genetika. TINJAUAN PUSTAKA Penjadwalan Penjadwalan merupakan manajemen atau pengaturan waktu pada suatu kegiatan operasi berhubungan dengan pemanfaatan sumber daya seperti pengalokasian fasilitas, peralatan maupun tenaga kerja dengan memutuskan urutan pelaksanaan serta pemanfaatan sumber daya tersebut bagi kegiatan operasi. Penjadwalan yang baik akan memaksimalkan pemanfaatan setiap sumber daya yang ada dalam suatu kegiatan operasi, sehingga penjadwalan merupakan kegiatan yang penting dalam perencanaan dan pengendalian proses. Tahap perencanaan dan tahap implementasi dari kegiatan penjadwalan termasuk masalah manajemen waktu yang kompleks (Syarif dan Gunawan, 2013) [2].
Penjadwalan Kuliah Penjadwalan kuliah dapat diartikan sebagai suatu pekerjaan untuk mendistribusikan sejumlah aktivitas yang melibatkan dosen, mata kuliah, dan seterusnya, ke dalam satuan waktu (bisa termasuk ruangan) yang terbatas dengan batasan-batasan tertentu [3]. Banyak kendala yang dihadapi ketika membuat penjadwalan mata kuliah. Beberapa batasan yang ada dalam penjadwalan mata kuliah apabila tidak diperhitungkan dengan baik akan menyebabkan sulitnya melakukan penjadwalan yang tepat dan baik. Constraint atau batasan yang biasa digunakan dalam kebanyakan masalah penjadwalan biasanya dibagi menjadi dua yaitu hard constraints dan soft constraints. Hard constraints memiliki prioritas lebih tinggi dibanding soft constraint, dan akan menjadi pertimbangan utama untuk bisa dipenuhi. Kenyataannya, penjadwalan biasanya hanya akan mempertimbangkan sebagian atau keseluruhan hard constraints dari suatu masalah yang telah dipenuhi. Sedangkan soft constraints, merupakan constraint atau pertimbangan yang bisa dilaksanakan jika memungkinkan dan biasanya menjelaskan apa saja yang bisa dipertimbangkan disesuaikan dengan kebijakan universitas, atau berdasarkan pengalaman dari orang yang biasa melaksanakannya. Algoritma Genetika Algoritma genetika adalah algoritma yang memanfaatkan proses seleksi alamiah yang dikenal dengan proses evolusi. Dalam proses evolusi, individu secara terus-menerus mengalami perubahan gen untuk menyesuaikan dengan lingkungan hidupnya. Proses seleksi alamiah ini melibatkan perubahan gen yang terjadi pada individu melalui proses perkembangbiakan. Dalam algoritma genetika ini, proses perkembangbiakan merupakan proses dasar yang menjadi perhatian utama, dengan tujuan mendapatkan keturunan yang lebih baik. Ada dua hal penting yang harus dilakukan pada awal proses algoritma genetika. Pertama, pendefinisian atau pengkodean kromosom yang merupakan solusi yang masih berbentuk simbol. Kedua, penentuan fungsi fitness atau fungsi obyektif. Dua hal ini berperan penting dalam algoritma genetika untuk menyelesaikan suatu masalah [4]. Istilah dalam Algoritma Genetika Terdapat beberapa definisi penting dalam algoritma genetika yang perlu diperhatikan, yaitu : 1. Genotype (gen), merupakan sebuah nilai yang menyatakan satuan dasar yang membentuk suatu arti tertentu dalam satu kesatuan gen yang dinamakan kromosom. Gen mengkodekan informasi yang disimpan didalam kromosom.
2. 3.
4.
5. 6.
Allele, merupakan nilai dari gen. Individu atau kromosom, merupakan gabungan gen-gen yang membentuk nilai tertentu dan merupakan suatu alternatif solusi terhadap permasalahan yang akan diselesaikan. Populasi, merupakan sekumpulan individu yang akan diproses bersama dalam satu siklus proses evaluasi. Generasi, merupakan satu siklus proses evolusi atau satu iterasi di dalam algoritma genetika. Offspring, merupakan kromosom baru yang dihasilkan.
Komponen-Komponen dalam Algoritma Genetika Ada beberapa komponen dalam menggunakan algoritma genetika, yaitu : 1. Pengkodean dan Inisialisasi Populasi Awal 2. Fungsi Evaluasi (Fungsi Fitness) 3. Seleksi 4. Pindah Silang (Crossover) 5. Mutasi METODE PENELITIAN Waktu dan Tempat Penelitian Penelitian ini akan berlangsung selama tiga bulan yaitu bulan Januari sampai April 2016 bertempat di Laboratorium Komputasi Jurusan Matematika FMIPA Universitas Halu Oleo. Materi Penelitian Dalam penelitian ini dibahas mengenai menentukan penjadwalan kuliah menggunakan metode algoritma genetika. Prosedur Penelitian Metode yang diterapkan dalam penyelesaian ini adalah metode kepustakaan dan studi kasus dengan mengikut langkah-langkah sebagai berikut: 1. Melakukan penelusuran pustaka yang relevan dengan masalah. 2. Membuat asumsi penjadwalan kuliah untuk mengidentifikasi masalah, kendala, faktor penentu, dan faktor-faktor lainnya yang mempengaruhi sistem penjadwalan mata kuliah. 3. Menyelesaikan masalah penjadwalan menggunakan algoritma genetika. Representasi kromosom Membangkitkan populasi awal Menghitung nilai fitness Crossover Mutasi 4. Membuat simulasi numerik dari solusi yang diperoleh dengan menggunakan software matlab. 5. Menginterpretasikan dan menganalisa hasil simulasi yang diperoleh.
HASIL DAN PEMBAHASAN Teknik Penggunaan Algoritma Genetika Pada Penjadwalan Kuliah Untuk mengetahui teknik atau cara kerja algoritma genetika pada penjadwalan kuliah, dimulai dengan membuat asumsi pembuatan jadwal perkuliahan. Pada contoh kasus berikut ini, diasumsikan memiliki pengajar sedikit yaitu 4 dosen yang akan mengampu masing-masing 7 mata kuliah dalam 5 hari yaitu senin, selasa, rabu, kamis dan jumat. Masing – masing memiliki 3 slot waktu kecuali hari jumat hanya 2 slot waktu yang disediakan. Ruang yang tersedia yaitu 2 ruangan saja. Proses Kerja Algoritma Genetika pada Penjadwalan Kuliah 1. Representasi Kromosom Representasi kromosom merupakan proses pengkodean dari penyelesaian asli dari suatu permasalahan. Pengkodean kandidat penyelesaian ini disebut dengan kromosom. Satu kandidat solusi (individu) dikodekan ke dalam suatu kromosom, dimana satu kromosom tersebut menyatakan satu solusi susunan jadwal mata kuliah. Untuk mengetahui teknik pengkodean penjadwalan dalam angka biner dapat dilihat pada Tabel 1. Tabel 1. Mata kuliah dan Dosen
3.
Fungsi Fitness Fungsi fitness digunakan untuk proses evaluasi kromosom agar memperoleh kromosom yang diinginkan. Fungsi ini membedakan kualitas dari kromosom untuk mengetahui seberapa baik kromosom yang dihasilkan. Kelayakan jadwal ditentukan dengan menggunakan nilai fitness. Nilai fitness yang dihasilkan berkisar antara 0.0 sampai 1.0, dimana kromosom yang telah memenuhi kriteria adalah kromosom yang memiliki nilai fitness = 1.0. Untuk memperoleh nilai fitness, ditentukan dengan rumus sebagai berikut : 1 𝑓𝑖𝑡𝑛𝑒𝑠𝑠 = , 0 < 𝑓𝑖𝑡𝑛𝑒𝑠𝑠 ≤ 1 1+𝑝+𝑞 keterangan : p = banyaknya dosen dengan jadwal bertabrakan q = banyaknya mata kuliah dengan jadwal berulang dalam seminggu Adapun nilai fitness masing-masing kromosom yang diperoleh dari proses pembangkitan populasi awal yang dibangkitkan sebanyak 10 kali, dapat dilihat dibawah ini : 𝑁𝑖𝑙𝑎𝑖 𝑓𝑖𝑡𝑛𝑒𝑠𝑠 𝑁𝑖𝑙𝑎𝑖 𝑓𝑖𝑡𝑛𝑒𝑠𝑠 𝑁𝑖𝑙𝑎𝑖 𝑓𝑖𝑡𝑛𝑒𝑠𝑠 𝑁𝑖𝑙𝑎𝑖 𝑓𝑖𝑡𝑛𝑒𝑠𝑠 𝑁𝑖𝑙𝑎𝑖 𝑓𝑖𝑡𝑛𝑒𝑠𝑠
Membangkitkan populasi awal Menentukan populasi awal adalah proses membangkitkan sejumlah kromosom secara acak (random). Pembangkitan (generate) populasi yang dilakukan adalah dengan cara mengacak dengan menggunakan random permutasi sehingga susunan gen mata kuliah yang dihasilkan berbeda antara satu kromosom dengan kromosom lainnya.
= 0,2 = 0,5 = 0,2 = 0,25 = 0,25
𝑁𝑖𝑙𝑎𝑖 𝑓𝑖𝑡𝑛𝑒𝑠𝑠 𝑁𝑖𝑙𝑎𝑖 𝑓𝑖𝑡𝑛𝑒𝑠𝑠 𝑁𝑖𝑙𝑎𝑖 𝑓𝑖𝑡𝑛𝑒𝑠𝑠 𝑁𝑖𝑙𝑎𝑖 𝑓𝑖𝑡𝑛𝑒𝑠𝑠 𝑁𝑖𝑙𝑎𝑖 𝑓𝑖𝑡𝑛𝑒𝑠𝑠
6 = 0,25 7 = 0,5 8 = 0,2 9 = 0,25 10 = 0,2
Dari hasil nilai fitness diatas, terlihat bahwa nilai fitness kromosom 2 dan 7 yang memiliki peluang untuk terpilih pada proses selanjutnya yaitu crossover. 4.
2.
1 2 3 4 5
Pindah Silang ( Crossover ) Pindah silang atau crossover adalah sebuah proses yang membentuk kromosom baru dari dua kromosom induk dengan menggabungkan bagian informasi dari masing-masing kromosom. Crossover menghasilkan kromosom baru yang disebut kromosom anak (offspring). Pada tahap ini, kromosom 2 dan 7 akan disilangkan untuk menghasilkan kromosom baru (offspring) yang lebih baik dari pada kromosom sebelumnya. Crossover dilakukan berdasarkan adanya tabrakan jadwal mengajar dosen yang muncul dalam waktu yang bersamaan pada ruang yang berbeda pada kromosom 2 dan 7. Penyilangan kromosom dapat dilihat pada Tabel 2.
Tabel 2. Hasil Persilangan Kromosom
Tabel 3 menunjukan hasil mutasi kromosom 2 dan 7 dengan mengganti tiap-tiap gen pada masingmasing kromosom sehingga constraint yang ditentukan terpenuhi. Dari Tabel 3, kemudian akan dihitung nilai fitness masing-masing kromosom hasil mutasi sebagai berikut : 𝑓 2 =
Tabel 2 merupakan offspring dari persilangan kromosom 2 dan kromosom 7. Selanjutnya, akan dihitung nilai fitness masing-masing kromosom hasil crossover. 𝑓𝑖𝑡𝑛𝑒𝑠𝑠 2 =
1 = 0,5 1+0+1
𝑓𝑖𝑡𝑛𝑒𝑠𝑠 7 =
1 = 0,5 1+0+1
Dari hasil perhitungan masing – masing nilai fitness pada kromosom diatas, dapat dijelaskan bahwa nilai fitness yang dihasilkan belum mencapai nilai fitness yang ditentukan, hal ini disebabkan karena ada beberapa matakuliah yang hilang dan tidak muncul dalam 1 populasi. Sehingga anak 2 dan 7 akan mengalami proses selanjutnya yaitu mutasi untuk memperoleh nilai fitness yang telah ditentukan. 5.
Mutasi Mutasi merupakan proses mengubah nilai dari satu atau beberapa gen dalam suatu kromosom. Mutasi adalah operator algoritma genetika yang bertujuan untuk membentuk individu-individu yang baik atau memiliki kualitas diatas rata-rata. Selain itu mutasi dipergunakan untuk mengembalikan kerusakan materi genetik akibat proses crossover. Proses mutasi akan dijalani oleh kromosom 2 dan kromosom 7 dengan mengubah nilai dari beberapa gen pada suatu kromosom yang mengalami bentrok dan tidak sesuai dengan constraint yang telah ditentukan. Hasil dari proses mutasi dapat dilihat pada Tabel 3. Tabel 3. Hasil Mutasi
1 =1 1+0+0
𝑓 7 =
1 =1 1+0+0
Berdasarkan nilai fitness diatas, menunjukan bahwa hasil mutasi untuk kromosom 2 dan 7 memiliki nilai fitness yang mencapai hasil optimal yang telah ditentukan yaitu nilai fitness pada masingmasing kromosom telah mencapai 1. Hal ini berarti bahwa hard constraint yang telah ditentukan telah terpenuhi dan mencapai hasil yang optimal sebagai penjadwalan kuliah. Berdasarkan Tabel 3 diperoleh penjadwalan kuliah yang masih berupa pengkodean angka biner, yang kemudian akan diubah kembali kedalam bentuk asli, untuk lebih jelasnya dapat dilihat pada Tabel 4 dan Tabel 5. Tabel 4. Jadwal kuliah Untuk kromosom 2
Tabel 5. Jadwal kuliah Untuk kromosom 7
PENUTUP Kesimpulan Dari hasil penelitian tentang teknik menentukan penjadwalan kuliah menggunakan metode algoritma genetika dengan studi kasus yang diasumsikan yaitu memiliki pengajar sekurang-kurangnya 4 dosen yang akan mengampu masing-masing 7 mata kuliah dalam 5 hari yaitu senin, selasa, rabu, kamis dan jumat yang dibagi dalam 3 slot waktu kecuali hari jumat hanya 2 slot waktu yang disediakan serta ruang yang tersedia yaitu 2 ruangan saja. Dari studi kasus tersebut disimpulkan bahwa metode algoritma dapat diterapkan dalam menentukan penjadwalan kuliah berdasarkan contoh dari kasus tersebut. Dari alur-alur algoritma genetika yang diterapkan seperti representasi kromosom, membangkitkan populasi awal, menghitung nilai fitness, crossover, dan terakhir mutasi dalam menyusun pembuatan jadwal kuliah diperoleh jadwala kuliah yang tidak bertabrakan lagi baik pada waktu, ruang maupun dosen yang mengampu jadwal tersebut. Pada proses pembuatan jadwal ini, teknik algoritma genetika yang sangat berperan dalam menghasilkan jadwal yang sempurna dalam hal ini tidak memiliki tabrakan jadwal adalah fungsi fitness karena nilai dari fungsi fitness merupakan acuan dalam memperoleh hasil yang maksimal dalam algoritma genetika. Hasil dari proses penjadwalan kuliah menggunakan algoritma genetika diperoleh dua jadwal kuliah yang dapat dipilih salah satunya untuk dijadikan sebuah jadwal yang tetap. Dua jadwal tersebut menghasilkan jadwal yang telah memenuhi dari constraint yang telah ditentukan. Saran Adapun saran yang dikemukakan adalah pada pada penelitian selanjutnya, diharapkan dapat mengambil permasalahan yang lebih kompleks dan
memberikan beberapa variasi pada faktor-faktor penentu dari masalah penjadwalan kuliah. Misalnya penjadwalan kuliah dengan 2 dosen dalam 1 matakuliah. DAFTAR PUSTAKA [1] Willemen, Robertus J. 2002. School timetable construction algorithms and complexity. Technische Universiteit Eindhoven) (Rhydian Marc Rhys Lewis. 2006. "Metaheuristics for University Course Timetabling". Napier University). [2] Syarif, A.C dan Gunawan, F.H. 2013. Penerapan Algoritma Evolusi Dengan Metode Generation Replacement Pada Aplikasi Penjadwalan Mata Kuliah (Studi Kasus Universitas Atma Jaya Makassar). Program Studi Teknik Informatika, Fakultas Teknologi Informasi, Universitas Atma Jaya Makassar Jurnal Tematika Vol. 1, No. 2 [3] Rhydian, M.R.L. 2006. Metaheuristics for University Course Timetabling. Napier University. [4] Arifudin, R. 2011. Optimasi Penjadwalan
Proyek dengan Penyeimbangan Biaya Menggunakan Kombinasi CPM dan Algoritma Genetika. Jurnal Masyarakat Informatika. Vol. 2, No. 4, ISSN 2086 – 4930.
