PENJADWALAN MATA KULIAH MENGGUNAKAN PEWARNAAN GRAF DENGAN ALGORITMA LARGEST FIRST

Abstract

Penjadwalan mata kuliah di universitas merupakan masalah multivariabel yang kompleks karena melibatkan banyak variabel yang memiliki keterbatasan yaitu banyak ruang kelas, jam kuliah, jadwal dosen, hingga jadwal mahasiswa yang akan berkuliah. Selama lebih dari 40 tahun masalah tersebut telah diteliti untuk diperoleh solusi optimal atau setidaknya mendekati optimal. Tujuan penelitian-penelitian itu adalah menghindari adanya bentrok antara variabel-variabel yang terlibat di dalam penjadwalan, dengan menggunakan model, pendekatan, metode, hingga membangun program komputer. Pewarnaan graf merupakan model yang paling banyak digunakan untuk memodelkan dan menyelesaikan masalah penjadwalan mata kuliah. Tulisan ini merupakan studi literatur mengenai beberapa algoritma pewarnaan graf dengan skema largest first yaitu algoritma Greedy dan algoritma Welsh-Powell yang digunakan untuk memodelkan dan menyelesaikan masalah penjadwalan matakuliah. Dengan memahami berbagai algoritma tersebut, diharapkan dapat dibentuk suatu model dan solusi yang sesuai untuk masalah penyusunan jadwal mata kuliah di universitas, khususnya di Indonesia. Kata Kunci : Pewarnaan Graf, Penjadwalan Mata Kuliah, Greedy, Welsh Powell.