Optimasi Penjadwalan PelajaranDi Hari Selasa SMKN 16 Samarinda dengan Graf Pewarnaan Algoritma Greedy dan Welch Powell

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.