¿Qué es un algoritmo efectivo para anidar longitudes 1 dimensionales en longitudes de stock predefinidas?Algoritmo de anidamiento 1-dimensional
Por ejemplo, si usted requiere barras de acero en las siguientes cantidades y longitudes,
- 5 x 2 metros
- 5 x 3 metros
- 5 x 4 metros
y estos se pueden cortar a partir de barras de 10 metros. ¿Cómo se puede calcular el patrón para cortar las barras de 10 m para que se use la cantidad mínima de barras?
Además, ¿cómo podría incorporar múltiples tiras de longitud en el algoritmo?
He tenido algo de tiempo para trabajar en esto, así que voy a escribir cómo lo resolví. Espero que esto sea útil para alguien. No estoy seguro si está bien responder mi propia pregunta de esta manera. Un moderador puede cambiar esto a una respuesta si eso es más apropiado.
En primer lugar gracias a todos los que respondieron. Esto me apuntó al algoritmo apropiado; the cutting stock problem.
Este artículo también fue útil; "Calculating a cutting list with the least amount of off cut waste".
Ok, a la solución.
Voy a usar la terminología siguiente en mi solución;
- Stock: un trozo de material que se va a cortar en pedazos más pequeños
- Corte: un trozo de material que ha sido cortado en stock. múltiples cortes se pueden tomar de la misma pieza de material
- residuos: la longitud del material que queda en una pieza de la acción después se han hecho todos los cortes.
Hay tres etapas principales para la solución del problema,
- identificar todas las posibles combinaciones de corte
- identificar qué combinaciones se pueden extraer de cada pieza de material
- encontrar la combinación óptima de corte combinaciones.
Paso 1
con N cortes, hay 2^N-1 combinaciones de corte únicos. Estas combinaciones se pueden representar como una tabla de verdad binaria.
Donde A, B, C son cortes únicos;
A B C | Combination
-------------------
0 0 0 | None
0 0 1 | C
0 1 0 | B
0 1 1 | BC
1 0 0 | A
1 0 1 | AC
1 1 0 | AB
1 1 1 | ABC
Se puede usar un bucle for-loop con algunos operadores bit a bit para crear rápidamente agrupaciones de cada combinación de corte.
Esto puede ser bastante tiempo para valores grandes de N.
En mi situación había múltiples instancias de la misma corte. Esto produjo combinaciones duplicadas.
A B B | Combination
-------------------
0 0 0 | None
0 0 1 | B
0 1 0 | B (same as previous)
0 1 1 | BB
1 0 0 | A
1 0 1 | AB
1 1 0 | AB (same as previous)
1 1 1 | ABB
Pude aprovechar esta redundancia para reducir el tiempo de cálculo de las combinaciones. Agrupé los cortes duplicados y calculé las combinaciones únicas de este grupo. A continuación, agregué esta lista de combinaciones a cada combinación única en un segundo grupo para crear un nuevo grupo.
Por ejemplo, con los cortes AABBC, el proceso es el siguiente.
A A | Combination
-------------------
0 1 | A
1 1 | AA
Call este grupo X.
Anexar X a instancias únicas de B,
B B X | Combination
-------------------
0 0 1 | A
| AA
0 1 0 | B
0 1 1 | BA
| BAA
1 1 0 | BB
1 1 1 | BBA
| BBAA
Call este grupo Y.
Anexar Y a instancias únicas de C,
C Y | Combination
-----------------
0 1 | A
| AA
| B
| BA
| BAA
| BB
| BBA
| BBAA
1 0 | C
1 1 | CA
| CAA
| CB
| CBA
| CBAA
| CBB
| CBBA
| CBBAA
Este ejemplo le produce 17 combinaciones únicas en lugar de 31 (2^5-1). Un ahorro de casi la mitad.
Una vez que se identifican todas las combinaciones, es hora de comprobar cómo encaja esto en el stock.
Paso 2
El objetivo de este paso es mapear las combinaciones de corte identificados en la etapa 1 a los tamaños comunes disponibles.
Este es un proceso relativamente simple. Para cada combinación de corte,
calculate the sum of all cut lengths.
for each item of stock,
if the sum of cuts is less than stock length,
store stock, cut combination and waste in a data structure.
Add this structure to a list of some sort.
Esto resultará en una lista de una válidos combinaciones corte anidados. No es estrictamente necesario almacenar los desechos, ya que esto se puede calcular a partir de las longitudes de corte y la longitud del material. Sin embargo, los residuos almacenar reduce el procesamiento requerido en el paso 3.
Paso 3
En este paso vamos a identificar la combinación de cortes que produce la menor de residuos. Esto se basa en la lista de nidos válidos generados en el paso 2.
En un mundo ideal, se calcularían todas las posibilidades y se seleccionaría la mejor. Para cualquier conjunto de cortes no triviales, llevaría una eternidad calcularlos todos. Simplemente tendremos que estar satisfechos con una solución no óptima. Existen varios algoritmos para realizar esta tarea.
Elegí un método que buscará un nido con el menor desperdicio. Se repetirá hasta que se hayan tenido en cuenta todos los cortes.
de inicio con tres listas
- cutlist: una lista de todos los cortes necesarios (incluyendo los duplicados).
- nestList: la lista de nidos generados en el paso 2. Esto se ordena de menor desperdicio a mayor desperdicio.
- finalList: Inicialmente vacío, esto almacenará la lista de combinaciones de corte que se enviarán al usuario.
Método
pick nest from nestList with the least waste
if EVERY cut in the nest is contained in cutList
remove cuts from cutList
copy this nest into the finalList
if some cuts in nest not in cutList
remove this nest from nestList
repeat until cutlist is empty
Con este método me las arreglé para conseguir una pérdida total de alrededor de 2-4% para algunos datos de prueba típicos. Espero poder volver a tratar este problema en algún momento y probar la implementación del algoritmo Delayed column generation. Esto debería dar mejores resultados.
Espero que esto ayude a cualquier otra persona que tenga este problema.
David
Esto lee mucho como una pregunta de tarea ... –
tal vez no es tarea - esto es muy similar a un problema industrial real que escribí un programa para alrededor de 1990 – DarenW
Usé un algoritmo diferente. Su resultado se puede ver en http://wood-cut.rhcloud.com. No da una solución óptima, ya que requeriría un enfoque enumerativo pero da una solución aceptable. He visto algunos softwares que ofrecen esto a un costo de más de $ 50 y usan Algoritmo Genético, y no garantizan una solución óptima, a veces incluso dan un resultado peor que http://wood-cut.rhcloud.com. Estoy trabajando para optimizar mi sitio y escribiré ese algoritmo cuando tenga tiempo. –