Tarea de corte
El problema de anidamiento es un problema de optimización NP-completo , esencialmente reducible a un problema de mochila . El problema es un problema de programación lineal entera . El problema surge en muchas áreas de la industria. Imagine que trabaja en una fábrica de pulpa y papel y tiene una cantidad de rollos de papel de ancho fijo, pero diferentes clientes necesitan diferentes cantidades de rollos de diferentes anchos. ¿Cómo cortar papel para minimizar el desperdicio?
Según la Confederación de Fabricantes Europeos de Papel [1] , en 2012, 1.331 máquinas de papel en la región generaron un desperdicio promedio de 56 millones de euros (aproximadamente 73 millones de dólares estadounidenses) cada una. Ahorrar incluso el 1% será muy significativo.
Formulación de problemas y enfoques para la solución
La formulación estándar del problema de anidamiento (pero no el único) asume una lista de m pedidos, cada pedido requiere piezas. Formamos todas las combinaciones de anidamiento posibles ("mapas de corte") y asociamos con cada mapa una variable entera positiva , que indica cuántas veces se usó el mapa. Escribamos el problema de programación lineal:
, entero
donde - cuántas veces aparece el pedido en la tarjeta y - el precio (a menudo perdido) de la tarjeta . La naturaleza precisa de las restricciones puede conducir a características matemáticas ligeramente diferentes. Los límites dados son límites mínimos ( al menos se debe producir una cantidad determinada, pero no se excluye que se produzca más). Si , se requiere minimizar el número de piezas cortadas del material de origen. Si las restricciones de las desigualdades se reemplazan por igualdades, el problema se denomina contenedorización . En una formulación más general, las restricciones tienen dos caras (y en este caso, la solución de minimización de pérdidas puede diferir de la solución con el número mínimo de piezas de material de origen):
Esta formulación del problema es aplicable no sólo al caso unidimensional. Son posibles muchas variaciones, por ejemplo, el objetivo no es minimizar el desperdicio, sino maximizar la cantidad total de bienes producidos.
En general, el número de cartas posibles crece exponencialmente con m , el número de pedidos. A medida que aumenta el número de pedidos, puede que no sea práctico enumerar posibles patrones de anidamiento.
Alternativamente, se puede usar la generación posterior . Este método resuelve el problema de anidamiento comenzando con algunas tarjetas. El método genera nuevos mapas, si es necesario, durante el proceso de solución. En el caso unidimensional, aparecen nuevos mapas al resolver un problema de optimización adicional, el problema de la mochila , que utiliza información sobre las variables duales de un problema de programación lineal . El problema de la mochila tiene métodos bien conocidos para resolverlo, como el método de ramificación y límite y la programación dinámica . La generación de columnas diferidas puede ser mucho más eficiente que el enfoque original, especialmente a medida que crece el tamaño de la tarea. Gilmour y Gomory utilizaron por primera vez la generación de columna retardada aplicada al problema de anidamiento en una serie de artículos publicados en la década de 1960 [2] [3] . Demostraron que este enfoque está garantizado para conducir a una solución óptima (fraccional) sin tener que enumerar todos los mapas posibles de antemano.
El método original de Gilmour y Gomory no era un número entero, por lo que la solución podía contener componentes fraccionarios, por ejemplo, un determinado mapa tenía que usarse 3,67 veces. El redondeo al entero más cercano a menudo no funciona, en el sentido de que da como resultado una solución subóptima y una subproducción o sobreproducción para algunos pedidos (y una posible violación de la restricción si es de dos lados). Esta deficiencia se supera en nuevos algoritmos que permiten encontrar soluciones óptimas (en el sentido de encontrar una solución con el mínimo desperdicio) de problemas muy grandes (generalmente más grandes de lo que se necesita en la práctica [4] [5] ).
El problema del anidamiento es a menudo extremadamente degenerado, ya que es posible un gran número de soluciones con la misma cantidad de pérdidas. Esta degeneración surge de la capacidad de reorganizar partes, creando nuevos patrones de anidamiento, pero sin cambiar las pérdidas resultantes. Esto da una colección completa de tareas relacionadas que satisfacen las mismas restricciones, tales como:
- La tarea de encontrar el número mínimo de mapas de anidamiento: encuentre una solución con un número mínimo de mapas de anidamiento entre soluciones con pérdidas mínimas. Esta tarea es muy difícil, incluso si se conocen las pérdidas [6] [7] . Existe la conjetura de que cualquier problema de anidamiento unidimensional restringido por ecuaciones con n órdenes tiene al menos una solución de desperdicio mínimo con n + 1 mapas de anidamiento. No se conocen los límites superiores del número de gráficos anidados, aunque se conocen ejemplos con n + 5.
- La tarea del almacén mínimo: encontrar una secuencia de corte para que no se acumule una gran cantidad de pedidos parcialmente completados. El problema estuvo abierto hasta 2007, cuando se publicó un algoritmo eficiente basado en programación dinámica [8] .
- El problema del número mínimo de cambios de cuchillas (para un problema de anidamiento unidimensional): encuentre la secuencia de aplicación de mapas de anidamiento para minimizar la cantidad de movimientos de las cuchillas de corte. Este problema es un caso especial del problema generalizado del viajante de comercio .
Una ilustración de un problema de corte unidimensional
La máquina de papel puede producir un número ilimitado de rollos (espacios en blanco), cada uno de 5600 mm de ancho. Necesitas obtener los siguientes 13 rollos finales:
| Ancho | rollos |
|---|---|
| 1380 | 22 |
| 1520 | 25 |
| 1560 | 12 |
| 1710 | catorce |
| 1820 | Dieciocho |
| 1880 | Dieciocho |
| 1930 | veinte |
| 2000 | diez |
| 2050 | 12 |
| 2100 | catorce |
| 2140 | dieciséis |
| 2150 | Dieciocho |
| 2200 | veinte |
Solución
Hay 308 posibles patrones de anidamiento para esta pequeña tarea. La solución óptima requiere 73 rollos originales y tiene un 0,401 % de desperdicio. Se puede demostrar que el número mínimo de nidos para esta cantidad de residuos es 10. También se puede calcular que existen 19 soluciones diferentes, cada una con 10 nidos y 0,401% de residuos. Una de esas soluciones se muestra a continuación y en la figura:
| Número de tarjetas | cortes |
|---|---|
| 2 | 1820 + 1820 + 1820 |
| 3 | 1380 + 2150 + 1930 |
| 12 | 1380 + 2150 + 2050 |
| 7 | 1380 + 2100 + 2100 |
| 12 | 2200 + 1820 + 1560 |
| ocho | 2200 + 1520 + 1880 |
| una | 1520 + 1930 + 2150 |
| dieciséis | 1520 + 1930 + 2140 |
| diez | 1710 + 2000 + 1880 |
| 2 | 1710 + 1710 + 2150 |
| 73 |
Clasificación
Las tareas de anidamiento se pueden clasificar de varias formas [9] . Una forma es anidar dimensiones: el ejemplo anterior ilustra el anidamiento unidimensional (1D). Otros usos industriales del anidamiento 1D son el corte de tuberías, cables y barras de acero. Los problemas bidimensionales se utilizan en la producción de muebles, ropa y vidrio. No hay muchas aplicaciones de anidamiento en 3D, pero los problemas relacionados con el empaque en 3D tienen muchas aplicaciones industriales, en particular, la distribución de objetos en contenedores de envío ( ver, por ejemplo , la hipótesis de Kepler) .
La tarea de corte en las industrias del papel, la película y el acero
Una aplicación industrial del problema de anidamiento para plantas de producción en masa ocurre cuando el material base se produce en rollos grandes y luego se corta en piezas más pequeñas (ver corte longitudinal ). Esto ocurre, por ejemplo, en la producción de películas de papel y polímeros, así como en la fabricación de láminas planas de metal (hierro o bronce). Hay muchas variaciones y restricciones adicionales debido a restricciones de fabricación o de proceso, requisitos del cliente y problemas de calidad. Algunos ejemplos:
- Un proceso de dos etapas donde el rollo se produce en la primera etapa y luego se procesa nuevamente en otra máquina. Por ejemplo, todo el papel de oficina (por ejemplo, A4 en Europa, Carta en EE. UU.) se produce en este proceso. Surgen dificultades porque las máquinas para el segundo proceso son más estrechas que las máquinas para el primero. El uso eficiente de ambos pasos del proceso es importante (tanto en términos de ahorro de material como de ahorro de energía) y lo que funciona para el primer paso puede no funcionar para el segundo, y se debe encontrar un compromiso. La película metalizada (utilizada para el envasado de alimentos) y el papel plastificado ( cartón para envasado de líquidos , por ejemplo, el envasado de jugos) son otros ejemplos de tales procesos.
- Las bobinadoras limitan el corte física o lógicamente: las restricciones generales surgen del hecho de que solo se permite un cierto número de cuchillos, por lo que la tabla de corte no debe contener más de un cierto número de cuchillos. Dado que las bobinadoras no están estandarizadas, existen muchas restricciones adicionales.
- Como limitación adicional, por ejemplo, se puede dar una restricción en la dirección de corte: diferentes bordes de la hoja pueden tener una gran diferencia de espesor y algunas aplicaciones son muy sensibles a esto.
- Un ejemplo del impacto de los requisitos de calidad es cuando el rollo principal contiene defectos que deben eliminarse. Los materiales costosos con altos requisitos de calidad, como el papel fotográfico o Tyvek , deben optimizarse cuidadosamente para minimizar el desperdicio.
- Las tareas multimáquina surgen cuando un pedido se puede producir en más de una máquina y estas máquinas tienen diferentes anchos. Básicamente, la disponibilidad de múltiples rollos de origen con diferentes anchos reduce el desperdicio. En la práctica, sin embargo, se debe tener en cuenta un orden de corte adicional.
- También hay problemas cuando los rollos resultantes no tienen que ser del mismo diámetro, pero pueden estar dentro de un cierto intervalo. A veces, este problema se llama el problema de 1½ dimensión . Esta variante aparece, por ejemplo, en la producción de cartón ondulado .
- En la industria del laminado de acero, una característica distintiva es que las bobinas originales difieren principalmente en ancho y largo. Por lo tanto, existe una similitud con la variante de múltiples máquinas descrita anteriormente. En este caso, el desperdicio puede ocurrir tanto en ancho como en largo.
El software de anidamiento para la industria papelera es suministrado por ABB Group , Greycon , Honeywell y Tieto .
El algoritmo de anidamiento para la industria del acero fue formulado por Robert Gongorra en 1998 y SONS (Steel Optimization Nesting Software) desarrolló un software para mejorar la utilización de la placa de acero y reducir el desperdicio.
Problema de corte para la industria del vidrio
La tarea de corte con guillotina es la tarea de cortar láminas de vidrio en rectángulos de dimensiones específicas, utilizando solo cortes que se extienden a lo largo de toda la longitud (o ancho) de la lámina.
Tarea de surtido
El problema relacionado de determinar (para el caso unidimensional) el mejor tamaño del rollo original que satisfaga los requisitos; conocido como el problema del surtido [10] .
Historia
El problema del corte fue formulado por primera vez por Kantorovich en 1939 [11] . En 1951, incluso antes de que las computadoras estuvieran ampliamente disponibles, L. V. Kantorovich y V. A. Zalgaller propusieron [12] un método para resolver el problema del uso económico del material durante el corte usando programación lineal. La técnica propuesta más tarde se denominó Método de Generación de Columnas .
Software
| Nombre | Licencia | Breve descripción |
|---|---|---|
| Solucionador de vicepresidente | GPL | Software gratuito "Vector Packing Solver" ( VPSolver ) que se puede utilizar para optimizar el anidamiento 1D. El método de solución se basa en la formulación del flujo en el gráfico. |
Notas
- ↑ Estadísticas clave 2012 (enlace no disponible) . Confederación de Industrias Papeleras Europeas. Consultado el 3 de julio de 2013. Archivado desde el original el 6 de octubre de 2014.
- ↑ PC Gilmore, RE Gomory. Un enfoque de programación lineal para el problema del material de corte // Investigación de operaciones. - 1961. - Nº 9 . - S. 849-859 .
- ↑ PC Gilmore, RE Gomory. Un enfoque de programación lineal para el problema del material de corte - Parte II // Investigación de operaciones. - 1963. - Nº 11 . - S. 863-888 .
- ↑ C. Goulimis. Soluciones óptimas para el problema del material de corte // European Journal of Operational Research. - 1990. - Nº 44 . - S. 197-208 .
- ↑ V. de Carvalho. Solución exacta de problemas de stock de corte mediante generación de columnas y branch-and-bound // Transacciones internacionales en investigación operativa. - 1998. - Nº 5 . - S. 35-44 .
- ↑ S. Umetani, M. Yagiura y T. Ibaraki. Problema de stock de corte unidimensional para minimizar el número de patrones diferentes // European Journal of Operational Research. - 2003. - Nº 146 . - S. 388-402 .
- ↑ A. Diegel, E. Montocchio, E. Walters, S. van Schalkwyk y S. Naidoo. Configuración que minimiza las condiciones en el problema de pérdida de ajuste // European Journal of Operational Research. - 1996. - Nº 95 . - S. 631-640 .
- ↑ María García de la Banda, PJ Stuckey. Programación dinámica para minimizar el número máximo de pilas abiertas // INFORMA Journal on Computing. - 3007. - T. 19 , N º 4 . - S. 607-617 .
- ↑ G. Wäscher, H. Haußner, H. Schumann. Una tipología mejorada de problemas de corte y empaque // European Journal of Operational Research. - T. 183 , N º 3 . - S. 1109-1130 .
- ↑ Raffensperger John F. El surtido generalizado y los mejores problemas de longitud de stock de corte // Transacciones internacionales en investigación operativa. - 2010. - Enero ( vol. 17 , No. 1 ). - S. 35-49 . — ISSN 0969-6016 . -doi : 10.1111/ j.1475-3995.2009.00724.x .
- ↑ L. V. Kantorovich. Métodos matemáticos de organización y planificación de la producción. – Universidad Estatal de Leningrado.
- ↑ Kantorovich L. V., Zalgaller V. A. Corte racional de materiales industriales. - Novosibirsk: Nauka, 1971.
Literatura
- programación lineal. - WH Freeman, 1983. - ISBN 978-0-7167-1587-0 .
- Hatem Ben Amor, JM Valério de Carvalho. Generación de columnas // Problemas de stock de corte en la generación de columnas / Guy Desaulniers, Jacques Desrosiers y Marius M. Solomon. - Springer, 2005. - T. XVI. — ISBN 0-387-25485-4 .