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