Efisiensi Pengaturan Jadwal Perkuliahan Menggunakan Pendekatan Pewarnaan Graf

Syamsyida Rozi, Niken Rarasati, Rosda Syelly

Abstract


The schedule for each course should be arranged such that the course taken by the same student or involving the same lecturer are not scheduled on the same day and time. This is to avoid conflicting schedules for students and lecturers. In the odd semester academic year 2021/2022, there were 23 courses scheduled at the study program of Mathematics, Universitas Jambi. The students in semesters 1 and 5 were divided into 2 classes, respectively, due to a large number of students in that semester. Therefore, the arrangement of the course schedule was getting more complicated. This research aimed to arrange the course schedule so that there is no clash by using the graph coloring approach. This research was classified as case study research and applied the descriptive method. The arrangement of the course schedule began with modeling the problem in the form of a graph and then using the Welch Powell algorithm to color the vertices in the graph. The graph consists of 36 vertices and 215 edges. By applying the Welch-Powell algorithm, the chromatic number obtained was 10, which means there are 10 optimum sessions or 10 minimum sessions of the course schedule in the odd semester in the Mathematics study program Universitas Jambi. Based on this result, the grouping of courses can be obtained that can be scheduled on the same day and at the same time.


Keywords


Schedule; Graph; Graph Coloring; Welch-Powell Algorithm

Full Text:

PDF

References


C. H. Meiliana and D. Maryono, “Aplikasi Pewarnaan Graf Untuk Optimalisasi Pengaturan Traffic Light Di Sukoharjo,” J. Ilm. Pendidik. Tek. dan Kejuru., vol. 10, no. 1, 2017, doi: 10.20961/jiptek.v7i1.12662.

D. A. Setiawan, A. Suyitno, and I. Artikel, “Penerapan Graf Pada Persimpangan Menggunakan Algoritma Welsh-Powel Untuk Optimalisasi Pengaturan Traffic Light,” Unnes J. Math., vol. 5, no. 2, pp. 144–152, 2016.

A. R. Komijan and M. N. Koupaei, “A new binary model for university examination timetabling: a case study,” J. Ind. Eng. Int., vol. 8, no. 1, pp. 1–7, 2012, doi: 10.1186/2251-712X-8-28.

S. Daskalaki, T. Birbas, and E. Housos, “An integer programming formulation for a case study in university timetabling,” Eur. J. Oper. Res., vol. 153, no. 1, pp. 117–135, 2004, doi: 10.1016/S0377-2217(03)00103-6.

A. Cerdeira-Pena, L. Carpente, A. Fariña, and D. Seco, “New approaches for the school timetabling problem,” 7th Mex. Int. Conf. Artif. Intell. - Proc. Spec. Sess. MICAI 2008, no. December, pp. 261–267, 2008, doi: 10.1109/MICAI.2008.19.

M. Yulistiana, D. Chaerani, and E. Lesmana, “Penerapan Metode Hungarian dalam Penentuan Penjadwalan Matakuliah Optimal (Studi Kasus: Departemen Matematika Universitas Padjadjaran Semester Ganjil 2013-2014),” J. Mat. Integr., vol. 11, no. 1, pp. 45–64, 2015, doi: 10.24198/jmi.v11i1.9391.

W. Tahir, D. Wungguli, and M. R. F. Payu, “Optimasi Penjadwalan Waktu Kerja Menggunakan Integer Programming,” Euler J. Ilm. Mat. Sains dan Teknol., vol. 7, no. 2, pp. 51–55, 2019, doi: 10.34312/euler.v7i2.10343.

E. K. Burke, B. McCollum, A. Meisels, S. Petrovic, and R. Qu, “A graph-based hyper-heuristic for educational timetabling problems,” Eur. J. Oper. Res., vol. 176, no. 1, pp. 177–192, 2007, doi: 10.1016/j.ejor.2005.08.012.

M. T. M. Perera and G. H. J. Lanel, “A Model to Optimize University Course Timetable Using Graph Coloring and Integer Linear Programming,” IOSR J. Math., vol. 12, no. 05, pp. 13–18, 2016, doi: 10.9790/5728-1205031318.

K. H. Rosen, Discrete Mathematics and Its Aplications, 7th ed. New York: McGraw-Hill, 2012.

E. Kreyszig, Advanced Engineering Mathematics, 10th ed. Wiley, 2011.

C. Vasudev, Graph Theory with Applications. New Delhi: New Age International (P) Limited, 2006.

R. Munir, Matematika Diskrit, Rev ke 5. Bandung: Informatika Bandung, 2016.

R. J. Wilson, Introduction to Graph Theory, 4th ed. Longman, 1996.

N. Deo, Graph Theory with Applications Engineering and Computer Science. New York: Prentice-Hall, 1974.




DOI: https://doi.org/10.34312/euler.v10i1.14034

Refbacks

  • There are currently no refbacks.


Copyright (c) 2022 Syamsyida Rozi, Niken Rarasati, Rosda Syelly

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

Euler : Jurnal Ilmiah Matematika, Sains dan Teknologi has been indexed by:

                         EDITORIAL OFFICE OF EULER : JURNAL ILMIAH MATEMATIKA, SAINS, DAN TEKNOLOGI

 Department of Mathematics, Faculty of Mathematics and Natural Science, Universitas Negeri Gorontalo
Jl. Prof. Dr. Ing. B. J. Habibie, Tilongkabila, Kabupaten Bone Bolango 96554, Gorontalo, Indonesia
 Email: euler@ung.ac.id
 +6287743200854 (Call/SMS/WA)
 Euler : Jurnal Ilmiah Matematika, Sains dan Teknologi (p-ISSN: 2087-9393 | e-ISSN:2776-3706) by Department of Mathematics Universitas Negeri Gorontalo is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.  Powered by Public Knowledge Project OJS.