IMPELEMENTASI ALGORITMA WELCH-POWELL DALAM PENJADWALAN PIKET JAGA SEKRETARIAT ORGANISASI MAHASISWA PADA HIMPUNAN MAHASISWA JURUSAN MATEMATIKA UNIVERSITAS NEGERI GORONTALO

Abstract

Graph theory is used to represent discrete objects and the relationships between them. One of its applications is scheduling through graph coloring. Scheduling duty shifts for an organizational secretariat often becomes a complex problem due to the varying class schedules of members. This article aims to implement graph coloring to arrange the duty schedule for HIMATIKA UNG using the Welch-Powell algorithm. This algorithm works by assigning different colors to adjacent vertices (representing members from the same class), resulting in a graph coloring with the minimum number of colors. The implementation results show that the chromatic number obtained is 6, representing six duty groups that do not overlap. This approach produces an optimal schedule that aligns with the academic schedules of HIMATIKA UNG members. The advantage of this algorithm lies in its efficiency in solving the problem and preventing overlapping schedules among members from the same class. The coloring process begins with the vertex of the highest degree as the initial step