Model Paralelisasi Algoritma Genetika Terpandu pada Sistem Penjadwalan Kuliah Universitas dengan Alokasi Waktu Dinamis

  • Muhammad Fachrie Universitas Teknologi Yogyakarta
  • Anita Fira Waluyo Universitas Teknologi Yogyakarta
Keywords: evolutionary computation, genetic algorithm, optimization, parallelization, university course timetable

Abstract

One of the many techniques used to solve the University Course Timetable Problem (UCTP) is Genetic Algorithm (GA) which is a technique in the field of Evolutionary Computation. However, GA has high computational complexity due to the large number of evolutionary operators that must be performed during the evolutionary process, so it takes a long time to produce an optimal timetable. The computation time will also increase when the number of optimized variables is very large, such as in UCTP. Of course, this makes the application less reliable by users. Therefore, this article proposes a parallelization model for GA to reduce computation time in solving UCTP problems. The proposed AG is designed with a multithreading CPU scheme and implements a guided creep mutation mechanism and eliminates the recombination mechanism to reduce more computation time. The proposed system was tested and evaluated using two different UCTP datasets from the University of Technology Yogyakarta which contained 878 and 1140 lecture meetings in even and odd semesters. Unlike the previous ones, this study discusses UCTP with dynamic time slots where the duration of the lecture depends on the course credits. From the tests that have been done, it is found that the GA that was built is able to generate optimal course timetable without any clashes in a relatively fast time, that is less than 60 minutes for 1140 lecture meetings and less than 20 minutes for 878 lecture meetings. The use of the multithreading CPU model has succeeded in reducing computation time by 62% when compared to the conventional model which only uses one thread.

Downloads

Download data is not yet available.

References

L. Shuguang and B. Lin, “Research on Complex Curriculum Arrangement Problem Based on Novel Quantum Genetic Evolutionary Algorithm,” Proc. 31st Chinese Control Decis. Conf. CCDC 2019, pp. 3783–3787, 2019, doi: 10.1109/CCDC.2019.8832728.

Y. Yang, W. Gao, and Y. Gao, “Mathematical modeling and system design of timetabling problem based on improved GA,” ICNC-FSKD 2017 - 13th Int. Conf. Nat. Comput. Fuzzy Syst. Knowl. Discov., pp. 214–220, 2018, doi: 10.1109/FSKD.2017.8393102.

S. Yang and S. N. Jat, “Genetic algorithms with guided and local search strategies for university course timetabling,” IEEE Trans. Syst. Man Cybern. Part C Appl. Rev., vol. 41, no. 1, pp. 93–106, 2011, doi: 10.1109/TSMCC.2010.2049200.

M. Lindahl, A. J. Mason, T. Stidsen, and M. Sørensen, “A strategic view of University timetabling,” Eur. J. Oper. Res., vol. 266, no. 1, pp. 35–45, 2018, doi: 10.1016/j.ejor.2017.09.022.

Suyanto, “An Informed Genetic Algorithm for University,” Lect. Notes Comput. Sci., vol. vol 6114, no. 1, pp. 229–236, 2010.

A. A. Gozali, J. Tirtawangsa, and T. A. Basuki, “Asynchronous island model genetic algorithm for university course timetabling,” PATAT 2014 - Proc. 10th Int. Conf. Pract. Theory Autom. Timetabling, no. August, pp. 179–187, 2014.

A. A. Gozali and S. Fujimura, “Reinforced island model genetic algorithm to solve university course timetabling,” Telkomnika (Telecommunication Comput. Electron. Control., vol. 16, no. 6, pp. 2747–2755, 2018, doi: 10.12928/TELKOMNIKA.v16i6.9691.

S. Pappu, K. T. Talele, and J. Mandviwala, “Application of Parallel Genetic Algorithm for Exam Timetabling Problem,” vol. 3, no. 9, pp. 1–4, 2012.

K. Henryk, “Parallelisation of genetic algorithms for solving university timetabling problems,” 2006.

A. R. East, “Timetable Scheduling via Genetic Algorithm,” 2019.

A. A. Mahiba and C. A. D. Durai, “Genetic algorithm with search bank strategies for university course timetabling problem,” Procedia Eng., vol. 38, pp. 253–263, 2012, doi: 10.1016/j.proeng.2012.06.033.

T. Song, S. Liu, X. Tang, X. Peng, and M. Chen, “An iterated local search algorithm for the University Course Timetabling Problem,” Appl. Soft Comput. J., vol. 68, pp. 597–608, 2018, doi: 10.1016/j.asoc.2018.04.034.

T. Mauritsius, A. N. Fajar, Harisno, and P. John, “Novel Local Searches for Finding Feasible Solutions in Educational Timetabling Problem,” Proc. 2017 5th Int. Conf. Instrumentation, Commun. Inf. Technol. Biomed. Eng. ICICI-BME 2017, no. November, pp. 270–275, 2018, doi: 10.1109/ICICI-BME.2017.8537723.

S. F. H. Irene, S. Deris, and S. Z. Mohd Hashim, “A combination of PSO and local search in university course timetabling problem,” Proc. - 2009 Int. Conf. Comput. Eng. Technol. ICCET 2009, vol. 2, pp. 492–495, 2009, doi: 10.1109/ICCET.2009.188.

D. Lohpetch and S. Jaengchuea, “A hybrid multi-objective genetic algorithm with a new local search approach for solving the post enrolment based course timetabling problem,” Adv. Intell. Syst. Comput., vol. 463, pp. 195–206, 2016, doi: 10.1007/978-3-319-40415-8_19.

J. B. Matias, A. C. Fajardo, and R. M. Medina, “A fair course timetabling using genetic algorithm with guided search technique,” Proc. 2018 5th Int. Conf. Bus. Ind. Res. Smart Technol. Next Gener. Information, Eng. Bus. Soc. Sci. ICBIR 2018, pp. 77–82, 2018, doi: 10.1109/ICBIR.2018.8391170.

J. B. Matias, A. C. Fajardo, and R. M. Medina, “Examining Genetic Algorithm with Guided Search and Self-Adaptive Neighborhood Strategies for Curriculum-Based Course Timetable Problem,” Proc. - 2018 4th Int. Conf. Adv. Comput. Commun. Autom. ICACCA 2018, pp. 1–6, 2018, doi: 10.1109/ICACCAF.2018.8776728.

Published
2021-06-26
How to Cite
Fachrie, M., & Anita Fira Waluyo. (2021). Model Paralelisasi Algoritma Genetika Terpandu pada Sistem Penjadwalan Kuliah Universitas dengan Alokasi Waktu Dinamis. Jurnal RESTI (Rekayasa Sistem Dan Teknologi Informasi), 5(3), 550 - 556. https://doi.org/10.29207/resti.v5i3.2988
Section
Artikel Teknologi Informasi