Skip to main content

Advertisement

SpringerLink
Log in

A hybrid approach based on genetic algorithms to solve the problem of cutting structural beams in a metalwork company

  • Published:
Journal of Heuristics Aims and scope Submit manuscript

Abstract

This work presents a hybrid approach based on the use of genetic algorithms to solve efficiently the problem of cutting structural beams arising in a local metalwork company. The problem belongs to the class of one-dimensional multiple stock sizes cutting stock problem, namely 1-dimensional multiple stock sizes cutting stock problem. The proposed approach handles overproduction and underproduction of beams and embodies the reusability of remnants in the optimization process. Along with genetic algorithms, the approach incorporates other novel refinement algorithms that are based on different search and clustering strategies. Moreover, a new encoding with a variable number of genes is developed for cutting patterns in order to make possible the application of genetic operators. The approach is experimentally tested on a set of instances similar to those of the local metalwork company. In particular, comparative results show that the proposed approach substantially improves the performance of previous heuristics.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Aktin, T., Özdemir, R.G.: An integrated approach to the one dimensional cutting stock problem in coronary stent manufacturing. Eur. J. Oper. Res. 196, 737–743 (2009)

    Article  MATH  Google Scholar 

  • Alves, C., Valério de Carvalho, J.M.: A stabilized branch-and-price-and-cut algorithm for the multiple length cutting stock problem. Comput. Oper. Res. 35, 1315–1328 (2008)

    Article  MATH  Google Scholar 

  • Anand, S., McCord, C., Sharma, R., et al.: An integrated machine vision based system for solving the nonconvex cutting stock problem using genetic algorithms. J. Manuf. Syst. 18, 396–415 (1999)

    Article  Google Scholar 

  • Belov, G., Scheithauer, G.: A cutting plane algorithm for the one-dimensional cutting stock problem with multiple stock lengths. Eur. J. Oper. Res. 141, 274–294 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  • Christofides, N., Hadjiconstantinou, E.: An exact algorithm for orthogonal 2-D cutting problems using guillotine cuts. Eur. J. Oper. Res. 83, 21–38 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  • Elizondo, R., Parada, V., Pradenas, L., Artigues, C.: An evolutionary and constructive approach to a crew scheduling problem in underground passenger transport. J. Heuristics 16, 575–591 (2010)

    Article  MATH  Google Scholar 

  • Fan, L., Mumford, C.L.: A metaheuristic approach to the urban transit routing problem. J. Heuristics 16, 353–372 (2010)

    Article  MATH  Google Scholar 

  • Gau, T., Wäscher, G.: CUTGEN1: a problem generator for the standard one-dimensional cutting stock problem. Eur. J. Oper. Res. 84, 572–579 (1995)

    Article  MATH  Google Scholar 

  • Gilmore, P.C., Gomory, R.E.: A linear programming approach to the cutting stock problem. Oper. Res. 9, 849–859 (1961)

    Article  MathSciNet  MATH  Google Scholar 

  • Gilmore, P.C., Gomory, R.E.: A linear programming approach to the cutting stock problem. Part II. Oper. Res. 11, 863–888 (1963)

    Article  MATH  Google Scholar 

  • Ghiani, G., Laganà, G., Laporte, G., Mari, F.: Ant colony optimization for the arc routing problem with intermediate facilities under capacity and length restrictions. J. Heuristics 16, 211–233 (2010)

    Article  MATH  Google Scholar 

  • Gonçalves, J.F., Resende, G.C.: Biased random-key genetic algorithms for combinatorial optimization. J. Heuristics (2011). doi:10.1007/s10732-010-9143-1

    Google Scholar 

  • Gradisar, M., Kljajic, M., Resinovic, G., et al.: A sequential heuristic procedure for one-dimensional cutting. Eur. J. Oper. Res. 114, 557–568 (1999)

    Article  MATH  Google Scholar 

  • Haessler, R.W.: One-dimensional cutting stock problems and solution procedures. Math. Comput. Model. 16, 1–8 (1992)

    Article  MATH  Google Scholar 

  • Haessler, R.W., Sweeney, P.E.: Cutting stock problems and solution procedures. Eur. J. Oper. Res. 54(2), 141–150 (1991)

    Article  MATH  Google Scholar 

  • Haessler, R.W.: Solving the two-stage cutting stock problem. Omega 7, 145–151 (1979)

    Article  Google Scholar 

  • Hinterding, R., Khan, L.: Genetic algorithms for cutting stock problems: with and without contiguity. In: Yao, X. (ed.) Progress in Evolutionary Computation. LNAI, vol. 956, pp. 166–186. Springer, Berlin (1995)

    Chapter  Google Scholar 

  • Holthaus, O.: Decomposition approaches for solving the integer one-dimensional cutting stock problem with different types of standard lengths. Eur. J. Oper. Res. 141, 295–312 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  • Kantorovich, L.V.: Mathematical methods of organizing and planning production. Manag. Sci. 6, 366–422 (1939) (Translation to English 1960)

    Article  MathSciNet  Google Scholar 

  • Liang, K., Yao, X., Newton, C., et al.: A new evolutionary approach to cutting stock problems with and without contiguity. Comput. Oper. Res. 29, 1641–1659 (2002)

    Article  MathSciNet  Google Scholar 

  • Poldi, K., Arenales, M.: Heuristics for the one-dimensional cutting stock problem with limited multiple stock lengths. Comput. Oper. Res. 36, 2074–2081 (2009)

    Article  MATH  Google Scholar 

  • Suliman, S.M.A.: Pattern generating procedure for the cutting stock problem. Int. J. Prod. Econ. 74, 293–301 (2001)

    Article  Google Scholar 

  • Talbi, E.-G.: A taxonomy of hybrid metaheuristics. J. Heuristics 8, 541–564 (2002)

    Article  Google Scholar 

  • Vahrenkamp, R.: Random search in the one-dimensional cutting stock problem. Eur. J. Oper. Res. 95, 191–200 (1996)

    Article  MATH  Google Scholar 

  • Vanderbeck, F.: Exact algorithm for minimizing the number of set ups in the one dimensional cutting stock problems. Oper. Res. 48, 915–926 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  • Wagner, B.J.: A genetic algorithm solution for one-dimensional bundled stock cutting. Eur. J. Oper. Res. 117, 368–381 (1999)

    Article  MATH  Google Scholar 

  • Wäscher, G., Haußner, H., Schumann, H.: An improved typology of cutting and packing problems. Eur. J. Oper. Res. 183, 1109–1130 (2007)

    Article  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Departamento de Organización de Empresas, Universidad Politécnica de Valencia, Camino de Vera s/n, 46022, Valencia, Spain

    Carlos Gracia & Carlos Andrés

  2. Instituto IDF, Universidad Politécnica de Valencia, Camino de Vera s/n, 46022, Valencia, Spain

    Luis Gracia

Authors
  1. Carlos Gracia
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Carlos Andrés
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Luis Gracia
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Carlos Gracia.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Gracia, C., Andrés, C. & Gracia, L. A hybrid approach based on genetic algorithms to solve the problem of cutting structural beams in a metalwork company. J Heuristics 19, 253–273 (2013). https://doi.org/10.1007/s10732-011-9187-x

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10732-011-9187-x

Keywords

Search

Navigation