¿Qué es el problema de corte de material?

Si alguna vez te has plantado frente a una pila de hojas de contrachapado con una lista de piezas y un lápiz, dibujando rectángulos en el reverso de un sobre, ya conoces este problema. Solo que no sabías que tenía un nombre formal. El problema de corte de material es lo que ocurre cuando necesitas dividir grandes materias primas en piezas más pequeñas requeridas y quieres desperdiciar lo menos posible. Es una forma de bin packing — encajar artículos en contenedores con el mínimo espacio sobrante. Fabricantes, talleres de ebanistería y aficionados a la carpintería se enfrentan a él cada día.

El problema que todo carpintero conoce

Imagina esto: estás construyendo un juego de muebles de cocina. Necesitas 14 laterales, 7 baldas, 7 traseras y 14 frentes de puerta — 42 piezas en total, cortadas de hojas estándar de 2800×2070 mm. Cada pieza tiene dimensiones concretas. Algunas necesitan la veta en sentido longitudinal, otras no. Tienes que contar con un ancho de corte (kerf) de 3 mm de tu sierra de mesa.

Ahora averigua cuántas hojas como mínimo debes comprar para obtener las 42 piezas. Adelante — inténtalo con lápiz y papel. Pasarás 20 minutos solo en la disposición de la primera hoja, borrando y volviendo a dibujar. Para la tercera hoja, ya habrás perdido la cuenta de qué piezas has colocado. E incluso después de todo ese esfuerzo, no tienes forma de saber si existe una mejor disposición.

Este es el problema de corte de material reducido a su esencia: dado un conjunto de piezas requeridas y un suministro de material de tamaño estándar, encontrar la disposición que use el menor número de hojas produciendo la menor merma.

Las matemáticas detrás (simplificadas)

Los informáticos clasifican el problema de corte de material como “NP-difícil”. En términos prácticos, eso significa que el número de disposiciones posibles crece tan rápido con cada pieza adicional que ningún ordenador puede probar todas y cada una de las opciones en un tiempo razonable. Ordenar solo 40 piezas da 40 factorial secuencias — un número de 48 cifras — y eso antes de decidir dónde aterriza cada una en la hoja, o cuáles se rotan. Con 100 piezas, aproximadamente una cocina completa, las ordenaciones superan a los átomos del universo observable en más de setenta órdenes de magnitud.

Esta es la misma familia de problemas estudiada por primera vez por Kantorovich (1939) y resuelta más tarde con generación de columnas por Gilmore y Gomory (1961). Los algoritmos no prueban todas las combinaciones. En su lugar, usan heurísticas — atajos inteligentes como first-fit decreasing, generación de columnas o algoritmos genéticos — que encuentran soluciones casi óptimas en segundos. No siempre encontrarán la disposición absolutamente perfecta, pero superarán de forma sistemática cualquier intento humano por un amplio margen.

El compromiso es sencillo: una mínima cantidad de tiempo de cálculo a cambio de una cantidad de material desperdiciado medible y menor.

¿De dónde salió el problema de corte de material?

Se formalizó dentro de la industria, no en una universidad, gracias a personas que intentaban evitar que la costosa materia prima se convirtiera en recortes.

Kantorovich escribió la primera versión mientras asesoraba a un consorcio de contrachapado sobre cómo planificar la producción con la menor merma — un trabajo reconocido después con un Premio Nobel de Economía. El método práctico de solución llegó de una industria distinta dos décadas más tarde: una papelera produce bobinas maestras de un ancho fijo y tiene que dividirlas en los anchos más estrechos que pidieron sus clientes. Cada combinación de anchos que cabe a lo ancho de una bobina es un patrón de corte, y la lista de patrones posibles es demasiado larga para escribirla. La respuesta de Gilmore y Gomory fue no escribirla — generar solo los patrones que la solución resulta necesitar.

Ese vocabulario sobrevive en tu taller. Una disposición sobre una sola hoja es un patrón; un plan de corte es un conjunto de patrones más cuántas hojas ejecutar de cada uno. Cuando un optimizador informa de “tres hojas así, una asá”, te está entregando la misma forma de respuesta que el método de 1961 producía para las papeleras, aplicada al contrachapado.

Una dimensión o dos — y por qué importa

El mismo problema aparece en dos formas, y dejan de ser igual de difíciles en el momento en que intentas cortarlas.

En una dimensión solo importa la longitud — barras, tubos, perfiles, largos de madera, un rollo de canteado. Hay exactamente una manera de que una pieza se asiente sobre una barra, así que toda la decisión es qué cortes salen de qué longitud de material. Esta es la forma original; el problema de división de la papelera es un problema 1D.

Dos dimensiones dan a una pieza un ancho, un alto y a menudo la libertad de rotar, así que una hoja tiene un número enorme de disposiciones en lugar de una sola ordenación. De ahí viene la explosión combinatoria de antes.

