Magíster en Gestión de Operaciones / Ingeniero Civil Matemático / En el presente trabajo se estudia el problema de envasado y embotellado de pedidos en
líneas de producción. El problema es de tipo scheduling con características propias. La resolución
del problema se aborda desde dos ángulos.
El primer enfoque consiste en plantear un problema de programación lineal mixto satisfaciendo
las restricciones operacionales del sistema. Los resultados de esta primera estrategia
satisfacen los requerimientos técnicos, sin embargo, los altos tiempos computacionales impiden
su utilización para casos reales.
El segundo enfoque consiste en la utilización de un Algoritmo Glotón Usando Constraint
Programming (AGUCP) más una estrategia de mejoramiento de la solución. AGUCP permite
encontrar una solución factible al problema planteado en el modelo de programación lineal
mixto con una calidad aceptable. En este caso, los tiempos computacionales son excelentes
incluso para casos de gran tamaño. Sin embargo existe un porcentaje de entre el 15% y el
20% de los casos estudiados en los cuales el algoritmo no encuentra solución.
Se presenta además una mejora a la heurística AGUCP, la cual se denomina AGUCP++ y
consiste básicamente en una implementación propia de AGUCP adaptando el modelo para
enfocarse directamente en las variables de decisión de modo de insertarse mejor al espíritu
del Constraint Programming. La implementación de este algoritmo fue hecha en Python. Las
principales mejoras de este nuevo algoritmo son: (i) Se trabaja con una menor cantidad de
variables debido al modo de guardar la información. (ii) El algoritmo entrega una solución,
a pesar que, haya uno o más trabajos que no pudieron incorporarse. (iii) Se disminuye la
cantidad de casos en los cuales no todos los trabajos son agendados a un 5 %. Esto depende
esencialmente de cuan exigentes sea el caso de estudio. (iv) Los tiempos computacionales
disminuyen en un 70% en comparación con AGUCP
Finalmente, se incorpora una técnica de mejoramiento de la solución obtenida a través
de AGUCP++, utilizando una estrategia basada en la técnica llamada Local Search. Estas
búsquedas locales operan optimizando sobre un número acotado de trabajos -a partir de una
solución inicial-, dejando fijos los demás. Esta estrategia permite, en poco tiempo, obtener
mejoras sustantivas de la solución. Según los experimentos realizados, el porcentaje de mejora
varía entre un 5% y un 28%.
| Identifer | oai:union.ndltd.org:UCHILE/oai:repositorio.uchile.cl:2250/113496 |
| Date | January 2013 |
| Creators | Basso Sotz, Franco Fabián |
| Contributors | Amaya Espinoza, Jorge Luis, Facultad de Ciencias Físicas y Matemáticas, Departamento de Ingeniería Industrial, Departamento de Ingeniería Matemática, Gouet Bañares, Raúl, Jofré Cáceres, René, Cortés Carrillo, Cristián |
| Publisher | Universidad de Chile |
| Source Sets | Universidad de Chile |
| Language | Spanish |
| Detected Language | Spanish |
| Type | Tesis |
Page generated in 0.002 seconds