This past weekend, I was thinking about cut optimization. This is a method for planning cuts to produce the most pieces of given sizes out of a quantity of material of some length with minimum waste. This was brought about by the planning process involved in building a new garden railway trestle. (I’ll cover the specifics of that in another post – I still have to finish my earlier series on the Curved Trestle with a final part covering stringers and installation.)
As a programmer, of course I always think of writing a program to solve that problem. It turns out, that particular problem is considered NP-Hard, which is a computer scientist way of saying you can’t practically solve that exactly in all cases. With this problem, though, I assumed I could generate a good-enough solution. It turns out, that I could.
First, definitions:
- The raw material that you have is the “stock.” You have some quantity of stock at given length.
- The pieces that you need to cut from that are a collection of “pieces,” each with a length and quantity needed.
- The remaining stock after all the cuts is the “waste.”
Because this is a physical world, and I’m working with wood, I considered the saw blade kerf in the calculation. (The kerf is the width of the cut that the blade produces.)
The first algorithm I tried is the “greedy” method, which finds the longest piece(s) that fit the stock, in turn, until none fit the remaining stock. The last bit after that is “waste”, as there are no pieces that are that size or less.
The second method I tried is what I call “best fit.” This picks the longest piece as the starting point, then finds the one or more pieces that best use up the remaining stock. I used recursion to test all the remaining piece combinations to find the best.
See Cut Optimize for my example program. This uses browser local storage so you can create a project, save it, and refer back to it later. It also uses a table with “editable” content, so there are no input boxes there, just click in the cell and edit the value. Really slick! (I didn’t write the table code.) On first use (or if no jobs are defined) a sample project may be created that has two “jobs”: one for the 90 degree cuts and one for the angled cuts.
What I found was that the greedy algorithm tended to get better results much of the time as a percentage of waste, but most of the waste was in pieces that were too short to have any value for another use (1-2″ long, for instance). The best fit algorithm, though it tends to lose out on a percentage of waste score, does a really good job of using almost all of the stock while there are still short pieces left, and produces more usable waste later in the cut list (3-5″ waste, for instance).
In the examples, both algorithms produced a lot of waste because of the large number of about 9.5″ lengths paired with the 24″ stock length. I’ll likely just get some 20″ or 30″ stock to make most of those pieces, then the waste will be dramatically reduced.
Update: 10/16/2017
I changed a few things:
- Added a minimum Usable Length setting. Remaining pieces greater than or equal to this value are not considered waste.
- Expanded the Stock inventory to five lengths and quantities.
- Changed the buttons to “glyphicons” for a more compact presentation.
Also, fixed a few random bugs in the page.
