Penerapan Metode Welch-Powell Improvement Pada Pewarnaan Graf Untuk Penjadwalan KBM SMAN 7 Mataram Menggunakan Python
Abstract
The preparation of teaching and learning schedules is often problematic, one of the reasons being the limited number of teachers, which means that one teacher has to teach several classes at the same time. This research is an applied study that aims to obtain a teaching and learning schedule without overlap by applying graph coloring using the Welch-Powell Improvement method. Graph coloring using the Welch-Powell Improvement method is a solution to solve scheduling problems at SMAN 7 Mataram. Based on the scheduling data, an adjacency matrix with a size of 898×898 and a chromatic number of 27 was obtained. The adjacency matrix was determined with the help of the Python programming language. The schedule was compiled by first creating a scheduling conflict graph based on the lesson schedule data, then coloring the graph using the Welch-Powell Improvement algorithm. Based on the coloring results obtained, the schedule was compiled by considering each node color. Subjects with the same color were scheduled at the same time and vice versa. The resulting class schedule was free of overlaps. This was because the chromatic number obtained in the graph coloring was smaller than the available time slots at SMAN 7 Mataram.
References
Ardiansyah, Efendi, F., Pinto, M., Pujianto, & Tempake, H. (2010). Implementasi algoritma greedy untuk melakukan graph coloring: studi kasus peta provinsi jawa timur. Jurnal Informatika, 4(2), 440–448. https://media.neliti.com/media/publications/103610-ID-implementasi-algoritma-greedy-untuk-mela.pdf
Assiyatun, H. (2023). Teori graf dalam peta matematika indonesia. Bandung: Institut Teknologi Bandung.
Awanis, Z. Y., Salwa, S., Aini, Q., Switrayni, N. W., Wardhana, I. G. A. W., Irwansyah, I., & Asmarani, E. Y. (2023). Pengenalan konsep teori graf di madrasah aliyah manhalul ma’arif darek, lombok tengah, nusa tenggara barat. Jurnal Pepadu, 4(1), 95–102. https://doi.org/10.29303/pepadu.v4i1.2242
Fathurrahman, F., Amrullah, A., Hayati, L., & Prayitno, S. (2023). Penerapan konsep pewarnaan graf dalam penyusunan jadwal kbm menggunakan metode welch-powell dengan pemrograman vba macro excel. Pendas: Jurnal Ilmiah Pendidikan Dasar, 8(1), 6377-6390.
Haniantara, R., Amrullah, Lu’luilmaknun, U., & Kurniati, N. (2023). Penerapan konsep pewarnaan graf dalam penjadwalan pembelajaran di sman 1 kopang. Journal Pendas, 08(2), 1201-1212.
Hasanah, G. L., Sripatmi, S., Amrullah, A., & Baidowi. (2022). Penerapan konsep pewarnaan graf dalam penyusunan jadwal kegiatan belajar mengajar di smkn. Griya Journal of Mathematics Education and Application, 2(2), 504–516. https://doi.org/10.29303/griya.v2i2.177
Husni. (2019). Panduan ringkas dasar pemrograman python. Madura: Universitas Trunojoyo.
Irawan, D., & Saputra, Y. (2024). Penerapan algoritma greedy untuk penyusunan jadwal kerja di industri perhotelan. IJCCS, 2(1). https://doi.org/10.62003/c53fxr97
Lim K. J., Nathanael C., Wijaya F. A., Dharma J. A., Andrian T K., Soetresno W., & Ningsih, R. Y. (2023). Penggunaan bahasa pemrograman python untuk memvisualisasikan data peluang selamat dari kecelakaan titanic. Jurnal Publikasi Teknik Informatika, 2(2), 66–79. https://doi.org/10.55606/jupti.v2i2.1735
Maro, L., & Banabera, C. (2020). Pewarnaan titik pada korona graf kipas. Jurnal Ilmiah Matematika dan Terapan, 2(2), 16-20. https://core.ac.uk/download/pdf/354907788.pdf
Maro, L., & Purab, L. K. S. (2021). Penerapan konsep pewarnaan graf dalam penyusunan jadwal perkuliahan menggunakan metode algoritma welch-powell pada program studi teknik informatika fakultas matematika dan ilmu pengetahuan alam universitas tribuana kalabahi. Jurnal Ilmiah Wahana Pendidikan, 7(6), 193–197. https://doi.org/10.5281/zenodo.5574383
Munir, R. (2010). Algoritma dan pemrograman dalam teori graf. Bandung: Informatika Bandung.
Murdani, & Ndruru, E. (2019). Algoritma ant colony sistem dalam penjadwalan kegiatan belajar mengajar di smp prayatna medan. Jurnal Armada Informatika, 3(1). https://doi.org/10.36520/jai.v3i1.24
Rahadi, A., P., & Pani, E., B. (2020). Pengembangan program komputer penjadwalan matakuliah berdasarkan pewarnaan graf dengan algoritma welsh-powell terbobot. Jurnal CoreIT, 6(1), 37–44. https://ejournal.uin-suska.ac.id/index.php/coreit/article/view/9955/pdf
Rahayuningsih, S. (2018). Teori graf dan penerapannya. Malang: IKIP Budi Utomo.
Rudianto, A., & Muhandhis, I. (2022). Rancang bangun sistem penyusunan jadwal pelajaran menggunakan algoritma genetika berbasis web (studi kasus mi mahalul ulum). Journal of System Engineering and Technological Innovation (JISTI), 1(1), 33–37. https://doi.org/10.38156/jisti.v1i01.14
Rukminingsih, Adnan, G., & Latief, M. A. (2020). Metode penelitian pendidikan: penelitian kuantitatif, penelitian kualitatif, penelitian tindakan kelas. Yogyakarta: ERHAKA UTAMA.
