Abstract
Reducing expensive raw material waste is an important goal in the industry. In this paper, two-dimensional irregular cutting stock problem—a nesting problem that differs from other in their irregular shape of the pieces—with demand is studied, in which the required pieces has to be produced from large rectangular sheet minimizing material waste. Structure of this problem made it intractable for practical applications such that exact algorithms are not able to solve it in a reasonable time. Greedy randomized adaptive search procedure (GRASP) meta-heuristic algorithm is adapted to tackle the problem by providing high-quality solution in an appropriate time. The algorithm does not depend on the shape (convexity and regularity) of pieces and is able to deliver an optimum solution for instances up to 30 pieces of 7 different types. In addition, computational results are provided for different test problems from the related literature.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Adamowicz M, Albano A (1976) Nesting two dimensional shapes in rectangular modules. Comp Aid Des 8(1):27–33
Albano A (1977) A method to improve two-dimensional layout. Comp Aid Des 9(1):48–52
Albano A, Sapuppo G (1980) Optimal allocation of two-dimensional irregular shapes using heuristic search methods. IEEE Trans Syst Man Cybern, SMC 10(5):242–248
Arbel A (1993) Large-scale optimization methods applied to the cutting stock problem of irregular shapes. Int J Prod Res 31(2):483–500
Arbib C, Marinelli F (2007) An optimization model for trim loss minimization in an automotive glass plant. Eur J Operat Res 183(3):1421–1432
Beasley J (1985) Algorithms for unconstrained two-dimensional guillotine cutting. Operat Res 36(4):297–306
Bennell JA, Oliveira JF (2009) A tutorial in irregular shape packing problems. J Operat Res Soc 60:93–105
Bennell J, Song X (2010) A beam search implementation for the irregular shape packing problem. J Heurist 16(2):167–188
Biro M, Boros E (1984) Network flows and non-guillotine cutting patterns. Eur J Operat Res 16(2):215–221
Blazewicz J, Hawryluk P, Walkowiak R (1993) Using a tabu search approach for solving the two-dimensional irregular cutting problem. Annal Operat Res 41(4):313–325
Cheng C, Feiring B, Cheng T (1994) A cutting stock problem—a survey. Int J Prod Econ 36(3):291–305
Delorme X, Gandibleux X, Rodriguez J (2004) GRASP for set packing problems. Eur J Operat Res 153(3):564–580
Dowsland K, Dowsland W (1995) Solution approaches to irregular nesting problems. Eur J Operat Res 84(3):506–521
Dyckhoff H (1990) A typology of cutting and packing problems. Eur J Operat Res 44(2):145–159
Egeblad J, Nielsen B, Odgaard A (2007) Fast neighborhood search for two- and three-dimensional nesting problems. Eur J Operat Res 183(3):1249–1266
Feo T, Resende A (1989) A probabilistic heuristics for a computationally difficult set covering problem. Operat Res Lett 8:67–71
Gendreau M, Potvin J (2010) Handbook of metaheuristics, 2nd edn. Springer, New York
Gilmore P, Gomory R (1961) A linear programming approach to the cutting stock problem. Operat Res 9(6):849–859
Gilmore P, Gomory R (1963) A linear programming approach to the cutting stock problem part II. Operat Res 11(6):863–888
Hahn S (1968) On the optimal cutting of defective sheets. Oper Res 16(6):1100–1113
Haims M, Freeman H (1970) A multistage solution of the template-layout problem. IEEE Trans Syst Sci Cybernet 6(2):145–151
Ismail H, Hon K (1992) New approaches for the nesting of two-dimensional shapes for press tool design. Int J Prod Res 30(4):825–837
Leung S, Lin Y, Zhang D (2012) Extended local search algorithm based on nonlinear programming for two-dimensional irregular strip packing problem. Comp Operat Res 39(3):678–686
Lutfiyya H, McMillin B, Poshyanonda P, Dagli C (1992) Composite stock cutting through simulated annealing. Mathemat Comput Model 16(1):57–74
Morabito R, Arenales M (2000) Optimizing the cutting of stock plates in a furniture company. Int J Prod Res 38(12):2725–2742
Morabito R, Belluzzo L (2007) Optimizing the cutting of wood fibre plates in the hardboard industry. Eur J Operat Res 183(3):1405–1420
Pierce F (1964) Some large scale production scheduling problems in the paper industry. Prentice-Hall, Englewood Cliffs
Prais M, Ribeiro C (2000) Reactive GRASP: an application to a matrix decomposition problem in TDMA traffic assignment. INFORMS J Comp 12(3):164–176
Prasad SS, Dhande SG (1986) Computer aided design of optimal pattern layouts. CAD/CAM/CAE for Industrial Progress, pp 105–117
Qu W, Sanders J (1987) A nesting algorithm for irregular parts and factors affecting trim losses. Int J Prod Res 25(3):381–397
Roberts SA (1984) Application of heuristic techniques to the cutting-stock problem for worktops. J Oper Res Soc 35:369–377
Sarker BR (1988) An optimum solution for one-dimensional slitting problems: a dynamic programming approach. J Operat Res Soc 39(8):749–755
Toledo F, Carravilla M, Ribeiro C, Oliveira J, Gomes A (2013) The dotted-board model: a new MIP model for nesting irregular shapes. Int J Prod Econ 145(2):478–487
Verkhoturov M, Sergeyeva O (2000) The sequential value correction method for the two-dimensional irregular cutting stock problem. Pes Oper 20(2):233–246
Wascher G, Haubner H, Schumann H (2007) An improved typology of cutting and packing problems. Eur J Operat Res 183(3):1109–1130
Yaodong C, Yiping L (2009) Heuristic algorithm for a cutting stock problem in the steel bridge construction. Comp Operat Res 36(2):612–622
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
MirHassani, S.A., Jalaeian Bashirzadeh, A. A GRASP meta-heuristic for two-dimensional irregular cutting stock problem. Int J Adv Manuf Technol 81, 455–464 (2015). https://doi.org/10.1007/s00170-015-7107-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00170-015-7107-1