Problema de corte de valores

El problema de corte de valores es un problema NP-completo optimización, esencialmente se reduce al problema de la mochila. Específicamente, es un problema de programación lineal con números enteros. Surge de muchas aplicaciones en la industria. Imagine que usted trabaja en una fábrica de papel y tiene un número de rollos de papel de ancho fijo a la espera de ser cortado, pero diferentes clientes quieren diferentes números de rollos de distintos tipos de anchos. ¿Cómo se van a cortar los rollos de manera que minimiza los residuos (cantidad de sobras)?

De acuerdo con la Confederación Europeas de Industrias Papeleras,^[1]​ en 2012 las 1,331 máquinas de papel en la región, producen cada una un promedio € 56 millones (aproximadamente $ 73 millones US.) de la facturación. Ahorrar incluso fracciones de 1% es, por tanto, significativo.

Formulación y solución de enfoques

La formulación estándar para el problema de corte de valores (pero no la única) comienza con una lista de m órdenes, cada una requiriere ${\displaystyle q_{j},j=1,\ldots ,m}$  piezas. A continuación se construye una lista de todas las combinaciones posibles de los recortes (a menudo llamados "patrones"), asociando a cada patrón una variable entera positiva ${\displaystyle x_{i}}$  que representa cuántas veces será utilizado cada patrón. El programa entero lineal es entonces:

${\displaystyle \min \sum _{i=1}^{n}c_{i}x_{i}}$ 

${\displaystyle {\text{s.t.}}\sum _{i=1}^{n}a_{ij}x_{i}\geq q_{j},\quad \quad \forall j=1,\dots ,m}$ 

${\displaystyle x_{i}\geq 0}$ , entero

donde ${\displaystyle a_{ij}}$  es el número de veces que la orden ${\displaystyle j}$  aparece en el patrón ${\displaystyle i}$  y ${\displaystyle c_{i}}$  es el costo (a menudo los residuos) del patrón ${\displaystyle i}$ . La naturaleza precisa de la cantidad de restricciones puede llevar a características matemáticas diferentes. Las mismas constituyen la cantidad de restricciones mínimas(por lo menos la cantidad que cada orden debe producir, pero posiblemente más). Cuando ${\displaystyle c_{i}=1}$  el objetivo minimiza el número de elementos maestros utilizados y, si la restricción de la cantidad a producir se sustituye por la igualdad, se llama la problema de embalaje Bin. La formulación más general tiene restricciones de dos lados (y en este caso una solución de conversión de residuos mínimo puede consumir más que el número mínimo de elementos maestros):

${\displaystyle q_{j}\leq \sum _{i=1}^{n}a_{ij}x_{i}\leq Q_{j},\quad \quad \forall j=1,\dots ,m}$ 

Esta formulación se aplica no sólo a los problemas de una sola dimensión. Muchas variaciones son posibles, incluyendo uno en el que el objetivo no es reducir al mínimo los desechos, si no maximizar el valor total de los artículos producidos, permitiendo que cada orden tenga un valor diferente.

En general, el número de posibles patrones crece exponencialmente en función del número de órdenes m. A medida que el número de pedidos aumenta, puede no ser práctico enumerar los posibles patrones de corte.

Un enfoque alternativo utiliza generación-retrasada de columnas. Este método resuelve el problema del corte de valores comenzando con unos pocos patrones. Genera patrones adicionales cuando se necesitan. Para el caso unidimensional, los nuevos patrones se introducen mediante la resolución de un problema de optimización auxiliar llamado el problema de la mochila, utilizando información de variables duales desde el programación lineal. El problema de la mochila tiene métodos de solución, como el conocido ramificación y acotación y programación dinámica. El método de generación de columnas retardada puede ser mucho más eficiente que el enfoque original, en particular como el tamaño del problema crece. El enfoque de generación de columna aplicado al problema de corte fue iniciado por Gilmore y Gomory en una serie de artículos publicados en la década de 1960.^[2]​^[3]​ Gilmore y Gomory demostraron que este enfoque garantiza la convergencia a la solución óptima (fraccionada), sin necesidad de enumerar todos los posibles patrones de antemano.

Una limitación del método original de Gilmore y Gomory es que no maneja integralidad, por lo que la solución puede contener fracciones, por ejemplo, un patrón particular se debe producir 3,67 veces. El redondeo al entero más próximo a menudo no funciona, en el sentido de que puede llevar a una solución subóptima y/o inviabilidad sub- o sobre-producción de algunas de las órdenes (y posible en presencia de restricciones de demanda de dos caras ). Esta limitación se supera en los algoritmos modernos, que pueden resolver óptimamente (en el sentido de encontrar soluciones con un mínimo de desperdicio) muy grandes instancias del problema (generalmente mayor de la habitual en la práctica^[4]​^[5]​).

El problema de corte de valores es a menudo degenerado, en que son posibles varias soluciones con el mismo residuos. Esta degeneración se debe a que es posible mover los elementos alrededor, creando nuevos patrones, sin afectar a los residuos. Esto da lugar a toda una colección de problemas afines que se ocupan de algún otro criterio, como el siguiente:

