problema de particionamento industrial

Question

Estamos falando de produtos metálicos fábrica. Há máquina que corta barras de ferro para partes menores que são posteriormente utilizados para a criação de vários produtos.

Por exemplo, eu tenho necessidade de bares produto da seguinte comprimento e quantidade: 2 partes de 248 milímetros, 5 de 1,150 milímetros, 6 de 2,843 milímetros, 3 de 3.621 milímetros.

Essa é a saída de particionamento.

No lado de entrada eu tenho (mais uma vez, por exemplo) 3 bares de 2.500 milímetros, 2 bares de 5.000 milímetros, 6 bares de 8,000 milímetro e 3 bares de 10,000 milímetros.

Eu deveria encontrar uma maneira como barras de entrada de corte de forma ideal -. O resto (restantes partes que são demasiado pequenos para ser usado) após o corte deve ser menor possível

Eu criei algoritmo que simplesmente cria todas as combinações possíveis e, em seguida, escolher melhor entre eles. Código funciona, mas assim como entrada e saída são pouco maior, o cálculo pode durar muito tempo, então eu devo encontrar uma nova abordagem para o problema.

Você tem alguma dica?

Answer 1

Seu problema é um problema bastante comum em Investigação Operacional. Olhe para problema . Este problema é essencialmente NP-duro como você ter descoberto em seu próprio país. Ele não escala muito bem.

Como resolver isso? Depois que você é capaz de descobrir o modelo que seria melhor chamar alguns solver de programação inteira mista. Eu já usou LPSolve 5,5

Pode haver algoritmos simplier que você poderia código que lidar com este problema em particular. O problema com esses algoritmos geralmente surge quando você precisa adicionar algumas restrições colaterais que os autores não ter pensado. O MIP Solver é uma ferramenta de forma mais genérica.

Answer 2

Este é o chamado tamanho variável problema bin embalagem . É NP duro, o que significa que sua solução irá invariavelmente falham para entrada grande. Este artigo, aqui , que infelizmente eu não tenho acesso também, endereços este problema e utiliza a indústria de corte do metal como um exemplo.

Answer 3

A programação linear é seu amigo. Consulte http://en.wikipedia.org/wiki/Linear_programming em geral, e, particularmente , 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 é semelhante ao problema da mochila (saber para ser realmente desagradável) Eu achei essa mensagem nos DADS NIST (referência útil) mais fácil para chegar ao que ACM para membros Bin Packing