APPLICATION OF GRAPH COLORING IN LEARNING SCHEDULE ARRANGEMENT AT MAN 1 PROBOLINGGO

Nurul Faiqoh; Olief Ilmandira Ratu Farisi

doi:10.36564/njca.v9i1.375

APPLICATION OF GRAPH COLORING IN LEARNING SCHEDULE ARRANGEMENT AT MAN 1 PROBOLINGGO

Nurul Faiqoh, Olief Ilmandira Ratu Farisi

Abstract

Learning schedule at MAN 1 Probolinggo has been carried out by utilizing a number processing application. However, the preparation is still done manually. This is due to the large number of teachers, study groups, subjects, and time allocation. Thus, there are still overlapping schedules. In this study, we propose graph coloring to arrange schedules at MAN 1 Probolinggo. Each vertex on the graph represents a subject in a class of X grade. Vertices which represent the subjects are connected by an edge if it taught by the same teacher or taken by the same class. Based on the data, there are 290 vertices in the graph. We used Welsh Powell Algorithm for coloring the graph and implemented by using Python. The results of this research showed that 30 different colors are needed to color the graph. This implies that the minimum period for scheduling all the subjects in each class in one week is 30 periods with one period equal to 2 lesson hours. From the graph coloring results, we obtained a class X schedule without overlap and easily rearranged according to the color groups.

Keywords

learning schedule arrangement; graph coloring; Welsh Powell Algorithm; Python

References

O. I. R. Farisi and G. Q. O. Pratamasunu, “PENYELESAIAN MULTI-DEPOT MULTIPLE TRAVELING SALESMAN PROBLEM MENGGUNAKAN K-MEANS DAN ANT COLONY OPTIMIZATION,” NJCA (Nusantara Journal of Computers and Its Applications), vol. 1, no. 2, Jan. 2017, doi: 10.36564/njca.v1i2.12.

K. Malik, S. T. Teknologi, and N. Jadid, “PREDIKSI PRESTASI SISWA SMP NURUL JADID MENGGUNAKAN ALGORITMA C4.5,” NJCA (Nusantara Journal of Computers and Its Applications), vol. 1, no. 2, Jan. 2017, doi: 10.36564/njca.v1i2.11.

O. I. R. Farisi, S. Maysyaroh, and E. F. Dewi, “Penerapan Pewarnaan Graf pada Penjadwalan Mengajar Dosen Pendidikan Matematika Universitas Nurul Jadid,” Jurnal Matematika, vol. 11, no. 1, pp. 10–19, Jun. 2021, doi: 10.24843/JMAT.2021.V11.I01.P132.

S. Arifin, I. B. Muktyas, and J. M. Mandei, “Graph coloring program for variation of exam scheduling modeling at Binus University based on Welsh and Powell algorithm,” p. 12005, 2022, doi: 10.1088/1742-6596/2279/1/012005.

D. C. Fransisca and S. D. Kurniawan, “Welch powell algoritma aplication to identify the conflict of lesson timetable (case study: informatics engineering, stikom yos sudarso Purwokerto),” International Journal of Technology, Innovation and Humanities, vol. 1, no. 1, pp. 57–61, Oct. 2020, Accessed: Jun. 07, 2023. [Online]. Available: http://journal.iicet.org/index.php/ijtih/article/view/18

S. Sallinen, K. Iwabuchi, S. Poudel, M. Gokhale, M. Ripeanu, and R. Pearce, “Graph Colouring as a Challenge Problem for Dynamic Graph Processing on Distributed Systems,” International Conference for High Performance Computing, Networking, Storage and Analysis, SC, vol. 0, pp. 347–358, Apr. 2016, doi: 10.1109/SC.2016.29.

F. Marpaung and A. Ritonga, “Application of graf coloring for optimization of traffic light settings in Medan,” J Phys Conf Ser, vol. 1188, no. 1, p. 012012, Mar. 2019, doi: 10.1088/1742-6596/1188/1/012012.

