Optimal Cutting of Lumber and Particleboards into Dimension Parts: Some Algorithms and Solution Procedures

Authors

  • Celso Carnieri
  • Guillermo A. Mendoza
  • Luciano Gavinho

Keywords:

Dynamic programming, knapsack algorithm, optimal cutting patterns, dimension cutting

Abstract

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.

References

Brunner III, C. C. 1984. A computer program to determine furniture cutting yields for both rip-first and crosscut-first sawing sequences. Ph.D. thesis, Virginia Polytechnique Institute and State University, Blacksburg, VA.nCarnieri, C., G. A. Mendoza, and L. Gavinho. 1991. Modified knapsack algorithms for cutting lumber into furniture parts. Working paper No. 2. Department of Forestry, University of Illinois, Urbana, IL.nForonda, S. U., and H. F. Carino. 1991. A heuristic approach to the lumber allocation and manufacturing in hardwood dimension and furniture manufacturing. European J. Operations Res. 54:151-162.nGiese, P. J., and K. A. McDonald. 1982. OPTYLD: A multiple rip-first computer program to maximize cutting yields. USDA Forest Service Res. Pap. FPL-412.nGiese, P. J., and J. D. Danielson. 1983. CROMAX—A crosscut-first computer simulation program to determine cutting yields. USDA Forest Service General Tech. Rep. FPL-38.nGilmore, P. C., and R. E. Gomory. 1965. Multi-stage cutting stock problems of two or more dimensions. Operations Research 13:94-120.nGilmore, R. C., S. J. Hanover, and J. D. Danielson. 1984. Dimension yields from yellow poplar lumber. USDA Forest Service General Tech. Rep. FPL-41.nMartens, D. G., and R. L. Nevel. 1985. OPTIGRAMI: Optimum lumber grade mix program for hardwood dimension parts. USDA Forest Service Res. Paper NE-563.nMendoza, G. A., and B. Bare. 1986. A two-stage decision model for log bucking and allocation. Forest Prod. J. 10:70-74.nShumann, D. R. 1971. Dimension yields from black walnut lumber. USDA Forest Service Res. Paper FPL-162.nShumann, D. R. 1972. Dimension yield from alder lumber. USDA Forest Service Res. Paper FPL-170.n

Downloads

Published

2007-06-22

Issue

Number 1 / January 1994

Section

Research Contributions

License

The copyright of an article published in Wood and Fiber Science is transferred to the Society of Wood Science and Technology (for U. S. Government employees: to the extent transferable), effective if and when the article is accepted for publication. This transfer grants the Society of Wood Science and Technology permission to republish all or any part of the article in any form, e.g., reprints for sale, microfiche, proceedings, etc. However, the authors reserve the following as set forth in the Copyright Law:

1. All proprietary rights other than copyright, such as patent rights.

2. The right to grant or refuse permission to third parties to republish all or part of the article or translations thereof. In the case of whole articles, such third parties must obtain Society of Wood Science and Technology written permission as well. However, the Society may grant rights with respect to Journal issues as a whole.

3. The right to use all or part of this article in future works of their own, such as lectures, press releases, reviews, text books, or reprint books.