Publicado

2020-11-05

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.85933

Palabras 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

Autores/as

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

[1]
J. Arias-Osorio y A. Mora-Esquivel, «A solution to the university course timetabling problem using a hybrid method based on genetic algorithms», DYNA, vol. 87, n.º 215, pp. 47–56, nov. 2020.

ACM

[1]
Arias-Osorio, J. y Mora-Esquivel, A. 2020. A solution to the university course timetabling problem using a hybrid method based on genetic algorithms. DYNA. 87, 215 (nov. 2020), 47–56. DOI:https://doi.org/10.15446/dyna.v87n215.85933.

ACS

(1)
Arias-Osorio, J.; Mora-Esquivel, A. A solution to the university course timetabling problem using a hybrid method based on genetic algorithms. DYNA 2020, 87, 47-56.

APA

Arias-Osorio, J., & Mora-Esquivel, A. (2020). A solution to the university course timetabling problem using a hybrid method based on genetic algorithms. DYNA, 87(215), 47–56. https://doi.org/10.15446/dyna.v87n215.85933

ABNT

ARIAS-OSORIO, J.; MORA-ESQUIVEL, A. A solution to the university course timetabling problem using a hybrid method based on genetic algorithms. DYNA, [S. l.], v. 87, n. 215, p. 47–56, 2020. DOI: 10.15446/dyna.v87n215.85933. Disponível em: https://revistas.unal.edu.co/index.php/dyna/article/view/85933. Acesso em: 11 ago. 2022.

Chicago

Arias-Osorio, Javier, y Andrés Mora-Esquivel. 2020. «A solution to the university course timetabling problem using a hybrid method based on genetic algorithms». DYNA 87 (215):47-56. https://doi.org/10.15446/dyna.v87n215.85933.

Harvard

Arias-Osorio, J. y Mora-Esquivel, A. (2020) «A solution to the university course timetabling problem using a hybrid method based on genetic algorithms», DYNA, 87(215), pp. 47–56. doi: 10.15446/dyna.v87n215.85933.

MLA

Arias-Osorio, J., y A. Mora-Esquivel. «A solution to the university course timetabling problem using a hybrid method based on genetic algorithms». DYNA, vol. 87, n.º 215, noviembre de 2020, pp. 47-56, doi:10.15446/dyna.v87n215.85933.

Turabian

Arias-Osorio, Javier, y Andrés Mora-Esquivel. «A solution to the university course timetabling problem using a hybrid method based on genetic algorithms». DYNA 87, no. 215 (noviembre 5, 2020): 47–56. Accedido agosto 11, 2022. https://revistas.unal.edu.co/index.php/dyna/article/view/85933.

Vancouver

1.
Arias-Osorio J, Mora-Esquivel A. A solution to the university course timetabling problem using a hybrid method based on genetic algorithms. DYNA [Internet]. 5 de noviembre de 2020 [citado 11 de agosto de 2022];87(215):47-56. Disponible en: https://revistas.unal.edu.co/index.php/dyna/article/view/85933

Descargar cita

Dimensions

PlumX

Descargas

Los datos de descargas todavía no están disponibles.

Visitas a la página del resumen del artículo

456