PEMROGRAMAN PENJADUALAN SEMESTER PENDEK DI JURUSAN MATEMATIKA DENGAN ALGORITMA PEWARNAAN TITIK PADA GRAF

Abstract

Dalam penyusunan jadual Semester Pendek di Jurusan Matematika perlu diperhatikan elemen-elemen penjadualan yang ada antara lain jumlah mata kuliah dan SKS-nya, jumlah dosen dan mata kuliah yang diajarkan, serta jumlah mahasiswa yang mengikuti Matta kuliah yang ditawarkan. Dengan menganggap bahwa mata kuliah sebagai titik dalam graf, maka jika ada mahasiswa yang menempuh lebih dari dua mata kuliah maka mata kuliah tersebut tidak boleh dilaksanakan secara bersamaan. Cara menyelesaikan adalah dengan pewarnaan titik pada mata kuliah. Algoritma pewarnaan yang digunakan mempertimbangkan derajat titik dan keterhubungan titik. Jika titik mata kuliah terhubungkan dengan titik mata kuliah yang lain maka mata kuliah tersebut diwarnai berbeda yang berarti kedua mata kuliah tersebut dilaksanakan dalam periode waktu yang berbeda. Analisa pemrograman dengan bahasa komputer, adalah dengan mengubah masukan data menjadi matriks. Dengan menggunakan matriks, perhitungan derajat titik adalah menjumlahkan elemen baris dari matriks adjacent mata kuliah, dilanjutkan dengan pengurutan elemen baris berdasarkan derajat. Pewarnaan titik mata kuliah dalam matriks menggunakan algoritma pewarnaan penjadualan, lalu dibuat matriks jadual l hari yang elemen barisnya berisi warna yang berbeda. Proses selanjutnya modifikasi matriks jadual l hari menjadi jadual keseluruhan dengan mempertimbangkan jumlah SKS mata kuliah. Penyusunan jadual dengan komputerisasi dapat lebih cepat dan mudah dilakukan hanya dengan memasukan data-data yang akan dijadualkan.