Correo Electrónico
DNINFOA - SIA
Bibliotecas
Convocatorias
Identidad U.N.
Publicado
A solution to the university course timetabling problem using a hybrid method based on genetic algorithms
Una solución al problema de horarios de cursos universitarios usando un método híbrido basado en algoritmos genéticos
DOI:
https://doi.org/10.15446/dyna.v87n215.85933Palabras clave:
Programming of university courses, Metaheuristics, Mixed Integer Linear programming, HGATS. (en)Programación de cursos universitarios, Metaheurísticas, Programación lineal entera mixta, HGATS (es)
Descargas
In this study, we address the current issues that usually manifest during the programming of university courses, classified as University Course Timetabling Problem, which is considered as a NP-hard problem due to the high computational demand that it requires.
To solve the problem, a Mixed Integer Linear Programming model is proposed, which serves as a reference when dimensioning the problem and the restrictions that must be considered. Next, a hybrid metaheuristic method is designed based on the HGATS algorithm, Hybrid Genetic Algorithm Tabu Search Approach, developed by [16], which combines the diversification capacity of the Genetic Algorithm with the strategy of intensification of the Tabu Search Algorithm. Finally, the validation of the proposed algorithm is performed using the data from the programming of the classes from the academic periods 2018-1 and 2018-2 for the academic program of Industrial Engineering at the Industrial University of Santander, obtaining interesting solutions in a reasonable computational time, being that the process of organizing the schedule by the coordinator can last from hours to days, depending on your ability.
En el presente estudio, abordamos las consideraciones típicas que se tienen en cuenta en la programación de cursos universitarios, clasificado esto dentro de la optimización matemática como el problema de programación de horarios de cursos universitarios, el cual es considerado un problema que converge en un tiempo no polinomial debido a la alta demanda computacional que requiere para alcanzar su solución óptima.
Para resolver el problema se propone un modelo de programación lineal entera mixta, el cual sirve como referencia en cuanto a dimensionamiento del problema y las restricciones a ser consideradas. Y a paso seguido, un método metaheurístico híbrido es diseñado, el cual es basado en el algoritmo HGATS, Algoritmo Híbrido Genético y Búsqueda Tabú, desarrollado por [16], donde combinan la capacidad de diversificación del Algoritmo Genético con la estrategia de intensificación de la Búsqueda Tabú. Finalmente, la validación del algoritmo propuesto se realiza usando los datos de la programación de horarios realizada para los periodos académicos 2018-1 y 2018-2 del programa de ingeniería industrial en la Universidad Industrial de Santander, sobre lo cual se obtienen interesantes resultados en un tiempo computacional razonable, siendo que el proceso de organizar el horario por parte del coordinador puede extenderse de horas a días, dependiendo de su habilidad.
Referencias
Abdelhalim, E. and El Khayat, G., A Utilization-based genetic algorithm for solving the University Timetabling Problem. Alexandria Engineering Journal, 55(2), pp. 1395-1409, 2016. DOI: 10.1016/j.aej.2016.02.017
Abuhamdah, A., Adaptive Acceptance Criterion (AAC) algorithm for optimization problems. Journal of Computer Science, 11(4), pp. 675-691, 2015. DOI: 10.3844/jcssp.2015.675.691
Abuhamdah, A. and Ayob, M., Adaptive randomized descent algorithm for solving course timetabling problems, International Journal of the Physical Sciences, [online]. 5(16), pp. 2516-2522, 2010. Avaliable at: https://academicjournals.org/journal/IJPS/article-full-text-pdf/0F9AE6934683
Al-betar, M.A. and Khader, A.T., A harmony search algorithm for university course timetabling. Annals of Operations Research, 194, pp. 3-31, 2012. DOI: 10.1007/s10479-010-0769-z
Al-Betar, M.A., Khader, A.T. and Zaman, M., University course timetabling using a hybrid harmony search metaheuristic algorithm. IEEE Transactions on Systems, Man and Cybernetics Part C: Applications and Reviews, 42(5), pp. 664-681, 2012. DOI: 10.1109/TSMCC.2011.2174356
Avella, P. and Vasil’ev, I., A computational study of a cutting plane algorithm for university course timetabling. Journal of Scheduling, 8, pp. 497-514, 2005. DOI: 10.1007/s10951-005-4780-1
Burke, E.K., Mareček, J., Parkes, A.J. and Rudová, H., A branch-and-cut procedure for the Udine Course Timetabling problem, Annals of Operations Research, 194, pp. 71-87, 2012. DOI: 10.1007/s10479-010-0828-5
Cruz-Chávez, M.A., Flores-Pichardo, M., Martínez-Oropeza, A., Moreno-Bernal, P. and Cruz-Rosales, M.H., Solving a real constraint satisfaction model for the university course timetabling problem: a case study, Mathematical Problems in Engineering, 2016, Article ID 7194864, 14 pages, 2016. DOI: 10.1155/2016/7194864
Jat, S.N. and Yang, S., A hybrid genetic algorithm and tabu search approach for post enrolment course timetabling, Journal of Scheduling, 14, pp. 617-637, 2011. DOI: 10.1007/s10951-010-0202-0
Nagata, Y. and Ono, I., Random partial neighborhood search for university course timetabling problem. In: Bartz-Beielstein, T., Branke, J., Filipič, B. and Smith, J., (Eds.), Parallel problem solving from Nature – PPSN XIII. PPSN 2014. Lecture Notes in Computer Science, vol 8672. Springer, Cham., 2014. DOI: 10.1007/978-3-319-10762-2_77
Obit, J.H., Developing novel meta-heuristic, hyper-heuristic and cooperative search for course timetabling problems, PhD Thesis, School of Computer Science, University of Nottingham, Nottingham, U.K., 2010.
Schaerf, A. and Di Gaspero, L., Local search techniques for educational timetabling problems. Proc. of the 6th International Symposium on Operations Research in Slovenia (SOR-01), [online]. 2001, pp. 13-23. Available at: http://citeseerx.ist.psu.edu/ viewdoc/citations;jsessionid=1379FD25B42F9EE05916B7D33496660A?doi=10.1.1.24.343
Schimmelpfeng, K. and Helber, S., Application of a real-world university-course timetabling model solved by integer programming. OR Spectrum, 29(4), pp. 783-803, 2007. DOI: 10.1007/s00291-006-0074-z
Vermuyten, H., Lemmens, S., Marques, I. and Beliën, J., Developing compact course timetables with optimized student flows. European Journal of Operational Research, 251(2), pp. 651-661, 2016. DOI: 10.1016/j.ejor.2015.11.028
Welsh, D.J. and Powell, M.B., An upper bound for the chromatic number of a graph and its application to timetabling problems. The Computer Journal, 10, pp. 85-86, 1967. DOI: 10.1093/comjnl/10.1.85
Yang, S. and Jat, S.N., Genetic algorithms with guided and local search strategies for university course timetabling, IEEE Transactions on Systems, Man and Cybernetics Part C: Applications and Reviews, 41(1), pp. 93-106, 2011. DOI: 10.1109/TSMCC.2010.2049200
Cómo citar
IEEE
ACM
ACS
APA
ABNT
Chicago
Harvard
MLA
Turabian
Vancouver
Descargar cita
CrossRef Cited-by
1. Fouad H. Awad, Ali Al-kubaisi, Maha Mahmood. (2022). Large-scale timetabling problems with adaptive tabu search. Journal of Intelligent Systems, 31(1), p.168. https://doi.org/10.1515/jisys-2022-0003.
2. Minh Tam Nguyen, Phat T. Tran-Truong, Anh Tuan Truong. (2026). Computational Intelligence. Communications in Computer and Information Science. 2828, p.164. https://doi.org/10.1007/978-3-032-15635-8_10.
3. Lingzhi Yan, Hua Deng. (2025). Adaptive genetic algorithm for computer course scheduling system under the background of educational informatization. Systems and Soft Computing, 7, p.200324. https://doi.org/10.1016/j.sasc.2025.200324.
4. Juan Guillermo Villegas Ramírez, Pablo Andrés Maya Duque, Karin Julieth Aguilar Imitola. (2025). Modelado matemático para la optimización. https://doi.org/10.17533/udea.978-958-501-248-6.
5. Jing Xu, Zhihan Lv. (2021). [Retracted] Improved Genetic Algorithm to Solve the Scheduling Problem of College English Courses. Complexity, 2021(1) https://doi.org/10.1155/2021/7252719.
6. Martín H. Cruz-Rosales, Marco Antonio Cruz-Chávez, Federico Alonso-Pecina, Jesus del C. Peralta-Abarca, Erika Yesenia Ávila-Melgar, Beatriz Martínez-Bahena, Juana Enríquez-Urbano. (2022). Metaheuristic with Cooperative Processes for the University Course Timetabling Problem. Applied Sciences, 12(2), p.542. https://doi.org/10.3390/app12020542.
7. Xin Gu, Muralee Krish, Shaleeza Sohail, Sweta Thakur, Fariza Sabrina, Zongwen Fan. (2025). From Integer Programming to Machine Learning: A Technical Review on Solving University Timetabling Problems. Computation, 13(1), p.10. https://doi.org/10.3390/computation13010010.
8. Evgenii Fedkin, Natalya Denissova, Iurii Krak, Irina Dyomina. (2021). Automation of Scheduling Training Sessions in Educational Institutions using Genetic Algorithms. 2021 11th IEEE International Conference on Intelligent Data Acquisition and Advanced Computing Systems: Technology and Applications (IDAACS). , p.278. https://doi.org/10.1109/IDAACS53288.2021.9660939.
Dimensions
PlumX
Visitas a la página del resumen del artículo
Descargas
Licencia
Derechos de autor 2020 DYNA
Esta obra está bajo una licencia internacional Creative Commons Atribución-NoComercial-SinDerivadas 4.0.
El autor o autores de un artículo aceptado para publicación en cualquiera de las revistas editadas por la facultad de Minas cederán la totalidad de los derechos patrimoniales a la Universidad Nacional de Colombia de manera gratuita, dentro de los cuáles se incluyen: el derecho a editar, publicar, reproducir y distribuir tanto en medios impresos como digitales, además de incluir en artículo en índices internacionales y/o bases de datos, de igual manera, se faculta a la editorial para utilizar las imágenes, tablas y/o cualquier material gráfico presentado en el artículo para el diseño de carátulas o posters de la misma revista.
