Optimización de procesos de planeación de horarios escolares mediante coloración de grafos

Hansel Amadeus Montúffar Otero

Buscar

dc.rights.license	http://creativecommons.org/licenses/by-nc-nd/4.0	es_ES
dc.contributor	Arturo González Gutiérrez	es_ES
dc.creator	Hansel Amadeus Montúffar Otero	es_ES
dc.date	2019-08-07
dc.date.accessioned	2023-06-13T21:00:46Z
dc.date.available	2023-06-13T21:00:46Z
dc.date.issued	2019-08-07
dc.identifier.uri	https://ri-ng.uaq.mx/handle/123456789/8674
dc.description	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.	es_ES
dc.format	Adobe PDF	es_ES
dc.language.iso	spa	es_ES
dc.publisher	Facultad de Ingeniería	es_ES
dc.relation.requires	Si	es_ES
dc.rights	Acceso Abierto	es_ES
dc.subject	Ingeniería y Tecnología	es_ES
dc.subject	Ciencias Tecnológicas	es_ES
dc.subject	Ciencia de los ordenadores	es_ES
dc.title	Optimización de procesos de planeación de horarios escolares mediante coloración de grafos	es_ES
dc.type	Tesis de maestría	es_ES
dc.creator.tid	CURP	es_ES
dc.creator.identificador	MOOH940730HNENTN04	es_ES
dc.contributor.role	Director	es_ES
dc.degree.name	Maestría en Ciencias en Inteligencia Artificial	es_ES
dc.degree.department	Facultad de Ingeniería	es_ES
dc.degree.level	Maestría	es_ES