Calcular una lista de corte con la menor cantidad de desperdicios cortados

Question

Estoy trabajando en un proyecto donde produzco una lista de corte por extrusión de aluminio.

Las extrusiones de aluminio vienen en longitudes de 5 m.

Tengo una lista de longitudes más pequeñas que deben cortarse de las longitudes de 5 m de extrusiones de aluminio.

Las longitudes más pequeñas deben cortarse en el orden que produzca la menor cantidad de residuos cortados de las longitudes de 5 m de extrusiones de aluminio.

Actualmente ordeno la lista de cortes de tal manera que generalmente la longitud más larga de las más pequeñas se corta primero y la más corta de las longitudes más pequeñas se corta al final.La excepción a esta regla es que cuando una longitud más corta no cabe en lo que queda de los 5 m de longitud de extrusión de aluminio, utilizo la longitud más larga y corta que quepa.

Esto parece producir una lista de cortes muy eficiente (muy poco desperdicio) y no lleva mucho tiempo calcularla.Me imagino, sin embargo, que aunque la lista de recortes sea muy eficiente, no es necesariamente el mayoría eficiente.

¿Alguien conoce alguna forma de calcular la lista de corte más eficiente que pueda calcularse en un período de tiempo razonable?

EDITAR:Gracias por las respuestas, continuaré usando el enfoque "codicioso", ya que parece estar haciendo un muy buen trabajo (supera cualquier intento humano de crear una lista de corte eficiente) y es muy rápido.

Answer 1

Este es un problema clásico y difícil de resolver de manera eficiente.El algoritmo que usted describe suena como un Algoritmo codicioso.Eche un vistazo a este artículo de Wikipedia para obtener más información: El problema de la reducción de existencias

Answer 2

Me temo que no hay ideas específicas sobre este problema, pero podrías buscar un 'algoritmo genético' (que iría algo como esto)...

Coloque las longitudes a cortar en un orden aleatorio y asigne a ese orden una puntuación en función de qué tan bien coincida con su solución ideal (0% de desperdicio, presumiblemente).

Luego, realice modificaciones aleatorias de forma iterativa en el orden y vuelva a puntuarlo.Si la puntuación es mayor, deshazte del resultado.Si la puntuación es menor, consérvela y úsela como base para su próximo cálculo.Continúe hasta que obtenga su puntuación dentro de límites aceptables.

Answer 3

Lo que usted describió de hecho está clasificado como un Material de corte problema, como caballito mencionado, y no un Embalaje del contenedor problema porque intenta minimizar el desperdicio (suma de sobras) en lugar del número de extrusiones utilizadas.

Ambos problemas pueden ser muy difíciles de resolver, pero es probable que el algoritmo de "mejor ajuste" que mencionó (utilizando la "longitud pequeña" más larga que se ajusta a la extrusión actual) le brinde muy buenas respuestas con una complejidad muy baja.

Answer 4

En realidad, dado que el tamaño del material es fijo, pero las solicitudes no, es un problema de embalaje del contenedor.

De nuevo, wikipedia al rescate!

(Algo que quizás también tenga que investigar para trabajar, así que ¡sí!)

Answer 5

Ese es un problema interesante porque supongo que depende de la cantidad de cada longitud que estés produciendo.Si todos son de la misma cantidad y puede colocar cada longitud diferente en una extrusión de 5 m, entonces tiene la solución óptima.

Sin embargo, si no todos encajan en una extrusión, entonces tienes un problema mayor.Para mantener la misma cantidad de cortes para cada longitud, necesita calcular cuántas longitudes (no necesariamente en orden) pueden caber en una extrusión y luego pasar en orden a través de cada extrusión.

Answer 6

Aquí también he estado luchando con este problema exacto (la longitud de mi problema es 6 m).

La solución en la que estoy trabajando es un poco fea, pero no me conformo con tu solución.Dejame explicar:

Tamaño del stock 5 metros

Necesita cortar en tamaños (1 de cada uno):

**3,5

1

1,5**

Tu solución:

3,5 | 1 con un desperdicio de 0,5

1,5 con un sobrante de 3,5

¿Ves el problema?

La solución en la que estoy trabajando -> Fuerza bruta

1 - Pruebe todas las soluciones posibles

2 - Ordenar la solución por sus residuos

3 - Elige la mejor solución

4 - Retire los elementos de la solución del "Universo"

5 - Ir a 1

Sé que lleva mucho tiempo (pero tardo 1h30m en almorzar...entonces...:) )

Realmente necesito la solución óptima (hago una solución casi óptima a mano (+-) en Excel) no solo porque soy obsesivo sino porque el producto no es barato.

Si alguien tiene una solución mejor y fácil, me encantaría.