1-dimensional nesting algorithm

Answer 1

Least Cost Bin Packing

edit: Here's a better link: http://en.wikipedia.org/wiki/Bin_packing_problem

Answer 2

Thanks for suggesting bin packing problem plinth. This lead me to the following post, Calculating a cutting list with the least amount of off cut waste. This appears to cover my question well

Answer 3

Actually, there's an even more specific problem that applies: The cutting stock problem:

The cutting stock problem is an optimization problem, or more specifically, an integer linear programming problem. It arises from many applications in industry. Imagine that you work in a paper mill and you have a number of rolls of paper of fixed width waiting to be cut, yet different customers want different numbers of rolls of various-sized widths. How are you going to cut the rolls so that you minimize the waste (amount of left-overs)?

The reason this applies better than the bin packing problem is because you are trying to minimise the waste, rather than minimise the number of 'bins'. In a sense, the bin packing problem is the inverse of the cutting stock problem: How would you take lengths of steel and reassemble them into as few bars as possible under a certain size?

Answer 4

Solved a problem similar to this years ago. I ended up using a genetic algorithm. That would be overkill for small problems. This program was somewhat fun to write, but not fun at the same time, being back in the 16-bit days.

First, it made a list of all the ways a 10' piece of raw material could be cut, using the given lengths. For each the amount of wasted material was recorded. (Though it is fast math, it's faster to store these for lookup later.) Then it looked at the list of required pieces. In a loop, it would pick from the way-to-cut list a way of cutting stock that didn't cut more pieces of any size than required. A greedy algorithm would pick one with minimal waste, but sometimes a better solution could be found by loosening up on that. Eventually a genetic algorithm made the choices, the "DNA" being some set of ways-to-cut that did pretty well in past solutions.

All this was way back in pre-internet days, hacked up with cleverness and experimentation. These days there's probably some .NET or java library thing to do it already black-boxed - but that would be less fun and less education, wouldn't it?