Minimizing Cutting Wastes of Reinforcement Steel Bars Using Genetic Algorithms and Integer Programming Models
Publication: Journal of Construction Engineering and Management
Volume 133, Issue 12
Abstract
Materials that are in the form of one-dimensional stocks such as steel rebars, structural steel sections, and dimensional lumber generate a major fraction of the generated construction waste. Cutting one-dimensional stocks to suit the construction project requirements result in trim or cutting losses, which is the major cause of the one-dimensional construction waste. The optimization problem of minimizing the trim losses is known as the cutting stock problem (CSP). In this paper, three approaches for solving the one-dimensional cutting stock problem are presented. A genetic algorithm (GA) model, a linear programming (LP) model, and an integer programming (IP) model were developed to solve the one-dimensional CSP. Three real life case studies from a steel workshop have been studied. The generated cutting schedules using the GA, LP, and IP approaches are presented and compared to the actual workshop’s cutting schedules. The comparison shows a high potential of savings that could be achieved using such techniques. Additionally, a user friendly Visual Basic computer program that utilizes genetic algorithms for solving the one-dimensional CSP is presented.
Get full access to this article
View all available purchase options and get full access to this article.
References
Al-Tabtabai, H., and Alex, A. P. (1997). “Manpower scheduling optimization using genetic algorithms.” Proc., Computing in Civil Engineering, ASCE, Reston, Va., 702–709.
Apotheker, S. (1990). “Construction and demolition debris—The invisible waste stream.” Resour. Recycl., 9(12), 66–74.
Brooks, K. A., Adams, C., and Demsetz, L. A. (1994). “Germany’s construction and demolition debris recycling infrastructure: What lessons does it have for the U.S.?” Proc., Sustainable Construction Conf., Tampa, Fla.
Chan, W. T., Fwa, T. F., and Tan, C. Y. (1994). “Road-maintenance planning using genetic algorithms. I: Formulation.” J. Transp. Eng., 120(5), 693–709.
Chung, Y. C., and Haupt, R. L. (1999). “Optimizing genetic algorithm parameters for adaptive nulling.” Proc., 15th Annual Review of Progress in Applied Computational Electromagnetics at the Naval Postgraduate School, Monterey, Calif.
Craven, D. J., Okraglik, H. M., and Eilenberg, I. M. (1994). “Construction waste and a new design methodology.” Proc., Sustainable Construction Conf., Tampa, Fla.
Davis, L. (1991). Handbook of genetic algorithms, Van Nostrand Reinhold, New York.
Elazouni, A., and Metwally, F. (2005). “Finance-based scheduling: Tool to maximize project profit using improved genetic algorithms.” J. Constr. Eng. Manage., 131(4), 400–412.
El-Rayes, K., and Kandil, A. (2005). “Time-cost-quality trade off analysis for highway construction.” J. Constr. Eng. Manage., 131(4), 477–486.
Feng, C., Liu, L., and Burns, S. A. (2000). “Stochastic construction time-cost trade-off analysis.” J. Comput. Civ. Eng., 14(2), 117–126.
Gavilan, R. M. (1992). “An analysis of construction solid waste.” Master’s thesis, North Carolina State Univ., Raleigh, N.C.
Gilmore, P. C., and Gomory, R. E. (1961). “A linear programming approach to the cutting-stock problem.” Operations Research Society of America, 9(6), 849–859.
Goldberg, D. E. (1989). Genetic algorithm in search, optimization and machine learning, Addison-Wesley, Reading, Mass.
Goulimis, C. (1990). “Optimal solutions for the cutting stock problem.” Eur. J. Oper. Res., 44(2), 197–208.
Haessler, R. W. (1975). “Controlling cutting patterns changes in one-dimensional trim problems.” Oper. Res., 23(3), 483–493.
Hegazy, T. (1999). “Optimization of construction time-cost trade-off analysis using genetic algorithms.” Can. J. Civ. Eng., 26(6), 685–697.
Hegazy, T., and Elbeltagi, E. (1999). “EvoSite: Evolution-based model for site layout planning.” J. Comput. Civ. Eng., 13(3), 198–206.
Hegazy, T., Elhakeem, A., and Elbeltagi, E. (2004). “Distributed scheduling model for infrastructure networks.” J. Constr. Eng. Manage., 130(2), 160–167.
Johnston, R. W. (1980). “Cutting schedules for the paper industry.” Proc., 4th IFAC Conf., Ghent, Belgium.
Khalifa, Y. M. A. (1997). “Evolutionary methods for the design of electronic circuits and systems.” Ph.D. dissertation, Univ. of Wales, Cardiff, U.K.
Khuri, S., Back, T., and Heitkotter, J. (1994). “An evolutionary approach to combinatorial optimization problems.” Proc., ACM Computer Science Conf., ACM, Phoenix, Ariz.
Lefrançois, P., and Gascon, A. (1995). “Solving a one-dimensional cutting-stock problem in a small manufacturing firm: A case study.” IIE Trans., 27(4), 483–496.
Li, H., and Love, P. E. (1998). “Site-level facilities layout using genetic algorithms.” J. Comput. Civ. Eng., 12(4), 227–231.
Liu, C., and Hammad, A. (1997). “Multiobjective optimization of bridge deck rehabilitation using genetic algorithm.” Microcomput. Civ. Eng., 12(6), 431–443.
Marzouk, M., and Moselhi, O. (2004). “Multiobjective optimization of earthmoving operations.” J. Constr. Eng. Manage., 130(1), 105–113.
Mawdesley, M., Al-jibouri, S., and Yang, H. (2002). “Genetic algorithms for construction site layout in project planning.” J. Constr. Eng. Manage., 128(5), 418–426.
Mills, T. H., Showalter, E., and Jarman, D. (1999). “Cost effective waste management plan.” Cost Eng., 41(3), 35–43.
Pierce, J. F. (1964). Some large-scale production scheduling problems in the paper industry, Prentice-Hall, Englewood Cliffs, N.J.
Que, B. (2002). “Incorporating practicability into genetic algorithm-based time-cost optimization.” J. Constr. Eng. Manage., 128(2), 139–143.
Shahin, A., and Salem, O. (2004). “Using genetic algorithms in solving the one-dimensional cutting stock problem in the construction industry.” Can. J. Civ. Eng., 31(2), 321–332.
Tam, C. M., Tong, T., and Chan, W. (2001). “Genetic algorithms for optimizing supply locations around tower crane.” J. Constr. Eng. Manage., 127(4), 315–321.
Vahrenkamp, R. (1996). “Random search in the one-dimensional cutting stock problem.” Eur. J. Oper. Res., 95(1), 191–200.
Zheng, D., Ng, T., and Kumaraswamy, M. (2004). “Applying a genetic algorithm-based multiobjective approach for time-cost optimization.” J. Constr. Eng. Manage., 130(2), 168–176.
Zheng, D., Ng, T., and Kumaraswamy, M. (2005). “Applying Pareto ranking and niche formation to genetic algorithm-based multiobjective time-cost optimization.” J. Constr. Eng. Manage., 131(1), 81–91.
Information & Authors
Information
Published In
Copyright
© 2007 ASCE.
History
Received: Jun 29, 2005
Accepted: Apr 9, 2007
Published online: Dec 1, 2007
Published in print: Dec 2007
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.