Optimasi Penjadwalan PelajaranDi Hari Selasa SMKN 16 Samarinda dengan Graf Pewarnaan Algoritma Greedy dan Welch Powell
DOI:
https://doi.org/10.21093/dijitac.v7i1.13068Keywords:
Graphs; Scheduling; Coloring; Welch PowellAbstract
Lesson scheduling in schools is often done manually, which is time-consuming and potentially leads to scheduling conflicts between teachers, classes, and subjects. This study aims to apply the concept of Graph Coloring using the Welch-Powell Algorithm in compiling lesson schedules at SMKN 16 Samarinda. The data used include 23 subjects, 28 teachers, and 13 classes in the even semester of the 2025/2026 academic year, focusing on the Tuesday schedule. The research stages start from data collection, graph formation based on teacher-class relationships, adjacency matrix construction, and graph coloring using the Welch-Powell algorithm. Each vertex in the graph represents a teacher, while edges indicate relationships or potential scheduling conflicts. The results show that the graph coloring process produces five different colors representing five groups of time slots without any scheduling conflicts. This indicates that the Welch-Powell method can help the schedule creation process more systematically, efficiently, and structured. Thus, the application of graph coloring using the Welch-Powell algorithm can be an alternative solution in optimizing lesson scheduling in the school environment.
Downloads
References
Ade Ima Afifa Himayati, D. (2021). EWARNAAN GRAF PADA PETA WILAYAH KOTA SEMARANG DENGAN ALGORITMA GREEDY Ade Ima Afifa Himayati. 9–16. https://doi.org/https://doi.org/10.26751/jikoma.v4i1.1788.g1063
Andrari, F. R., & Qadarsih, N. D. (2023). TAHFIDZ MENGGUNAKAN ALGORITMA WELCH POWELL. 7(1), 81–92. https://doi.org/https://doi.org/10.36526/tr.v7i1.2833
Anggraini, R., Resti, N. C., & Ilmiyah, N. F. (2024). Perbandingan Pewarnaan Graf Dengan Algoritma Welch Powell dan Algoritma Tabu Search Dalam Penjadwalan Seminar Proposal. 8(2), 72–80. https://doi.org/https://doi.org/10.29407/gj.v8i2.22263
Aristianto, S., Danawati, S., & Purwanto, E. (2022). Penentuan Jadwal Ujian Skripsi di Universitas Duta Bangsa Surakarta Menggunakan Algoritma. 733–738. https://doi.org/https://doi.org/10.47701/senatib.v2i1
Cyrenia Novella Krisnamurti, D. (2022). Jurnal Sains Matematika dan Statistika Algoritma Welch-Powell untuk Menyusun Jadwal Perkuliahan Program Studi Pendidikan Fisika Universitas Sanata Dharma. 8(2), 123–132. https://doi.org/http://dx.doi.org/10.24014/jsms.v8i2.18453
Dewi, S. V. (2025). Optimalisasi Penyusunan Jadwal Pelajaran Menggunakan Pewarnaan Graf dengan Algoritma Welch – Powell. 751–761. https://doi.org/https://doi.org/10.63976/jimat.v6i2.1155
Dhamayyana, R., Cinthami, D., & Prayitno, S. (2025). Penerapan Pewarnaan Graf pada Pembagian Kamar Asrama Mahasiswa Universitas Mataram dengan Algoritma Welch Powell. 7, 2220–2231. https://doi.org/https://doi.org/10.29303/jm.v7i4.10001
Diana, U., & Fauzi, R. (2024). MENGGUNAKAN PEWARNAAN GRAF BESERTA ANALISIS BEBAN PENUGASAN [ Distribution Of Weekly Morning Call Assignments Of XYZ Agency Employees Using Graph Coloring And Assignment Load Analysis ]. 31–42. https://doi.org/https://doi.org/10.59896/aqlu.v3i1.60
Fathoni, M. I. A., Sari, A. C., Nahdlatul, U., Sunan, U., Nama, G., Tinggi, P., Welch-powell, A., & Graf, P. (2023). PROGRAM STUDI MATEMATIKA UNUGIRI MENGGUNAKAN ALGORITMA WELCH POWELL. 6, 14–24. https://doi.org/https://doi.org/10.30605/proximal.v6i1.2139
Faturahman, D. (2023). Penerapan Konsep Pewarnaan Graf dalam Penyusunan Jadwal KBM Menggunakan Metode Welch-Powell dengan Pemrograman VBA Macro Exce. 08. https://doi.org/https://doi.org/10.35870/jtik.v6i1.359
Hanifah Ekawati, D. (2025). Penerapan Pewarnaan Graf Pada Penjadwalan Ujian Semester Program Studi Bisnis Digital Menggunakan Algoritma Welch Powell. 6(1), 41–57. https://doi.org/https://doi.org/10.30872/bedu.v6i1.5079
Harahap, R. K., & Khairani, N. (2024). Penerapan Pewarnaan Graf dalam Penjadalan Kerja Menggunakan Algoritma Welch-Powell ( Studi Kasus : Rumah Sakit Grand Medistra Lubuk Pakam ). 4, 3358–3369. https://doi.org/https://doi.org/10.31004/innovative.v4i2.9728
Landerius, & 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. 7(6). https://doi.org/10.5281/zenodo.5574383
Lazuardi, M. A., Sari, R. P., Rahmayuda, S., Informasi, J. S., Tanjungpura, U., Penjadwalan, S. I., & Graf, P. (2025). Coding : Jurnal Komputer dan Aplikasi Penerapan Algoritma Welch-Powell Untuk Optimasi Sistem Informasi Penjadwalan Mata Pelajaran ( Studi Kasus : MIN 2 Pontianak ) Coding : Jurnal Komputer dan Aplikasi. 13(2). https://doi.org/https://doi.org/10.26418/coding.v13i2.90290
Mulyati, E., & Sanggala, E. (2021). MATRIK Penjadwalan Sopir Pengangkutan Sampah Dalam Meminimalkan Ketidakmerataan Jam Kerja Di Kota Cimahi Dengan Greedy Algorithm. XXI(2). https://doi.org/10.350587/Matrik
Rahadi, A. P., Pani, E. B., & Matakuliah, P. (2020). Pengembangan Program Komputer Penjadwalan Matakuliah Berdasarkan Pewarnaan Graf dengan Algoritma Welsh-Powell Terbobot. 6(1), 37–44. https://doi.org/http://dx.doi.org/10.24014/coreit.v6i1.9955
Rohmawati, R. M., & Fathoni, M. I. A. (2022). Penerapan Algoritma Welch-Powell Pada Penyusunan Jadwal Perkuliahan di Program Studi Pendidikan Matematika. 10(2), 200–210. https://doi.org/https://doi.org/10.34312/euler.v10i2.16649
Sopiyan, M., Gunaryati, A., & Fitri, I. (2022). Graph coloring Sistem Pendaftaran dan Proses Penjadwalan Data Instruktur Berbasis Web dengan Algoritma Welch-powell. 6(1), 1–6. https://doi.org/https://doi.org/10.35870/jtik.v6i1.359
Surbakti, N. M. (2023). Implementasi Pewarnaan Graf Menggunakan Metode Algoritma Welch Powell pada Penjadwalan Seminar Proposal Skripsi di Program Studi Matematika Universitas Negeri Medan. 137–148. https://doi.org/https://doi.org/10.36456/buanamatematika.v13i2.7261
Tanaya, T. A., & Syahmarani, A. (2024). Zero : Jurnal Sains , Matematika , dan Terapan Graph Coloring With Welch-Powell Algorithm In Determining Lecture Schedule Data obtained from previous lecture schedules in the Undergraduate Mathematics Study Program. 8(2). https://doi.org/10.30829/zero.v8i2.21027
