Problema de particionamiento industrial

Question

Estamos hablando de fábrica de productos metálicos. Hay una máquina que corta barras de hierro largas en partes más pequeñas que luego se usan para crear varios productos.

Por ejemplo, tengo el requisito de producir barras de la siguiente longitud y cantidad: 2 piezas de 248mm, 5 de 1150mm, 6 de 2843mm, 3 de 3621mm.

Esa es la salida de partición.

En el lado de entrada tengo (de nuevo, por ejemplo) 3 barras de 2500mm, 2 barras de 5000mm, 6 barras de 8000mm y 3 barras de 10000mm.

Debería encontrar una forma de cortar de manera óptima las barras de entrada: el resto (las partes restantes que son demasiado pequeñas para ser utilizadas) después de cortar deben ser lo más pequeñas posible.

He creado un algoritmo que simplemente crea todas las combinaciones posibles y luego elige la mejor entre ellas. El código funciona, pero tan pronto como la entrada y la salida son un poco más grandes, el cálculo puede durar mucho tiempo, por lo que debo encontrar un nuevo enfoque para el problema.

¿Tienes algún consejo?

Answer 1

Su problema es un problema bastante común en la investigación de operaciones. Mirar Recorte del problema de stock . Este problema es esencialmente NP-duro como lo has descubierto por tu cuenta. No se escala muy bien.

¿Cómo resolverlo? Una vez que pueda averiguar el modelo, sería mejor llamar a algún solucionador de programación de enteros mixtos. He utilizado anteriormente LPSolve 5.5

Puede haber algoritmos más simples que podría codificar para tratar este problema en particular. El problema con estos algoritmos generalmente surge cuando es necesario agregar algunas restricciones laterales que los autores no han pensado. El MIP Solver es una herramienta mucho más genérica.

Answer 2

Esto se denomina problema de empaquetado de contenedores de tamaño variable . Es NP duro, lo que significa que su solución siempre fallará para una entrada grande. Este artículo, aquí , que desafortunadamente no tengo acceso también, direcciones este problema y utiliza la industria de corte de metal como ejemplo.

Answer 3

La programación lineal es tu amiga. Consulte http://en.wikipedia.org/wiki/Linear_programming en general, y, en particular, http://en.wikipedia.org/wiki/Linear_programming#Uses , < a href = "http://en.wikipedia.org/wiki/Linear_programming#Algorithms" rel = "nofollow noreferrer"> http://en.wikipedia.org/wiki/Linear_programming#Algorithms .

Answer 4

Parece que es similar al problema de la mochila (sé que es realmente desagradable) Encontré esto en el NIST DADS (referencia práctica) más fácil de encontrar que ACM para no miembros Contenedor de basura