Üniversite Ders Çizelgeleme Probleminin Genetik Algoritma ile Optimizasyonu

Recep Çolak; Tuncay Yiğit

doi:10.29130/dubited.1012132

TR EN

Üniversite Ders Çizelgeleme Probleminin Genetik Algoritma ile Optimizasyonu

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.

Details

Primary Language

Turkish

Subjects

Engineering

Journal Section

Research Article

Authors

Recep Çolak ^*
0000-0002-7119-6202
Türkiye

Tuncay Yiğit
0000-0001-7397-7224
Türkiye

Publication Date

December 31, 2021

Submission Date

October 19, 2021

Acceptance Date

December 6, 2021

Published in Issue

Year 2021 Volume: 9 Number: 6

DOI

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

IZ

https://izlik.org/JA95CW68LH

APA

Çolak, R., & Yiğit, T. (2021). Üniversite Ders Çizelgeleme Probleminin Genetik Algoritma ile Optimizasyonu. Duzce University Journal of Science and Technology, 9(6), 150-166. https://doi.org/10.29130/dubited.1012132

AMA

1.Çolak R, Yiğit T. Üniversite Ders Çizelgeleme Probleminin Genetik Algoritma ile Optimizasyonu. DUBİTED. 2021;9(6):150-166. doi:10.29130/dubited.1012132

Chicago

Çolak, Recep, and Tuncay Yiğit. 2021. “Üniversite Ders Çizelgeleme Probleminin Genetik Algoritma Ile Optimizasyonu”. Duzce University Journal of Science and Technology 9 (6): 150-66. https://doi.org/10.29130/dubited.1012132.

EndNote

Çolak R, Yiğit T (December 1, 2021) Üniversite Ders Çizelgeleme Probleminin Genetik Algoritma ile Optimizasyonu. Duzce University Journal of Science and Technology 9 6 150–166.

IEEE

[1]R. Çolak and T. Yiğit, “Üniversite Ders Çizelgeleme Probleminin Genetik Algoritma ile Optimizasyonu”, DUBİTED, vol. 9, no. 6, pp. 150–166, Dec. 2021, doi: 10.29130/dubited.1012132.

ISNAD

Çolak, Recep - Yiğit, Tuncay. “Üniversite Ders Çizelgeleme Probleminin Genetik Algoritma Ile Optimizasyonu”. Duzce University Journal of Science and Technology 9/6 (December 1, 2021): 150-166. https://doi.org/10.29130/dubited.1012132.

JAMA

1.Çolak R, Yiğit T. Üniversite Ders Çizelgeleme Probleminin Genetik Algoritma ile Optimizasyonu. DUBİTED. 2021;9:150–166.

MLA

Çolak, Recep, and Tuncay Yiğit. “Üniversite Ders Çizelgeleme Probleminin Genetik Algoritma Ile Optimizasyonu”. Duzce University Journal of Science and Technology, vol. 9, no. 6, Dec. 2021, pp. 150-66, doi:10.29130/dubited.1012132.

Vancouver

1.Recep Çolak, Tuncay Yiğit. Üniversite Ders Çizelgeleme Probleminin Genetik Algoritma ile Optimizasyonu. DUBİTED. 2021 Dec. 1;9(6):150-66. doi:10.29130/dubited.1012132

Üniversite Ders Çizelgeleme Probleminin Genetik Algoritma ile Optimizasyonu

Üniversite Ders Çizelgeleme Probleminin Genetik Algoritma ile Optimizasyonu

Abstract

Keywords

Optimization of University Course Scheduling Problem with Genetic Algorithm

Abstract

Keywords

References

Details

Primary Language

Subjects

Journal Section

Authors

Publication Date

Submission Date

Acceptance Date

Published in Issue

DOI

IZ

Cite

Cited By

ÇAY HASADI ÇİZELGELEME İÇİN MATEMATİKSEL MODEL ÖNERİSİ

Harvest optimization for sustainable agriculture: The case of tea harvest scheduling

PANDEMİ KOŞULLARI ALTINDA DERS PROGRAMI ÇİZELGELEME PROBLEMİNİN GENETİK ALGORİTMA İLE ÇÖZÜMÜ: BİR UYGULAMA

Visible Digital Image Watermarking Using Single Candidate Optimizer