PEWARNAAN SISI GRAF BIPARTIT UNTUK PENJADWALAN KULIAH Studi Kasus: Penjadwalan Kuliah Jurusan Matematika FMIPA Untan Tahun 2013/2014

Fanti Setiawati, Evi Noviani, Bayu Prihandono.

Abstract


Suatu permasalahan yang kerap terjadi pada suatu perguruan tinggi adalah masalah penjadwalan kuliah. Mata kuliah yang harus dijadwalkan, akan selalu berbenturan dengan kendala-kendala  yang ada pada perguruan tinggi tersebut. Masalah penjadwalan ini dapat diselesaikan secara matematis dengan pewarnaan graf. Kendala dalam penyelesaian kasus penjadwalan ini dapat diinterpresentasikan dalam sebuah graf bipartit, yaitu graf yang dapat dipartisi menjadi dua himpunan berbeda. Simpul-simpul dari himpunan yang berbeda akan saling terhubung oleh sisi graf. Mata kuliah yang terdapat dalam kasus penjadwalan kuliah, akan terhubung dengan berbagai kendala, seperti hari-hari efektif perkuliahan, rentang waktu perkuliahan, ketersediaan dosen, dan ruangan. Graf  bipartit merepresentasikan keterhubungan berbagai kendala tersebut dalam beberapa tahap. Graf bipartit yang terbentuk pada tahap akhir kemudian diwarnai sisi-sisinya. Jumlah warna minimum yang diperlukan untuk mewarnai sisi graf bipartit menginterpretasikanjumlah ruangan minimum yang diperlukan untuk melaksanakan perkuliahan. Berdasarkan hasil pewarnaan tersebut, dapat diketahui jumlah ruangan minimum yang harus dipersiapkan untuk mengatur jadwal perkuliahan. Hasil dari penelitian ini dapat diketahui bahwa ruangan yang diperlukan untuk melaksanakan perkuliahan di jurusan Matematika FMIPA Untan adalah tiga ruangan. Output dari penelitian ini adalah sebuah rancangan jadwal perkuliahan.

Kata Kunci : teori graf, graf bipartit, pewarnaan graf, penjadwalan

Full Text:

PDF

Refbacks

  • There are currently no refbacks.