Penjadwalan Mata Pelajaran dengan Pewarnaan Graf Menggunakan Algoritma Greedy

Abstract

Penjadwalan mata pelajaran merupakan salah satu permasalahan penting dalam dunia pendidikan yang bertujuan untuk mengatur waktu pembelajaran secara efektif tanpa terjadi benturan antar mata pelajaran, dan guru. Permasalahan ini termasuk dalam kategori optimasi kombinatorial yang kompleks, sehingga diperlukan metode yang efisien untuk menyelesaikannya. Salah satu pendekatan yang dapat digunakan adalah pewarnaan graf dengan algoritma greedy.

Dalam penelitian ini, setiap mata pelajaran direpresentasikan sebagai simpul (vertex), sedangkan konflik antar mata pelajaran, seperti penggunaan guru pada waktu bersamaan, direpresentasikan sebagai sisi (edge). Proses penjadwalan dilakukan dengan menerapkan algoritma greedy pada pewarnaan graf, di mana setiap simpul diberi warna yang merepresentasikan slot waktu tertentu dengan aturan bahwa simpul yang bertetangga tidak boleh memiliki warna yang sama dan pewarnaan dimulai dari urutan subgraph lengkap dengan derajat tertinggi terlebih dahulu..

Hasil penerapan algoritma greedy menunjukkan bahwa metode ini mampu menghasilkan jadwal yang valid dengan waktu komputasi yang relatif cepat. Meskipun tidak selalu menghasilkan solusi optimal global, pendekatan ini cukup efektif dan praktis untuk digunakan dalam skala permasalahan nyata. Dengan demikian, pewarnaan graf menggunakan algoritma greedy dapat menjadi solusi alternatif dalam penyusunan jadwal mata pelajaran yang efisien dan minim konflik