Optimal cutting of lumber and particle boards into dimension parts – some algorithms and solution procedures

This paper describes some algorithms and procedures that can be used for determining the optimal cutting of lumber or composite boards into dimension or furniture parts. Methodologies are described for various production scenarios: (1) cutting when the direction of the grain matters (e.g., lumber), (2) cutting composite boards where grain direction does not matter, (3) rip-first cutting, (4) crosscut-first cutting, and (5) a combination of rip-first and crosscut-first. An algorithm for optimizing the cutting of all lumber types while at the same time satisfying a given order of dimension parts is also described. The models can be used interactively for comprehensive optimization of cutting a mix of lumber as shown by the two-stage decision model, or the double knapsack algorithms could be used as stand alone models for optimizing the cutting of individual lumber.