Programación de trabajos en líneas de producción

Abstract

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%.