ESTUDIO DE MODELOS DE OPTIMIZACIÓN PARA EL PROBLEMA DE GENERACIÓN DE MULTIPLES MALLAS CURRICULARES BALANCEADAS

Abstract

Los problemas de optimización combinatoria tienen una enorme importancia en muchas aplicaciones de la vida real. Especialmente, en este trabajo se estudia uno de estos, el Múltiple Balanced Academic Curriculum Problem (MBACP). El MBACP es una generalización del BACP que considera la resolución simultánea de currículos académicos, donde el objetivo es minimizar la máxima diferencia entre las máximas diferencias de todas las cargas académicas de los currículos involucrados. El objetivo de este trabajo fue estudiar y desarrollar modelos matemáticos para el ya mencionado problema, ya que hasta entonces exista un escaso estudio del problema. Es así como en el presente trabajo se proponen dos nuevos modelos los cuales solucionan parcialmente algunas de las complicaciones que presenta el original. Posteriormente, se estudia el comportamiento de estos tanto en un solver de Programación con Restricciones como en un solver de Programación Lineal Entera. Las instancias utilizadas para realizar las pruebas son los currículos vigentes de Ingeniería Ejecución Informática, Ingeniera Informática e Ingeniería Civil Informática de la Universidad Técnica Federico Santa María. La comparación de resultados demuestra que la mejor combinación modelo-solver esta relacionado con el modelo original bajo un solver de Programación Lineal Entera, sin embargo, no es factible encontrar la solución óptima en instancias que consideran tres currículos académicos. Otra conclusión obtenida del estudio es que el tercer modelo obtiene mejores resultados en un solver de Programación con Restricciones en comparación con el primer modelo bajo el mismo solver; esto se explica fundamentalmente a la posibilidad de realizar más propagaciones debido a la naturaleza del mismo. Es importante mencionar que el modelo número tres en ninguna instancia encuentra el óptimo. Finalmente, el estudio muestra que el modelo número dos bajo ninguna combinación de solver-instancia encuentra alguna solución factible, lo cual se explica fundamentalmente a su naturaleza, ya que en la practica se deben resolver tres mallas curriculares por separado.