Perbandingan Algoritma Welch-Powell, Algoritma Greedy, dan Algoritma Recursive Largest First dalam Penjadwalan Mata Pelajaran di SMP Swasta Islam Terpadu Iqra

Abstract

This research aims to compare the Welch-Powell algorithm, the Greedy algorithm, and the Recursive Largest First algorithm in scheduling subjects for the odd semester of the 2024/2025 academic year at SMP Swasta Islam Terpadu Iqra. This research shows that these three algorithms have the same chromatic number, which is 12. This means that to resolve all conflicts between subjects and ensure no two subjects overlap in time, a minimum of 12 time slots (colors) per week is required. Based on execution time testing of the three graph coloring algorithms, the Greedy algorithm has the fastest execution time compared to the other algorithms. This aligns with its lighter theoretical complexity, which is O(V + E). Meanwhile, the Welch-Powell algorithm takes longer than the Greedy algorithm, which has a complexity of O(V^2). The Recursive Largest First algorithm performs the slowest among the three, with a complexity of O(V^3).