Cut Lists and Bin Packing

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.

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.

Sheets are a two-dimensional problem, and much harder

Cutting lengths from stock is one-dimensional packing. Cutting parts from sheets is two-dimensional, and the difference is not one of degree — the number of ways to arrange parts on a sheet is vastly larger, and good heuristics are correspondingly harder to write.

Real saws also constrain the arrangement. A panel saw makes GUILLOTINE cuts: each cut crosses the whole piece being cut, so a layout that requires an L-shaped cut is unbuildable however efficient it looks. Nesting software for routers and lasers has no such restriction, which is why an optimiser has to know which machine it is cutting for.

Material direction removes another freedom. Grain in timber, pattern in fabric or laminate, and the machine direction in some boards all mean a part cannot simply be rotated ninety degrees to fit, and an optimiser that rotates freely returns a plan that cannot be built. Halving the allowed orientations roughly halves the search and usually costs material.

The optimal plan is sometimes the wrong plan

A packing that minimises material can maximise everything else. It may require many partial sheets held for later, a cutting sequence that changes the fence setting on every piece, or offcuts that have to be labelled, stored and found again — and the labour in all of that is real.

A slightly less efficient plan with simple repeated cuts is frequently cheaper overall, particularly where material is inexpensive relative to labour. This is the reverse of the usual intuition about optimisation, and it is why a cut list is a proposal rather than an instruction.

REMNANT POLICY decides which answer is right, and it is a business rule rather than a mathematical one. If offcuts above a threshold length return to stock and are genuinely used, the optimiser should be told to produce them; if they are thrown away, a plan that generates fewer and longer remnants is worse than one that generates none. The same cut list scores differently under the two policies.

Real stock is not the idealised stock in the model

The packing assumes every stock piece is exactly its nominal size and usable end to end. Timber is neither: lengths run over or under, ends are damaged, and knots, shakes, wane and bow make sections unusable for a part that has to be straight and clear.

So a practical cut list either works to a clear-cutting yield — an assumed fraction of each length that is usable — or it is prepared after the stock has been inspected and defects marked. A plan built on nominal lengths and perfect material is optimistic in a direction that is discovered at the saw, one piece at a time.

Sheet goods have their own version. Factory edges are not always square or clean, so a trim allowance comes off two sides before any part is cut, and a layout that uses the full nominal sheet dimension has already lost the margin it needed. Both cases argue for the same discipline: state the assumption about the stock on the plan, because the plan is worthless against stock it does not describe.