Implementasi algoritma pewarnaan graf pada persoalan penjadwalan ujian

Format: Bachelors Doctoral
Terbitan: Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Indonesia , 2010
Subjects:
Online Access: http://lib.ui.ac.id/file?file=digital/20340133-S-Laninca Swarintha Christine.pdf
Daftar Isi:
  • Penjadwalan ujian merupakan tantangan yang dihadapi oleh universitas tiap semester atau tiap tahun. Tantangannya adalah untuk menjadwalkan ujian dari sekian banyak mata kuliah, yang diikuti oleh sejumlah mahasiswa (satu mahasiswa mungkin mengikuti lebih dari satu mata kuliah), ke dalam waktu yang terbatas dan jumlah ruangan yang terbatas. Dalam persoalan perwanaan graf, terdapat sifat yang dapat digunakan untuk merepresentasikan persoalan penjadwalan ujian, dimana tidak ada dua atau lebih simpul yang bertetangga mempunyai warna yang sama. Dalam persoalan penjadwalan ujian, tidak boleh terdapat dua ujian yang diikuti oleh minimal satu mahasiswa yang sama dilaksanakan pada waktu yang sama. Dalam persoalan pewarnaan graf, kondisi tersebut dipenuhi ketika dua simpul yang bertetangga yang merepresentasikan dua ujian tersebut mempunyai warna yang berbeda. Jumlah minimal warna yang diberikan pada suatu graf dapat merepresentasikan jumlah minimal hari yang digunakan dalam pelaksanaan ujian. Di dalam skripsi ini akan ditampilkan algoritma berbasis pewarnaan graf untuk mendapatkan jadwal ujian yang memenuhi aspek keadilan bagi mahasiswa, akurat, dan mempunyai periode waktu yang optimal. Kompleksitas dan efisiensi dari algoritma ini juga merupakan hal yang diperhatikan dalam skripsi ini.