Aplikasi Pewarnaan Graf dengan Algoritma Recursive Largest First pada Penjadwalan Mata Kuliah
(1) Jurusan Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Negeri Makassar
(2) Jurusan Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Negeri Makassar
(3) Jurusan Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Negeri Makassar
(*) Corresponding Author
DOI: https://doi.org/10.35580/jmathcos.v2i1.12461
Abstract
Penelitian ini merupakan penelitian terapan yang menggunakan algoritma Recursive Largest First (RLF) pada penjadwalan mata kuliah di salah satu program studi pada salah satu universitas di Makassar. Penjadwalan mata kuliah dilakukan dengan merepresentasikan masalah ke dalam bentuk graf berdasarkan data yang diperoleh dengan menganggap mata kuliah sebagai simpul dan dosen sebagai sisi. Dibentuk matriks ketetanggaan dari graf yang terbentuk, kemudian simpulya diwarnai menggunakan algoritma RLF, sehingga diperoleh jadwal kuliah. Penjadwalan mata kuliah menggunakan pewarnaan simpul graf dengan algoritma RLF digunakan VBA for Microsoft Excel 2016 sebagai alat bantu dalam pewarnaan simpul graf. Diperoleh 102 simpul dengan 25 warna yang menunjukkan bahwa dibutuhkan 25 waktu perkuliahan. Jumlah simpul yang diwarnai dengan warna yang sama 6 simpul artinya dalam setiap slot dibutuhkan maksimal 6 ruangan perkuliahan. Mata kuliah yang terjadwal dijamin bahwa tidak ada jadwal dosen yang bersamaan untuk setiap mata kuliah yang diajarkan.
Kata Kunci: Graf, Recursive Largest First, Jadwal Kuliah
This research discusses the colorization of graph vertex using algorithm of Recursive Largest First (RLF) in scheduling courses in one of the study programs at one of the universities in Makassar. Representation of problems in scheduling courses was done by making it in the shape of the graph assuming subjects as vertex and the presence of the same lecturers teach different courses as a side. The steps in solving a problem that was mapping the lectures data, representing the lectures data as a graph, forming adjacency matrix, coloring the graph vertex using algorithm of RLF, so that the schedule was retrieved. Scheduling of courses using the colorization of graph vertex with algorithm of RLF as well as the help of VBA for Microsoft Excel 2016 at Faculty of Animal Husbandry obtained 102 vertices with 25 colors indicates that it takes 25 of lecture schedules. The number of vertices that were colored with the same color ≤ 6 vertices meaning in every slot needed 6 lecture rooms in maximum. Scheduled courses are guaranteed that no schedule conflicts for each lecturer of courses taught.
Keywords: Graph, Recursive Largest First, Lecture Schedules.
Full Text:
PDFReferences
Adiwijaya. (2016). Matematika Diskrit dan Aplikasinya. Bandung: Alfabeta.
Harianto, K. & Fathda, T. S. E. (2015). Penerapan Pewarnaan Simpul Graf Untuk Menentukan Jadwal Ujian Skripsi pada STMIK Amik Riau Menggunakan Algoritma Welch-Powell. Jurnal Sains dan Teknologi Informasi, 1(2). 48-54.
Hidayatulloh, T. (2015). Perancangan Sistem Penjadwalan Pembelajaran Graph Coloring. Jurnal INFORMATIKA, 2(2). 416-424.
Hiryanto, L. & Thio, J. S. (2011). Pengembangan Metode Graph Coloring Untuk University Course Timetabling Problem pada Fakultas Teknologi Informasi Universitas Tarumanagara Jakarta. Jurnal Ilmu Komputer dan Informasi, 4(2).
Mahardika, F. & Marcos, H. (2017). Penerapan Algoritma Graf Welvh Powel pada Penjadwalan Mata Kuliah dan Jadwal Asisten Study Kasus Forum Asisten STMIK AMIKOM Purwokerto. Jurnal SIMETRIS, 8(2). 825-832.
Muktyas, I. B. (2010). Program Pewarnaan Graf untuk Pemodelan Penjadwalan Ujian Semester di Jurusan Matematika UNNES (Skripsi). Universitas Negeri Semarang, Semarang.
Munir, R. (2003). Matematika Diskrit. Bandung: Informatika.
Sari, P. B., Rachmawati, H., & Akbar, M. (2013). Pewarnaan Graph Untuk Penyusunan Jadwal Kuliah Menggunakan Algoritma Recursive Lerge First (Studi Kasus: Politeknik Caltex Riau). Jurnal Aksara Komputer Terapan Politeknik Caltex Riau, 2(2). 36-42.
Sudirman, E. (2013). Pewarnaan Simpul Graf Menggunakan Algoritma Welch-Powell dan Aplikasinya pada Penjadwalan Kuliah di Jurusan Matematika FMIPA UNM (Skripsi). Universitas Negeri Makassar, Makassar.
Sunarni, T., Bendi, K. J., & Alfian, A. (2017). Optimasi Penjadwalan Mata Kuliah Menggunakan Pewarnaan Graf. Prosiding SNTI dan SATELIT (pp. E48-53). Malang, Indonesia: Jurusan Teknik Industri Universitas Brawijaya.
Article Metrics
Abstract view : 848 times | PDF view : 94 timesRefbacks
- There are currently no refbacks.
Copyright (c) 2020 Journal of Mathematics, Computations, and Statistics
Indexed by:
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.