Cutting to Order in the Rough Mill: A Sampling Approach
Keywords:Cutting order, linear program, secondary manufacturing, knapsack problem, optimizer
AbstractA 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
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.