PENERAPAN KONSEP PEWARNAAN GRAF DALAM PENJADWALAN PEMBELAJARAN DI SMAN 1 KOPANG

Abstract

Scheduling is a way to determine the time and place an activity will be carried out. A learning schedule that is free from overlapping scheduling problems needs to be available before teaching and learning activities begin so that the early teaching and learning activities can take place effectively. One way that can be used to overcome the problem of overlapping learning scheduling is to use the concept of graph coloring contained in the topic of graph theory. Therefore, the goal to be achieved in this study is to obtain a schedule of teaching and learning activities that are free from overlapping scheduling at SMAN 1 Kopang by applying the concept of graph coloring. The type of research used is applied research. Based on the scheduling data, we get a neighboring matrix with a size of 224×224 and a chromatic number of 22. The determination of neighboring matrices using the help of the Excel VBA programming language. The schedule-making begins by creating a scheduling conflict graph based on the lesson schedule data, then the graph obtained will be colored using Welch Powell's algorithm. After the coloring results are obtained, a learning schedule can be arranged based on the coloring results. Subjects of the same color can be scheduled at the same time and vice versa. The lesson schedule produced in this study requires six additional time slots so that the lesson schedule is free from scheduling overlap because the chromatic number obtained in graph coloring is greater than the available time slots at SMAN 1 Kopang.