Pewarnaan Graf dalam Penjadwalan Mata Pelajaran SMP Menggunakan Algoritma DSATUR

Abstract

Penjadwalan mata pelajaran merupakan pekerjaan rutin dalam sistem akademik di sekolah yang dilakukan setiap kali menghadapi semester baru. Proses ini sering menghadapi tantangan berupa bentroknya waktu mengajar antar guru atau kelas. Pewarnaan graf dapat menjadi solusi untuk mengatasi masalah tersebut. Penelitian ini bertujuan memodelkan masalah penjadwalan mata pelajaran menjadi graf dan mengimplementasi pewarnaan graf menggunakan algoritma DSATUR. Algoritma DSATUR adalah metode pewarnaan graf heuristik yang didasarkan pada derajat kejenuhan dari setiap simpul. Hasil penelitian menunjukkan bahwa graf yang direpresentasikan dari masalah penjadwalan memiliki derajat simpul maksimum sebesar delapan dan dapat diwarnai dengan empat warna. Pendekatan ini menyelesaikan masalah penjadwalan dengan baik, dalam hal ini tidak ada tumpang tindih waktu mengajar.

Subject scheduling is a routine work in the academic system in schools that is carried out every time a new semester begins. This process often faces challenges in the form of clashes in teaching time between teachers or classes. Graph coloring can be a solution to overcome this problem. This study aims to model the subject scheduling problem into a graph and implement graph coloring using the DSATUR algorithm. The DSATUR algorithm is a heuristic graph coloring method based on the degree of saturation of each node. The results of the study show that the graph represented by the scheduling problem has a maximum node degree of eight and can be colored with four colors. This approach solves the scheduling problem well, in this case there is no overlap in teaching time.