TELEKONTRAN. VOL. NO. OKTOBER 2019 DOI 10. 34010/telekontran. TELEKONTRAN. VOL. NO. OKTOBER 2019 p-ISSN : 2303 Ae 2901 e-ISSN : 2654 Ae 7384 Algoritma Ant Colony Optimization untuk Optimasi Penjadwalan Mata Kuliah Ant Colony Optimization Algorithm for Lecturing Schedule Optimization Meiton Boru* Program Studi Ilmu Komputer Fakultas Sains dan Teknik Universitas Nusa Cendana Jl. Adisucipto. Lasiana. Kelapa Lima. Kupang. Nusa Tenggara Timur 85228. *Email : meitonboru@staf. Abstrak Ae Tujuan dari penelitian ini adalah mengoptimalkan penjadwalan mata kuliah menggunakan algoritma Ant Colony Optimization (ACO). Metode yang dikembangkan akan mencari solusi optimal dari penjadwalan mata kuliah dimana terdapat beberapa batasan yang harus dipertimbangkan. Batasan-batasan tersebut diantaranya adalah seorang dosen atau suatu kelas hanya boleh dijadwalkan kuliah maksimal dua kali secara berturut-turut. Batasan lainnya adalah dua angkatan yang berbeda satu tahun, tidak boleh dijadwalkan pada waktu yang sama. Batasan ketiga adalah jangan sampai ada dosen atau kelas yang melakukan perkuliahan dengan frekuensi terlalu tinggi pada suatu hari. Dan batasan keempat adalah waktu alternatif dimana dosen dapat mengajar akan terbatas dikarenakan adanya aktivitas lain yang harus dilakukan oleh dosen tersebut. Agar kasus penjadwalan mata kuliah dapat diselesaikan menggunakan algoritma ACO, maka dibuat suatu graph dimana setiap nodenya adalah nama mata kuliah yang harus dijadwalkan. Jalur yang dibuat oleh semut dari node awal ke node akhir akan berisi urutan mata kuliah yang harus dilaksanakan pada satu minggunya. Berdasarkan hasil pengujian, algoritma ACO telah berhasil melakukan penjadwalan mata kuliah yang melibatkan 38 mata kuliah, 4 angkatan kelas, 6 lokasi perkulihan dan 12 dosen pengampu mata kuliah. Solusi penjadwalan yang diperoleh memiliki nilai fitness 0,0092. Dimana tidak terdapat dosen yang memiliki frekuensi mengajar tinggi pada suatu hari, tetapi terdapat 12 jadwal kuliah yang menyebabkan suatu kelas mengikuti frekuensi perkuliahan yang tinggi. Serta terdapat 4 mata kuliah yang dijadwalkan Hasil penjadwalan dapat memiliki nilai fitness yang baik karena algoritma ACO menerapkan prinsip Aupembelajaran dan perbaikan dari hasil sebelumnyaAy. Dapat disimpulkan bahwa algoritma ACO telah berhasil digunakan untuk mengoptimalkan penjadwalan mata kuliah. Kata Kunci : Ant colony optimization, fitness, optimasi, penjadwalan Abstract - The purpose of this study is to optimize the the lecturing schedule using the Ant Colony Optimization (ACO) algorithm. The method developed will find an optimal solution of lecturing schedule where there are some limitations that must be considered. These limitations include being a lecturer or a class that can only be scheduled to lecture a maximum of two times in a row. Another limitation is that two adjacent level may not be scheduled at the same time. The third limitation is that there should be no lecturers or classes that conduct lectures with too high a frequency one day. And the fourth limitation is the alternative time where lecturers can teach will be limited due to other activities that must be carried out by the lecturer. So that the course scheduling case can be solved using the ACO algorithm, a graph is made where each node is the name of the course that must be scheduled. The path created by the ants from the initial node to the end node will contain the order of courses that must be carried out one week. Based on the test results, the ACO algorithm has succeeded in scheduling courses involving 38 subjects, 4 class forces, 6 recovery locations and 12 lecturers supporting the courses. The scheduling solution obtained has a fitness value of 0. Where there are no lecturers who have a high teaching frequency one day, but there are 12 class schedules that cause a class to follow a high frequency of lectures. And there are 4 courses scheduled to be close together. The results of scheduling can have a good fitness value because the ACO algorithm applies the principle of "learning and improvement from previous results". It can be concluded that the ACO algorithm has been successfully used to optimize course scheduling. Keywords : Ant colony optimization, fitness, optimization, scheduling TELEKONTRAN. VOL. NO. OKTOBER 2019 PENDAHULUAN Penjadwalan kegiatan perkuliahan merupakan pekerjaan yang tidak sederhana. Terdapat beberapa batasan yang harus dipertimbangkan, diantaraya adalah sebagai berikut . Tidak boleh ada mata kuliah pada suatu angkatan yang dijadwalkan beririsan dengan mata kuliah lain dari angkatan yang berbeda setahun diatasnya atau dibawahnya. Hal ini dikarenakan sering adanya mahasiswa yang mengulang mengambil mata kuliah di angkatan bawah atau mengambil mata kuliah di angkatan atas Alternatif waktu kuliah yang bisa dilakukan oleh seorang dosen bisa jadi terbatas. Dosen sering memiliki aktivitas selain mengajar yang harus dilakukannya. Distribusi jadwal mengajar diharapkan dapat merata untuk setiap kelas. Diharapkan tidak ada dosen atau kelas yang memiliki frekuensi kuliah terlalu tinggi pada satu harinya Pekerjaan penjadwalan mata kuliah akan semakin rumit jika melibatkan semakin banyak mata kuliah, kelas maupun dosen. Untuk mendapatkan jadwal yang optimal, maka Karena itu dibutuhkan metode mengerjakan penjadwalan mata kuliah dengan batasan-batasan Terdapat beberapa alternatif metode optimasi yang dapat digunakan untuk mengoptimalkan penjadwalan, seperti Algoritma Genetik (GA) . , logika Fuzzy . , . Particle Swarm Optimization (PSO) . , maupun Ant Colony Optimization (ACO) . Pendekatan menggunakan ACO menjadi pilihan dalam penelitian ini. ACO diinspirasi dari perilaku kelompok semut dalam mencari dan mengumpulkan makanan. Pada saat awal pencarian, kelompok semut akan menyebar secara acak hingga menemukan makanan. Jika makanan sudah ditemukan maka semut akan bolak-balik antara makanan dan sarang. Selama perjalanan bolak-balik tersebut, semut akan menebarkan pheromone. Jika terdapat semut yang melalui jalur yang pendek, maka semut itu akan bolak-balik lebih cepat sehingga pheromone yang disebar pada jalur tersebut akan lebih banyak. Sedangkan jika ada semut yang melalui jalur yang jauh, maka semut akan membutuhkan waktu bolak-balik lebih lama dan pheromone yang disebar pada jalur tersebut akan lebih sedikit. Karena semut akan tertarik pada jalur yang lebih banyak pheromone, maka jalur yang terpendek akan dipilih oleh kelompok semut. Prinsip dari algoritma ini ditunjukkan pada Gambar 1. Algoritma ACO menyelesaikan permasalahan optimasi dalam kasus diskrit . Dalam permasalahan optimasi ACO diimplementasikan dalam berbagai kasus, seperti masalah travelling-salesman problem (TSP) . , penjadwalan pekerjaan . ataupun perutean . Penelitian mengimplementasikan algoritma ACO untuk mengoptimalkan jadwal perkuliahan dengan melibatkan berbagai batasan yang sering terjadi pada kasus penjadwalan perkuliahan. Gambar 1. Prinsip dari algoritma ACO : . Kelompok semut secara acak mencari jalur menuju makanan, . jalur terpendek akan terdapat lebih banyak pheromone yang tersebar, maka kelompok semut akan cenderung melalui jalur tersebut Terdapat beberapa publikasi mengenai penelitian optimasi penjadwalan menggunakan ACO. Deng . menggunakan algoritma ACO untuk penjadwalan awak pesawat. Chen . menggunakan ACO untuk penjadwalan staf pada suatu proyek berdasarkan suatu peristiwa. Zhou . menggunakan algoritma ACO untuk diimplementasikan pada kasus dynamic job-shop Zhang . menggunakan algoritma ACO untuk pengendalian multi satelit. Perbedaan yang dilakukan pada penelitian ini adalah melibatkan batasan-batasan . yang harus dipertimbangkan dalam penyusunan jadwal Batasan yang dilibatkan diantaranya adalah dosen dan suatu kelas tidak boleh dijadwalkan kuliah berturut-turut lebih dari dua kali mata kuliah, tidak boleh angkatan yang berdekatan dijadwalkan secara bersamaan agar mahasiswa tetap dapat mengulang suatu mata kuliah, tidak boleh ada dosen dan kelas yang memiliki frekuensi kuliah terlalu tinggi dalam satu hari, serta mengakomodasi terbatasnya waktu dosen yang dapat digunakan untuk perkuliahan. TELEKONTRAN. VOL. NO. OKTOBER 2019 Penelitia ini bertujuan untuk mengoptimalkan penjadwalan mata kuliah menggunakan algoritma ACO. Metode yang dikembangkan akan menemukan solusi optimal dari penjadwalan mata kuliah di mana ada beberapa batasan . yang perlu dipertimbangkan. Batasan-batasan itu adalah dosen atau suatu kelas hanya diijinkan untuk dijadwalkan kuliah berturut-turut maksimal dua mata kuliah. Batasan kedua adalah tidak boleh dua angkatan yang berbeda satu tahun dijadwalkan dalam waktu yang bersamaan, agar memungkinkan bagi mahasiswa untuk mengambil mata kuliah ke bawah atau ke atas. Batasan ketuga adalah tidak boleh ada jadwal kuliah dengan frekuensi yang terlalu tinggi dalam satu hari bagi dosen maupun kelas yang sama. Dan batasan keempat adalah harus dapat mengoptimalkan jadwal perkuliahan meskipun jadwal alternatif yang disediakan oleh dosen terbatas. Agar kasus penjadwalan mata kuliah ini dapat diselesaikan menggunakan algoritma ACO, maka dibangkitkan gragp dengan setiap nodenya adalah nama mata kuliah yang harus dijadwalkan. Jalur yang dibuat oleh semut dari node awal ke node akhir akan berisi urutan mata kuliah yang harus dijadwalkan dalam satu minggunya. II. METODE Agar algoritma ACO dapat menyelesaikan kasus penjadwalan mata kuliah ini, maka digunakan grafik graph seperti yang ditunjukkan pada Gambar 2. Pada graph tersebut berisi nodenode yang mewakili setiap mata kuliah yang harus Jalur yang dibuat oleh semut dari node awal ke node akhir akan berisi urutan mata kuliah yang harus dijadwalkan dalam satu Jika suatu node mata kuliah sudah dilalui oleh semut, maka node-node lain dengan nama mata kuliah yang sama akan dihilangkan sementara dari graph. Hal ini akan menjaga agar suatu mata kuliah yang akan dijadwalkan sekali Graph mentransformasikan masalah penjadwalan mata kuliah kedalam bentuk permasalahan optimasi Algoritma ACO akan diterapkan melalui graph ini. Pada setiap jalur yang dilaluinya, semut-semut akan meletakan pheromone. Terdapat dua jenis pembaharuan . nilai pheromone, yaitu update pheromone local, dan update pheromone Setelah semut membangun jalur lengkap yang menghubungkan node awal ke node akhir, maka dilakukan update pheromone lokal yang mengikuti persamaan . Dimana Variabel disebut variabel peng-update-an adalah jumlah jalur yang digunakan, sedangkan adalah nilai fitness dari kualitas jadwal yang diberikan oleh jalur Untuk update pheromone global, ada update pheromone positif . dan ada update pheromone negative . Persamaan yang digunakan adalah sebagai berikut. Gambar 2. Representasi graph permasalahan penjadwalan mata kuliah TELEKONTRAN. VOL. NO. OKTOBER 2019 Dimana adalah nilai pheromone dari tur yang memberikan nilai fitness terbaik (Cbes. dalam satu iterasi. Adapun pheromone dari tur yang memberikan nilai fitness terburuk (Cwors. dalam satu iterasi. Pheromone dari jalur yang yang memberikan nilai fitness terbaik akan terus bertambah. Adapun pheromone dari jalur yang memberikan nilai fitness terburuk akan terus berkurang selama iterasi. Setelah satu iterasi selesai , beberapa pheromone akan menguap dari jalur. Penguapan pheromone menggunakan persamaan . Proses penguapan ini akan membuat algoritma ACO lebih terbuka untuk melakukan pelacakan pada arah baru. Dengan adalah konstanta penguapan serta adalah hasil penjumlahan persamaan . Evaluasi fitness dari suatu hasil penjadwalan dilakukan dengan menghitung faktor-faktor Apakah ada mata kuliah yang dipecah Jika ada mata kuliah dengan bobot 3 SKS, sistem dapat menjadwalkannya dengan cara dibagi dalam 2 kelompok jam kuliah. Pemecahan ini dilakukan jika tidak ditemukan menjadwalkan mata kuliah tersebut dalam satu Proses penjadwalan berdasarkan masukan yang ada. Tetapi proses pemecahan mata kuliah ini akan memperkecil nilai fitness. Sehingga program penjadwalan yang tidak terlalu banyak memiliki pemecahan mata kuliah. Apakah ada pemadatan jadwal disuatu waktu ( )? Agar produktivitas pemakaian ruangan meningkat, maka dikehendaki agar ruangan dapat beroperasi semenjak pagi hingga petang. Jika program menghasilkan jadwal dimana terdapat waktu kosong dimana ruangan tidak tergunakan, maka akan mengurangi nilai Apakah ada frekuensi mengajar dosen yang terlalu tinggi ( ) ? Diinginkan agar tugas mengajar dosen dapat terdistribusi merata tiap harinya. Hal ini agar performansi mengajar dosen tetap optimal. Jika dosen mengajar terlalu banyak dalam suatu harinya, maka akan lelah dan tidak Maka nilai fitness akan berkurang jika dalam suatu jadwal yang dibuat terdapat frekuensi mengajar dosen yang terlalu tinggi. Apakah ada frekuensi kuliah mahasiswa yang terlalu tinggi ( ) ? Seperti halnya dosen, mahasiswa juga akan lelah dan susah konsentrasi jika mengikuti perkuliahan yang terlalu banyak pada suatu Maka nilai fitness akan berkurang jika dalam suatu jadwal yang dibuat terdapat frekuensi kuliah mahasiswa yang terlalu tinggi. Apakah ada mata kuliah yang diikuti kelas yang sama yang berdekatan ( ) ? Diinginkan agar mahasiswa memiliki waktu istirahat setelah selesai perkuliahan dan sebelum memulai perkuliahan selanjutnya. Maka jika terdapat dua mata kuliah yang diikuti kelas yang sama dan dijadwalkan berdekatan, maka akan mengurangi nilai Apakah dalam satu hari ada dua mata kuliah yang diikuti kelas yang sama yang terpisah terlalu jauh waktunya ( ) ? Walaupun dikehendaki ada jeda antar dua mata kuliah, tetapi diinginkan mahasiswa tidak perlu menunggu terlalu lama diantara dua mata kuliah tersebut. Maka rumus fitness yang digunakan ditunjukkan pada persamaan . = banyaknya pemecahan mata kuliah = banyaknya waktu yang kosong = banyaknya frekuensi mengajar dosen tinggi = banyaknya frekuensi kuliah mahasiswa tinggi = banyaknya mata kuliah berdekatan = banyaknya mata kuliah berjauhan = bobot pemecahan mata kuliah = bobot adanya waktu yang kosong = bobot frekuensi mengajar dosen tinggi = bobot frekuensi kuliah mahasiswa tinggi = bobot mata kuliah berdekatan = bobot mata kuliah berjauhan TELEKONTRAN. VOL. NO. OKTOBER 2019 HASIL DAN DISKUSI Terdapat empat masukan data yang harus diberikan kepada sistem, yaitu tabel mata kuliah, tabel waktu kesediaan dosen untuk mengajar . abel dose. , tabel kelas, dan tabel ruang. Tabel I adalah contoh dari tabel dosen. Tabel II adalah contoh dari tabel kelas. Tabel i adalah contoh dari tabel ruang. Dan Tabel IV adalah contoh dari tabel mata kuliah. Tabel mata kuliah berisikan daftar seluruh mata kuliah yang hendak dijadwalkan. Data yang perlu dimasukkan pada tabel mata kuliah adalah nama kelas, jumlah sks, nama mata kuliah dan dosen pengajar mata kuliah tersebut. Tabel dosen, tabel kelas dan tabel ruang berisi informasi mengenai waktu yang dapat digunakan untuk mengalokasikan suatu mata kuliah. Angka 1 pada Tabel I Ae Tabel i menunjukkan bahwa pada waktu tersebut tidak dapat dialokasikan jadwal Pada Tabel I merupakan contoh dimana dosen pada hari Senin hingga Rabu dapat dijadwalkan diantara jam 07. 00 Ae 14. Tetapi pada hari Kamis hanya bisa dijadwalkan untuk mengajar diantara jam 07. 00 Ae 12. Tabel I Tabel i akan diupdate setiap suatu mata kuliah selesai dijadwalkan. Tabel I. Contoh Tabel Dosen Dosen A Senin Selasa Rabu Kamis 00 Ae 08. 00 Ae 09. 00 Ae 10. 00 Ae 11. JumAoat Sabtu JumAoat Sabtu 00 Ae 12. 00 Ae 13. 00 Ae 14. 00 Ae 15. 00 Ae 16. 00 Ae 17. Tabel II. Contoh Tabel Kelas 19TE-1 Senin Selasa Rabu Kamis 00 Ae 08. 00 Ae 09. 00 Ae 10. 00 Ae 11. 00 Ae 12. 00 Ae 13. 00 Ae 14. 00 Ae 15. 00 Ae 16. 00 Ae 17. Tabel i. Contoh Tabel Ruang Senin Selasa Rabu Kamis JumAoat Sabtu 00 Ae 08. 00 Ae 09. 00 Ae 10. 00 Ae 11. 00 Ae 12. 00 Ae 13. 00 Ae 14. 00 Ae 15. 00 Ae 16. 00 Ae 17. Tabel IV Contoh Tabel Mata Kuliah Kelas 19TE-1 19TE-1 19TE-1 19TE-1 19TE-1 18TE-1 18TE-1 18TE-1 18TE-1 18TE-1 18TE-1 17TE-1 17TE-1 17TE-1 17TE-1 Mata Kuliah Bahasa Inggirs II Fisika Dasar II Pancasila Pengukuran Listrik Agama Rangkaian Listrik II Matematika Teknik II Elektronika Elektromagnetika Telekomunikasi I Dasar Sistem Kontrol Mikrokontroller Bahasa Indonesia Metodologi Penelitian Teknik Tenaga Listrik SKS Dosen Dosen I Dosen JU Dosen OS Dosen BH Dosen JA Dosen TR Dosen TR Dosen BH Dosen MA Dosen LO Dosen IR Dosen S Dosen J Dosen YE Dosen BH Selanjutnya tabel mata kuliah, tabel dosen, tabel ruang dan tabel kelas akan digabungkan menjadi tabel prioritas mata kuliah. Tabel banyaknya alternatif waktu yang dapat dipilih untuk mengalokasikan suatu mata kuliah. Tabel prioritas mata kuliah mengurutkan mata kuliah dari yang paling sedikit alternatif waktu yang dapat dipilihnya, hingga mata kuliah yang paling banyak memiliki alternatif waktu pilihannya. Proses ini dilakukan agar tidak ada mata kuliah yang tidak dapat dialokasikan karena jadwal alternatif yang memungkinkan pelaksanaan mata kuliah tersebut sudah dijadwalkan untuk pelaksanana mata kuliah lainnya. Implementasi dari algoritma ini dilakukan pada program LabVIEW. Block diagram ditunjukkan pada Gambar 3. Tampilan program yang dibuat ditunjukkan pada Gambar 4. TELEKONTRAN. VOL. NO. OKTOBER 2019 Gambar 3. Implementasi program pada block diagram LabVIEW TELEKONTRAN. VOL. NO. OKTOBER 2019 Gambar 4. Tampilan front panel LabVIEW Terdapat tiga kondisi berhenti dimana semut tidak perle melanjutkan iterasinya lagi. Pertama adalah jika setelah beberapa iterasi berturut-turut tidak lagi terjadi perubahan nilai fitness. Kondisi berhenti yang kedua adalah jika jumlah iterasi maksimum sudah tercapai. Adapun kondisi berhenti yang ketiga adalah jika nilai fitness minimal yang dikehendaki sudah tercapai. Jika salah satu kondisi diatas sudah tercapai, maka algoritma ACO akan dihentikan, dan selama ketiga kondisi tersebut belum ada yang tercapai maka semut masih akan mengulangi proses Contoh hasil penjadwalan yang diberikan oleh program ditunjukkan pada Gambar 5. Terlihat bahwa hampir seluruh jadwal pemakaian ruang telah berhasil diisi oleh program. Hal ini menunjukkan kemampuan program untuk memanfaatkan setiap waktu yang tersedia. Bobot fitness yang digunakan adalah sebagai berikut. = 20 = 20 = 20 Berdasarkan nilai bobot yang digunakan dapat terlihat bahwa prioritas utama dalam penjadwalan ini adalah agar tidak ada mata kuliah yang dipecah penjadwalannya serta agar tidak ada jadwal kuliah dosen dan mahasiswa yang terlalu sering pada suatu hari. Prioritas ini dapat terlihat dari nilai bobot yang dibuat lebih tinggi daripada bobot lainnya. Adapun jadwal yang dibuat tidak mempermasalahkan jika ada dua mata kuliah dari satu kelas yang letaknya berjauhan ( = . Algoritma yang dirancang telah diujikan pada penjadwalan mata kuliah yang melibatkan 38 mata kuliah, 4 angkatan kelas, 6 ruang perkulihan serta 12 dosen pengampu mata kuliah. Algoritma ACO berhasil menyusun jadwal final yang memiliki nilai fitness 0,0092. Pada jadwal tersebut tidak terdapat dosen yang memiliki frekuensi mengajar tinggi pada suatu harinya. Tetapi terdapat 12 jadwal mata kuliah yang membuat suatu kelas mengikuti perkuliahan dalam frekuensi yang tinggi. Serta terdapat 4 mata kuliah yang dijadwalkan berdekatan. Performansi akhir ini dinilai cukup baik dan penjadwalan mata kuliah yang memiliki beberapa constraint telah berhasil dilakukan menggunakan algoritma ACO. TELEKONTRAN. VOL. NO. OKTOBER 2019 Gambar 4. Contoh hasil penjadwalan Hasil penjadwalan dapat memiliki nilai fitness yang baik karena algoritma ACO menerapkan prinsip Aupembelajaran dan perbaikan dari hasil sebelumnyaAy. Hasil fitness yang diperoleh dari penjadwalan menggunakan algoritma ACO ini, yaitu sebesar 0,0092, lebih baik dari hasil penjadwalan menggunakan algoritma GA yang dilakukan Aria pada . , yaitu 0,0083. Walaupun pada hasil penjadwalan keduanya masih terdapat mata kuliah yang berdekatan. IV. KESIMPULAN Penelitian mengimplementasikan algoritma ACO untuk mengoptimalkan penjadwalan mata kuliah pada kasus multi angkatan dan multi ruangan. Program yang dibuat telah dapat mencari solusi penjadwalan pada waktu yang dapat digunakan oleh dosen, mahasiswa maupun ruangan. Program juga dapat meminimalkan mata kuliah yang harus dilaksanakan dengan dipecah serta meminimalkan jadwal kuliah dengan frekuensi yang tinggi baik Hasil TELEKONTRAN. VOL. NO. OKTOBER 2019 penjadwalan dapat memiliki nilai fitness yang baik karena algoritma ACO menggunakan prinsip Aupembelajaran dan perbaikan dari hasil sebelumnyaAy. Dari salah satu hasil pengujian penjadwalan 38 mata kuliah, 4 angkatan kelas, 6 lokasi perkulihan dan 12 dosen pengampu mata kuliah, algoritma yang diusulkan dapat memperoleh fitness 0,0092. Tidak terdapat dosen yang memiliki frekuensi mengajar tinggi pada suatu hari, tetapi terdapat 4 mata kuliah yang dijadwalkan berdekatan dan 12 jadwal kuliah yang menyebabkan suatu kelas mengikuti frekuensi perkuliahan yang tinggi. REFERENCES