Penerapan Pewarnaan Graf Menggunakan Algoritma Welch-Powell pada Penjadwalan Mata Pelajaran

Studi Kasus: Penjadwalan Mata Pelajaran SMP Terpadu Rea Kaltim Kembang Janggut

Abstract View: 35, PDF Download: 27

Authors

  • Monica Yeyen Yusak Universitas Mulawarman
  • Desi Febriani Putri Universitas Mulawarman
  • Syaripuddin Syaripuddin Universitas Mulawarman

DOI:

https://doi.org/10.32665/james.v7i2.2272

Keywords:

Penjadwalan, Algoritma Welch-powell, Pewarnaan graf, Scheduling, Graph coloring

Abstract

Penjadwalan mata pelajaran adalah unsur penting dalam manajemen sekolah yang efisien. Pewarnaan graf digunakan sebagai pendekatan untuk menyelesaikan permasalahan pada proses penyusunan penjadwalan menggunakan algoritma welch-powell. Pada penelitian ini, dilakukan peenjadwalan penyusunan mata pelajaran di SMP Terpadu Rea Kaltim Kembang Janggut menggunakan pewarnaan graf. Algoritma yang digunakan adalah algoritma welch-powell, untuk menyusun penjadwalan yang meminimalkan bentrok antara mata pelajaran yang memiliki jadwal tumpang tindih. Penelitian ini bertujuan untuk mengetahui model mata pelajaran dan guru pengampu kedalam bentuk graf, serta untuk mengetahui hasil dari pewarnaan graf menggunakan algoritma welch-powell di SMP Terpadu Rea Kaltim Kembang Janggut. Penelitian ini berfokus pada pewarnaan titik menggunakan algoritma welch-powel, jadi untuk setiap titik yang bertetangga tidak boleh memiliki warna yang sama. Data pada penelitian ini mencakup informasi tentang guru pengampu mata pelajaran, jumlah kelas, dan jumlah mata pelajaran. Berdasarkan hasil penelitian diketahui bahwa pewarnaan graf dengan algoritma welch-powell dapat digunakan pada penyusunan penjadwalan mata pelajaran SMP Terpadu Rea Kaltim Kembang Janggut. Pada implementasi pewarnaan graf diperoleh bilangan kromatik adalah 5 atau   yang terdiri dari warna merah, kuning, hijau, ungu, dan biru.

References

Y. G. Nengsih dan M. Kom, Matematika Diskrit. Surabaya: Jakad Media Publishing, 2020.

S. Wibisono, Matematika Diskrit. Yogyakarta: Graha Ilmu, 2008.

M. Mahmudah dan T. N. Irawati, “Aplikasi Pewarnaan Graf Terhadap Pembuatan Jadwal Ujian Semester di Jurusan Pendidikan Matematika Universitas Islam Jember,” KadikmA, vol. 9, no. 2, hal. 12–21, 2018.

H. Afriantini dan F. Fran, “Pewarnaan Simpul, Sisi, Wilayah Pada Graf Dan Penerapannya,” Bimaster Bul. Ilm. Mat. Stat. dan Ter., vol. 8, no. 4, 2019.

P. Gupta dan O. Sikhwal, “A Study Of Vertex-Edge Coloring Techniques With Application,” Int. J. Core Eng. Manag., vol. 1, no. 2, hal. 27–32, 2014.

S. Astuti, “Penyusunan Jadwal Ujian Mata Kuliah Dengan Algoritma Pewarnaan Graf Welch Powell,” J. Dian, vol. 11, no. 1, 2011.

A. A. Pratama, M. Bettiza, dan A. Uperiati, “Aplikasi Penjadwalan Mata Pelajaran Menggunakan Algoritma Genetika,” Student Online J. Umr., vol. 2, no. 1, hal. 97–105, 2021.

L. D. Putri, “Penerapan Pewarnaan Graf Menggunakan Algoritma Welch Powell Dengan Pemrograman Python Untuk Menyusun Jadwal Mata Pelajaran di SMP Kansius Pakem. (Skripsi),” Universitas Sanata Dharma.

A. M. Nasir dan D. Setyawan, “Optimalisasi Penjadwalan Mata Kuliah Menggunakan Teori Pewarnaan Graf,” Prox. J. Penelit. Mat. dan Pendidik. Mat., vol. 5, no. 1, hal. 57–69, 2022.

A. W. Bustan dan M. R. Salim, “Penerapan Pewarnaan Graf Menggunakan Algoritma Welch Powell untuk Menentukan Jadwal Bimbingan Mahasiswa,” J. THEOREMS (The Orig. Res. Math., vol. 4, no. 1, hal. 79–86, 2019.

E. Rosely dan P. Mayadewi, “Penerapan Algoritma Welch Powell Dengan Pewarnaan Graph Pada Penjadwalan Mata Pelajaran SMA,” Semin. Nas. Sist. Inf. Indones., hal. 334–338, 2016.

D. T. Puspasari dan S. Dafik, D. Slamin, “Pewarnaan Titik pada Graf Khusus Operasi dan Aplikasinya,” Universitas Jember.

C. Pricilla, Perenapan Pewarnaan Graf Dalam Penentuan Jadwal Perkuliahan. Bandung: Institut Teknologi Bandung, 2015.

T. Kristanto, T. Indriyani, dan N. M. Khoiroh, “Penjadwalan Ruang Kuliah Menggunakan Vertex Graph Coloring Dan Simulated Annealing,” Pros. Semin. Nas. Sains dan Teknol. Terap., hal. 61–68, 2016.

U. Maftukhah, S. Amiroch, dan M. S. Pradana, “Implementasi Algoritma Greedy Pada Pewarnaan Wilayah Kecamatan Sukodadi Lamongan,” UJMC (Unisda J. Math. Comput. Sci., vol. 6, no. 2, hal. 29–38, 2020.

Downloads

Published

2024-10-10

How to Cite

[1]
M. Y. Yusak, D. F. Putri, and S. Syaripuddin, “Penerapan Pewarnaan Graf Menggunakan Algoritma Welch-Powell pada Penjadwalan Mata Pelajaran: Studi Kasus: Penjadwalan Mata Pelajaran SMP Terpadu Rea Kaltim Kembang Janggut”, JaMES, vol. 7, no. 2, pp. 177–183, Oct. 2024.
Abstract View: 35, PDF Download: 27