Üniversite Ders Çizelgeleme Probleminin Genetik Algoritma ile Optimizasyonu

Year 2021, Volume: 9 Issue: 6 - ICAIAME 2021, 150 - 166, 31.12.2021

Recep Çolak , Tuncay Yiğit

https://doi.org/10.29130/dubited.1012132

Cited By: 2

Abstract

Üniversitelerin her dönem başında yaptığı ders çizelgeleme problemi kombinatortal optimizasyon problemlerindendir. Çizelgeleme problemleri NP-Hard sınıfına giren ve çözümü zor problemlerdendir. Determinist bir yaklaşımla olası bütün ihtimallerin denenmesi gibi algoritmalarla çözüm mümkün olsa da çok zaman alıcı bir işlem olduğundan pratikte bu algoritmalar kullanılmamaktadır. Özelikle probleme ait veriler arttıkça ve çözülmesi gereken çok fazla kısıt olması durumunda çözüme ulaşmak daha da güçleşmektedir. Bu çalışmada ders çizelgeleme problemi çözülmesi gereken katı ve esnek kısıtlar olarak ele alınmıştır. Katı kısıtlar ders çakışması, derslik çakışması, kapasiteye uygun olmayan dersliğe şube atanması gibi kesin olarak çözülmesi gereken kısıtlardır. Esnek kısıtlar ise derslerin istenmeyen zaman dilimlerine atanması bir kısmı ihmal edilebilen kısıtlardır. Bu çalışmada probleme ait katı ve esnek kısıtlar belirlenmiş ve bu kısıtları ihlal edilen durumlara ceza puanları atanarak en az ceza puanına sahip çözümler aranmıştır. Problemin çözümü için çizelgeleme problemlerinde sıkılıkla kullanılan Genetik Algoritma kullanılmıştır. Yapılan testeler sonucunda Genetik Algoritma ile ders çizelgeleme probleminin kısa sürede çözülebildiği görülmüştür.

Keywords

Genetik algoritma, ders çizelgeleme, ders programı, sezgisel algoritmalar

Optimization of University Course Scheduling Problem with Genetic Algorithm

Abstract

The course scheduling problem that universities do at the beginning of each semester is one of the combinatorial optimization problems. Scheduling problems are NP-Hard problems and difficult to solve. Although it is possible to solve with algorithms such as trying all possible possibilities with a deterministic approach, these algorithms are not used in practice because it is a very time-consuming process. Especially when the data of the problem increases and there are too many constraints to be solved, it becomes more difficult to reach a solution. In this study, the lesson scheduling problem is considered as hard and soft constraints that need to be solved. Hard constraints are constraints that need to be resolved, such as course conflict, classroom conflict, assigning a branch to a classroom that is not suitable for capacity. Soft constraints, on the other hand, are constraints that can be neglected by assigning courses to undesirable time slots. In this study, the hard and soft constraints of the problem were determined and the solutions with the least penalty points were sought by assigning penalty points to the situations in which these constraints were violated. Genetic Algorithm, which is frequently used in scheduling problems, was used to solve the problem. As a result of the tests, it was seen that the course scheduling problem could be solved in a short time with the Genetic Algorithm.

Keywords

Genetic algorithm, course scheduling, course timetabling, heuristic algorithm

References

