PENJADWALAN MATA KULIAH MENGGUNAKAN PEWARNAAN GRAF DENGAN ALGORITMA LARGEST FIRST

Authors

https://doi.org/10.35974/jpd.v2i1.1067

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.

Article Metrics

Downloads

Download data is not yet available.

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

Published

2019-01-31

How to Cite

Rahadi, A. P. (2019). PENJADWALAN MATA KULIAH MENGGUNAKAN PEWARNAAN GRAF DENGAN ALGORITMA LARGEST FIRST. Jurnal Padegogik, 2(1), 1-13. https://doi.org/10.35974/jpd.v2i1.1067