Perbandingan Algoritma Welch Powell dan Algoritma Greedy dalam Optimasi Penjadwalan Ruang Kuliah Semester Genap Fakultas Teknik

Yohana Christela Oktaviani, Yosefina Finsensia Riti

Abstract


Penjadwalan merupakan suatu proses yang dilaksanakan secara terstruktur untuk mengefisiensikan waktu kerja serta menghindari terjadinya constraint  dalam suatu permasalahan. Penjadwalan ini banyak diterapkan dalam dunia pendidikan, salah satunya ialah penyusunan penjadwalan mata kuliah. Penyusunan penjadwalan sendiri perlu dioptimalisasikan agar proses perkuliahan dapat berjalan dengan lancar tanpa adanya constraint  antar mata kuliah. Seperti yang terjadi pada Fakultas Teknik, Universitas Katolik Darma Cendika, dimana dalam penyusunan penjadwalan ini belum terdapat informasi ruangan kuliah. Oleh sebab itu, penulis menyusun jurnal optimasi penjadwalan ruang kuliah dengan membandingkan kinerja antara algoritma Welch Powell dengan algoritma Greedy. Data yang digunakan dalam penelitian ini ialah sejumlah 109 mata kuliah yang tersebar dari 4 Prodi Fakultas Teknik, yakni Prodi Teknik Industri, Prodi Arsitektur, Prodi Ilmu Informatika, serta Prodi Akupuntur dan Pengobatan Herbal. Metode yang digunakan dalam penelitian ini ialah metode komparatif yang diterapkan pada pewarnaan simpul graf, dimana  parameter yang digunakan ialah waktu pengeksekusian, kompleksitas algoritma, serta perhitungan algoritma  secara manual. Berdasarkan penelitian yang telah dilakukan, diperoleh hasil 7 warna kromatik yang selanjutnya diterapkan pada 7 ruang perkuliahan Fakultas Teknik.  


Keywords


Penjadwalan; Optimasi; Algoritma Welch Powell; Algoritma Greedy; Constraint

Full Text:

PDF (Indonesian)

References


K. Harianto and T. S. Eiva Fatdha, “Penerapan Pewarnaan Simpul Graf untuk Menentukan Jadwal Ujian Skripsi pada STMIK Amik Riau Menggunakan Algoritma Welch-powell,” SATIN - Sains dan Teknol. Inf., vol. 1, no. 2, p. 48, 2016, doi: 10.33372/stn.v1i2.27.

A. N. Silitonga and D. Apdillah, “Penjadwalan Perkuliahan Dengan Metode Vertex Graph Coloring Dan Simulated Annealing,” J. Ind. Manuf. Eng., vol. 1, no. 2, p. 56, 2019, doi: 10.31289/jime.v1i2.2328.

Y. Rusdiana and A. Maulani, “Algoritma Welch-Powell Untuk Pewarnaan Graf pada Penjadwalan Perkuliahan,” Sci. Phys. Educ. J., vol. 3, no. 1, pp. 37–47, 2019, doi: 10.31539/spej.v3i1.915.

D. Hendrikx et al., “Using graph theory to assess the interaction between cerebral function, brain hemodynamics, and systemic variables in premature infants,” Complexity, vol. 2018, 2018, doi: 10.1155/2018/6504039.

a. W. Lund et al., “Quantification of spatial parameters in 3D cellular constructs using graph theory,” J. Biomed. Biotechnol., vol. 2009, 2009, doi: 10.1155/2009/928286.

R. Oddang and H. Hamrul, “Pembangunan Sistem Penjadwalan Kuliah Menggunakan Algoritma Pewarnaan Graf,” J. Ilm. d’ComPuterE, vol. 1, pp. 50–55, 2011.

