Kısıt Optimizasyonu için Malatya Vertex Coloring Algoritması Kullanılarak Graf Tabanlı Ders Çizelgeleme

Year 2025, Volume: 14 Issue: 3, 46 - 56, 26.09.2025

Cezayir Karaca , Selman Yakut

https://doi.org/10.46810/tdfd.1629184

Abstract

Ders çizelgeleme problemi, 20. yüzyılın ikinci yarısından itibaren araştırmacıların dikkatini çeken önemli bir kombinatoryal optimizasyon problemidir. Geleneksel olarak manuel yöntemlerle yürütülen çizelgeleme süreci, zaman alıcı ve zorlayıcı olmakla birlikte hata yapmaya açık bir yapıdadır. Bu nedenle, teknolojik ilerlemelerle birlikte çeşitli algoritmalar geliştirilerek daha etkili ve hızlı çözümler sunulmaya çalışılmıştır. Bu çalışmada, "Malatya Vertex Coloring(MVC) Algoritması" ders çizelgeleme problemine uygulanmaktadır. Algoritma, iki temel adımda çalışmaktadır: ilk olarak, çizelge grafındaki düğümlerin Malatya Merkezilik değerleri hesaplanmakta; ardından en yüksek merkeziliğe sahip düğüm seçilerek uygun bir renkle etiketlenmektedir. Süreç boyunca temel hedef, ders çakışmalarını en aza indirmek ve tanımlı kısıtlamalara uyumlu, geçerli bir çizelge üretmektir. MVC Algoritması, işlem adımlarının öngörülebilirliği ve polinom zamanda çalışabilme potansiyeliyle dikkat çekmekte, bu yönüyle literatürde önerilen klasik ve sezgisel yöntemlere etkili bir alternatif sunmaktadır.

Keywords

Course Scheduling , Centrality , Malatya Coloring , Timetabling

Graph-Based Course Scheduling Using the Malatya Vertex Coloring Algorithm for Constraint Optimization

Abstract

The course timetabling problem is a significant combinatorial optimization problem that has attracted the attention of researchers since the second half of the 20th century. Traditionally managed through manual methods, the scheduling process is time-consuming, challenging, and prone to errors. Therefore, with technological advancements, various algorithms have been developed to offer more efficient and faster solutions. In this study, the "MVC Algorithm" is applied to the course timetabling problem. The algorithm operates in two main steps: first, the Malatya Centrality(MC) values of the nodes in the timetable graph are calculated; then, the node with the highest centrality is selected and labeled with an appropriate color. Throughout the process, the main objective is to minimize course conflicts and to generate a valid timetable that complies with defined constraints. The MVC Algorithm stands out with its predictability of procedural steps and its potential to operate in polynomial time, thus offering an effective alternative to classical and heuristic methods proposed in the literature.

Keywords

Course Scheduling , Centrality , Malatya Coloring , Timetabling

References

