Perpustakaan Digital ITB

Pada tugas akhir ini dibahas tentang pembuatan jadwal kuliah untuk Program Studi Sarjana Matematika, Program Studi Magister Matematika, Program Studi Magister Aktuaria, dan Program Studi Magister Pengajaran Matematika, Institut Teknologi Bandung. Ada beberapa batasan yang dipertimbangkan dalam pembuatan jadwal tersebut. Adapun batasan-batasan tersebut berhubungan dengan tiga hal yaitu dosen, mahasiswa, dan ruangan. Dosen tidak boleh mengajar dua atau lebih mata kuliah pada jadwal yang sama dan dosen sedapat mungkin tidak mengajar lebih dari dua mata kuliah per hari. Mata kuliah - mata kuliah yang setingkat tidak dijadwalkan pada jadwal yang sama dan diusahakan tidak ada dua mata kuliah pada dua tingkat berurutan pada jadwal yang sama. Banyak ruangan yang dapat dipakai pada satu jadwal terbatas. Metode yang digunakan untuk menyelesaikan masalah tersebut yaitu pewarnaan titik pada graf. Setiap titik pada graf mewakili satu mata kuliah yang akan dijadwalkan. Jika dua mata kuliah yang berbeda tidak boleh dijadwalkan pada satu jadwal yang sama, maka titik-titik yang mewakili kedua mata kuliah tersebut dihubungkan oleh sebuah sisi dan kedua titik tersebut tidak boleh diwarnai dengan warna yang sama. Setiap mata kuliah dengan warna titik yang sama dapat dijadwalkan pada jadwal yang sama selagi masih tersedia ruangan. Algoritma yang dikembangkan merupakan perumuman dari algoritma pewarnaan graf Welsh-Powell supaya batasan-batasan di atas terakomodasi.