PENJADWALAN MATAKULIAH DENGAN PENDEKATAN PEWARNAAN GRAF DI UNIVERSITAS KRISTEN DUTA WACANA YOGYAKARTA

Abstract

Penjadwalan matakuliah merupakan suatu kegiatan untuk mengalokasikan matakuliah-matakuliah pada slot-slotwaktu tertentu dan pada ruang-ruang yang tersedia dengan memperhatikan batasan-batasan yang ada. Penjadwalanmatakuliah sulit dilakukan secara manual jika matakuliah yang ditawarkan jumlahnya banyak dan batasan-batasan yangharus diperhatikan banyak.Dalam membentuk suatu jadwal matakuliah yang dapat memenuhi batasan-batasan yang ada, penulis memodelkanmatakuliah ke dalam bentuk graf dan membagi proses pembentukan jadwal ke dalam 3 tahap yaitu tahap pembentukan paketmatakuliah, tahap alokasi paket matakuliah ke slot waktu dan tahap alokasi matakuliah ke ruang kelas.Hasil dari penelitian yang penulis lakukan adalah dengan pemodelan yang dibuat dan penerapan pewarnaan grafdapat membentuk paket matakuliah yang bebas dari tabrakan, kombinasi pewarnaan verteks dapat digunakan sebagaialternatif-alternatif solusi yang berguna untuk membuat seluruh matakuliah mendapatkan ruang kelas, paket-paketmatakuliah hasil pewarnaan graf dengan algoritma welch-powell tidak dapat secara langsung memenuhi batasan yang ada.Sehingga harus dilakukan beberapa modifikasi. Selain itu juga, ternyata sistem paket matakuliah yang dihasilkanmenyebabkan ketergantungan dalam hal alokasi ke slot waktu.