Combinatorial Algorithm for Optimizing Wood Waste in Framing Designs
Publication: Journal of Construction Engineering and Management
Volume 137, Issue 3
Abstract
As a result of elevated labor costs, a shortage of trades personnel, and a lack of efficient construction methods, many construction companies in western Canada waste primary materials. In general, these firms suffer from a lack of effective construction guidelines and process standardizations. This paper focuses on the use of a mathematical algorithm, referred to here in this paper as CUTEX, which maximizes the use of wood materials for platform-framing residential construction. In particular, CUTEX is designed to reduce waste by generating a cutting list for wood studs and sheathing (oriented strand boards—OSB). A combinatorial analysis algorithm has been developed and applied to determine the best cutting procedure for wood stick frame houses. Restrictions, such as nominal lumber dimensions and sizes encountered in the North American market, were taken into account. A two-dimensional optimization for sheathing layout has also been developed to minimize the disposal of OSB boards, making the construction process leaner and more economical. A direct and positive impact on the environment and a reduction in construction costs are expected as a result of reducing the amount of primary materials utilized.
Get full access to this article
View all available purchase options and get full access to this article.
Acknowledgments
This research was supported by the Canadian research network of Mathematics of Information Technology and Complex Systems (MITACS 2007), the Landmark Group of Builders, Edmonton, Canada, and the Natural Science and Engineering Research Council of Canada (NSERC), CRD Grant No. NSERCCRDPJ 350089-06.
References
Armor, B. H., and De Carvalho, J. V. (2005). “Cutting-stock problems.” Column generation, G. Desaulniers, J. Desrosiers, and M. M. Solomon, eds., Springer, New York.
Barnhardt, C., Johnson, E. L., Nemhauser, G. L., Savelsberg, M. W. P., and Vance, P. (2000). “Branch-and-price: Column generation for solving huge integer programs.” Oper. Res., 48(2), 318–326.
Beasley, J. E. (2004). “A population heuristic for constrained two-dimensional non-guillotine cutting.” Eur. J. Oper. Res., 156(3), 601–627.
Canadian Institute of Timber Construction. (1993). Timber construction: A manual for architects and engineers, Ottawa.
Degraeve, Z., and Schrage, L. (1999). “Optimal integer solutions to industrial cutting stock problems.” INFORMS J. Comput., 11(4), 406–419.
Diegel, A., Miller, G., Montocchio, E., Schalkwyk, S., and Diegel, O. (2006). “Enforcing minimum run length in the cutting-stock problem.” Eur. J. Oper. Res., 171(2), 708–721.
Dyckhoff, H. (1981). “A new linear programming approach to the cutting-stock problem.” Oper. Res., 29(6), 1092–1104.
Gilmore, P. C., and Gomory, R. E. (1961). “A linear programming approach to the cutting-stock problem.” Oper. Res., 9(6), 849–859.
Haessler, R. W. (1980). “A note on computational modifications to the Gilmore-Gomory cutting-stock algorithm.” Oper. Res., 28(4), 1001–1005.
Landanyi, L., Lee, J., and Lougee-Heimer, R. (2005). “Rapid prototyping of optimization algorithms using COIN-OR: A case study involving the cutting-stock problem.” Ann. Oper. Res., 139, 243–265.
Landmark Group of Builders, Drafting Department. (2007). 〈www.landmarkhomes.ca〉 (Sep. 15, 2007).
Laquatra, J., and Pierce, M. (2004). “Managing waste at the residential construction site.” J. Solid Waste Technol. Manage., 30(2), 45–20.
Mah, D. (2007). “Analysis of material waste from the framing stage in residential construction based on Landmark Homes field investigation.” Construction Engineering and Management Dept., Univ. of Alberta, Alberta, Canada.
Manrique, J. D., Al-Hussein, M., Bouferguene, A., Safouhi, H., and Nasseri, R. (2007). “Shop drawing automation and material waste minimization in the construction of wood houses utilizing 3D-CAD and optimization techniques.” Proc., 4th Int. Structural Engineering and Construction Conf., Univ. of Wollongong, NSW, Australia
MacLeod, B., Moll, R., Girkar, M., and Hanif, N. (1993). “An algorithm for the 2D guillotine cutting-stock problem.” Eur. J. Oper. Res., 68(3) 400–412.
Mullens, M. A., and Arif, M. (2006). “Structural insulated panels: Impact on the residential construction process.” J. Constr. Eng. Manage., 132(7), 786–794.
Scheithauer, G., and Terno, J. (1995). “A branch and bound algorithm for solving one-dimensional cutting-stock problems exactly.” Appl. Math., 23(2), 151–167.
Scheithauer, G., Terno, J., Muller, A., and Belov, G. (2001). “Solving one-dimensional cutting-stock problems exactly with a cutting plane algorithm.” J. Oper. Res. Soc., 52(12), 1390–1401.
Song, X., Chu, C. B., Nie, Y. Y., and Benell, J. A. (2006). “An iterative sequential heuristic procedure to a real-life 1.5-dimensional cutting-stock problem.” Eur. J. Oper. Res., 175(3), 1870–1889.
Sustainable Communities Network (SCN). (2000). “Residential construction waste: From disposal to management.” 〈www.smartgrowth.org〉 (July 20, 2007).
Tracy, J. (2000). “SIPs: Overcoming the elements.” Forest Prod. J., 50(3), 12–18.
Trkman, P., and Gradisar, M. (2007). “One-dimensional cutting-stock optimization in consecutive time periods.” Eur. J. Oper. Res., 179(2), 291–301.
Vance, P. (1998). “Branch and price algorithms for one-dimensional cutting-stock problem.” Comput. Optim. Appl., 9(3), 211–228.
Vanderbeck, F. (1999). “Computational study of column generation algorithm for bin packing and cutting stock problems.” Math. Program., 86(3), 565–594.
Information & Authors
Information
Published In
Journal of Construction Engineering and Management
Volume 137 • Issue 3 • March 2011
Pages: 188 - 197
Copyright
© 2011 American Society of Civil Engineers.
History
Received: Mar 16, 2009
Accepted: Jul 6, 2009
Published online: Jul 10, 2009
Published in print: Mar 1, 2011
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.