• Xiang, K., Hu, X., Yu, M., & Wang, X. (2024). Exact and heuristic methods for a university course scheduling problem. Expert Systems with Applications, 248. https://doi.org/10.1016/j.eswa.2024.123383.
• Zhaohui, F., 2000, A. L.-T. with A. Intelligence. I., & 2000, undefined. (n.d.). Heuristics for the exam scheduling problem. Ieeexplore.Ieee.OrgF Zhaohui, A LimProceedings 12th IEEE Internationals Conference on Tools with, 2000•ieeexplore.Ieee.Org. Retrieved October 21, 2024, from https://ieeexplore.ieee.org/abstract/document/889864/
• Pillay, N., & Banzhaf, W. (2007). A genetic programming approach to the generation of hyper-heuristics for the uncapacitated examination timetabling problem. Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 4874 LNAI, 223–234. https://doi.org/10.1007/978-3-540-77002-2_19.
• Rina, I., Sulistiowati, D., & Raudhatuloktavi, D. (2022). Graph Coloring Applications in Scheduling Courses using Welch-Powell Algorithm - A Case Study. Proceeding - 2022 International Symposium on Information Technology and Digital Innovation: Technology Innovation During Pandemic, ISITDI 2022, 131–135. https://doi.org/10.1109/ISITDI55734.2022.9944511
• Egwuche, O. S. (2020, March 1). Examination Timetabling with Graph Coloring for Emerging Institutions. 2020 International Conference in Mathematics, Computer Engineering and Computer Science, ICMCECS 2020. https://doi.org/10.1109/ICMCECS47690.2020.246988
• Bania, R. K., & Duarah, P. (2018). Exam Time Table Scheduling using Graph Coloring Approach. International Journal of Computer Sciences and Engineering, 6(5), 84–93. https://doi.org/10.26438/ijcse/v6i5.8493
• Mursyidah, H. (2019). Graph edges coloring to determine lecture classroom of mathematics education department at muhammadiyah university of surabaya. Journal of Physics: Conference Series, 1188(1). https://doi.org/10.1088/1742-6596/1188/1/012096
• Lampung, U. B., Kesuma, R., #2, W., & Yusman, M. (n.d.). The Use of Edge Coloring Concept for Solving The Time Schedule Problem at Senior High School (Case Study at SMAN 9 Bandarlampung).
• 2019 1st AL-Noor International Conference for Science and Technology (NICST). (2019). IEEE.
• Han, X., & Wang, D. (2025). Gradual Optimization of University Course Scheduling Problem Using Genetic Algorithm and Dynamic Programming. Algorithms, 18(3). https://doi.org/10.3390/a18030158
• Budiarto, A. S., Satvika Iswari, N. M., & Dharma, E. M. (2024). Application of Genetic Algorithm for School Timetable Scheduling. 2024 International Conference on Informatics Electrical and Electronics, ICIEE 2024 - Proceedings. https://doi.org/10.1109/ICIEE63403.2024.10920446
• Rahardjo, E. Tjipto., & Zulkifli, F. Yuli. (2013). 2013 International Conference on QiR (Quality in Research). Faculty of Engineering, Universitas Indonesia.
• Burke, E. K., McCollum, B., Meisels, A., Petrovic, S., & Qu, R. (2007). A graph-based hyper-heuristic for educational timetabling problems. European Journal of Operational Research, 176(1), 177–192. https://doi.org/10.1016/j.ejor.2005.08.012
• Rappos, E., Thiémard, E., Robert, S., & Hêche, J. F. (2022). A mixed-integer programming approach for solving university course timetabling problems. Journal of Scheduling, 25(4), 391–404. https://doi.org/10.1007/s10951-021-00715-5
• Steiner, E., Pferschy, U., & Schaerf, A. (2024). Curriculum-based university course timetabling considering individual course of studies. Central European Journal of Operations Research. https://doi.org/10.1007/s10100-024-00923-2
• Subulan, K. (2024). A multi-objective mathematical programming model for a novel capability-based university course timetabling problem. Journal of the Faculty of Engineering and Architecture of Gazi University, 40(1), 365–379. https://doi.org/10.17341/gazimmfd.1391236
• Nakasuwan, J., Asia, P. S.-S. & T., & 1999, undefined. (n.d.). Class scheduling optimization. Thaiscience.Info. Retrieved January 28, 2025, from https://www.thaiscience.info/Journals/Article/TSTJ/10480612.pdf
• Gunawan, A., Leng, K., Gunawan, A. ;, Ng, M. ;, & Poh, K. L. (2007). Solving the teacher assignment-course scheduling problem by a Solving the teacher assignment-course scheduling problem by a hybrid Algorithm hybrid Algorithm Kien Ming NG Citation Citation Solving the teacher assignment-course scheduling problem by a hybrid Algorithm. In International Journal of Computer, Information, and Systems Science, and Engineering (Vol. 1, Issue 2). https://ink.library.smu.edu.sg/sis_research
• Computers & Informatics (ISCI), 2013 IEEE Symposium on. (2013). Institute of Electrical and Electronics Engineers.
• Fizzano, P., & Swanson, S. (2000). Scheduling Classes on a College Campus. In Computational Optimization and Applications (Vol. 16).
• Özavci, A., & Yakut1, S. (n.d.). Based on Malatya Centrality Algorithm Development of Suggestion System in Social Platforms and Commercial Applications.
• Karci, A., Yakut, S., & Öztemiz, F. (2022). A New Approach Based on Centrality Value in Solving the Minimum Vertex Cover Problem: Malatya Centrality Algorithm. Computer Science. https://doi.org/10.53070/bbd.1195501
• Yakut, S., Öztemiz, F., & Karci, A. (2023). A new robust approach to solve minimum vertex cover problem: Malatya vertex-cover algorithm. Journal of Supercomputing, 79(17), 19746–19769. https://doi.org/10.1007/s11227-023-05397-8
• YAKUT, S., & BAKAN, C. T. (2023). Development of Text Summarization Method based on Graph Theory and Malatya Centrality Algorithm. Computer Science. https://doi.org/10.53070/bbd.1350971
• UniTime | University Course Timetabling Benchmark Benchmark Datasets. (n.d.). Retrieved January 28, 2025, from https://www.unitime.org/uct_datasets.php