Perbandingan Pewarnaan Graf Dengan Algoritma Welch Powell dan Algoritma Tabu Search Dalam Penjadwalan Seminar Proposal
Abstract
Penelitian ini bertujuan untuk menemukan penyelesaian dan penerapan Algoritma Welch Powell dan Algoritma Tabu Search dalam menentukan jadwal seminar proposal. Penelitian ini merupakan penelitian deskriptif dengan pendekatan kuantitatif. Teknik pengumpulan data menggunakan wawancara dan telaah dokumen. Kedua algoritma menghasilkan simulasi penjadwalan yang berbeda. Perbedaan hasil ini ditunjukkan oleh jumlah bilangan kromatik yang didapatkan pada bulan November. Melalui Algoritma Welch Powell, bilangan kromatik yang dihasilkan adalah 26, sedangkan melalui Algoritma Tabu Search menghasilkan bilangan kromatik lebih minimum yakni 22. Sementara itu dari hasil percobaan, Algoritma Welch Powell lebih unggul karena mudah diimplementasikan dan menghasilkan konflik lebih sedikit. Berdasarkan hasil uji keakuratan menggunakan Software Microsoft Excel, simulasi penjadwalan menunjukkan bahwa tidak ditemukan dosen yang menguji diwaktu yang sama. Artinya hasil implementasi Algoritma Welch Powell dan Algoritma Tabu Search terbukti valid dan tidak ada jadwal yang bentrok.
References
K. R. Baker, “Scheduling a full-time workforce to meet cyclic staffing requirements,” Manage. Sci., vol. 20, no. 12, pp. 1561–1568, 1974.
C. Pricilla, “Penerapan Pewarnaan Graf Dalam Penentuan Jadwal Perkuliahan,” Institut Teknologi Bandung, 2015.
Novian Riskiana Dewi, “Penerapan Pewarnaan Graf Terhadap Penyusunan Jadwal Seminar Proposal Skripsi di Prodi Pendidikan Matematika UIN Raden Intan Lampung,” Buana Mat. J. Ilm. Mat. dan Pendidik. Mat., vol. 10, no. 1, pp. 103–112, 2020, doi: 10.36456/buanamatematika.v10i1.2610.
S. Hizriani, “Penerapan Algoritma Welch Powell untuk Melakukan Graph Colouring pada Peta Kabupaten Serdang Bedagai,” Doctoral Dissertation, 2017.
R. R. Gani, “Penerapan Pewarnaan Titik Pada Graf Untuk Menyusun Jadwal Pelajaran (Studi Kasus MI Al Wathoniyyah 02 Semarang).,” Universitas Negeri Semarang, 2018.
I. Suryani, “Implementasi Masalah Pewarnaan Graph Dengan Algoritma Tabu Search Pada Penjadwalan Kuliah,” Universitas Negeri Malang, 2013.
Betrianis and P. T. Aryawan, “Penerapan Algoritma Tabu Search dalam Penjadwalan Job Shop,” Makara Teknol., vol. 7, no. 3, pp. 107–112, 2003.
A. W. Bustan and 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, pp. 79–86, 2019.
E. C. L. Tobing, “Analisis Jaringan Komunikasi #Percumalaporpolisi Di Twitter,” UPN Veteran Jawa Timur, 2022.
Supiyandi and M. Eka, “Penerapan Teknik Pewarnaan Graph Pada Penjadwalan Ujian Dengan Algoritma Welch-Powell,” Algoritm. J. Ilmu Mat. dan Komput., vol. 3, no. 1, pp. 58–63, 2018, [Online]. Available: http://jurnal.uinsu.ac.id/index.php/algoritma/article/view/3153
S. Lipschutz and M. Lipson, Schaum’s Outlines Of: Theory and Problems of Discrete Mathematics (Third Edition). Doi: http://dx.doi.org/10.1036/0071470387. New York: Mc Graw Hill, 2007.
M. Gendreau and J. Y. Potvin, Handbook of metaheuristics. New York: Springer, 2010.
C. H. Aladag and G. Hocaoglu, “A tabu search algorithm to solve a course timetabling problem,” Hacettepe J. Math. Stat., pp. 53–64, 2007.
S. Almirawati and B. Rahadjeng, “Penerapan Pewarnaan Titik Graf Pada Penyusunan Jadwal Seminar Proposal Di Jurusan Bahasa Inggris Uin Sayyid Ali Rahmatullah Tulungagung,” MATHunesa J. Ilm. Mat., vol. 10, no. 2, pp. 249–257, 2022, doi: 10.26740/mathunesa.v10n2.p249-257.
M. Firdaus, “Aplikasi pewarnaan Graf menggunakan Algoritma Welch-Powell pada penyusunan jadwal mata kuliah prodi matematika UIN Sunan Ampel Surabaya,” UIN Sunan Ampel Surabaya, 2020.
R. W. Permatasari, “Aplikasi Graph Coloring Dengan Algoritma Tabu Search Dalam Penyelesaian Masalah Penjadwalan kereta Api,” UIN Sunan Kalijaga Yogyakarta, 2016.
K. Harianto and T. S. E. 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, 2016.
Copyright (c) 2024 Rizky Anggraini, Nalsa Cintya Resti, Nur Fadilatul Ilmiyah
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Authors who publish with this journal agree to the following terms:
1. Copyright on any article is retained by the author(s).
2. The author grants 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.
3. 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.
4. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
5. The article and any associated published material is distributed under the Creative Commons Attribution-ShareAlike 4.0 International License