Comparación de algoritmos genéticos para resolver el problema de asignación de horarios y profesores en los cursos del departamento de Ingeniería Electrónica y Mecatrónica de la Universidad del Valle de Guatemala.

Abstract

Uno de los aspectos claves en la administración de los departamentos de las universidades es la asignación de los diferentes horarios y profesores que deben tener cada uno de los cursos en los diferentes años de cada programa de estudio. Debido a que durante un plan de estudios los cursos son impartidos por diferentes departamentos, especialmente durante los primeros dos años. Una de las restricciones más importantes a tomar en cuenta en este modelo por el departamento de Electrónica y Mecatrónica son los horarios prohibidos, posibles periodos ya ocupados por otros departamentos, a cada estudiante de diferente año en cursos que debe asignarse para satisfacer su programa de estudios. La programación de los horarios es una tarea que puede consumir tiempo significativo al cuerpo administrativo, la cual podría solucionarse o acercarse a una solución computacionalmente para reducir el tiempo invertido por el departamento. Un problema de asignación de horarios es considerado un problema de tipo NP-Hard dentro de la teoría de complejidad computacional. La utilización de algoritmos metaheurísticos es muy efectiva y aplicable en este tipo de problemas de optimización combinatoria. En los resultados obtenidos en este trabajo de graduación se puede observar como actúan las diferentes variaciones de un algoritmo genético frente a los parámetros de entrada y como lograr su convergencia. Entre los resultados más relevantes se pudo demostrar que una mutación pequeña como uno de cada cien periodos es suficiente para lograr una convergencia en el programa de algoritmo genético. Los parámetros de entrada del algoritmo son los que definen el comportamiento en la convergencia de una solución ya que estos deben ser posibles de lograr en el horario cumpliendo todas las restricciones.