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

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

Abstract View: 72, PDF Download: 76

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.

Issue

Vol. 7 No. 2 (2024): Journal of Mathematics Education and Science

Section

Articles

Categories

License

Copyright (c) 2024 Journal of Mathematics Education and Science

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

Authors who publish with this journal agree to the following terms:

  1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this journal.
  2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial publication in this journal.
  3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) before and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work
Abstract View: 72, PDF Download: 76