Un problema real de corte óptimo de bobinas de film de plástico
Grupo de Tecnologías de la Computación www.aic.uniovi.es/Tc
UNIVERSIDAD DE OVIEDOCentro de Inteligencia ArtificialDepartamento de InformáticaCampus de Viesques, 33271 Gijón (Asturias)
IV WorkShop on Planning, Scheduling and Temporal Reasoning
IV WorkShop on Planning, Scheduling and Temporal Reasoning 2 de 13
Introducción
Formulación del Problema
Cálculo de Planes de Corte
Resultados Experimentales
Consideraciones Finales
Índice
IV WorkShop on Planning, Scheduling and Temporal Reasoning 3 de 13
Introducción
Objetivo
Optimizar los cortes de bobinas de film de plástico cumpliendo las restricciones y criterios de optimización de la empresa ERVISA (Extrusión de Resinas Vinílicas, S.A.)
Proceso Productivo de ERVISA
1. Generación de bobinas madre de film de plástico de 6 m de ancho
2. Introducción de la bobina madre en la máquina cortadora para la obtención de bobinas de diferentes anchos (según el pedido) pero igual longitud
3. Rebobinado de las distintas bandas generadas en el corte para la obtención de un conjunto de bobinas
4. Paletización de las bobinas generadas tras el corte
IV WorkShop on Planning, Scheduling and Temporal Reasoning 4 de 13
Introducción
Máquina
Margen Aprovechable
Velocidad de Corte
Cambios de Brazos
Rodillos de Presión
Sentido de desplazamiento
del Film
Bobinas generadas
Brazos de Corte
Ancho Aprovechable
Desperdicio Madre
Bobina Madre
Rodillos de Presión generadas
Desperdicio Madre
Bobinas generadas
IV WorkShop on Planning, Scheduling and Temporal Reasoning 5 de 13
Introducción
4 3 2 1ANCHO PEDIDO CLIENTE 1 2 3 4 5 6 7 8 T P 1 790 610 900 900
900 179175 SIERRA DEL ORO 2 1 3 0,1 2 790 610 950 950790 179102 PLASTICAS SUR 4 4 -0,3 3 965 965 965 965790 179103 PLASTICAS SUR 2 2 -0,1 4 1085 880 610 880790 179101 PLASTICAS SUR 4 4 -0,3 5 1085 880 760 610950 179104 PLASTICAS SUR 2 1 3 0 6 1085 880 760 965965 179207 ERVISA 4 6 2 2 14 -1,2 7 965 790 570880 179209 FLEXIPRINT 9 1 10 -0,6 8610 179148 FINA 6 2 1 9 0 9
1085 179147 FINA 12 12 -0,6 10760 179190 ENVASES CANT. 4 4 -0,4
0 0 5800 5790 5735 58400 00 00 00 00 00 00 00 00 00 00 00 00 00 0
24 21 14 6 0 0 0 0 65 -3,4
ER-PP21 25M 152 16000M
BOBINAS APLICADAS
CORTES
B R
A Z
O S
CLIENTE-01 CLIENTE-02
CLIENTE-02 CLIENTE-02 CLIENTE-02 CLIENTE-03 CLIENTE-04 CLIENTE-05 CLIENTE-05 CLIENTE-06
Stocks: palé completo de bobinas de interés para el stock de la empresa
Paletización de Productos: tipo de producto y ancho
Sistema Actual
IV WorkShop on Planning, Scheduling and Temporal Reasoning 6 de 13
Formulación del Problema Variante de 1D-CSP (One Dimension Cutting-Stock Problem)
Dados
Parámetros máquina corte: margen aprovechable [Lmin, Lmax] y Nº máximo de bobinas que se pueden generar en un corte Cmax
Conjunto de Pedidos M = {1,...,m}, anchos (l1,...,lm) y demandas (d1,...,dm)
Conjunto de Stocks S = {m+1,...,m+p}, anchos (lm+1,...,lm+p), máximos permitidos (dm+1,...,dm+p) y restricciones de cantidad (r1,...,rp) (tamaño de lote)
Conjunto de patrones de corte factibles P = {p1,...,pk}
pj = (a1j,...,amj, a(m+1)j,...,a(m+p)j) y aij = bobinas del pedido o stock i que se generan con el patrón pj.
pj es factible sii cumple
La suma de los anchos de las bobinas que lo componen [Lmin, Lmax]
El nº de bobinas generadas en pj Cmax
IV WorkShop on Planning, Scheduling and Temporal Reasoning 7 de 13
Formulación del Problema
Objetivo
Encontrar el plan de cortes Π P y las frecuencias de sus patrones x = (x1,...,x|Π|) que satisfagan las restricciones y cumplan los criterios de optimización
Restricciones
Conjunto de Bobinas generadas estará compuesto por todas las bobinas del pedido y eventualmente por alguna bobina del Stock.
Si existe Stock, será en lotes completos y sin superar un máximo permitido
Criterios de Optimización
1. Minimizar el nº total de cortes que representa el plan de cortes
2. Minimizar el nº de patrones de corte
3. Maximizar la cantidad de Stock generado
4. Minimizar el ancho aprovechado en los cortes (seguridad)
5. Minimizar el nº total de las configuraciones de los brazos de corte
IV WorkShop on Planning, Scheduling and Temporal Reasoning 8 de 13
Algoritmo Heurístico de naturaleza estocástica que resuelve el problema mediante la aplicación sucesiva de varias estrategias de optimización local
Cálculo de Planes de Corte
Algoritmo CalculaPlanDeCortes_1(CP: ConjuntoDePedidos)
// Minimizar Nº de Cortes y Nº de Patrones de Corte
1. ProblemaResidual = CP;
mientras ProblemaResidual {
// Cálculo de la siguiente columna
2. Seleccionar aleatoriamente L[Lmin, Lmax];
3. Buscar el patrón pjP’ P con L Lj Lmax y con más repeticiones, si no hay patrones con LjL se elige el de mayor Lj ;
4. Añadir pj a la solución (Π,x) y actualizar el ProblemaResidual ;
}
5. Devuelve la solución (Π,x);
fin.
IV WorkShop on Planning, Scheduling and Temporal Reasoning 9 de 13
Algoritmo CalculaPlanDeCortes(CP: Conjunto de Pedidos, S: Stock)
1. (Π,x) = CalculaPlanDeCortes_1(CP);
// Maximizar Stock
mientras Se puedan añadir bobinas de S y No empeore la solución actual {
2. Añadir a CP bobinas de S de acuerdo con D|Π|; 3. (Π,x) = CalculaPlanDeCortes_1(CP);
}
// Minimizar Máximo Aprovechado en los Cortes
mientras No empeore la solución actual {
4. Lmax = Lmax - L; 5. (Π,x) = CalculaPlanDeCortes_1(CP);
}
6. Devuelve la solución (Π,x);
fin.
Cálculo de Planes de Corte
IV WorkShop on Planning, Scheduling and Temporal Reasoning 10 de 13
Resultados ExperimentalesObjetivo
Mostrar que el método aquí planteado encuentra soluciones mucho mejores que las que el experto es capaz de encontrar y en un tiempo considerablemente menor
Solución Experto, 30 minutos
Solución Prototipo, 5 segundos
Problema 1
66 Bobinas (65+1) de 9 anchos distintos
IV WorkShop on Planning, Scheduling and Temporal Reasoning 11 de 13
Resultados ExperimentalesProblema 2
127 Bobinas de 21 anchos distintos
Solución Experto, 4 horas Solución Prototipo, 15 segundos
21 Cortes8 Configuraciones4 Configuraciones de BrazosMáximo Aprovechado 5780 mm
21 Cortes7 Configuraciones2 Configuraciones de BrazosMáximo Aprovechado 5680 mm
IV WorkShop on Planning, Scheduling and Temporal Reasoning 12 de 13
Resultados ExperimentalesProblema 3
200 Bobinas de 13 anchos distintos
Solución Experto, > 4 horas Solución Prototipo, 1.5 minutos
25 Cortes5 Configuraciones2 Bobinas de Stock3 Configuraciones de BrazosMáximo Aprovechado 5750 mm
24 Cortes5 Configuraciones0 Bobinas Stock2 Configuraciones de BrazosMáximo Aprovechado 5800 mm
IV WorkShop on Planning, Scheduling and Temporal Reasoning 13 de 13
Consideraciones Finales Versión Real de problema cutting-stock unidimensional
Criterio Secundario de Optimización: minimización del ancho aprovechado (aumenta la fiabilidad)
Objetivo a Corto Plazo
Nuevos criterios de optimización
Eliminación de bobinas
Configuraciones de Rodillos
Priorización de Clientes
Paletización de Pedidos
Tiempo de Respuesta
Mejora de los resultados obtenidos con el prototipo actual
Algoritmos Genéticos
Algoritmos de Ramificación y Poda