Graph Coloring Application with Modified Tabu Search Algorithm in School Scheduling

Abstract:

Graph coloring is one of the common problems encountered in scheduling optimization. In the context of school scheduling, graph coloring is used to efficiently allocate time for various school activities. The objective of this research is to apply the Tabu Search algorithm in solving the graph coloring problem for school scheduling. This study utilizes the Tabu Search algorithm as an optimization method to find schedule solutions that satisfy all given constraints. The Tabu Search algorithm combines local search with a broader exploration mechanism. The Tabu Search algorithm is implemented by considering various important factors such as the number of subjects, time constraints, and specific preferences. In the graph coloring modeling, each subject is represented as a graph node, while the relationships between subjects that cannot take place at the same time are represented by graph edges. The results of this research show that the Tabu Search algorithm is capable of producing schedule solutions that meet all the given constraints. The found solutions have advantages in efficient time allocation, avoiding overlaps between activities, and considering the preferences compared to manual scheduling. This research contributes to the field of school scheduling by utilizing the Tabu Search algorithm from graph coloring.

• Periodical: Engineering Headway (Volume 27)
• Pages: 854-865
• DOI: https://doi.org/10.4028/p-ZDXab3
• Online since: October 2025
• Authors: Oviana Listiyaningrum*, Darmaji Darmaji
• Keywords: Bipartite Graph, Constraint Satisfaction, Graph Coloring, Integer Programming, Modified Tabu Search, Scheduling Optimisation, School Scheduling, Tabu Search Algorithm

References

[1] K.A. Dowsland, and J.M. Thompson, "An improved ant colony optimisation heuristic for graph colouring," Discrete Appl Math (1979) 156(3), 313–324 (2008).

DOI: 10.1016/j.dam.2007.03.025

[2] F. Glover, "Future paths for integer programming and links to artificial intelligence," Comput Oper Res 13(5), 533–549 (1986).

DOI: 10.1016/0305-0548(86)90048-1

[3] E.K. Burke, A. Meisels, S. Petrovic, and R. Qu, A Graph-Based Hyper Heuristic for Timetabling Problems (2004).

[4] A. Slavík, Unbiased Version of Hall's Marriage Theorem in Matrix Form (n.d.). Implementasi Metode Pewarnaan Graf Menggunakan Algoritma Welch Powell untuk Simulasi Penerapan Frekuensi Radio di Jawa Timur," (n.d.).

DOI: 10.12962/j23373520.v6i2.26738

[5] "22. Implementasi Metode Pewarnaan Graf Menggunakan Algoritma Welch Powell untuk Simulasi Penerapan Frekuensi Radio di Jawa Timur," (n.d.).

DOI: 10.12962/j23373520.v6i2.26738

[6] L.T. Amik, M. Gama, J. Kayangan, N. 99, and D.- Riau, Implementasi Algoritma Genetika Dalam Pembuatan Jadwal Kuliah (2017).

[7] "10. Tabu search for graph coloring, T-colorings and set T-colorings. ," (n.d.).

[8] N. Luh Gede Pivin Suwirmayanti, I. Made Sudarsana, S. Darmayasa, S. STIKOM Bali Jl Raya Puputan No, R. Denpasar, and P. Studi Sistem Komputer, Penerapan Algoritma Genetika Untuk Penjadwalan Mata Pelajaran Implementation of Genetic Algorithm for Course Scheduling (2016).

[9] J.A. Tilley, "The a-graph coloring problem," Discrete Appl Math (1979) 217, 304–317 (2017).

[10] H. Budiman, Penerapan Graph Colouring Untuk Merencanakan Jadwal (n.d.).

[11] P. Pewarnaan Graf Menggunakan Algoritma Welch-powell Untuk Menentukan Jadwal Bimbingan Mahasiswa, A. Widyastuty Bustan, M. Rais Salim, P. Morotai, J. Siswa Darame, K. Morotai Selatan, K. Pulau Morotai, M. Utara, P. Studi Pendidikan Guru Sekolah Dasar, F. Kip, and U. Pasifik Morotai, Implementation of Graph Colouring Using Welch-Powell Algorithm to Determine Student Mentoring Schedule (n.d.).

DOI: 10.24905/jip.v1i2.608

[12] L. Candra, Penerapan Algoritma Tabu Search Untuk Penjadwalan Mata Pelajaran Di SMK SWASTA Pelita-2 AEKKANOPAN (2016).

[13] Y. Jin, J.P. Hamiez, and J.K. Hao, "Algorithms for the minimum sum coloring problem: a review," Artif Intell Rev 47(3), 367–394 (2017).

DOI: 10.1007/s10462-016-9485-7

[14] "34. Pencarian jalur tercepat rute perjalanan wisata dengan algoritma Tabu Search. ," (n.d.).

[15] B. Hardy, R. Lewis, and J. Thompson, "Tackling the edge dynamic graph colouring problem with and without future adjacency information," Journal of Heuristics 24(3), 321–343 (2018).

DOI: 10.1007/s10732-017-9327-z

[16] "16. Finding a feasible course scheduling using tabu search," (n.d.).

[17] A. Hertz, and D. de Werra, "Using tabu search techniques for graph coloring," Computing 39(4), 345–351 (1987).

DOI: 10.1007/bf02239976

[18] L. Di Gaspero, and A. Schaerf, Tabu Search Techniques for Examination Timetabling (n.d.).

[19] F. Glover, M. Laguna, P. Pardalos, D.-Z. Du, and R. Graham, TABU SEARCH * Chapter to Appear in the Handbook of Combinatorial Optimization, 2 Nd Edition (n.d.).

[20] "19. Implementasi Algoritma Genetika Pada Aplikasi Penjadwalan Perkuliahan Berbasis Web Dengan Mengadopsi Model Waterfall," (n.d.).

DOI: 10.30591/jpit.v2i2.517

[21] F. Mahardika, and H. Marcos, "Penerapan Algoritma Graf Welch Powel Pada Penjadwalan Mata Kuliah Dan Jadwal Asisten Study Kasus Forum Asisten Stmik Amikom Purwokerto," Jurnal SIMETRIS 8, (2017).

DOI: 10.24176/simet.v8i2.1208

[22] A.P. Rahadi, Penjadwalan Mata Kuliah Menggunakan Pewarnaan Graf Dengan Algoritma Largest First (n.d.).

DOI: 10.35974/jpd.v2i1.1067

[23] "32. Implementasi Algoritma Genetika Dalam Pengembangan Sistem Aplikasi Penjadwalan Kuliah," (n.d.).

[24] S.C. Chu, and H.L. Fang, "Genetic algorithms vs. Tabu search in timetable scheduling," International Conference on Knowledge-Based Intelligent Electronic Systems, Proceedings, KES, 492–495 (1999).

DOI: 10.1109/kes.1999.820230

[25] R. Qu, E.K. Burke, and B. McCollum, "Adaptive automated construction of hybrid heuristics for exam timetabling and graph colouring problems," Eur J Oper Res 198(2), 392–404 (2009).

DOI: 10.1016/j.ejor.2008.10.001

[26] H.D. Lawal, I.A. Adeyanju, E.O. Omidiora, O.T. Arulogun, and O.I. Omotosho, "University Examination Timetabling Using Tabu Search," Int J Sci Eng Res 5(10), (2014).

[27] P. Galinier, and A. Hertz, "A survey of local search methods for graph coloring," Comput Oper Res 33(9), 2547– 2562 (2006).

DOI: 10.1016/j.cor.2005.07.028

[28] Seminar Nasional Riset Dan Teknologi Terapan 8 (RITEKTRA 8) (2018).