B. Muflikhudin and D. Pratama, “Teknik Pewarnaan Graf Pada Penjadwalan Piket Osis Dengan Algoritma Welch-Powell Pada Smp Negeri 2 Kemranjen,” FUSIOMA (Fundamental Sci. J. Math. , vol. 1, no. 2, pp. 8–13, 2021, [Online]. Available: https://jurnal.unupurwokerto.ac.id/index.php/fusioma/article/view/14.

L. Maro and L. K. S. Purab, “Penerapan Konsep Pewarnaan Graf dalam Penyusunan Jadwal Perkuliahan Menggunakan Metode Algoritma Welch-Powell pada Program Studi Teknik Informatika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Tribuana Kalabahi,” J. Wahana Pendidik., vol. 07, no. 06, pp. 193 – 197, 2021, doi: 10.5281/zenodo.5574383.

F. Mahardika and H. Marcos, “Penerapan Algoritma Graf Welch Powel pada Penjadwalan Mata Kuliah dan Jadwal Asisten Study Kasus Forum Asisten STMIK AMIKOM Purwokerto,” Simetris J. Tek. Mesin, Elektro dan Ilmu Komput., vol. 8, no. 2, p. 825, 2017, doi: 10.24176/simet.v8i2.1208.

a. M. Nasir, Faisal, and Dedy Setyawan, “Optimalisasi Penjadwalan Mata Kuliah Menggunakan Teori Pewarnaan Graf,” Prox. J. Penelit. Mat. dan Pendidik. Mat., vol. 5, no. 1, pp. 57–69, 2022, doi: 10.30605/proximal.v5i1.1398.

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

Y. Xiao, G. Dong, and X. Song, “Data-Based Reconstruction of Chaotic Systems by Stochastic Iterative Greedy Algorithm,” Math. Probl. Eng., vol. 2020, 2020, doi: 10.1155/2020/6718304.

E. Al Farisi, Olief Ilmandira Ratu, “Penerapan Pewarnaan Graf pada Penjadwalan Mengajar Dosen Pendidikan Matematika Universitas Nurul Jadid,” J. Mat., vol. 11, no. 1, pp. 10–19, 2021, doi: 10.24843/JMAT.2021.v11.i01.p132.

Y. Shao, S. Chu, T. Zhang, Y. J. Yang, and T. Yu, “A Greedy Sampling Design Algorithm for the Modal Calibration of Nodal Demand in Water Distribution Systems,” Math. Probl. Eng., vol. 2019, 2019, doi: 10.1155/2019/3917571.

Y. Zhu, Q. Chen, J. Liu, and X. Tian, “Fast Adaptive Character Animation Synthesis Based on Greedy Algorithm,” Complexity, vol. 2021, pp. 1–11, 2021, doi: 10.1155/2021/6685861.

P. Lu, T. Hu, H. Wang, R. Zhang, and G. Wu, “G-CAS: Greedy Algorithm-Based Security Event Correlation System for Critical Infrastructure Network,” Secur. Commun. Networks, vol. 2021, 2021, doi: 10.1155/2021/3566360.

A. P. Rahadi, “Penjadwalan Mata Kuliah Menggunakan Pewarnaan Graf Dengan Algoritma Largest First,” J. Padegogik, vol. 2, no. 1, pp. 1–13, 2019.

R. Syam, H. Ihsan, and a. Asman, “Aplikasi Pewarnaan Graf dengan Algoritma Recursive Largest First pada Penjadwalan Mata Kuliah,” J. Math. Comput. Stat., vol. 2, no. 1, p. 63, 2020, doi: 10.35580/jmathcos.v2i1.12461.

S. Astuti, “Penyusunan Jadwal Ujian Mata Kuliah dengan Algoritma Pewarnaan Graf Welch Powell,” J. Dian, vol. 11, no. 1, pp. 68–74, 2011, [Online]. Available: publikasi.dinus.ac.id.

Niarama, B. Pramono, and L. . Tajidun, “Aplikasi penjadwalan menggunakan algoritma welch powell (studi kasus : sma muhammadiyah kendari),” semanTIK, vol. 4, no. 1, pp. 1–6, 2018.




DOI: http://dx.doi.org/10.51213/jimp.v7i3.560

Copyright (c) 2023 Yohana Christela Oktaviani, Yosefina Finsensia Riti

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