S. S. M. Rajagaspar, “Applications of Graph Coloring Using Vertex Coloring,” J Algebr Stat, vol. 13, no. 2, pp. 3447–3454, Jul. 2022, Accessed: May 31, 2023. [Online]. Available: https://publishoa.com/index.php/journal/article/view/1082

N. R. O. Putri, E. Saputra, and A. A. Lisnasari, “IMPLEMENTATION OF GRAPH COLORING IN UMMUL MUKMININ HIGH SCHOOL STUDENT’S DORMITORY USING WELCH-POWELL ALGORITHM,” BAREKENG: Jurnal Ilmu Matematika dan Terapan, vol. 17, no. 1, pp. 0593–0600, Apr. 2023, doi: 10.30598/BAREKENGVOL17ISS1PP0593-0600.

W. Song and J. Park, “Clustering-Based Channel Allocation Method for Mitigating Inter-WBAN Interference,” Applied Sciences 2022, Vol. 12, Page 11851, vol. 12, no. 22, p. 11851, Nov. 2022, doi: 10.3390/APP122211851.

Y. V. Ermanto and Y. F. Riti, “Comparison of Welch-Powell and Recursive Largest First Algorithm Implementation in Course Scheduling,” Journal of Management Science (JMAS), vol. 5, no. 1, pp. 5–12, Accessed: Jun. 07, 2023. [Online]. Available: https://exsys.iocspublisher.org/index.php/JMAS/article/view/119/89

J. L. Gross and J. Yellen, Graph Theory and Its Applications, Second Edition (Discrete Mathematics and Its Applications), 3rd ed. Chapman & Hall/CRC, 2018.

O. I. R. Farisi, Teori Graf dan Aplikasinya. Probolinggo: Pustaka Nurja, 2023.

P. Formanowicz and K. Tanaś, “A survey of graph coloring - Its types, methods and applications,” Sep. 2012, Sciendo. doi: 10.2478/v10209-011-0012-y.

J. A. Tilley, “The a-graph coloring problem,” Discrete Appl Math (1979), vol. 217, pp. 304–317, Jan. 2017, doi: 10.1016/J.DAM.2016.09.011.

D. J. A. Welsh, “An upper bound for the chromatic number of a graph and its application to timetabling problems,” Comput J, vol. 10, no. 1, pp. 85–86, Jan. 1967, doi: 10.1093/comjnl/10.1.85.

F. T. Leighton, “A Graph Coloring Algorithm for Large Scheduling Problems,” J Res Natl Bur Stand (1934), vol. 84, no. 6, p. 489, 1979, doi: 10.6028/JRES.084.024.

I. Méndez-Díaz, G. Nasini, and D. Severín, “An exact DSatur-based algorithm for the Equitable Coloring Problem,” Electron Notes Discrete Math, vol. 44, pp. 281–286, May 2014, doi: 10.1016/j.endm.2013.10.044.

L. Yuan, L. Qin, X. Lin, L. Chang, and W. Zhang, “Effective and efficient dynamic graph coloring,” Proceedings of the VLDB Endowment, vol. 11, no. 3, pp. 338–351, Nov. 2017, doi: 10.14778/3157794.3157802.

E. Malaguti, M. Monaci, and P. Toth, “An exact approach for the Vertex Coloring Problem,” Discrete Optimization, vol. 8, no. 2, pp. 174–190, May 2011, doi: 10.1016/J.DISOPT.2010.07.005.

M. Aslan and N. A. Baykan, “A Performance Comparison of Graph Coloring Algorithms,” International Journal of Intelligent Systems and Applications in Engineering, vol. 4, no. Special Issue-1, pp. 1–7, Dec. 2018, doi: 10.18201/ijisae.273053.

L. N. M. Vu, H. C. Tran, and A. T. T. Nguyen, “A study on constructing an efficient examination scheduling system,” HO CHI MINH CITY OPEN UNIVERSITY JOURNAL OF SCIENCE - ENGINEERING AND TECHNOLOGY, vol. 14, no. 1, pp. 52–64, Mar. 2024, doi: 10.46223/HCMCOUJS.TECH.EN.14.1.2920.2024.

DOI: http://dx.doi.org/10.36564/njca.v9i1.375