Abstract
In this paper, we address the irregular strip packing problem (or nesting problem) where irregular shapes have to be placed on strips representing a piece of material whose width is constant and length is virtually unlimited. We explore a constructive heuristic that relies on the use of graphical processing units to accelerate the computation of different geometrical operations. The heuristic relies on static selection processes, which assume that a sequence of pieces to be placed is defined a priori. Here, the emphasis is put on the analysis of the impact of these sequences on the global performance of the solution algorithm. Computational results on benchmark datasets are provided to support this analysis, and guide the selection of the most promising methods to generate these sequences.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
- Graphical Processing Unit
- Packing Problem
- Constructive Heuristic
- Graphical Processing Unit Memory
- Nest Problem
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Bennell, J., Oliveira, J.: The geometry of nesting problems: A tutorial. European Journal of Operational Research 184, 397–415 (2008)
Bennell, J., Oliveira, J.: A tutorial in irregular shape packing problems. Journal of the Operational Research Society 60, 93–105 (2009)
Burke, E., Hellier, R., Kendall, G., Whitwell, G.: A new bottom-left-fill heuristic algorithm for the two-dimensional irregular packing problem. Operations Research 54, 587–601 (2006)
Fowler, R.J., Paterson, M.S., Tanimoto, S.L.: Optimal packing and covering in the plane are np-complete. Information Processing Letters 12, 133–137 (1981)
Gomes, A.M., Oliveira, J.: A 2-exchange heuristic for nesting problems. European Journal of Operational Research 141, 359–370 (2002)
Owens, J.D., Luebke, L., Govindaraju, N., Harris, M., Krüger, J., Lefohn, A.E., Purcell, T.J.: A survey of general-purpose computation on graphics hardware. Computer Graphics Forum 26, 1467–8659 (2007)
Sampaio, S., Gomes, A.M., Rodrigues, R.: Exploring graphical processing in irregular strip packing problems. To be published in CIM Series in Mathematical Sciences, by Springer Verlag, for IO2013 - XVI Congresso da APDIO (June 2013)
Wäscher, G., Hauβner, H., Schumann, H.: An improved typology of cutting and packing problems. European Journal of Operational Research 183, 1109–1130 (2007)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this chapter
Cite this chapter
Rocha, P., Rodrigues, R., Gomes, A.M., Alves, C. (2015). GPU-Based Computing for Nesting Problems: The Importance of Sequences in Static Selection Approaches. In: Póvoa, A., de Miranda, J. (eds) Operations Research and Big Data. Studies in Big Data, vol 15. Springer, Cham. https://doi.org/10.1007/978-3-319-24154-8_23
Download citation
DOI: https://doi.org/10.1007/978-3-319-24154-8_23
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-24152-4
Online ISBN: 978-3-319-24154-8
eBook Packages: EngineeringEngineering (R0)