Penerapan Metode Pewarnaan Graf dengan Algoritma Welch-Powell dalam Penjadwalan Perkuliahan

Abstract

Arrangement of lecture schedules at the university involves time sharing, lecturer availability, and classroom availability. One algorithm that can be used to make a good schedule without any conflict is the Welch Powell algorithm. In the Bachelor degree of Mathematics FMIPA USU there are 61 courses for odd semester and 44 courses for even semester in 2023/2024. Each semester is divided into 2 classes for required courses and there are optional courses in semester 5 as many as 5 optional courses, in semester 6 and 7 there are 12 optional courses. Therefore, graph coloring is needed to organize lecture schedules so that there are no conflict between the time sharing, lecturer availability, and classroom availability. The courses are represented in the form of a graph and afterwards the graph is colored with the Welch-Powell algorithm which produces 12 chromatic numbers or 12 colors so that there are 12 optimum sessions needed for scheduling lectures in odd and even semesters. Based on this result, the same color can be scheduled on the same day and same time with different classes.