Búsqueda de soluciones factibles para el problema de horarios de cursos universitarios

RESUMEN En esta tesis se aborda el problema de los horarios universitarios (UCTP). En el contexto de una universidad, el cual se encuentra dentro de los problemas NP-Completos. El problema consiste en la asignación de una serie de eventos (conferencias, exámenes, tutorías, sesiones de laboratorio, etc) a un número limitado de intervalos de tiempo y salones, de modo que se cumplan una serie de restricciones. El problema que se aborda en esta tesis contempla tres conjuntos de restricciones duras, las cuales deberán cumplirse para obtener un horario factible. Se trabajó con el benchmark propuesto por Rhyan Lewis: 60 instancias que tienen una complejidad mayor a las utilizadas por la competencia de Practice and Theory of Automated Timetabling (PATAT, 2002), la cual está enfocada en el estudio del problema de Timetabling (el problema de programación de horarios). Para encontrar Factibilidad en dichas instancias, se abordan 3 algoritmos, el primero es un enfoque Heurístico que ayuda crear la solución inicial y también logra hallar factibilidad en algunas instancias de tipo “Small”, posterior se desarrollaron dos enfoques Metaheurísticos: Aceptación por Umbral y Recocido Simulado, en los cuales se implementaron los vecindarios “Mover evento” e “Intercambio de eventos”. Se logro encontrar 55 soluciones factibles solo por debajo de un algoritmo que ha encontrado 58. Con la implementación de las metaheurísticas se logró aumentar la factibilidad en las soluciones encontradas. El porcentaje de factibilidad aumento considerablemente entre la heurística del “evento más restringido” y las Metaheurísticas aceptación por Umbral y Recocido Simulado. La heurística obtuvo 8.33% de factibilidad, posteriormente al emplear Aceptación por Umbral se obtuvo el 70% de factibilidad, finalmente con la implementación de Recocido Simulado se obtuvo un 91.66% de factibilidad.

ABSTRACT This tesis address the university Course Timetabling problem (UCTP), In the context of a university, which is within NP-Complete problems. The problem consists of assigning a series of events (conferences, exams, tutorials, lab sessions, etc.). to a limited number of time slots and rooms, so that a set of restrictions are met. The problem tackle in this thesis contemplates 3 hard restrictions which must be met to obtain a feasible schedule. We worked with the benchmark proposed by Rhyan Lewis: 60 instances that have a greater complexity than those used by the Practice and Theory of Automated Timetabling competition (PATAT 2002), which is focused on the study of the Timetabling problem (the problem of scheduling university events). To find Feasibility in these instances, 3 algorithms are approached, the first is a Heuristic approach that helps to create the initial solution and also manages to find Feasibility in some instances of type "Small". After we developed two metaheuristic approaches: Threshold Accepting and Simulated Annealing, in which the neighborhoods "Move event" and "Exchange events" were implemented. It was possible to find 55 feasible solutions only below an algorithm that has found 58. With the implementation of metaheuristics, it was possible to increase the feasibility of the solutions found. The percent of feasibility increases considerably between the heuristic of the "most restricted event" and the metaheuristics Threshold Acceptance and Simulated Annealing. The heuristic obtained 8.33% of feasibility, later when using Threshold Acceptance, 70% of feasibility was obtained, finally with the implementation of Simulated Annealing, a 91.66% of feasibility was obtained.