Qué algoritmo utilizar para la distribución de piezas

Question

Hola estoy trabajando para una empresa de fabricación cuya operación funciona de esta manera

Recibimos rollos de un material en un tamaño determinado de nuestro proveedor, digamos 8000 metros por rollo. Luego recibimos pedidos de diferentes clientes de tamaños más pequeños, como 2000 metros, 3000 metros, etc. Estoy tratando de desarrollar un software para esto y me preguntaba si hay alguna técnica matemática en la que simplemente introduzcan su tamaño de rollo actual y los diferentes pedidos que tenemos en ese momento, y que pueda generar la mejor manera de cortar los diferentes rollos para minimizar el desperdicio.

Por ejemplo, en un momento dado podemos tener los siguientes pedidos 2 piezas de 3000 metros 2 piezas de 4000 metros 6 piezas de 1500 metros

Entonces todo lo que tenemos que introducir son los pedidos anteriores junto con el tamaño del rollo que nuestro proveedor nos proporciona, para este ejemplo asumimos que son 8000 metros.

A continuación, el software debería generar resultados como Rollo 1 - Dos piezas de 4000 metros Rollo desperdiciado 0 Rollo 2 - Dos piezas de 3000 metros y 1 pieza de 1500 (Rollo desperdiciado 500) Rollo 3 - Cinco piezas de 15000 (Rollo desperdiciado 500)

El script debe ser optimizado ya que el ejemplo anterior es bastante pequeño. Normalmente tendremos pedidos de unas 200 piezas a la vez

Sé que podemos hacerlo por fuerza bruta probando cada combinación. Pero, ¿existen otros algoritmos y técnicas de ordenación que puedan ayudar en este caso a reducir la carga del ordenador?

Answer 1

Aunque hay muchas matemáticas interesantes detrás de los problemas de empaquetado de papeleras, y muchos algoritmos interesantes que pueden obtener soluciones casi óptimas, en tu caso lo que quieres es probablemente una simple heurística que sea "suficientemente buena" casi todo el tiempo.

He codificado una implementación sencilla del primer ajuste disminuyendo que ordena los objetos a empaquetar en orden descendente y los coloca en el primer contenedor en el que caben. Puede encontrar el código en GitHub . Genera objetos aleatorios entre 0 y 4000 metros (en intervalos de 100) y luego aplica el algoritmo.

El resultado de una ejecución típica es el siguiente:

Objects packed: 200
     Bins used: 63
  Space wasted: 2.0 percent
    Time taken: 0.00 seconds

Si puede soportar un desperdicio del 2% y un algoritmo que funciona tan rápido que su tiempo de ejecución es de cero a dos decimales, entonces este puede ser el enfoque que necesita.

Answer 2

Su problema se conoce como Problema de embalaje de contenedores El problema es NP-difícil por lo que dudo, incluso para un número pequeño, que la fuerza bruta pueda resolver el problema.

Una posible solución es construir una combinación de heurística (como el mejor primero, como sugiere nbubis), la poda (por ejemplo, procesar los elementos en orden no creciente) y la aleatorización (si su proceso de construcción no es determinista, puede repetirlo varias veces, y tomar la mejor solución posible).

Otra buena heurística es resolver como subproblema el problema de la mochila : intenta llenar el primer rollo, minimizando el rollo desperdiciado. Si hay un número relativamente pequeño de cortes posibles (por ejemplo, cada longitud es un número intermedio de metros, por lo que los posibles cortes son 8000) este problema puede ser resuelto a través de la programación dinámica (véase el artículo de wikipedia) que es O(número de posibles cortes * número de artículos).

Otra cosa útil es tratar de construir una solución parcial con algún método, luego tomar 2 rollos en la solución parcial con algunos espacios desperdiciados (eg. 5000+2500 y 4500+1500+1500, ambos con 500) y tratar de reorganizarlos para que el espacio desperdiciado se maximice (en este caso, 5000+1500+1500 y 4500+2500, el primero lleno y el otro con 1000 restantes), entonces tal vez usted puede llenar otro elemento en el nuevo espacio más grande, o puede volver a hacer este proceso con el segundo rollo y uno nuevo, tratando de aumentar el máximo espacio desperdiciado, hasta que un nuevo elemento puede ser colocado allí. Este subproblema también se puede resolver con la programación dinámica de la mochila.

Otra optimización puede depender mucho de otras propiedades del pedido que reciba, por ejemplo, si a menudo los artículos solicitados son del mismo tamaño puede preferir escribir un subprograma para este problema en particular, porque puede ser necesaria una optimización diferente para encontrar una solución para 100x73m + 100x550m que para 200 artículos de tamaño aleatorio. O tal vez usted sabe que el 90% de los artículos están entre 550m y 450m, por lo que puede preferir optimizar el problema utilizando esa cosa. O que tienes muchas piezas pequeñas (10 m), por lo que los huecos se pueden rellenar fácilmente. O cualquier otra cosa peculiar en su problema, que puede ayudar a construir un mejor programa para este problema en particular.

Sugiero encarecidamente construir un programa para resolver este problema, la mayoría de las veces se puede encontrar una solución óptima a mano, pero escribir un programa puede ahorrarte tiempo y de vez en cuando un rollo completo.

Answer 3

Una heurística básica:

1. Encuentre la pieza más grande necesaria (digamos 5000).
2. Encuentra la siguiente pieza más grande que encaje (digamos 2500).
3. Continúe la etapa 2 hasta que no haya más espacio en el rollo.

Envía el pedido y repite.