Luego la realidad añade una restricción que la versión de libro de texto no tiene: el corte de guillotina. Una seccionadora, y una sierra de mesa también, solo pueden hacer cortes que van de borde a borde a lo ancho del tablero que haya sobre la mesa en ese momento. No puedes recortar una muesca en mitad de una hoja. Una disposición que encaja de maravilla pero necesita un corte que se detiene a medio camino no es un plan, es una foto. El anidado libre — piezas colocadas en cualquier lugar, en cualquier orientación — pertenece a una fresadora CNC, que corta cada contorno por su cuenta. Esa única restricción es la razón por la que una disposición óptima sobre el papel puede ser imposible de fabricar en tu taller. 1D vs 2D optimización de corte explica dónde cae la línea.

Por qué el cálculo manual siempre desperdicia más

Veamos un ejemplo concreto. Necesitas 5 paneles grandes de una hoja europea estándar (2800×2070 mm):

• 2× laterales: 2100×600 mm
• 2× baldas: 800×500 mm
• 1× panel trasero: 2100×800 mm

Manualmente, la mayoría coloca primero las piezas más grandes y encaja las más pequeñas en los huecos. Con una hoja de cálculo, puedes controlar el uso de superficie pero aun así no puedes probar rotaciones o disposiciones alternativas con rapidez. Un algoritmo optimizador evalúa cientos de variaciones de disposición en menos de un segundo.

Esa diferencia importa rápido. A 50–70 $ por hoja, ahorrar aunque sea una sola hoja en un proyecto de cocina se amortiza de inmediato. En una serie de producción de 50 muebles, los ahorros se acumulan hasta miles de dólares.

Casos de uso reales

El problema de corte de material aparece en todas partes donde se cortan materiales a partir de tamaños de material estándar:

• Ebanistería y producción de muebles — Paneles de melamina, MDF y contrachapado cortados en decenas de tamaños de pieza por proyecto. Las restricciones de dirección de la veta lo complican.
• Anidado CNC — Las máquinas de corte automatizadas necesitan un archivo de disposición. El optimizador lo genera directamente, eliminando el anidado manual en el controlador de la máquina.
• Fabricación de chapa metálica — Las hojas de acero y aluminio cuestan bastante más por metro cuadrado, así que incluso una reducción de merma del 3–5% se traduce en dinero serio.
• Corte de vidrio y azulejo — Materiales frágiles donde los cortes incorrectos no se pueden reutilizar. Acertar la disposición a la primera evita errores costosos.
• Corte lineal (1D) — Barras, tubos, perfiles y largos de madera. El mismo problema, con una dimensión menos. Sigue siendo NP-difícil con suficientes piezas.

Cómo lo resuelve el software de optimización de corte

El proceso es más sencillo de lo que esperarías. Introduces tus piezas requeridas — dimensiones, cantidades, dirección de la veta si procede. Especificas el tamaño de tu hoja de material (o varios tamaños si tu proveedor los ofrece). Fijas el ancho de corte (kerf) de tu hoja de sierra, normalmente 3–4 mm. Luego pulsas optimizar.

Entre bastidores, el software ejecuta una serie de pasadas algorítmicas. Prueba distintas colocaciones de piezas, rotaciones (cuando la veta lo permite) y disposiciones de hojas. Evalúa cada disposición por el porcentaje de merma total y el número de hojas necesarias. En segundos, devuelve un plan de corte — un mapa visual de exactamente dónde va cada pieza en cada hoja.

Obtienes una disposición imprimible, una lista de piezas con posiciones y cifras de merma claras. Sin conjeturas, sin volver a dibujar, sin piezas olvidadas.

¿Se puede resolver de forma perfecta?

En un trabajo pequeño, sí — e incluso se puede demostrar. En uno grande, no, y eso importa menos de lo que parece.

La demostración procede de una cota inferior, que un optimizador puede calcular antes de disponer nada. Suma la superficie de cada pieza, divide por la superficie de una hoja, redondea hacia arriba: ese es el mínimo de hojas que cualquier plan podría usar, porque el material no se puede crear. Si el plan que encuentra el software usa exactamente esa cantidad de hojas, no hay un plan mejor — no “no se encontró ninguno”, sino que no existe ninguno. Esa es la diferencia entre una buena respuesta y una demostrada.

Cuando un plan queda por encima de la cota, la diferencia tiene dos explicaciones posibles y normalmente no puedes distinguir cuál. O bien queda por encontrar una mejor disposición, o bien la cota nunca fue alcanzable para tus tamaños de pieza — una suma de superficies no tiene ni idea de que tres piezas de 900 mm no cabrán a lo ancho de una hoja de 2070 mm por mucho que se giren. La cota es un suelo, no una promesa.

¿Dejar la búsqueda funcionando más tiempo produce un mejor plan? Hasta cierto punto. Las grandes mejoras llegan primero, porque las colocaciones obviamente mejores son las más fáciles de encontrar; después de eso la búsqueda está en gran medida confirmando que lo que ya tiene es difícil de superar. Una respuesta lenta casi nunca es la razón por la que un trabajo desperdició material. Los datos de entrada sí lo son — un kerf equivocado, una pieza que falta, un tamaño de material que en realidad no puedes comprar.