Penerapan Pewarnaan Graf untk Penjadwalan Mata Pelajaran di SMA Nurul Amaliyah Tanjung Morawa

Abstract

Subject scheduling in schools, such as at Nurul Amaliyah Senior High School in Tanjung Morawa, is often done manually using Microsoft Excel, which is time-consuming and prone to errors and scheduling conflicts. This study aims to apply the concept of graph coloring with the Greedy algorithm to address the subject scheduling problem at the school. In its implementation, each unique teaching session is modeled as a vertex, and conflicts between sessions (e.g., the same teacher or class at the same time) are represented as edges in a graph. The Greedy Graph Coloring algorithm is then applied to assign a color to each session, ensuring that no conflicting sessions receive the same color. The result is an allocation of sessions into basic, conflict-free abstract time slots, which are then mapped to a concrete daily schedule. The resulting schedule is proven valid in avoiding conflicts between teachers and classes occupying the same time slot. However, due to the inherent nature of the Greedy algorithm, which does not explicitly consider the specific number of sessions per day per class or other daily distributions, the resulting schedule structure may not be fully optimal under all desired daily constraints, even if the fundamental conflict has been resolved. This study demonstrates that graph coloring with the Greedy algorithm can provide a practical and effective solution for developing conflict-free lesson schedules in schools.