• [1] A. I. Diveev and O. V. Bobr, “Variational genetic algorithm for np-hard scheduling problem solution,” Procedia Computer Science, vol. 103, pp. 52–58, 2017.
• [2] A. Muklason, R. G. Irianti, and A. Marom, “Automated course timetabling optimization using tabu-variable neighborhood search based hyper-heuristic algorithm,” Procedia Computer Science, vol. 161, pp. 656–664, 2019.
• [3] K. Alomari, O. Almarashdi, A. Marashdh, and B. Zaqaibeh, “A new optimization on harmony search algorithm for exam timetabling system,” Journal Of Information And Knowledge Management, vol. 19, no. 1, pp. 202009_1-202009_13, 2020.
• [4] M. Chen, X. Tang, T. Song, C. Wu, S. Liu, and X. Peng, “A tabu search algorithm with controlled randomization for constructing feasible university course timetables,” Computers & Operations Research, vol. 123, pp. 105007, 2020.
• [5] A. Gülcü And C. Akkan, “Robust university course timetabling problem subject to single and multiple disruptions,” European Journal Of Operational Research, vol. 283, no. 2, pp. 630–646, 2020.
• [6] K. Patrick and Z. Godswill, “Greedy ants colony optimization strategy for solving the curriculum based university course timetabling problem,” British Journal Of Mathematics & Computer Science, vol. 14, no. 2, pp. 1–10, 2016.
• [7] E. A. Abdelhalim and G. A. El Khayat, “A utilization-based genetic algorithm for solving the university timetabling problem (uga),” Alexandria Engineering Journal, vol. 55, no. 2, pp. 1395–1409, 2016.
• [8] M. W. Carter, “A comprehensive course timetabling and student scheduling system at the university of waterloo,” Practice and Theory of Automated Timetabling III. PATAT 2000, 2000 pp. 64–82
• [9] M. Shahvali Kohshori and M. Saniee Abadeh, “Hybrid genetic algorithms for university course timetabling,” International Journal of Computer Science Issues (IJCSI), vol. 9, no. 2, pp. 446-455, 2012.
• [10] T. Yiğit, “Meslek liseleri haftalık ders çizelgelerinin genetik algoritmalar yardımıyla oluşturulması,” Gazi Üniversitesi Endüstriyel Sanatlar Eğitim Fakültesi Dergisi, vol. 19, pp. 25–39, 2004.
• [11] M. A. Cruz-Chávez, M. Flores-Pichardo, A. Martínez-Oropeza, P. Moreno-Bernal, And M. H. Cruz-Rosales, “Solving a real constraint satisfaction model for the university course timetabling problem: a case study,” Mathematical Problems İn Engineering, vol. 2016, 2016.
• [12] J. H. Obit, K. Y. Junn, and R. Alfred, “A performance comparison of metaheuristics search for university course timetabling problems,” Advanced Science Letters, vol. 23, no. 11, pp. 11012–11015, 2017.
• [13] K. Y. Junn, J. H. Obit, and R. Alfred, “A constraint programming approach to solving university course timetabling problem (uctp),” Advanced Science Letters, vol. 23, no. 11, pp. 11023–11026, 2017.
• [14] M. Lindahl, A. J. Mason, T. Stidsen, and M. Sørensen, “A strategic view of university timetabling,” European Journal Of Operational Research, vol. 266, no. 1, pp. 35–45, 2018.
• [15] T. L. June, J. H. Obit, Y.-B. Leau, and J. Bolongkikit, “Implementation of constraint programming and simulated annealing for examination timetabling problem,” Computational Science and Technology, pp. 175–184, 2019.
• [16] R. Çolak, “Sezgisel algoritmalarla ders programı çizelegeleme probelmi çözümü,” YL tezi, Bilgisayar Mühendisliği Bölümü, Süleyman Demirel Üniversitesi, Isparta, Türkiye, 2015.
• [17] M. C. Chen, S. N. Sze, S. L. Goh, N. R. Sabar, and G. Kendall, “A survey of university course timetabling problem: perspectives, trends and opportunities,” IEEE Access, vol. 9, pp. 106515–106529, 2021.
• [18] D. De Werra, A. S. Asratian, and S. Durand, “Complexity of some special types of timetabling problems,” Journal Of Scheduling, vol. 5, no. 2, pp. 171–183, 2002.
• [19] E. K. Burke, B. Mccollum, A. Meisels, S. Petrovic, and R. Qu, “A graph-based hyper-heuristic for educational timetabling problems,” European Journal Of Operational Research, vol. 176, no. 1, pp. 177–192, 2007.
• [20] N. L. Lawrie, “An integer linear programming model of a school timetabling problem,” The Computer Journal, vol. 12, no. 4, pp. 307–316, 1969.
• [21] N. Boland, B. D. Hughes, L. T. G. Merlot, and P. J. Stuckey, “New integer linear programming approaches for course timetabling,” Computers & Operations Research, vol. 35, no. 7, pp. 2209–2233, 2008.
• [22] G. B. Bucco, C. J. Bornia-Poulsen, and D. L. Bandeira, “Development of a linear programming model for the university course timetabling problem,” Gestao E Producao, vol. 24, no. 1, pp. 40–49, 2017.
• [23] J. M. Maldonado-Matute, M. J. González Calle, and R. M. Celi Costa, “Development of a solution model for timetabling problems through a binary ınteger linear programming approach,” Intelligent Human Systems Integration, vol. 1131, pp. 510–516, 2020.
• [24] O. Kaynar ve A. Yurtsal, “Ders programıçizelgeleme probleminin genetik algoritma ile optimizasyonu,” Journal Of Information Systems And Management Research, vol. 1, no. 1, pp. 9–14, 2019.
• [25] A. Colorni, M. Dorigo, and V. Maniezzo, “A genetic algorithm to solve the timetable problem,” Politecnico Di Milano, pp. 90-060, 1992
• [26] M. A. Mohammed, M. Khanapi, A. Ghani, O. I. Obaid, and S. Mostafa, “A review of genetic algorithm application in examination timetabling problem,” Journal Of Engineering And Applied Sciences, vol. 12, no. 20, pp. 5166–5181, 2017.
• [27] S. Naseem Jat and S. Yang, “A guided search genetic algorithm for the university course timetabling problem,” 4th Multidisciplinary International Conference On Scheduling : Theory And Applications (MISTA 2009), Dublin, Ireland, 2009, pp. 180-191.
• [28] W. Herbawi and M. Weber, “A genetic and ınsertion heuristic algorithm for solving the dynamic ridematching problem with time windows,” Proceedings Of The 14th International Conference On Genetic And Evolutionary Computation, New York, USA, 2012, pp. 385-392.
• [29] A. A. Gozali, B. Kurniawan, W. Weng, and S. Fujimura, “Solving university course timetabling problem using localized island model genetic algorithm with dual dynamic migration policy,” IEEJ Transactions On Electrical And Electronic Engineering, vol. 15, no. 3, pp. 389–400, 2020.
• [30] C. Akkan and A. Gülcü, “A bi-criteria hybrid genetic algorithm with robustness objective for the course timetabling problem,” Computers And Operations Research, vol. 90, pp. 22–32, 2018.
• [31] A. A. Mahiba and C. A. D. Durai, “Genetic algorithm with search bank strategies for university course timetabling problem,” Procedia Engineering, vol. 38, pp. 253–263, 2012.
• [32] J. H. Holland, “Genetic algorithms and the optimal allocation of trials,” Siam Journal On Computing, vol. 2, no. 2, pp. 88–105, 1973.
• [33] D. E. Goldberg, Genetic Algorithms in Search, Optimization, And Machine Learning, Addison-Wiley, 1989.
• [34] G. Panchal and D. Panchal, “Solving np hard problems using genetic algorithm,” International Journal Of Computer Science And Information Technologies, vol. 6, no. 2, pp. 1824–1827, 2015.
• [35] Babaei, H., Karimpour, J.,Hadidi, A. “A survey of approaches for university course timetabling problem, ” Computers & Industrial Engineering, vol. 86, pp. 43-59, 2015.
• [36] Rezaeipanah, A., Matoori, S. S., and Ahmadi, G. “A hybrid algorithm for the university course timetabling problem using the improved parallel genetic algorithm and local search,” Applied Intelligence, vol.51, pp.467-492, 2021
• [37] A. J. Umbarkar and P. D. Sheth, “Crossover operators in genetıc algorithms: a revıew,” Ictact Journal On Soft Computing, vol. 6 pp. 1083-1092, 2015.