Graph Coloring Application with Modified Tabu Search Algorithm in School Scheduling

Graph coloring is one of the common problems encountered in scheduling optimization. In the context of school scheduling, graph coloring is used to efficiently allocate time for various school activities. The objective of this research is to apply the Tabu Search algorithm in solving the graph coloring problem for school scheduling. This study utilizes the Tabu Search algorithm as an optimization method to find schedule solutions that satisfy all given constraints. The Tabu Search algorithm combines local search with a broader exploration mechanism. The Tabu Search algorithm is implemented by considering various important factors such as the number of subjects, time constraints, and specific preferences. In the graph coloring modeling, each subject is represented as a graph node, while the relationships between subjects that cannot take place at the same time are represented by graph edges. The results of this research show that the Tabu Search algorithm is capable of producing schedule solutions that meet all the given constraints. The found solutions have advantages in efficient time allocation, avoiding overlaps between activities, and considering the preferences compared to manual scheduling. This research contributes to the field of school scheduling by utilizing the Tabu Search algorithm from graph coloring.