Optimal algorithm for this geometric (carpentry-related) program

Question

As the title states, my question regards finding an optimal algorithm to solve a problem I'm working on. I am just looking for insight/suggestions.

This problem was posed to me by my uncle who thought that it would be both a good challenge for me and also potentially a useful piece of software if I could implement it on a mobile platform. Here it is:

"I’m doing some carpentry work using sheet goods of a known, standard size (either 4’ x 8’, or 5’ x 5’). I have a “cut list” of pieces of wood of various known dimensions that I need. What I’d like to be able to do is quickly figure out how to break the sheet goods down into useful pieces with as little waste as possible.

The other factor that needs to be considered is the saw blade kerf (or width). For example, you’d only get three 2’ x 4’ pieces (not four) out of a 4’ x 8’ sheet because of the material lost when making the three cuts.

What I envision is a program where I could input the sheet size, the kerf of the blade I’m using (it’s variable), the dimensions of the finished goods I want, and the program would generate a rough drawing of the cut pattern that most effectively minimized waste."

For now I'm just working on writing up an algorithm to find a solution with minimal waste. I'll leave implementing it onto Android for another day.

In terms of the actual algorithm, here are my thoughts so far:

• Order the "cut-list" in order of descending area
• Place the first item in this list on the sheet such that it occupies the upper-most left-most available position
• If the current item in the list cannot fit on the sheet, attempt to place the next largest
• If none of the pieces in the cut list can fit on the current sheet, begin filling a new sheet
• repeat until the cut list is empty

I'm not familiar with the world of algorithms (yet) so any insight here is appreciated!

If anything is unclear, please let me know.

Thanks, KWarr

Answer 1

Suppose the kerf is k units. Then move each edge of each piece out by k/2 units, and also move each edge of the sheet out by k/2 units. This reduces the problem to ye olde fashioned 2D cutting stock problem, which as the commenters have noted is NP complete. However, if you're happy to limit yourself to a small number of pieces or to accept an approximation, there're a whole pile of algorithms that'll suit your needs.

If I were you, I'd implement a dumb greedy algorithm first and build the app around that. If it later turns out to be too slow or produces poor results, come back and substitute it for something more complex.