Model Paralelisasi Algoritma Genetika Terpandu pada Sistem Penjadwalan Kuliah Universitas dengan Alokasi Waktu Dinamis
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
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.
Copyright (c) 2021 Jurnal RESTI (Rekayasa Sistem dan Teknologi Informasi)
This work is licensed under a Creative Commons Attribution 4.0 International License.
Copyright in each article belongs to the author
- The author acknowledges that the RESTI Journal (System Engineering and Information Technology) is the first publisher to publish with a license Creative Commons Attribution 4.0 International License.
- Authors can enter writing separately, arrange the non-exclusive distribution of manuscripts that have been published in this journal into other versions (eg sent to the author's institutional repository, publication in a book, etc.), by acknowledging that the manuscript has been published for the first time in the RESTI (Rekayasa Sistem dan Teknologi Informasi) journal ;
