Industrial partitioning problem

Question

We're talking about metal products factory. There is machine which cuts long iron bars to smaller parts which are later used for creating various products.

For example, I have requirement to produce bars of following length and quantity: 2 pieces of 248mm, 5 of 1150mm, 6 of 2843mm, 3 of 3621mm.

That is the partitioning output.

On input side I have (again for example) 3 bars of 2500mm, 2 bars of 5000mm, 6 bars of 8000mm and 3 bars of 10000mm.

I should find a way how to cut input bars optimally - the rest (remaining parts that are too small to be used) after cutting should be smallest as possible.

I've created algorithm which simply creates all possible combinations and then pick best one among them. Code works, but as soon as input and output are little bit bigger, calculation can last very long, so I must find new approach to the problem.

Do you have any hints?

Answer 1

Your problem is quite common problem in Operations Research. Look at Cutting stock problem. This problem is essentially NP-hard as you have figured out on your own. It doesn't scale very well.

How to solve it ? After you are able to figure out the model it would be best to call some mixed integer programming solver. I have previously used LPSolve 5.5

There may be simplier algorithms that you could code that deal with this problem in particular. The problem with these algorithms usually arises when you need to add some side constraints that the authors haven't thought of. The MIP Solver is way more generic tool.

Answer 2

This is called the variable size bin packing problem. It's NP hard, which means that your solution will invariably fail for large input. This article, here, which unfortunately I don't have access too, addresses this problem and uses the metal cutting industry as an example.

Answer 3

Linear programming is your friend. See http://en.wikipedia.org/wiki/Linear_programming in general, and, particulary, http://en.wikipedia.org/wiki/Linear_programming#Uses, http://en.wikipedia.org/wiki/Linear_programming#Algorithms.

Answer 4

Looks like it's similar to the knapsack problem (know to be really nasty) I found this on the NIST DADS (handy reference) easier to get to than ACM for non members Bin Packing