PENJADWALAN MATA KULIAH MENGGUNAKAN PEWARNAAN GRAF DENGAN ALGORITMA LARGEST FIRST

Abstract: Scheduling courses at university is a multivariable problem that is complex because it involves many variables that have limitations, e.g. the classrooms, lecture hours, lecturer schedules, and the schedule of students who will take the course. For more than 40 years the problem has been examined to obtain an optimal solution or at least close to optimal. The purpose of these studies is to avoid clashes between variables involved in the scheduling. Some research focus on developing model and/or approaches, and the other focus on building a computer program. Graph coloring is the most widely used model for modeling and resolving courses scheduling problems. This paper is a literature study on several graph coloring algorithms with the largest first scheme, i.e. the Greedy algorithm and the Welsh-Powell algorithm that are used to model and solve scheduling problems in the university course. By understanding these various algorithms, it is expected that a model and solution can be formed that is suitable for the problem of scheduling courses at universities, especially in Indonesia. Keywords : Graph Coloring, Course Scheduling, Greedy, Welsh Powell.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