Título :	Optimización de procesos de planeación de horarios escolares mediante coloración de grafos
Autor(es):	Hansel Amadeus Montúffar Otero
Palabras clave:	Ingeniería y Tecnología Ciencias Tecnológicas Ciencia de los ordenadores
Fecha de publicación :	7-ago-2019
Editorial :	Facultad de Ingeniería
Facultad:	Facultad de Ingeniería
Programa académico:	Maestría en Ciencias en Inteligencia Artificial
Resumen:	En esta tesis se estudia el problema de planeación de horarios escolares y se modela mediante el problema de coloración de vértices en un grafo. Un grafo apropiadamente coloreado consiste en una asignación de color a cada uno de sus vértices de modo tal que ningún par de vértices tienen el mismo color si existe una arista que los una. La modelación consiste en representar cada materia mediante un vértice, y si dos materias no se deben ofrecer en el mismo horario, ya que el plan de estudios requiere que ambas materias se deben cursar durante el mismo período académico, o porque existe al menos un estudiante que deba llevar ambas, entonces se construye una arista uniendo esos dos vértices. El número de colores necesarios corresponde al número de ranuras de tiempo requeridas para ofertar las materias que un alumno regular puede tomar, donde cada subconjunto de vértices del mismo color representa las materias que pueden ofrecerse al mismo tiempo sin riesgos de conflicto de horario. Se ha demostrado que el problema de coloración de grafos es NP-completo, por lo que se conjetura que no existe un algoritmo eficiente que produzca soluciones óptimas para cualquier instancia del problema. En esta tesis se discuten una serie de algoritmos metaheurísticos eficientes basados en técnicas de inteligencia artificial, tales como Búsqueda Local, Búsqueda Tabú y Algoritmos Genéticos. Asimismo se exploran algunas heurísticas basadas en criterios que establecen un orden preferente de coloración de vértices. La eficiencia y resultados de estos algoritmos son medidos utilizando instancias de grafos publicadas por el DIMACS (\textit{Center for Discrete Mathematics and Theoretical Computer Science}). Finalmente, se propone un prototipo de sistema en el cual el usuario puede obtener una planeación de horarios de cursos dado el requerimiento de curso a ofertar durante un semestre determinado de acuerdo al plan de estudios en cuestión que establece el orden en que los cursos puedan ser tomados por un estudiante.
URI:	https://ri-ng.uaq.mx/handle/123456789/8674
Aparece en:	Maestría en Ciencias en Inteligencia Artificial

Los ítems de DSpace están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.