SOME APPROACHES TO SOLVE MULTIPLE BALANCED ACADEMIC CURRICULUM PROBLEM

Abstract

En el siguiente trabajo se contrastan algunos enfoques de resolución para el Multiple Balanced Academic Curriculum Problem (MBACP), un problema de optimizaci ón y satisfacción de restricciones (Constraint Satisfaction Optimization Problem, CSOP) de complejidad NP-Dif??cil, que busca la planificación de los cursos que los estudiantes deben seguir de tal forma de balancear la carga académica en varias mallas curriculares simultáneamente, incluyendo los elementos que comparten. Este problema es una derivación del Balanced Academic Curriculum Problem (BACP), un tópico altamente abordado con diferentes técnicas de resoluci ón. Para lograr esto se definieron los siguientes objetivos: ? Implementar tres técnicas de resolución de CSOP: Programación Lineal Entera, Búsqueda Local y/o Metaheur??sticas, e Hibridación entre Programaci ón Lineal Entera y Metaheur??sticas. ? Definir un conjunto de instancias a resolver. ? Generación de métricas para la realización de benchmarking. Como resultado se obtienen el desempeo de las diversas técnicas aplicadas, las cuales son comparadas, demostrando la capacidad costo/desempeo de éstas con respecto a un problema de alta complejidad, a esto se le aade, un análisis del por qué de su comportamiento. También, se verifica la naturaleza compleja de MBACP. Finalmente, se generan cursos de acción para el inicio de trabajos futuros en la materia.