algorithm - muse - Cálculo de una lista de corte con la menor cantidad de residuos extraídos
algorithms book (6)
Es un problema interesante porque supongo que depende de la cantidad de cada longitud que está produciendo. Si son todas la misma cantidad y puede obtener Cada longitud diferente en una extrusión de 5 m, entonces tiene la solución óptima.
Sin embargo, si no todos se ajustan a una extrusión, entonces usted tiene 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 ir en una orden a través de cada extrusión.
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 los 5 m de longitud de las extrusiones de aluminio.
Las longitudes más pequeñas deben cortarse en el orden en que se produce la menor cantidad de desperdicios extraídos de los 5 m de longitud de las extrusiones de aluminio.
Actualmente ordeno la lista de corte 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 más pequeñas se corta al final. La excepción a esta regla es que cada vez que una longitud más corta no cabe en lo que queda de los 5 m de longitud de la extrusión de aluminio, utilizo la longitud más corta que cabrá.
Esto parece producir una lista de corte muy eficiente (muy poco desecho de desperdicio) y no tarda en calcularse. Me imagino, sin embargo, que a pesar de que la lista de corte es muy eficiente, no es necesariamente la más eficiente.
¿Alguien sabe de una manera de calcular la lista de corte más eficiente que se puede calcular en un tiempo razonable?
EDIT: Gracias por las respuestas, continuaré usando el enfoque "codicioso" ya que parece estar haciendo un muy buen trabajo (realiza cualquier intento humano de crear una lista de corte eficiente) y es muy rápido.
Este es un problema clásico y difícil de resolver de manera eficiente. El algoritmo que describes suena como un algoritmo codicioso . Eche un vistazo a este artículo de Wikipedia para más información: El problema de las existencias de corte
No tengo ideas específicas sobre este problema, me temo, pero podría examinar un " algoritmo genético " (que sería algo como esto) ...
Coloque las longitudes para cortar en un orden aleatorio y ordene a esa orden según la buena compatibilidad con su solución ideal (0% de desperdicio, presumiblemente).
Luego, iterativamente haga alteraciones al azar en el orden y vuelva a puntuarlo. Si el puntaje es más alto, abandone el resultado. Si el puntaje es más bajo, consérvelo y úselo como base para su próximo cálculo. Continúe hasta que obtenga su puntaje dentro de los límites aceptables.
He estado luchando con este problema exacto (la longitud de mi problema es de 6 m) aquí también.
La solución en la que estoy trabajando es un poco fea, pero no me conformaré con su solución. Dejame explicar:
Tamaño del stock 5 m
Necesita cortar en tamaños (1 de cada):
** 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
Ver el problema?
La solución en la que estoy trabajando -> Fuerza bruta
1 - Prueba todas las soluciones posibles
2 - Ordene la solución por sus residuos
3 - Elija la mejor solución
4 - Eliminar los elementos en la solución del "Universo"
5 - Ir a 1
Sé que lleva mucho tiempo (pero tomo 1h30 m para almorzar ... entonces ... :))
Realmente necesito la solución óptima (hago una solución óptima para usar a mano (+ -) en Excel) no solo porque soy obsesivo sino porque el producto no es barato.
Si alguien tiene una mejor solución, me encantaría
En realidad, dado que el tamaño del material es fijo, pero las solicitudes no lo son, se trata de un problema de embalaje en el contenedor.
De nuevo, wikipedia al rescate!
(Algo que podría tener que buscar también, ¡sí!)
Lo que describió está de hecho clasificado como un problema de Stock de corte , como lo mencionó Wheelie , y no como un problema de empaquetamiento de bandejas porque intenta minimizar el desperdicio (suma de las sobras) en lugar de la cantidad de extrusiones utilizadas.
Ambos problemas pueden ser muy difíciles de resolver, pero el algoritmo "mejor ajustado" que mencionaste (usando la "longitud pequeña" más larga que se ajusta a la extrusión actual) es probable que te brinde respuestas muy buenas con una complejidad muy baja.