Penerapan Konsep Pewarnaan Graf Dalam Penyusunan Jadwal Kegiatan Belajar Mengajar Di SMKN

Laili Gadis Hasanah; Sripatmi Sripatmi; Amrullah Amrullah; Baidowi

doi:10.29303/griya.v2i2.177

Laili Gadis Hasanah Universitas Mataram
Sripatmi Sripatmi Universitas Mataram
Amrullah Amrullah Universitas Mataram
Baidowi Universitas Mataram

DOI: https://doi.org/10.29303/griya.v2i2.177

Keywords: Algoritma Largest Degree Ordering, graph coloring, Scheduling

Abstract

The problem of scheduling learning activities at SMKN 4 Mataram is the same teachers are scheduled at the same time in two class or more. The coloring graph concept can be used to find out the causes of the scheduling problems at SMKN 4 Mataram. Based on result of the application coloring graph concept generated to the chromatic number is 23 with slots number is 46 which is smaller than 55 or time slots at SMKN 4 Mataram. Because slots of chromatic number are smaller than the time slots at SMKN 4 Mataram, it is known that the causes of scheduling problems at SMKN 4 Mataram are wrong scheduling way. One of solution to this problem is to compile a schedule based on the coloring graph concept by mapping 419 subjects with 84 teachers and 55 time slots spread from Monday to Saturday. In applying the coloring graph concept, the Largest Degree Ordering (LDO) algorithm is used. It is because this algorithm is simpler than other algorithms.

Author Biographies

Sripatmi Sripatmi, Universitas Mataram

Dosen Pendidikan Matematika

Amrullah Amrullah, Universitas Mataram

Dosen Pendidikan Matematika

Baidowi , Universitas Mataram

Dosen Pendidikan Matematika

References

Astuti, S. (2011). Penyusunan Jadwal Ujian Mata Kuliah Dengan Algoritma Pewarnaan Graf Welch Powell. Jurnal Dian , 11 (1), 68-74.
Daniel, F., & Taneo, P. N. (2019). Teori Graf. Yogyakarta: Deepublish.
Dewi, F. K. S. (2014). Pembangunan Perangkat Lunak Pembangkit Jadwal Kuliah dan Ujian dengan Metode Pewarnaan Graf. Buana Informatika. I (1), 57-68.
Fahrudin, A. (2014). Penjadwalan Matakuliah Otomatis pada Perguruan Tinggi menggunakan simulated annealing dan vertex graph coloring dengan algoritma largest degree ordering dan saturated degree ordering
Kebudayaan, D. P. (t.thn.). Dipetik Desember 12, 2019, dari https://kbbi.kemendikbud.go.id
Manik, N. I. (2013). Matematika Diskrit Soal-Jawab. Bogor: Graha Ilmu.
Manongga, D., & Nataliani, Y. (2013). Matematika Diskrit. Salatiga: Prenadamedia Group.
Munir, R. (2016). Matematika Diskrit. Bandung: Informatika Bandung.
Niarma, Pramono, B., & Tajidun, L. (2018). Aplikasi Penjadwalan Menggunakan Algoritma Welch Powell (Studi Kasus : SMA Muhammadiyah Kendari). semanTIK , 4 (1), 1-6.
Purwanto. (2010). Matematika Diskrit. Malang: IKIP Malang.
Sari, K. P., Armiati, & Mirna. (2014). Perbandingan Algoritma Pewarnaan LDO, SDO, dan IDO pada Graf Sederhana. Jurnal Matematika UNPAD , 1-9.
Sari, P. W., Yulianti, L., & Narwen. (2017). Penjadwalan Kuliah dengan Algoritma Welsh-powell (Studi Kasus: Jurusan Matematika FMIPA UNAND). Jurnal Matematika UNAND , VI (I), 134-141.
Setyawan, Y. (2014). Visualisasi Graf Dan Algoritma-Algoritma Dalam Teori Graf Menggunakan Beberapa Paket Software. Prosiding Seminar Nasional Aplikasi Sains & Teknologi (SNAST)2014 , 259-268.
Sunarni, T., Bendi, R., & Alfian, A. (2018) Penerapan Teknik Pewarnaan Simpul Graf Pada Permasalahan Penjadwalan Kuliah. Prosiding Ritekra. 8 (1), 84-91
Yahya, N. I., Zakaria, P., & Yahya, L. (2013). Penerapan Konsep Graf Dalam Penyusunan Jadwal Perkuliahan Di Jurusan Pendidikan Matematika FMIPA UNG. Jurnal Matematika UNG , 1-12.
Wijaya, A. (2009). Matematika Diskrit. Bandung: Politeknik Telkom.