PENJADWALAN MATA KULIAH MENGGUNAKAN PEWARNAAN GRAF DENGAN ALGORITMA LARGEST FIRST
Abstract
Abstract: Scheduling courses at university is a multivariable problem that is complex because it involves many variables that have limitations, e.g. the classrooms, lecture hours, lecturer schedules, and the schedule of students who will take the course. For more than 40 years the problem has been examined to obtain an optimal solution or at least close to optimal. The purpose of these studies is to avoid clashes between variables involved in the scheduling. Some research focus on developing model and/or approaches, and the other focus on building a computer program. Graph coloring is the most widely used model for modeling and resolving courses scheduling problems. This paper is a literature study on several graph coloring algorithms with the largest first scheme, i.e. the Greedy algorithm and the Welsh-Powell algorithm that are used to model and solve scheduling problems in the university course. By understanding these various algorithms, it is expected that a model and solution can be formed that is suitable for the problem of scheduling courses at universities, especially in Indonesia.
Keywords : Graph Coloring, Course Scheduling, Greedy, Welsh Powell.
Downloads
References
Ariani, D. (2011). Optimasi Penjadwalan Mata Kuliah di Jurusan Teknik Informatika Menggunakan Particle Swarm Optimization. Retrieved 12 30, 2018, from https://www.researchgate.net/publication/277171205_OPTIMASI_PENJADWALAN
_MATA_KULIAH_DI_JURUSAN_TEKNIK_INFORMATIKA_PENS_DENGAN_
MENGGUNAKAN_ALGORITMA_PARTICLE_SWARM_OPTIMIZATION_PSO/
Astuti, S. (2011). Penyusunan Jadwal Ujian Matakuliah Dengan Algoritma Pewarnaan Graf Welch Powell. Jurnal Dian Vol. 11. https://publikasi.dinus.ac.id/index.php/dian/article/view/23/10
Burke, E. K. (2002). A New Adaptive Heuristic Framework for Examination Timetabling Problems. Working Group on Automated Timetabling. https://pdfs.semanticscholar.org/8947/aed4a6f3e8f33df9c404ac827efebd9a1132.pdf?_ga=2.169996576.1699274703.1569216537-1478071356.1569216537
Chauduri, A., & De, K. (2010). Fuzzy Genetic Heuristic for University Course Timetable Problem. International Journal of Advances in Soft Computing and its Applications.
Euler, L. (1741). Euler Solution to the Konigsberg Bridge Problem. Retrieved 12 30, 2018, from https://www.maa.org/press/periodicals/convergence/leonardeulers-solution-to-the-konigsberg-bridge-problem
Rosen, K. H. (2012). Discrete Mathematics and Its Applications, 7th Edition. New York: McGraw Hill.
Setiawan, H. (2015). Implementasi Algoritma Kunang-Kunang Untuk Penjadwalan Mata Kuliah di Universitas Ma Chung. Jurnal Buana Informatika.
Stevens, B. (2005). Graph Coloring and Their Properties. Retrieved 12 30, 2018, from https://www.whitman.edu/Documents/Academics/Mathematics/stevens.pdf
Werra, D. d. (1984). An Introduction to Timetabling. European Journal of Operation Research. https://doi.org/10.1016/0377-2217(85)90167-5
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2019 Jurnal Padegogik
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
The submitting author warrants that
- The submission is original and that she/he is the author of the submission together with the named co-authors; to the extend the submission incorporates text passages, figures, data, or other material from the work of others, the submitting author has obtained any necessary permission.
- Articles in this journal are published under the Creative Commons Share-Alike Attribution Licence (CC-BY-SA What does this mean?). This is to get more legal certainty about what readers can do with published articles, and thus a wider dissemination and archiving, which in turn makes publishing with this journal more valuable for you, the authors.
- By submitting an article the author grants to this journal the non-exclusive right to publish it. The author retains the copyright and the publishing rights for his article without any restrictions.