• El problema de recuento mínimo de patrones: para encontrar una solución de la cantidad mínima de patrones entre las soluciones de desecho mínimo. Este es un problema muy difícil, incluso cuando se conoce los residuos.^[6]​^[7]​ Hay una conjeturas que cualquier instancia unidimensional de restricciones de igualdad con n órdenes tiene al menos una solución mínima de residuos con no más n+ 1 patrones. No se conoce tampoco cota superior del número de patrones, ejemplos con n + 5 son conocidos.

• El problema de apilamiento mínimo: esto se refiere a la secuencia de los patrones a fin de no tener demasiadas órdenes parcialmente terminados en cualquier momento. Este era un problema abierto hasta 2007, cuando se publicó un algoritmo eficiente basado en programación dinámica.^[8]​

• El problema del cambio mínimo del número de cuchillo (para problema unidimensional): esto se refiere permutación de los patrones a fin de minimizar el número de veces que las cuchillas de corte longitudinal tienen que ser movido. Este es un caso especial del generalizado problema del viajante.

Ilustración del problema unidimensional de corte de valores

Una máquina de papel puede producir un número ilimitado de rollos maestros (jumbo), cada uno mide 5600 mm de ancho. Los siguientes 13 artículos deben ser cortados:

Width	Rolls
1380	22
1520	25
1560	12
1710	14
1820	18
1880	18
1930	20
2000	10
2050	12
2100	14
2140	16
2150	18
2200	20

Solución

Hay 308 patrones posibles para este pequeño ejemplo. La respuesta óptima requiere 73 rollos maestros y tiene 0,401% de residuos; se puede demostrar computacionalmente que en este caso el número mínimo de patrones con este nivel de residuos es 10. También se puede calcular que existen 19 diferentes soluciones, cada una con 10 patrones y una pérdida de 0,401%, de las que una solución se muestra a continuación:

Repetition	Contents
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
16	1520 + 1930 + 2140
10	1710 + 2000 + 1880
2	1710 + 1710 + 2150
73

Clasificación

Los problemas de corte de acciones se pueden clasificar de varias maneras.^[9]​ Una forma es la dimensionalidad del corte: el ejemplo anterior ilustra un problema unidimensional (1D); otras aplicaciones industriales de 1D se producen al cortar los tubos, cables y barras de acero. Problemas de dos dimensiones (2D) se encuentran en los muebles, la ropa y la producción de vidrio. No se conocen muchas aplicaciones tridimensionales (3D) que implican el corte; sin embargo, el estrechamente relacionados problema de empaquetamiento 3D tiene muchas aplicaciones industriales, tales como el empaquetamiento de objetos en los contenedores de transporte (ver por ejemplo contenerización - el relacionado Empaquetamiento de esferas problema que ha sido estudiado desde el siglo XVII (Conjetura de Keplerr )).

Problema de corte de valores en las industrias de papel, película y metal

Las aplicaciones industriales de los problemas de corte por acciones de altos volúmenes de producción surgen sobre todo cuando el material de base se produce en grandes rollos que se cortan en unidades más pequeñas (véase rollo rajar). Esto se hace, por ejemplo, no solo en las industrias de película de plástico y papel, sino también en la producción de metales planos, como el acero o el latón. Hay muchas variantes y restricciones adicionales derivadas de las limitaciones de producción especiales debido a la maquinaria y procesos límites, los requisitos del cliente y los problemas de calidad; Algunos ejemplos son:

• En dos etapas, donde los rollos producidos en la primera etapa se procesan entonces por segunda vez. Por ejemplo, toda la papelería de oficina (por ejemplo, A4 tamaño en Europa, Tamaño carta en los Estados Unidos) se produce en un proceso de este tipo. La complicación surge porque la maquinaria en la segunda etapa es más estrecha que la primaria. La utilización eficiente de las dos etapas de la producción es importante (desde el punto de vista de la energía o el uso de materiales) y lo que es eficaz para la etapa primaria puede ser ineficiente para la secundaria, dando lugar a soluciones de compromiso. Metalizado película (utilizado en los envases de aperitivos), y el plástico por extrusión sobre papel (utilizado en envases de líquido, por ejemplo, cartones de jugo) son otros ejemplos de este proceso.

• Limitaciones Winder donde el proceso de corte tiene limitaciones físicas o lógicas: una restricción muy común es que sólo un cierto número de cuchillas de corte longitudinal están disponibles, por lo que los patrones viables no deben contener más de un número máximo de rodillos. Debido a que el enrollado de la maquinaria no es estándar, se encuentran muchas otras restricciones.

• Un ejemplo de un requisito de cliente es cuando un orden en particular no puede ser satisfecho desde cualquiera de las dos posiciones de borde: esto es porque los bordes de la lámina tienden a tener mayores variaciones en el espesor y algunas aplicaciones pueden ser muy sensibles a estos.

• Un ejemplo de un problema de calidad es cuando el rollo maestro contiene defectos que tienen que ser cortado alrededor. Materiales caros con características de calidad exigentes, tales como papel fotográfico o Tyvek tienes que estar optimizado cuidadosamente para que se reduzca al mínimo el área perdida.

