Application of Genetic Algorithms Technique in the Generation of Academic Schedules
Abstract
This paper presents an application to solve the problem of low efficiency in the generation of academic schedules for an educational institution through metaheuristic techniques. The agile SCRUM methodology was used for the planning and development of the system, in addition a sample of four processes for the evaluation of system efficiency was determined. In the planning phase, 15 user stories, 13 technical stories and 19 system sprints were identified. In the development phase the design of the architecture, interfaces, database was carried out. The process for working the genetic algorithms in the generation of schedules through the processes of initialization, selection, crossing, mutation and recombination was carried out until compliance with an objective function thus obtaining an academic schedule with the conditions that the educational institution requires. To evaluate the efficiency of the system, the ISO/ IEC 25010 standard was used through the sub-characteristics of time behavior and resource utilization. The results obtained in time behavior reveal that with the use of the system it is reduced by 99.12%, compared to the manual processes thus showing a total efficiency of 93.75%.
Resumen. Este trabajo presenta una aplicación para resolver el problema de la poca eficiencia en la generación de horarios académicos para una institución educativa a través de técnicas metaheurísticas. Se utilizó la metodología ágil SCRUM para la planificación y desarrollo del sistema, además se determinó una muestra de cuatro procesos para la evaluación de eficiencia del sistema. En la fase de planificación se identificaron 15 historias de usuario, 13 historias técnicas y 19 sprints del sistema. En la fase de desarrollo se realizó el diseño de la arquitectura, interfaces, base de datos, además se señaló el proceso de como los algoritmos genéticos trabajan en la generación de horarios mediante los procesos de inicialización, selección, cruce, mutación y recombinación hasta cumplir con una función objetivo obteniendo así un horario académico con las condiciones que la institución educativa requiere. Para evaluar la eficiencia del sistema se utilizó la norma ISO/IEC 25010 a través de las subcaracterísticas de comportamiento de tiempos y utilización de recursos. Los resultados obtenidos en cuanto a tiempos revelan que con el uso del sistema se reduce en un 99.12% en comparación a los procesos manuales, mostrando así una eficiencia total del 93.75%.
References
[1] J. A. Ahumada, “Generacion de horarios academicos en INACAP utilizando algoritmos geneticos,” 2014.
[2] M. Andres, G. Cubillos, E. Hamid, P. Quiroga, R. Emilio, and S. Ruiz, “Problema del school timetabling y algoritmos genéticos” pp. 259–276, 2013.
[3] L. Nuñez, “Aplicaciónde algoritmos geneticosen la generacionde horariosde clase en la Escuela de Enfermeria de la Universidad Nacional de Chimborazo,” 2016.
[4] O. D. Castrillón, “Combinación entre algoritmos genéticos y aleatorios para la programación de horarios de clases basado en ritmos cognitivos,” vol. 25, no. 4, pp. 51–62, 2014.
[5] C. D. Oliva and G. Ramírez, “Algoritmo de tipo búsqueda tabú para un problema de programación de horarios universitarios vespertinos,” Inge Cuc, vol. 9, no. 2, pp. xx–xx, 2013.
[6] M. D. Lozano, “Diseño de un algoritmo para realizar la programación de horarios de la carrera de Ingeniería Industrial de la Pontificia Universidad Javeriana,” 2016.
[7] O. Chavez, P. Pozos, and J. L. Gomez, “Aspiración probabilístico aplicada a la generación de horarios escolares,” vol. 22, no. 1, pp. 153–177, 2015.
[8] J. Marin Lozada, D. L. Hoyos B, C. A. Peñuela, and J. J. Santa Chávez, “Herramientas heurísticas para la asignación óptima de horarios de clase,” Av. Investig. en Ing., vol. 10, no. 1, pp. 68–74, 2013.
[9] J. A. M. Pérez, “Metaheurísticas?: Conceptos y propiedades,” 2004.
[10] F. Herrera, “Introducción a los algoritmos metaheurísticos introducción a los algoritmos,” 2010.
[11] N. Alancay, S. M. Villagra, and N. A. Villagra, “Metaheurísticas de trayectoria y poblacional aplicadas a problemas de optimización combinatoria,” Inf. Científicos - Técnicos UNPA, vol. 8, no. 1, p. 202, 2018.
[12] J. Gallart Suárez, F. A. Manchego, A. A. Nole, G. B. Nicho, and M. T. Anticona, “Generación inteligente dehorariosempleandoheurísticasGRASPconBúsqueda TabúparalaPontificiaUniversidadCatólica del Perú,” no. November 2015, 2009.
[13] C. A. Algarín Robles, “Optimización por colonia de hormigas: aplicaciones y tendencias,” Rev. Ing. Solidar., vol. 6, pp. 83–89, 2010.
[14] M. César and J. A. Montoya, Revista EIA., no. 8. Escuela de ingenieria de Antioquia, 2007.
[15] J. V. Paredes and P. M. R. Basalo, “Estudio y aplicación de metaheurísticas y comparación con métodos exhaustivos,” 2016.
[16] A. A. Vivanco Villamar, “Evaluación de calidad del sistema integrado proyecto,” p. 224, 2011.
[17] E. C. VALENCIA ESPINOZA, “Desarrollo de una aplicación web para la gestión de la información de un centro odontológico usando el framework Zend.,” p. 200, 2018.
[18] Rashedi, E., Nezamabadi-pour, H., Saryazdi, S.: GSA: A Gravitational Search Algorithm. Inf. Sci. 179, 2232–2248, (2009).