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, 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 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 que representa cuántas veces será utilizado cada patrón. El programa entero lineal es entonces:
, entero
donde es el número de veces que la orden aparece en el patrón y es el costo (a menudo los residuos) del patrón . 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 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):
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.Gilmore P. C., R. E. Gomory (1961). A linear programming approach to the cutting-stock problem. Operations Research 9: 849-859Gilmore P. C., R. E. Gomory (1963). A linear programming approach to the cutting-stock problem - Part II. Operations Research 11: 863-888 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ácticaGoulimis C (1990). Optimal solutions for the cutting stock problem. European Journal of Operational Research 44: 197-208de Carvalho V (1998). Exact solution of cutting stock problems using column generation and branch-and-bound. International Transactions in Operational Research 5: 35–44).
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.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–402A. 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 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.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.
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:
{| class="wikitable" |- ! width="80pt" | Width ! width="80pt" | Rolls |- | align=center | 1380 || align=center | 22 |- | align=center | 1520 || align=center | 25 |- | align=center | 1560 || align=center | 12 |- | align=center | 1710 || align=center | 14 |- | align=center | 1820 || align=center | 18 |- | align=center | 1880 || align=center | 18 |- | align=center | 1930 || align=center | 20 |- | align=center | 2000 || align=center | 10 |- | align=center | 2050 || align=center | 12 |- | align=center | 2100 || align=center | 14 |- | align=center | 2140 || align=center | 16 |- | align=center | 2150 || align=center | 18 |- | align=center | 2200 || align=center | 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:
{| class="wikitable" border="0" cellpadding="4" !Repetition !align=center | Contents |- | align=center | 2 || 1820 + 1820 + 1820 |- | align=center | 3 || 1380 + 2150 + 1930 |- | align=center | 12 || 1380 + 2150 + 2050 |- | align=center | 7 || 1380 + 2100 + 2100 |- | align=center | 12 || 2200 + 1820 + 1560 |- | align=center | 8 || 2200 + 1520 + 1880 |- | align=center | 1 || 1520 + 1930 + 2150 |- | align=center | 16 || 1520 + 1930 + 2140 |- | align=center | 10 || 1710 + 2000 + 1880 |- | style="border-bottom:3px solid grey" align=center | 2 || 1710 + 1710 + 2150 |- | align=center | 73
Clasificación
Los problemas de corte de acciones se pueden clasificar de varias maneras.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 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 (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.