Mostrar el registro sencillo del ítem

Algoritmo basado en la coloración de grafos para la programación flexible de horarios y salones en una institución universitaria: caso de estudio en Colombia

dc.contributor.advisorChauta Torres, José Manuel
dc.contributor.authorLeal Figueredo, Andrés David
dc.coverage.spatialBogotá D.C.
dc.date.accessioned2025-01-30T16:34:40Z
dc.date.available2025-01-30T16:34:40Z
dc.date.issued2024-12-05
dc.identifier.urihttp://hdl.handle.net/10823/7524
dc.description.abstractLa asignación de horarios y salones en instituciones universitarias es un problema complejo clasificado como NP-Completo, debido a la interdependencia de variables y restricciones asociadas. Este trabajo presenta el diseño de un algoritmo basado en la coloración de grafos para la programación eficaz y flexible de horarios en la Institución Universitaria Politécnico Grancolombiano. El modelo propuesto aborda restricciones estrictas y opcionales, representando las sesiones de los cursos como vértices de un grafo no dirigido, con conflictos definidos por aristas. Los resultados incluyen la caracterización de variables, el diseño del algoritmo con una complejidad temporal cuadrática para una parte del problema y una normalización preliminar de datos. Se destaca la flexibilidad del enfoque mediante la asignación de espacios libres por tipo de salón y la aproximación a restricciones suaves, como la programación consecutiva y la asignación en un mismo campus. Las conclusiones proponen mejoras futuras, como la incorporación de la disponibilidad de profesores y el desarrollo de una interfaz gráfica para visualizar horarios. Este estudio contribuye al desarrollo de soluciones flexibles y adaptables en la programación académica universitaria.spa
dc.description.tableofcontentsRESUMEN... 7 INTRODUCCIÓN... 8 JUSTIFICACIÓN Y ANTECEDENTES... 9 OBJETIVO GENERAL... 14 OBJETIVOS ESPECÍFICOS... 14 ALCANCE... 14 MARCO TEÓRICO... 16 GRAFO... 16 DIRECCIÓN DE ARISTAS... 16 TRAYECTORIA (WALK)... 16 CAMINO (PATH)... 17 CONECTIVIDAD DE GRAFO... 17 GRADO Y ADYACENCIA DE VÉRTICES... 17 REPRESENTACIÓN COMPUTACIONAL... 17 MATRIZ DE ADYACENCIA... 17 LISTA DE ADYACENCIA... 18 PROBLEMA DE COLORACIÓN... 18 PROPIEDADES DE COLORACIÓN... 18 COMPLEJIDAD COMPUTACIONAL (NP COMPLETO)... 19 METODOLOGÍA... 21 CARACTERIZACIÓN DE PARÁMETROS... 21 PROGRAM (PROGRAMA ACADÉMICO)... 21 CAMPUS... 21 BUILDING (EDIFICIO)... 21 ROOM TYPE (TIPO DE SALÓN)... 22 ROOM (SALÓN)... 22 SUBJECT (ASIGNATURA)... 22 CURRICULUM (PLAN DE ESTUDIOS)... 22 SESSION (SESIÓN)... 22 COURSE (GRUPO DE CURSO)... 23 TEACHER (PROFESOR/A)... m23 COURSE – SESSION – TEACHER (GRUPO DE CURSO – SESIÓN – PROFESOR/A)... 23 RESTRICCIONES... 24 RESTRICCIONES DURAS... 24 Temporales... 24 Espaciales... 24 RESTRICCIONES SUAVES... 24 Temporales... 24 Espaciales... 24 OBTENCIÓN DE LA INFORMACIÓN... 24 SESIONES POR CURSOS Y PROFESORES... 25 SALONES DISPONIBLES... 26 PLAN DE ESTUDIOS DE PROGRAMAS ACADÉMICOS... 26 OTRAS VARIABLES... 26 GENERACIÓN DE LAS ESTRUCTURAS DE DATOS... 27 VARIABLES DE CANTIDAD... 27 LISTA DE ADYACENCIA DE LAS SESIONES... 27 ARREGLO DE ÚLTIMO COLOR CON DISPONIBILIDAD POR TIPO DE SALÓN... 28 MATRIZ DE OCUPACIÓN ACTUAL DE TIPOS DE SALÓN POR COLOR... 28 ARREGLO DE PORCENTAJES DE OCUPACIÓN MAXIMA POR TIPO DE SALÓN... 28 ARREGLO DE DISPONIBILIDAD POR TIPO DE SALÓN... 28 ARREGLO DE OCUPACIÓN MAXIMA POR TIPO DE SALÓN... 28 ARREGLO DE CLASES DE COLORES... 28 MATRIZ DE COLORES ASIGNADOS A VÉRTICES... 28 ARREGLO DE CAMPUS OBLIGATORIOS POR VÉRTICE... 28 ARREGLO DE SALONES POR TIPO DE SALÓN... 29 ORDEN DE LOS BLOQUES DE TIEMPO... 29 ORDEN EN LA ASIGNACIÓN DE SALONES... 29 ALGORITMO... 30 CREACIÓN DE VARIABLES... 30 COLORACIÓN DE VÉRTICES DE UN MISMO NÚMERO DE BLOQUES DE TIEMPO... 30 COLORACIÓN DE GRAFO... 33 ASIGNACION DE SALON DE CAMPUS A UNA SESION... 34 CALCULAR CAMPUS UNICO DE ADYACENTE EN BLOQUE CONSECUTIVO... 35 ASIGNAR SALONES... 36 RESULTADOS Y DISCUSIÓN... 38 ESPECIFICACIÓN DE PARÁMETROS... 38 RESULTADOS... 38 CONCLUSIONES... 39 TRABAJO FUTURO... 39 REFERENCIAS... 40spa
dc.format.mimetypeapplication/pdfspa
dc.language.isospaspa
dc.titleAlgoritmo basado en la coloración de grafos para la programación flexible de horarios y salones en una institución universitaria: caso de estudio en Colombiaspa
dc.typebachelorThesisspa
dc.type.localTesis/Trabajo de grado - Monografía - Pregradospa
dc.type.driverinfo:eu-repo/semantics/bachelorThesisspa
dc.title.translatedGraph Coloring-Based Algorithm for Flexible Scheduling of Classes and Rooms in a University Institution: A Case Study in Colombiaspa
dc.subject.proposalAsignación de horariosspa
dc.subject.proposalColoración de grafosspa
dc.subject.proposalRestricciones duras y suavesspa
dc.subject.lembGestión administrativaspa
dc.subject.lembInnovación tecnológica - algoritmosspa
dc.subject.lembRegistro de tiempos - horariosspa
dc.description.abstractenglishThe allocation of schedules and classrooms in university institutions is a complex problem classified as NP-Complete, due to the interdependence of associated variables and constraints. This paper presents the design of an algorithm based on graph coloring for the effective and flexible scheduling of classes at the Politécnico Grancolombiano University Institution. The proposed model addresses both strict and optional constraints, representing course sessions as vertices of an undirected graph, with conflicts defined by edges. The results include the characterization of variables, the design of the algorithm with quadratic time complexity for part of the problem, and a preliminary data normalization. The flexibility of the approach is highlighted through the allocation of free spaces by room type and the approximation to soft constraints, such as consecutive scheduling and assignment on the same campus. The conclusions propose future improvements, such as incorporating the availability of professors and developing a graphical interface to visualize schedules. This study contributes to the development of flexible and adaptable solutions in university academic scheduling.spa
dc.subject.keywordsGraph coloringspa
dc.subject.keywordsHard and soft restrictionsspa
dc.subject.keywordsSchedule assignmentspa
dc.relation.referencesF. Zabidee y M. H. M. Adnan, «Optimization in University Student Timetables: A Comprehensive Literature Review,» Journal of Advanced Research in Applied Sciences and Engineering Technology, p. 14 – 43, 2024.spa
dc.relation.referencesP. Nandal, A. Satyawali, D. Sachdeva y A. S. Tomar, «Graph Coloring based Scheduling Algorithm to automatically generate College Course Timetable,» 2021 11th International Conference on Cloud Computing, Data Science & Engineering (Confluence), pp. 210-214, 2021.spa
dc.relation.referencesAvinash, R. Jain y R. Kumar, «University Time Table Scheduling Using Graph Coloring Technique,» ResearchGate, 2018.spa
dc.relation.referencesV. Donderia y P. K. Jana, «A novel scheme for graph coloring,» Procedia Technology, vol. 4, pp. 261-266, 1 2012.spa
dc.relation.referencesD. Brélaz, «New methods to color the vertices of a graph,» Communications of the ACM, vol. 22, nº 4, pp. 251-256, 4 1979.spa
dc.relation.referencesN. Poddar y B. Mondal, «AN INSTRUCTION ON COURSE TIMETABLE SCHEDULING APPLYING GRAPH COLORING APPROACH,» International Journal of Recent Scientific Research, vol. 9, nº 2, pp. 23939-23945, 2 2018.spa
dc.relation.referencesM. Assi, B. Halawi y R. A. Haraty, «Genetic Algorithm Analysis using the Graph Coloring Method for Solving the University Timetable Problem,» Procedia Computer Science, p. 899 – 906, 2018.spa
dc.relation.referencesT. W. Ekanayake, P. Subasinghe, S. Ragel, A. Gamage y S. Attanayaka, «Intelligent Timetable Scheduler: A Comparison of Genetic, Graph Coloring, Heuristic and Iterated Local Search Algorithms,» 2019 International Conference on Advancements in Computing, ICAC 2019, p. 85 – 90, 2019.spa
dc.relation.referencesR. K. J. Bendi, T. Sunarni y A. Alfian, «Using Graph Coloring For University Timetable Problem,» International Journal of Science and Research, vol. 7, nº 11, pp. 1692-1697, 2018.spa
dc.relation.referencesA. Muklason, B. A. Nugroho, E. Riksakomara, R. Tyasnurita, F. Mahananto, R. A. Vinarti y M. A. Nuriman, «Flexible Automated Course Timetabling System with Lecturer Preferences Using Hyper-heuristic Algorithm,» ACM International Conference Proceeding Series, p. 258 – 262, 2022.spa
dc.relation.referencesD. J. A. Welsh y M. B. Powell, «An upper bound for the chromatic number of a graph and its application to timetabling problems,» The Computer Journal, vol. 10, nº 1, pp. 85-86, 1 1967.spa
dc.relation.referencesM. Laguna y R. Martí, «A GRASP for Coloring Sparse Graphs,» Computational Optimization and Applications, vol. 19, nº 2, pp. 165-178, 1 2001.spa
dc.relation.referencesB. S. Baker y E. G. Coffman, «Mutual exclusion scheduling,» {Theoretical Computer Science, vol. 162, nº 2, pp. 225-243, 1996.spa
dc.relation.referencesR. P. Grimaldi, Discrete and combinatorial mathematics, 5 ed., Rose-Hulman Institute of Technology: Addison Wesley, 2004.spa
dc.relation.referencesA. Laaksonen, Competitive Programmer's Handbook, Helsinki: CSES, 2018.spa
dc.relation.referencesR. Lewis, A Guide to Graph Colouring, UK: Springer, 2015.spa
dc.relation.referencesE. Bampis, A. Kononov, G. Lucarelli y I. Milis, «Bounded max-colorings of graphs,» Journal of Discrete Algorithms, p. 56 – 68, 2014.spa
dc.publisher.programIngeniería de Sistemasspa
dc.type.coarhttp://purl.org/coar/resource_type/c_7a1fspa
dc.publisher.facultyFacultad de ingeniería y Diseño e Innovaciónspa
dc.identifier.instnameinstname:Politécnico Grancolombianospa
dc.identifier.reponamereponame:Alejandría Repositorio Comunidadspa
dc.type.hasversioninfo:eu-repo/semantics/acceptedVersion
dc.rights.accessrightsinfo:eu-repo/semantics/openAccess
dc.identifier.repourlrepourl:http://alejandria.poligran.edu.cospa
dc.type.redcolhttps://purl.org/redcol/resource_type/TP
dc.rights.creativecommonsAtribución-NoComercial-SinDerivadas 2.5 Colombiaspa
dc.type.versioninfo:eu-repo/semantics/acceptedVersionspa
dc.type.coarversionhttp://purl.org/coar/version/c_ab4af688f83e57aaspa


Ficheros en el ítem

Thumbnail
Nombre:
Tesis v3 corregida.pdf
Tamaño:
1.342Mb
Formato:
PDF
Ver/

Este ítem aparece en la(s) siguiente(s) colección(ones)

Mostrar el registro sencillo del ítem