En la investigación de operaciones , el problema del material de corte es el problema de cortar piezas de material de stock de tamaño estándar , como rollos de papel o láminas de metal , en piezas de tamaños específicos mientras se minimiza el desperdicio de material. Es un problema de optimización en matemáticas que surge de aplicaciones en la industria. En términos de complejidad computacional , el problema es un problema NP-difícil reducible al problema de la mochila . El problema se puede formular como un problema de programación lineal de números enteros .
Ilustración de un problema de material de corte unidimensional
Una máquina de papel puede producir un número ilimitado de rollos maestros (jumbo), cada uno de 5600 mm de ancho. Se deben cortar los siguientes 13 elementos, en la siguiente tabla.
Lo importante de este tipo de problema es que se pueden fabricar muchas unidades de producto diferentes a partir del mismo rollo maestro, y el número de combinaciones posibles es en sí mismo muy grande, en general, y no es trivial de enumerar.
Por lo tanto, el problema es encontrar un conjunto óptimo de patrones para hacer rollos de producto a partir del rollo maestro, de manera que se satisfaga la demanda y se minimicen los desperdicios.
Ancho #Artículos 1380 22 1520 25 1560 12 1710 14 1820 18 1880 18 1930 20 2000 10 2050 12 2100 14 2140 dieciséis 2150 18 2200 20
Límites y cheques
Se obtiene un límite inferior simple dividiendo la cantidad total de producto por el tamaño de cada rollo de master. El producto total requerido es 1380 x 22 + 1520 x 25 + ... + 2200 x 20 = 407160 mm. Cada rollo maestro mide 5600 mm, lo que requiere un mínimo de 72,7 rollos, lo que significa que se requieren 73 rollos o más.
Solución
![](http://wikiimg.tojsiabtv.com/wikipedia/en/thumb/c/cb/CuttingStock.gif/430px-CuttingStock.gif)
Hay 308 patrones posibles para esta pequeña instancia. La respuesta óptima requiere 73 rollos maestros y tiene un desperdicio de 0.401%; se puede demostrar computacionalmente que en este caso el número mínimo de patrones con este nivel de desperdicio es 10. También se puede calcular que existen 19 soluciones diferentes, cada una con 10 patrones y un desperdicio de 0.401%, de los cuales una de estas soluciones se muestra a continuación y en la imagen:
Repetición Contenido 2 1820 + 1820 + 1820 3 1380 + 2150 + 1930 12 1380 + 2150 + 2050 7 1380 + 2100 + 2100 12 2200 + 1820 + 1560 8 2200 + 1520 + 1880 1 1520 + 1930 + 2150 dieciséis 1520 + 1930 + 2140 10 1710 + 2000 + 1880 2 1710 + 1710 + 2150 73
Clasificación
Los problemas de material de corte se pueden clasificar de varias formas. [1] Una forma es la dimensionalidad del corte: el ejemplo anterior ilustra un problema unidimensional (1D); Otras aplicaciones industriales de 1D ocurren al cortar tuberías, cables y barras de acero. Los problemas bidimensionales (2D) se encuentran en la producción de muebles, ropa y vidrio. Cuando el artículo principal o las piezas requeridas tienen una forma irregular (una situación que se encuentra a menudo en las industrias del cuero, textiles y metales), esto se conoce como el problema de anidamiento .
No se conocen muchas aplicaciones tridimensionales (3D) que involucren el corte; sin embargo, el problema del embalaje 3D estrechamente relacionado tiene muchas aplicaciones industriales, como el embalaje de objetos en contenedores de transporte (véase, por ejemplo, contenedorización : el problema del embalaje de esferas relacionado se ha estudiado desde el siglo XVII ( conjetura de Kepler )).
Aplicaciones
Las aplicaciones industriales de los problemas de material de corte para grandes volúmenes de producción surgen especialmente cuando el material básico se produce en rollos grandes que luego se cortan en unidades más pequeñas (ver corte de rollos ). Esto se hace, por ejemplo, en las industrias de películas de papel y plástico, pero también en la producción de metales planos como el acero o el latón. Hay muchas variantes y limitaciones adicionales que surgen de las limitaciones especiales de producción debido a los límites de la maquinaria y el proceso, los requisitos del cliente y los problemas de calidad; algunos ejemplos son:
- De dos etapas, donde los rollos producidos en la primera etapa se procesan luego por segunda vez. Por ejemplo, todo el material de oficina (por ejemplo, tamaño A4 en Europa, tamaño Carta en EE. UU.) Se produce en este proceso. La complicación surge porque la maquinaria de la segunda etapa es más estrecha que la primaria. La utilización eficiente de ambas etapas de producción es importante (desde la perspectiva del uso de energía o materiales) y lo que es eficiente para la etapa primaria puede ser ineficiente para la secundaria, lo que da lugar a compensaciones. La película metalizada (utilizada en el envasado de aperitivos) y la extrusión de plástico sobre papel (utilizado en el envasado de líquidos , por ejemplo, cartones de zumo) son otros ejemplos de dicho proceso.
- Restricciones de la bobinadora donde el proceso de corte tiene restricciones físicas o lógicas: una restricción muy común es que solo se dispone de un cierto número de cuchillas de corte, por lo que los patrones factibles no deben contener más de un número máximo de rollos. Debido a que la maquinaria devanadora no está estandarizada, se encuentran muchas otras limitaciones.
- Un ejemplo de un requisito del cliente es cuando un pedido en particular no se puede satisfacer desde ninguna de las dos posiciones de los bordes: esto se debe a que los bordes de la hoja tienden a tener mayores variaciones de espesor y algunas aplicaciones pueden ser muy sensibles a estos.
- Un ejemplo de un problema de calidad es cuando el rollo de master contiene defectos que deben cortarse. Los materiales costosos con características de calidad exigentes, como el papel fotográfico o Tyvek, deben optimizarse cuidadosamente para minimizar el área desperdiciada.
- Los problemas de múltiples máquinas surgen cuando los pedidos se pueden producir en más de una máquina y estas máquinas tienen diferentes anchos. Generalmente, la disponibilidad de más de un ancho de rollo de master mejora considerablemente el desperdicio; en la práctica, sin embargo, es posible que deban tenerse en cuenta restricciones adicionales de división de pedidos.
- También existe un problema semicontinuo, donde los rollos producidos no tienen que ser del mismo diámetro, pero pueden variar dentro de un rango. Esto suele ocurrir con los pedidos de hojas. Esto a veces se conoce como un problema de 1½ dimensión . Esta variante también se produce en la producción de tableros de fibra ondulada , donde se denomina, de forma algo confusa, el problema de programación de la onduladora .
- Debido a que algunas máquinas de papel son relativamente estrechas en comparación con los artículos demandados, algunas empresas han invertido en un proceso secundario de biselado (también conocido como soldadura de banda ), mediante el cual dos bobinas (producidas cortando las bobinas jumbo iniciales) se unen una al lado de la otra. lado (con un poco de superposición) para formar un rollo más ancho. La producción de bobinas más estrechas en el proceso primario conduce a un menor desperdicio general. [2]
- En la industria de los metales, una diferencia clave es que, por lo general, los rollos maestros se producen antes y generalmente son diferentes entre sí (tanto en términos de ancho como de largo). Por lo tanto, existen similitudes con el problema de múltiples máquinas mencionado anteriormente. La presencia de variaciones de longitud crea un problema de 2-D, porque el desperdicio puede ocurrir tanto a lo ancho como a lo largo. [ cita requerida ]
- El problema de la guillotina es otro problema bidimensional de cortar hojas en rectángulos de tamaños específicos; sin embargo, solo se permiten cortes que continúan a lo largo de cada hoja. Las aplicaciones industriales de este problema se pueden encontrar en la industria del vidrio.
![](http://wikiimg.tojsiabtv.com/wikipedia/en/thumb/a/a9/CuttingStockGuillotine.png/220px-CuttingStockGuillotine.png)
![](http://wikiimg.tojsiabtv.com/wikipedia/en/thumb/4/48/CuttingStockNonGuillotine.png/220px-CuttingStockNonGuillotine.png)
- El problema del material de corte de determinar, para el caso unidimensional, el mejor tamaño de maestro que satisfará la demanda dada, se conoce como problema de surtido . [3]
Historia
El problema del material de corte fue formulado por primera vez por Kantorovich en 1939. [4] En 1951, antes de que las computadoras estuvieran ampliamente disponibles, LV Kantorovich y VA Zalgaller sugirieron [5] resolver el problema del uso económico del material en la etapa de corte con la ayuda de sistemas lineales programación. La técnica propuesta se denominó posteriormente método de generación de columnas .
Enfoques matemáticos de formulación y solución
La formulación estándar para el problema del material de corte (pero no el único) comienza con una lista de m pedidos, cada uno de los cuales requiere piezas, donde . Luego construimos una lista de todas las posibles combinaciones de cortes (a menudo llamados "patrones"). Dejarsea el número de esos patrones. Asociamos con cada patrón una variable entera positiva, que representa cuántas veces el patrón se va a utilizar, donde . El programa de enteros lineales es entonces:
- , entero
dónde es el número de veces que orden aparece en patrón y es el costo (a menudo el desperdicio) del patrón . La naturaleza precisa de las restricciones cuantitativas puede conducir a características matemáticas sutilmente diferentes. Las restricciones de cantidad de la formulación anterior son restricciones mínimas (se debe producir al menos la cantidad dada de cada pedido, pero posiblemente más). Cuándoel objetivo minimiza el número de artículos maestros utilizados y, si la restricción de la cantidad a producir se reemplaza por la igualdad, se denomina problema de embalaje en contenedores . La formulación más general tiene restricciones de dos caras (y en este caso una solución de desperdicio mínimo puede consumir más que el número mínimo de elementos maestros):
Esta formulación se aplica no solo a problemas unidimensionales. Son posibles muchas variaciones, incluida una en la que el objetivo no es minimizar el desperdicio, sino maximizar el valor total de los artículos producidos, permitiendo que cada pedido tenga un valor diferente.
En general, el número de patrones posibles crece exponencialmente en función de m , el número de órdenes. A medida que aumenta el número de pedidos, puede resultar impráctico enumerar los posibles patrones de corte.
Un enfoque alternativo utiliza la generación de columnas retrasada . Este método resuelve el problema del material de corte comenzando con unos pocos patrones. Genera patrones adicionales cuando se necesitan. Para el caso unidimensional, los nuevos patrones se introducen resolviendo un problema de optimización auxiliar llamado problema de mochila , utilizando información de variable dual del programa lineal . El problema de la mochila tiene métodos bien conocidos para resolverlo, como la programación dinámica y ramificada . El método de Generación de columnas demoradas puede ser mucho más eficiente que el enfoque original, especialmente a medida que aumenta el tamaño del problema. El enfoque de generación de columnas aplicado al problema del material de corte fue pionero en Gilmore y Gomory en una serie de artículos publicados en la década de 1960. [6] [7] Gilmore y Gomory demostraron que se garantiza que este enfoque convergerá a la solución óptima (fraccional), sin necesidad de enumerar todos los patrones posibles de antemano.
Una limitación del método original de Gilmore y Gomory es que no maneja la integralidad, por lo que la solución puede contener fracciones, por ejemplo, un patrón particular debe producirse 3.67 veces. Redondear al número entero más cercano a menudo no funciona, en el sentido de que puede conducir a una solución subóptima y / o una producción insuficiente o excesiva de algunos de los pedidos (y una posible inviabilidad en presencia de restricciones de demanda de dos caras ). Esta limitación se supera en algoritmos modernos, que pueden resolver de manera óptima (en el sentido de encontrar soluciones con un desperdicio mínimo) casos muy grandes del problema (generalmente más grandes que los encontrados en la práctica [8] [9] ).
El problema del material de corte es a menudo muy degenerado, ya que son posibles múltiples soluciones con la misma cantidad de desperdicio. Esta degeneración surge porque es posible mover elementos, creando nuevos patrones, sin afectar la cantidad de desperdicio. Esto da lugar a toda una colección de problemas relacionados que tienen que ver con algún otro criterio, como el siguiente:
- El problema de conteo mínimo de patrones: encontrar una solución de conteo mínimo de patrones entre las soluciones de desperdicio mínimo. Este es un problema muy difícil, incluso cuando se conoce el desperdicio. [10] [11] [12] Existe la conjetura de que cualquier instancia unidimensional restringida por igualdad con n tamaños tiene al menos una solución de desperdicio mínima con no más de n + 1 patrones. Esta conjetura fue refutada por primera vez en abril de 2020 con un ejemplo con 9 tamaños que requiere 11 patrones. [13]
- El problema de la pila mínima: se trata de la secuenciación de los patrones para no tener demasiados pedidos parcialmente completados en ningún momento. Este fue un problema abierto hasta 2007, cuando se publicó un algoritmo eficiente basado en programación dinámica. [14]
- Problema del número mínimo de cambios de cuchilla (para el problema unidimensional): se trata de secuenciar y permutar los patrones para minimizar el número de veces que las cuchillas de corte tienen que moverse. Éste es un caso especial del problema generalizado del viajante de comercio .
Referencias
- ^ Wäscher, G .; Haußner, H .; Schumann, H. Una tipología mejorada de problemas de corte y empaque . Revista europea de investigación operativa, volumen 183, número 3, 1109-1130
- ^ MP Johnson, C.Rennick & E. Zak (1997), Además del desbaste al problema del material de corte en la industria del papel , Revisión de SIAM, 472-483
- ^ Raffensperger, JF (2010). "El surtido generalizado y los mejores problemas de longitud de material de corte". Transacciones internacionales en investigación operativa . 17 : 35–49. doi : 10.1111 / j.1475-3995.2009.00724.x .
- ^ LV Kantorovich Métodos matemáticos de organización y planificación de la producción . Universidad Estatal de Leningrado. 1939
- ^ Kantorovich LV y Zalgaller VA. (1951). Cálculo de Corte Racional de Stock . Lenizdat, Leningrado.
- ^ Gilmore PC, RE Gomory (1961). Un enfoque de programación lineal para el problema del material de corte . Investigación de operaciones 9: 849-859
- ^ Gilmore PC, RE Gomory (1963). Un enfoque de programación lineal para el problema del material de corte - Parte II . Investigación de operaciones 11: 863-888
- ^ Goulimis C (1990). Soluciones óptimas para el problema del material de corte . Revista europea de investigación operativa 44: 197-208
- ↑ de Carvalho V (1998). Solución exacta de problemas de material de corte mediante generación de columnas y ramificación y encuadernación . Transacciones internacionales en investigación operativa 5: 35–44
- ^ S. Umetani, M. Yagiura y T. Ibaraki (2003). Problema de material de corte unidimensional para minimizar el número de patrones diferentes . European Journal of Operational Research 146, 388–402
- ^ A. Diegel, E. Montocchio, E. Walters, S. van Schalkwyk y S. Naidoo (1996). Configuración minimizando las condiciones en el problema de la pérdida de recorte . Revista europea de investigación operativa 95: 631-640
- ^ C. McDiarmid (1999). Minimización de patrones en problemas de material de corte . Matemáticas aplicadas discretas, 121-130
- ^ Constantine Goulimis. Contraejemplos en el CSP . arXiv: 2004.01937
- ^ María García de la Banda, PJ Stuckey. Programación dinámica para minimizar el número máximo de pilas abiertas . INFORMS Revista de Computación, Vol. 19, núm. 4, otoño de 2007, 607-617.
Otras lecturas
- Chvátal, V. (1983). Programación lineal . WH Freeman. ISBN 978-0-7167-1587-0.
- Hatem Ben Amor, JM Valério de Carvalho, Cutting Stock Problems in Column Generation, editado por Guy Desaulniers, Jacques Desrosiers y Marius M. Solomon, Springer, 2005, XVI, ISBN 0-387-25485-4
- M. Delorme, M. Iori, S. Martello, Problemas de material de corte y embalaje en contenedores : modelos matemáticos y algoritmos exactos , European Journal of Operational Research 2016, 255, 1–20, doi : 10.1016 / j.ejor.2016.04.030