• Surgen problemas multi-máquina cuando las órdenes se pueden producir en más de una máquina y estas máquinas tienen diferentes anchuras. Generalmente la disponibilidad de más de una anchura de rollo maestro mejora considerablemente los residuos; en la práctica sin embargo las limitaciones de orden de división adicionales pueden ser tenido en cuenta.

• También hay un problema semi-continuo, donde los rollos producidos no tienen que ser del mismo diámetro, pero pueden variar dentro de un rango. Esto suele ocurrir con las órdenes de hoja. Esto a veces se conoce como un 1 ½ dimensional problema. Esta variante se encuentra también en la producción de cartón corrugado, donde se llama, un tanto confusamente, el problema de programación del corrugado.

• En la industria de los metales una diferencia clave es que normalmente los rollos maestros son producidos anteriormente y son generalmente diferentes entre sí (tanto en términos de anchura y longitud). Por lo tanto, hay similitudes con el problema multi-máquina que se ha mencionado anteriormente. La presencia de variaciones de longitud crea un problema en 2D, ya que los residuos se puede producir tanto a lo ancho como en sentido longitudinal.

Proveedores de software que solucionan el problema de corte de valores para la industria del papel incluyen ABB Group, Greycon, Honeywell y Tieto.
Un algoritmo cutstock para la industria siderúrgica más tarde fue formulada por Robert Gongorra en 1998 and SONS (Software de Optimización de anidamiento de Acero) fue desarrollado para la industria del acero para mejorar el uso de acero y reducir al mínimo los residuos.

Problema de corte de valores en la industria del vidrio

El problema guillotina es un problema de cortar láminas de vidrio en rectángulos de tamaños especificados, utilizando sólo los cortes que siguen todo el camino a través de cada hoja.

El problema surtido

El problema relacionado de determinar, para el caso unidimensional, el mejor tamaño de master que se reunirá dada la demanda se conoce como el problema variedad.^[10]​

Historia

El problema de corte de valores fue formulada por primera vez por Kantorovich en 1939.^[11]​ En 1951 antes de que se dispusiera de los ordenadores, L. V. Kantorovich y VA Zalgaller sugirieron^[12]​ resolver el problema de la utilización económica de material en la etapa de corte con la ayuda de la programación lineal. La técnica propuesta más tarde se llamó el método de generación de columnas.

Software

Nombre	Licencia	Breve información
VPSolver	GPL	Vector Solución de Código Abierto (VPSolver) que se puede utilizar para resolver los problemas de corte optimalidad unidimensional como problema de embalaje de vector unidimensional. El método de solución se basa en una formulación de arco de flujo con compresión gráfico.

Referencias

1. «Key Statistics 2012». Confederation of Europear Paper Industries. Consultado el 3 de julio de 2013. 
2. Gilmore P. C., R. E. Gomory (1961). A linear programming approach to the cutting-stock problem. Operations Research 9: 849-859
3. Gilmore P. C., R. E. Gomory (1963). A linear programming approach to the cutting-stock problem - Part II. Operations Research 11: 863-888
4. Goulimis C (1990). Optimal solutions for the cutting stock problem. European Journal of Operational Research 44: 197-208
5. de Carvalho V (1998). Exact solution of cutting stock problems using column generation and branch-and-bound. International Transactions in Operational Research 5: 35–44
6. S. Umetani, M. Yagiura, and T. Ibaraki (2003). One dimensional cutting stock problem to minimize the number of different patterns. European Journal of Operational Research 146, 388–402
7. A. Diegel, E. Montocchio, E. Walters, S. van Schalkwyk and S. Naidoo (1996). Setup minimizing conditions in the trim loss problem. European Journal of Operational Research 95:631-640
8. Maria Garcia de la Banda, P. J. Stuckey. Dynamic Programming to Minimize the Maximum Number of Open Stacks. INFORMS Journal on Computing, Vol. 19, No. 4, Fall 2007, 607-617.
9. Wäscher, G.; Haußner, H.; Schumann, H. An Improved Typology of Cutting and Packing Problems. European Journal of Operational Research Volume 183, Issue 3, 1109-1130
10. [1], Raffensperger, J. F. (2010). "The generalized assortment and best cutting stock length problems". International Transactions in Operational Research 17: 35.
11. L. V. Kantorovich Mathematical methods of organizing and planning production. Leningrad State University. 1939
12. Kantorovich L. V. and Zalgaller V. A. . (1951). Calculation of Rational Cutting of Stock. Lenizdat, Leningrad. 

Lecturas

• Chvátal, V. (1983). Linear Programming. W.H. Freeman. ISBN 978-0-7167-1587-0. 
• Hatem Ben Amor, J.M. Valério de Carvalho, Cutting Stock Problems in Column Generation, edited by Guy Desaulniers, Jacques Desrosiers, and Marius M. Solomon, Springer, 2005, XVI, ISBN 0-387-25485-4

Enlaces externos

• A rudimentary brute-force algorithm for cutting stock
• Bin Packing and Cutting Stock Solver Algorithm

•   Datos: Q1306230