Formulación De Un Modelo De Programación Matemática

UNIVERSIDAD DE CHILE FACULTAD DE CIENCIAS FISICAS Y MATEMATICAS DEPARTAMENTO DE INGE NIERIA INDUSTRIAL

FORMULACIÓN DE UN MODELO DE PROGRAMACIÓN MATEMÁTICA PARA LA ASIGNACIÓN DE HORARIOS ESCOLARES

TESIS PARA OPTAR AL GRADO DE MAGÍSTER EN GESTION DE OPERACIONES

ROBERTO DEL BARCO GAMARRA

PROFESOR GUIA: SR. PABLO ANDRES REY MIEMBROS DE LA COMISIÓN EVALUADORA SR. RICHARD WEBER HAAS SR. JAIMEMIRANDA PINO SR. VICTOR PARADA DAZA SANTIAGO DE CHILE MAYO, 2010

A mis Padres , hermanos y Zumel, por su apoyo y confianza incondicional.

-ii-

Agradecimientos
A Dios, pues sin su guía, compañía y fortaleza ésta tarea hubiera quedado inconclusa. A toda mi familia, a quienes no puedo menos que agradecerles por el apoyo tanto económico como espiritual, pues he corrido con la mejor de las suertes altenerlos a mi lado. A mi esposa, Zumel Espinoza, por haberse contagiado con mi entusiamo en el momento de emprender con el Magíster, quedando en statu quo otros planes conjuntos. Como parte de este proyecto de formación profesional, tiene un particular espacio la acogida recibida por la Residencia Universitaria Cardenal Caro. Expreso a sus directores y principalmente amigos Gabriela Vivanco yVictor Allende -al igual que a la Comunidad Marianista- mi mayor agradecimiento por su consejo y amistad. Agradezco a la Universidad de Chile que me permitió vivir una experiencia académica que marcará mi desarrollo profesional de aquí en adelante. La enseñanza recibida por parte de los señores docentes -quiénes son personajes reconocidos dentro del área de la gestión de operaciones- motiva mi actuar ycondicionan el deseo de aportar, desde cualquier esfera, al desarrollo de la ciencia. Al Dr. Pablo Rey, tutor del presente trabajo, quién no escatimó su tiempo para poder guiar el desarrollo del mismo, sus comentarios y observaciones permitieron hacer de éste un mejor trabajo. Finalmente, y como una enseñanza práctica de cómo la logistica se constituye en un pilar fundamental en la prestación deservicios, agradezco a Julie Lagos Barra por su colaboración y gestión.

A todos ellos, gracias.

-iii-

Resumen
El problema de programación de horarios en una instituci n educativa consiste en determinar ó una secuencia de encuentros entre profesores y estudiantes en un determinado período de tiempo satisfaciendo un conjunto de restricciones de diversa índole. En particular, una buenaconfiguración horaria permite construir los lineamientos estratégicos, programáticos y operativos de la política de servicio en el área educativa. La motivación del presente trabajo se basa en la solución a un problema que pertenece a esta familia combinatorial, donde el entorno esta definido por el sistema educativo boliviano focalizado en la Unidad Educativa Colegio Americano de la Ciudad de Oruro,tomando en cuenta las condicionantes distintivas de la misma. La soluci n planteada obedece a un enfoque exacto, mediante la conformación de un modelo de ó programación entera mixta. La determinación de la funci n objetivo consistió en dividir el ó conjunto de restricciones esenciales y el otro con los atributos deseables en un horario a ser penalizados en la función objetivo. La instancia abordada,correspondiente a la configuración horaria de la gestión 2008, presentó alrededor de 25.000 variables y 89.000 restricciones alcanzando soluciones con un gap menor al 5% en aproximadamente 2 horas de funcionamiento. El problema de programación entera 8 mixta fue modelado con OPL STUDIO 3.5.1. y resuelto con CPLEX 7.5. Sobre la misma instancia se evaluó la aplicación de un enfoque alternativo basadoen la búsqueda local para disminuir el costo computacional además de generar un horario compacto para los educadores, alcanzándose soluciones con menos del 5% de gap en 8 horas.

Por la comparación del desempeño del enfoque exacto con la heuística se desarrollo una familia de instancias cuyos resultados revelaron que para instancias pequeñas se alcanza buenos rendimientos en tiempos razonables...