Methodology
Cut Lists and Bin Packing
Why sheet and length counts are a packing problem, why kerf is charged per cut, and why the optimiser is a heuristic rather than an optimum.
Not a division problem
Ordering stock lengths or sheets is not total length divided by stock length. It is a bin-packing problem: each stock piece is a bin of fixed capacity, each required piece must go entirely into one bin, and the question is how few bins suffice.
The distinction matters because remnants are usually unusable. Three pieces of 1.8 metres cannot come from two 2.4-metre lengths even though the total length allows it — each 2.4 gives one 1.8 and a 0.6 remnant, so you need three lengths and throw away 1.8 metres.
First-fit decreasing
Optimal bin packing is NP-hard, so the cut-list optimiser here uses first-fit decreasing: sort the required pieces longest first, then place each into the first stock piece it fits, opening a new one only when none has room.
Sorting longest-first is what makes the heuristic good. Long pieces are the constrained ones, and placing them while bins are still empty leaves the short pieces to fill the gaps they create. First-fit decreasing is provably within a modest constant factor of optimal, and on real cut lists it usually matches it.
- ℓ
- length of part j
- m
- number of parts taken from this stock piece
- k
- kerf — material removed by one cut
Kerf is per cut, not per part
The blade removes material, and that material comes out of the stock. Charging kerf per part rather than per cut over-counts by one kerf on every stock piece, because the final part needs no cut after it.
It sounds like a triviality and it is not. On a job cutting many short pieces from long stock — balusters, blocking, studs — the cumulative kerf across dozens of cuts per length is a measurable fraction of a stock piece, and it is the difference between the last piece fitting and not.
Basis
- First-fit decreasing bin packing; a standard approximation for the one-dimensional cutting stock problem.