SOLVING THE COURSE SCHEDULING PROBLEM UNDER THE PANDEMIC CONDITIONS WITH GENETIC ALGORITHM: AN APPLICATION

Yıl 2024, Sayı: 69, 79 - 94, 30.12.2024

Tuğçe Nur Yılmaz , Birsen İrem Kuvvetli

https://doi.org/10.18070/erciyesiibd.1486042

Öz

There is no single solution to the course scheduling problem, which is solved using various methods. In this study, a solution to the course scheduling problem was sought with a Genetic Algorithm. A mathematical model of the problem for Osmaniye Korkut Ata University, Department of Business Administration and was solved with the Genetic Algorithm. The purpose of this study is creating a course schedule by taking into account situations such as reducing contact and reducing indoor circulation to prevent contamination between students and faculty members as a result of any epidemic. For this problem, when single-point crossover was used, the optimal result was found in 23 seconds with a crossover rate of 0.8 and a mutation rate of 0.05 when the population size was 50. When sequential crossover was used for the same problem, the optimal result was found in 60 seconds with a crossover rate of 0.8 and a mutation rate of 0.05 when the population size was 50. The problem was also solved for a population of 100 units with two different crossover methods and the results were discussed. In addition, the results were evaluated according to the change in online course percentages in the scenario analysis.

Anahtar Kelimeler

Heuristics, Genetic Algorithm, Curriculum Scheduling, Pandemic

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

Öz

Birçok yöntemden yararlanılarak çözülen ders programı çizelgeleme probleminin tek bir çözüm yöntemi yoktur. Bu çalışmada, ders programı çizelgeleme problemine Genetik Algoritma ile bir çözüm aranmıştır. Osmaniye Korkut Ata Üniversitesi, İşletme Bölümü için matematiksel model oluşturulmuş ve Genetik Algoritma ile çözülmüştür. Bu çalışmanın amacı, herhangi bir salgın sonucunda öğrenciler ve öğretim üyeleri arasında gerçekleşebilecek bulaşın önüne geçilmesini sağlamak adına temasın azaltılması, bina içi dolaşımın azaltılması gibi durumları göz önünde bulundurarak ders programı çizelgesini oluşturmaktır. Bu örnek problem için tek noktalı çaprazlama kullanıldığında, popülasyon büyüklüğü 50 iken 0.8 çaprazlama oranı ve 0.05 mutasyon oranı ile optimal sonuç 23 saniyede bulunmuştur. Aynı problem için sıralı çaprazlama kullanıldığında ise, yine popülasyon büyüklüğü 50 iken 0.8 çaprazlama oranı ve 0.05 mutasyon oranı ile optimal sonuç 60 saniyede bulunmuştur. Problem, iki farklı çaprazlama yöntemi ile 100 birimlik popülasyon için de çözülmüş ve sonuçlar tartışılmıştır. Ayrıca senaryo analizinde çevrimiçi ders yüzdelerindeki değişime göre sonuçlar değerlendirilmiştir.

Anahtar Kelimeler

sezgisel algoritmalar, genetik algoritma, ders programı çizelgeleme problemi, pandemi

Kaynakça

