# construction.timber-length

A cutting list: given the pieces a job needs, the length timber is bought in
and the saw's kerf, how many lengths to buy and which pieces to cut from each.

## The rule

- **First-fit decreasing.** Pieces are sorted longest first, and each goes on
  the first bar (in the order bars were opened) that still has room; if none
  has, a new bar is opened. It is not always the fewest bars possible (that
  problem is NP-hard), but it is never more than 11/9 of the optimum plus one,
  it is what most cutting-list tools and carpenters do by hand, and it is
  deterministic: equal lengths are interchangeable, so the input order does
  not change the answer.
- **Kerf.** Every cut removes `kerf` millimetres. A bar holds pieces p1..pn
  when `sum + kerf × (n − 1) <= stockLength`: there is a kerf between each
  pair, and the last piece may run to the very end of the bar with no final
  cut. So three 1200 mm pieces do not come out of a 3600 mm length with a 3 mm
  blade; ignoring kerf is the usual mistake.
- **Offcut** is what is left after cutting the last piece off:
  `stockLength − sum − kerf × n`. When that is less than zero (less than a
  kerf's width remained) it is 0: the saw turned it to dust.
- **Waste** is everything bought but not in a piece,
  `barCount × stockLength − sum of cuts`: offcuts plus all the kerf.

All lengths are whole millimetres. One call is one section size and one
stock length; call it once per section (47×100 studs, 47×150 joists). It does
not trim a factory end or allow for defects: add that to each piece, or
shorten `stockLength`, if your timber needs squaring.

Errors: a piece that is not a positive whole number, a piece longer than the
stock, a stock length that is not positive, or a negative kerf. An empty list
buys nothing.

Source: D. S. Johnson, "Near-optimal bin packing algorithms" (MIT, 1973), for
first-fit decreasing and its 11/9 bound.