Secondary log breakdown optimization with dynamic programming

Log breakdown can be viewed as a two-stage process with logs sawn into slabs of wood known as flitches during the primary stage and flitches further processed during the secondary stage to produce edged (cut lengthwise) and trimmed (cut widthwise) pieces. This paper addresses the secondary problem and describes some procedures for determining the optimal cutting of flitches into graded dimensional boards. The problem is formulated as a set packing problem with the objective being to maximise total value. Extensions to the basic formulation include constraints which restrict the number of saws and which disallow waste between adjacent edged pieces. The problem is solved using dynamic programming techniques and the algorithms incorporated into a sawing simulation system. Comparisons with existing edging and trimming procedures show that substantial reductions in solution time (to as little as 1/25th of the time required for an enumerative search) can be achieved.