Cutting to Order in the Rough Mill: A Sampling Approach


  • Evan D. Hamilton
  • David A. Butler
  • Charles C. Brunner


Cutting order, linear program, secondary manufacturing, knapsack problem, optimizer


A cutting order is a list of dimension parts along with demanded quantities. The cutting-order problem is to minimize the total cost of filling a cutting order from a given lumber supply. Similar cutting-order problems arise in many industrial situations outside of forest products. This paper adapts an earlier, linear programming approach that was developed for uniform, defect-free stock materials. The adaptation presented here allows the method to handle nonuniform stock material (e.g., lumber) that contains defects that are not known in advance of cutting. The main differences are the use of a random sample to construct the linear program and the use of prices rather than cutting patterns to specify a solution. The primary result of this research is that the expected cost of filling an order under the proposed method is approximately equal to the minimum possible expected cost for sufficiently large order and sample sizes. A secondary result is a lower bound on the minimum possible expected cost. Computer simulations suggest that the proposed method is capable of attaining nearly minimal expected costs in moderately large orders.


Anderson, J. D., C. C. Brunner, and A. G. Maristany. 1992. Effect of sawing stages on fixed-width, fixed-length dimension yields. Forest Prod. J.42(11/12):74-78.nAnderson, J. D., C. C. Brunner, and S. U. Randhawa. 1997. Design and implementation of a fuzzy logic controller for wood parts recovery in rough mills. Int. J. Flexible Autom. Int. Mfg.4(3-4):255-271.nBrunner, C. C., M. S. White, F. M. Lamb, and J. G. Schroeder. 1989. CORY: A computer program for determining dimension stock yields. Forest Prod. J.39(2):23-24.nCarino, H. F., and S. U. Foronda. 1990. SELECT: A model for minimizing blank costs in hardwood furniture manufacturing. Forest Prod. J.40(5):21-26.nCarnieri, C., G. A. Mendoza, and L. Gavinho. 1994. Optimal cutting of lumber and particleboards into dimension parts: Some algorithms and solution procedures. Wood Fiber Sci.26(1):131-141.nCochran, W. G. 1977. Sampling techniques. John Wiley & Sons, New York, NY.nDmitrovic, B., D. Wolf, and R. H. C. Husson. 1992. A standard model of the placement problem aimed at resolving a cutting stock problem. IEEE Trans. Industry Appl.28(6):1406-1415.nForonda, S. U., and H. F. Carino. 1991. A heuristic approach to the lumber allocation problem in hardwood dimension and furniture manufacturing. European J. Operational Res.54:151-162.nGatchell, C. J., R. B. Anderson, and P. A. Araman. 1983. Effect of gang-ripping width on CIF yields from No. 2 Common oak lumber. Forest Prod. J.33(6):43-48.nGiese, P. J., and K. A. McDonald. 1982. OPTYLD—A multiple rip-first computer program to maximize cutting yields. Research Paper FPL-412. USDA Forest Serv., Forest Products Lab, Madison, WI.nGiese, P. J., and J. D. Danielson. 1983. CROMAX—A crosscut-first computer simulation program to determine cutting yield. Gen. Tech. Rep. FPL-38. USDA Forest Serv., Forest Products Lab, Madison, WI.nGilmore, P. C., and R. E. Gomory. 1961. A linear programming approach to the cutting stock problem. Operations Res.9:849-859.nGilmore, P. C., and R. E. Gomory. 1963. A linear programming approach to the cutting stock problem—Part II. Operations Res.11:863-888.nHahn, S. G. 1968. On the optimal cutting of defective sheets. Operations Res.16(6):1100-1114.nHallock, H. 1980. Cutting yields from standard hardwood lumber grades when gang ripping. Research Paper FPL-370. USDA Forest Serv., Forest Products Lab, Madison, WI.nHamilton, E. D. 2001. A linear programming and sampling approach to the cutting-order problem. Ph.D. thesis, Oregon State University, Corvallis, OR.nHarding, O. V., and P. H. Steele. 1997. RIP-X: Decision software to compare crosscut-first and rip-first rough mill systems. Wood Sci. Technol.31(5):367-381.nKlinkhachorn, P., J. P. Franklin, C. W. McMillin, and H. A. Huber. 1989. ALPS: Yield optimization cutting program. Forest Prod. J.39(3):53-56.nMartens, D. G., and R. L. Nevel, Jr. 1985. OPTIGRA-MI: Optimum lumber grade mix program for hardwood dimension parts. Tech. Rep. NE-563. USDA Forest Service, Northeastern Forest Experiment Station, Princeton, WV.nMcDonald, K. A., P. J. Giese, and R. O. Woodfin. 1981. 5/4 ponderosa pine shop cutting yields. Research Paper FPL-394. USDA Forest Service.nMcDonald, K. A., P. J. Giese, and R. O. Woodfin. 1983. Maximum cutting yields for 6/4 ponderosa pine shop lumber. Research Paper FPL-437. USDA Forest Service, Forest Products Lab, Madison, WI.nMurty, K. G. 1976. Linear and combinatorial programming. Wiley, New York, NY.nRamsey, F. L., and D. W. Schafer. 1997. The statistical sleuth: A course in methods of data analysis. Duxbury Press, Pacific Grove, CA.nSuter, Jr., W. C., and J. A. Calloway. 1994. Rough mill policies and practices examined by a multiple-criteria goal program called ROMGOP. Forest Prod. J.44(10):19-28.nThomas, R. E. 1996. Prioritizing parts from cutting bills when gang-ripping first. Forest Prod. J.46(10):61-66.nThomas, R. E. 1997. ROMI-CROSS: ROugh Mill CROSScut-first simulator. Tech. Rep. NE-229. USDA Forest Service, Northeastern Forest Experiment Station, Princeton, WV.nThomas, R. E. 1999. ROMI-RIP Ver. 2: ROugh Mill RIP-first simulator. Tech. Rep. NE-259. USDA Forest Service, Northeastern Forest Experiment Station, Princeton, WV.nWodzinski, C., and E. Hahm. 1966. A computer program to determine yields of lumber. Tech. Rep. 66-009. USDA Forest Service, Forest Products Lab, Madison, WI.n






Research Contributions