• Abduljabbar, I. A., & Abdullah, S. M. (2022). An evolutionary algorithm for solving academic courses timetable scheduling problem. Baghdad Science Journal, 19(2), (s. 399-408). https://doi.org/10.21123/bsj.2022.19.2.0399
• Ahmad, I. R., Sufahani, S., Ali, M., & Razali, S. N. (2018). A heuristics approach for classroom scheduling using. Journal of Physics: Conference Series, 995(1).
• Alnowaini, G., & Aljomai, A. A. (2021). Genetic algorithm for solving university course timetabling problem using dynamic chromosomes. In 2021 International Conference of Technology, Science and Administration (s. 1-6). IEEE. https://doi.org/10.1109/ICTSA52017.2021.9406539
• Altunay, H., & Eren, T. (2017). Ders programı çizelgeleme problemi için bir literatür taraması. Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi, 23(1), (s. 55-70). https://doi.org/10.5505/pajes.2016.37233
• Alvarez-Valdes, R., Crespo, E., & Tamarit, J. M. (2002). Design and implementation of a course scheduling system using tabu search. European Journal of Operational Research, 137(3), (s. 512-523). https://doi.org/10.1016/S0377-2217(01)00091-1
• Akı, O. (2020). University course timetabling using genetic algorithms. In International Scientific Conference (UNITECH), (s. Vol. 1, p. 390).
• Amrulloh, A., & Sela, E. (2021). Optimization of course scheduling using genetic algorithm and tabu search. Doctoral dissertation, Universitas Teknologi Yogyakarta.
• Ansari, R., & Saubari, N. (2020). Application of genetic algorithm concept on course scheduling. In IOP Conference Series: Materials Science and Engineering (Vol. 821, No. 1, p. 012043). IOP Publishing.
• Bagley, J. D., The Behavior of Adaptive Systems Which Emply Genetic and Correlation Algorithms, Doktora Tezi, University of Michigan, 1967.
• Behrenk, A. B., Güçlükol Ergin, S., & Toy, A. Ö. (2022, Ekim). Course scheduling problem and real-life ımplementation. In The International Symposium for Production Research (s. 749-758). Cham: Springer International Publishing.
• Bosworth, J. L., Foo, N. Y., & Zeigler, B. P. (1972). Comparison of genetic algorithms with conjugate gradient methods (No. NASA-CR-2093). NASA.
• Burke, E., & Petrovic, S. (2002). Recent research directions in automated timetabling. European Journal of Operational Research, 140(2) (s. 266-280). https://doi.org/10.1016/S0377-2217(02)00069-3
• Cavicchio, D. J. (1970). Adaptive search using simulated evolution.
• Chaouachi, J., & Harrabi, O. (2022). Toward artifical intelligence tools for solving the real world problems: effective hybrid genetic algorithms proposal. In Advances in Selected Artificial Intelligence Areas: World Outstanding Women in Artificial Intelligence (s. 231-254). Cham: Springer International Publishing.
• Chen, X., Yue, X. G., Li, R., Zhumadillayeva, A., & Liu, R. (2021). Design and application of an improved genetic algorithm to a class scheduling system. International Journal of Emerging Technologies in Learning, 16(1), (s. 44-59). https://doi.org/10.3991/ijet.v16i01.18225
• Cruz-Rosales, M. H., Cruz-Chávez, M. A., Alonso-Pecina, F., Peralta-Abarca, J. D., Ávila-Melgar, E. Y., Martínez-Bahena, B., & Enríquez-Urbano, J. (2022). Metaheuristic with cooperative processes for the university course timetabling problem. Applied Sciences, 12(2), 542.
• Çolak, R., & Yiğit, T. (2021). Üniversite ders çizelgeleme probleminin genetik algoritma ile optimizasyonu. Düzce Üniversitesi Bilim ve Teknoloji Dergisi, 9(6), (s.150-166). https://doi.org/10.29130/dubited.1012132
• Dele, O. A. (2019). An ant colony algorithm based system for allocating course timetable in federal polytechnic Bali, Taraba State, Nigeria. Bakundi Journal of Technology, Agriculture and Entrepreneurship, 1(1).
• Duan, Y., & Lu, W. (2021). Automatic course scheduling system in universities based on hybrid genetic-ant colony algorithm. In Journal of Physics: Conference Series. 2066(1), (s. 012079). IOP Publishing. https://doi.org/10.1088/1742-6596/2066/1/012079
• Eren, T., Taş, C., & Bedir, N. (2018). 0-1 tamsayılı programlama ile ders programı çizelgeleme probleminin çözümü: bir yükseköğretim kurumunda uygulama. Harran Üniversitesi Mühendislik Dergisi: 3(3), (s. 166-175).
• Ewi, E. I., & Radiles, H. (2023). Mitigasi premature convergence pada genetic algorithm menggunakan metoda dynamics growth population dalam kasus university course scheduling. JEKIN-Jurnal Teknik Informatika, 3(1), (s. 33-44). https://doi.org/10.58794/jekin.v3i1.486
• Fedkin, E., Denissova, N., Krak, I., & Dyomina, I. (2021). Automation of scheduling training sessions in educational ınstitutions using genetic algorithms. In 2021 11th IEEE International Conference on Intelligent Data Acquisition and Advanced Computing Systems: Technology and Applications (IDAACS), (s. 278-283). IEEE. https://doi.org/10.1109/IDAACS53288.2021.9660939
• Frantz, D. R. (1972). Non-linearities in genetic adaptive search. Doktora Tezi, University of Michigan.
• Goldberg, D. E. (1989). Genetic algorithms in search, optimization and machine learning. Addison-Wesley Longman Publishing.
• Gozali, A. A., Kurniawan, B., Weng, W., & Fujimura, S. (2020). Solving University course Timetabling Problem Using Localized Island Model Genetic Algorithm with Dual Dynamic Migration Policy. Transactions on Electrical and Electronic Engineering , 15, 389-400.
• Hollstien, R. (1971). Artificial genetic adaptation in computer control systems. University of Michigan.
• Hossain, S. I., Akhand, M. A., Shuvo, M. I., Siddique, N., & Adeli, H. (2019). Optimization of University course scheduling problem using particle swarm optimization with selective search. Expert Systems with Applications, 127, 9-24.
• Hu, Y., Wang, S., & Duan, Z. (2021). Using dynamic search mandatory genetic algorithm to solve the university course timetabling problem considering walking distance. In Proceedings of the Fifteenth International Conference on Management Science and Engineering Management, (s. 34-45). Springer, Cham. https://doi.org/10.1007/978-3-030-79203-9_4
• Huang, Q. &Wang, Y. (2022). Application of Genetic Algorithm in University Teaching Management System. In Innovative Computing, (613-620). Springer, Singapore.
• Jiang, C. B., & Liu, H. (2019). A course scheduling algorithm based on improved genetic algorithm with multi-objective constrains. In 2019 Eleventh International Conference on Advanced Computational Intelligence (ICACI) (s. 202-206). IEEE.
• Junjun, Z., Hexia, Y., Oyam, D. M., & Yi, W. (2022). Design and ımplementation of ıntelligent course scheduling system for deep ıntegration of education and teaching. Frontiers in Educational Research, 5(19), (s. 81-89). https://doi.org/10.25236/FER.2022.051915.
• Kakkar, M. K., Singla, J., Garg, N., Gupta, G., Srivasta, P., & Kumar, A. (2021, Ağustos). Class schedule generation using evolutionary algorithms. In Journal of Physics: Conference Series 1950(1), (s. 012067). IOP Pubalishing. https://doi.org/10.1088/1742-6596/1950/1/012067
• Kamışlı Öztürk, Z., Kasımbeyli, N., Özdemir, M. S., Acar, M. S., & Özçetin, E. (2015). Kullanıcı tercihlerinin dikkate alınması durumunda üniversite ders çizelgeleme problemi. Endüstri Mühendisliği Dergisi, 27(1), (s. 2-18).
• Kaynar, O., & Yurtsal, A. (2019). Ders programı çizelgeleme probleminin genetik algoritma ile optimizasyonu. Journal of Information Systems and Management Research, 9-14.
• Kristiadi, D., & Hartanto, R. (2019). Genetic algorithm for lecturing schedule optimization. IJCCS (Indonesian Journal of Computing and Cybernetics Systems) 13(1), 83-94.
• Li, T., Xie, Q., & Zhang, H. (2022). Design of college scheduling algorithm based on improved genetic ant colony hybrid optimization. Security and Communication Networks. https://doi.org/10.1155/2022/2565639
• Luo, X., Sun, Y., Liu, X., Gao, Y., Sun, H., & Liu, Y. (2022). Course timetable optimization for a university teaching building considering the building energy efficiency and time-varying thermal perception of students. Building and Environment, 219, 109175. https://doi.org/10.1016/j.buildenv.2022.109175
• Mahlous, A. R., & Mahlous, H. (2023). Student timetabling genetic algorithm accounting for student preferences. PeerJ Computer Science, 9, e1200. https://doi.org/10.7717/peerj-cs.1200.
• Mahmud, A. (2021). Highly Constrained University Class Scheduling using Ant Colony Optimization. International Journal of Computer Science & Information Technology, 13.
• Martin, V. F., & Peluffo‐Ordóñez, H. (2022). Virtual and face-to-face course timetabling using multiobjective genetic algorithms based on dynamic gene spaces. Universidad Internacional de Valencia.
• Mauluddin, S., Ikbal, I., & Nursikuwagus, A. (2020). Complexity and performance comparison of genetic algorithm and ant colony for best solution timetable class. Journal of Engineering Science and Technology, 15(1), 278-292.
• Modibbo, U. M., Umar, I., Mijinyawa, M., & Hafisu, R. (2019). Genetic algorithm for solving university timetabling problem. Amity Journal of Computational Sciences (AJCS), 3(1), 43-50.
• Muklason, A., Irianti, R. G., & Marom, A. (2019). Automated course timetabling optimization using tabu-variable neighborhood search based hyper-heuristic algorithm. Procedia Computer Science, 161, 656-664.
• Nasien, D. & Andi, A. (2022). Optimization of genetic algorithm in courses scheduling. IT Journal Research and Development (ITJRD), 6(2), (s. 151-161). https://doi.org/10.25299/itjrd.2022.7896
• Nugroho, A. K., Permadi, I., & Yasifa, A. R. (2022). Optimizing course scheduling faculty of engineering unsoed using genetic algorithms. JITK (Jurnal Ilmu Pengetahuan dan Teknologi Komputer), 7(2), (s. 91-98). https://doi.org/10.33480/jitk.v7i2.2262
• Özyandı, G. (2010). Ders çizelgeleme probleminin 0-1 tamsayılı programlama tabanlı uygulaması. Gazi Üniversitesi Yüksek Lisans Tezi.
• Pérez, E. C., Rios, O. M., Bautista, D. P., Sanchez, S. S., & Acevedo, F. A. (2021). A genetic algorithm solution for scheduling problem. In 2021 XVII International Engineering Congress (CONIIN) (s. 1-10). IEEE. https://doi.org/10.1109/CONIIN54356.2021.9634725
• Pinedo, M. (2008). Scheduling: Theory, Algorithms, and Systems. New York: Prentice Hall: 3rd Edition.
• Pongcharoen, P., Promtet, W., Yenradee, P., & Hicks, C. (2008). Stochastic optimisation timetabling tool for university course scheduling. International Journal of Production Economics, 2 (112), (s. 903-918).
• Ren, X., & Li, C. (2022). Computer intelligent course scheduling system based on deep learning. In 2022 International Conference on Knowledge Engineering and Communication Systems (ICKES), (s. 1-5). Chickballapur, India. https://doi.org/10.1109/ICKECS56523.2022.10060177
• Rezaeipanah, A., Matoori, S. S., & Ahmadi, G. (2021). A hybrid algorithm for the university course timetabling problem using the improved parallel genetic algorithm and local search. Applied Intelligence: The International Journal of Research on Intelligent Systems for Real Life Complex Problems, 51(1), (s. 467–492). https://doi.org/10.1007/s10489-020-01833-x
• Rodprasert, N., Taetragool, U., & Akkarajitsakul, K. (2023). Online/offline course and multiple lecturers scheduling using meta-heuristic approaches. In Proceedings of the 2023 9th International Conference on Computer Technology Applications, (s. 166-171). https://doi.org/10.1145/3605423.3605440
• Rosenberg, R.S. 1967. Simulation of genetic populations with biochemical properties. Doktora Tezi, University of Michigan, Ann Harbor Michigan.
• Sakal, J., Fieldsend, J. E., & Keedwell, E. (2021). Learning assignment order in an ant colony optimiser for the university course timetabling problem. In Proceedings of the Genetic and Evolutionary Computation Conference Companion, (s. 77-78).
• Sari, R., Ramdhania, K. F., & Purnomo, R. (2022). Team-teaching-based course scheduling using genetic algorithm. PIKSEL: Penelitian Ilmu Komputer Sistem Embedded and Logic, 10(1), (s. 55-66). https://doi.org/10.33558/piksel.v10i1.4416
• Shuai, C. J. (2021). Design of automatic course arrangement system for electronic engineering teaching based on monte carlo genetic algorithm. Security and Communication Networks. (s. 1-11). https://doi.org/10.1155/2021/3564722
• Subagio, R. T., Putri, T. E., Sokibi, P., & Harahap, S. Z. (2021). Application of genetic algorithm to optimize lecture scheduling based on lecturers’ teaching day willingness. In Journal of Physics: Conference Series. 1842(1) 012007. IOP Publishing. https://doi.org/10.1088/1742-6596/1842/1/012007
• Sun, Y., Luo, X., & Liu, X. (2021). Optimization of a university timetable considering building energy efficiency: an approach based on the building controls virtual test bed platform using a genetic algorithm. Journal of Building Engineering, 35, 102095. https://doi.org/10.1016/j.jobe.2020.102095.
• Sun, G., & Li, Y. (2020). Research and analysis of course arrangement based on genetic algorithm. Journal of Physics: Conference Series, 1650 (3), 032050. IOP Publishing.
• Susan, S., & Bhutani, A. (2019). A novel memetic algorithm incorporating greedy stochastic local search mutation for course scheduling. CSE/EUC, 254-259.
• Szea, S. N., Kuan, H., Chiewa, K. L., Tionga, W. K., & Hengb, C. S. (2020). Heuristic Algorithm for Multi-Location Lecture Timetabling. Advanced Science Engineering Information Technology, 10(2), 455-460.
• Şen, Z. (2004). Genetik algoritmalar ve eniyileme yöntemleri. İstanbul: Su Vakfı.
• Şimşek, A. B. (2021). A course timetabling formulation under circumstances of online education. Journal of Turkish Operations Management, (5)2, (s. 781-791).
• Tan, J. S., Goh, S. L., Sura, S., Kendall, G., & Sabar, N. R. (2021). Hybrid particle swarm optimization with particle elimination for the high school timetabling problem. Evolutionary Intelligence, 14(4), 1915-1930.
• Taşkın, Ç., & Emel, G. G. (2009). Sayısal yöntemlerde genetik algoritmalar. Bursa: Alfa Aktüel.
• Thakare, S., Nikam, T., & Patil, M. (2020). Automated Timetable Generation using Genetic Algorithm. International Journal of Engineering Research & Technology (IJERT), 9 (07), 1425-1427.
• Thang, H. Q., Giang, V. T., Son, N. T., & Anh, B. N. (2023). Teaching assignment based on nash equilibrium and genetic algorithm. In 2023 IEEE Symposium on Industrial Electronics & Applications (ISIEA) (s. 1-7). IEEE. https://doi.org/10.1109/ISIEA58478.2023.10212338
• Tian, R., Si, H., Guo, Z., Zhao, X., & Feng Y. (2021). Realization of course scheduling system based on ımproved genetic algorithm. In 2021 16th International Conference on Computer Science & Education (ICCSE). (s. 1072-1077). IEEE. https://doi.org/10.1109/ICCSE51940.2021.9569620
• Topcu, İ., & Kabak, Ö. (2021). Yöneylem araştırması ders notları. İstanbul Teknik Üniversitesi, 6-7. Erişim adresi https://web.itu.edu.tr/topcuil/ya/END331.pdf
• Trenggonowati, D. L., Herlina, L., Febianti, E., Ilhami, M. A., Muharni, Y., Kurniawan, B., & Irman, A. (2022). Bibliometric analysis of university timetabling using publish and perish. In Conference on Broad Exposure to Science and Technology 2021 (BEST 2021) (s. 307-311). Atlantis Press. https://doi.org/10.2991/aer.k.220131.047
• Tung Ngo. S., Jafreezal, J., Hoang Nguyen, G., & Ngoc Bui, A. (2021). A genetic algorithm for multi-objective optimization in complex course timetabling. In 2021 10th International Conference on Software and Computer Applications, (s. 229-237). https://doi.org/10.1145/3457784.3457821
• Wang, Y., & Lei, A. (2018). Design and research of course arranging system based on niche ımproved genetic algorithm. International Journal of New Developments in Engineering and Society, 2(1), 33-38.
• Wang, P., & Huang, J. (2023, Şubat). Research on multi-objective course scheduling method in colleges based on epidemic prevention and control. In 2023 IEEE 6th Information Technology, Networking, Electronic and Automation Control Conference (ITNEC). 6, (s. 683-687). IEEE. https://doi.org/10.1109/ITNEC56291.2023.10082461
• Weinberg, R., & Berkus, M. (1971). Computer simulation of a living cell: Part I. International Journal of Bio-Medical Computing, 2(2), (s. 95-120).
• Wong, C. H., Goh, S. L., & Likoh, J. (2022). A genetic algorithm for the real-world university course timetabling problem. In 2022 IEEE 18th International Colloquium on Signal Processing & Applications (CSPA) (s. 46-50). IEEE. https://doi.org/10.1109/CSPA55076.2022.9781907
• Wren, A. (1995). Scheduling, timetabling and rostering - a special relationship?. In International conference on the practice and theory of automated timetabling (s. 46-75). Berlin: Springer.
• Xu, J. (2021). Improved genetic algorithm to solve the scheduling problem of college English courses. Complexity. (s. 1-11). https://doi.org/10.1155/2021/7252719
• Yang, Y., Gao, W., & Gao, Y. (2017). Mathematical modeling and system design of timetabling problem based on improved GA. In 2017 13th International Conference on Natural Computation, Fuzzy Systems and Knowledge Discovery (ICNC-FSKD) (s. 214-220). IEEE.
• Yang, Z. (2021). Application of multidirectional mutation genetic algorithm and ıts optimization neural network in intelligent optimization of english teaching courses. Computational Intelligence and Neuroscience. https://doi.org/10.1155/2021/4297600
• Yang, Z. (2022). Research on college english classroom teaching model based on adaptive genetic algorithm. Computational Intelligence and Neuroscience. https://doi.org/10.1155/2022/9527070 Yılmaz, T. N. (2023). Ders programı çizelgeleme probleminin genetik algoritma ile çözümü: bir uygulama (Yayımlanmış yüksek lisans tezi). Osmaniye Korkut Ata Üniversitesi Lisansüstü Eğitim Enstitüsü.
• Yüksek Öğretim Kurulu. Yüksek Öğretim Kurumlarında Uzaktan Öğretime İlişkin Usul ve Esaslar Md.6, (b) Bendi. Erişim Tarihi: 07.01.2022 Erişim Adresi: https://www.yok.gov.tr/Documents/Kurumsal/egitim_ogretim_dairesi/Uzaktan_ogretim/yuksekogretim-kurumlarinda-uzaktan-ogretime-iliskin-usul-ve-esaslar.pdf
• Zaulir, Z. M., Abdülaziz, N. L., & Aizam, N. A. H. (2022). A general mathematical model for university courses timetabling: ımplementation to a public university in malaysia. Malaysian Journal of Fundamental and Applied Sciences, 18(1), (s. 82-94). https://doi.org/10.11113/mjfas.v18n1.2408
• Zhang, Q. (2022). An optimized solution to the course scheduling problem in universities under an improved genetic algorithm. Journal of Intelligent Systems, 31(1), (s. 1065-1073). https://doi.org/10.1515/jisys-2022-0114
• Zhang, Y., Li, C., & Zhang, Y. (2021). Intelligent course scheduling scheme in high school for elective course system in college entrance examination. In 2021 International Conference on Education, Information Management and Service Science (EIMSS) (s. 324-332). IEEE. https://doi.org/10.1109/EIMSS53851.2021.00077
• Zheng, H., Peng, Y., Guo, J., & Chen, Y. C. (2022). Course scheduling algorithm based on improved binary cuckoo search. The Journal of Supercomputing, 78(9), (s. 11895-11920). https://doi.org/10.1007/s11227-022-04341-6