Skip to main content
SpringerLink
Log in

A tutorial in irregular shape packing problems

  • Special Issue Paper
  • Published:
Journal of the Operational Research Society

Abstract

Cutting and packing problems have been a core area of research for many decades. Irregular shape packing is one of the most recent variants to be widely researched and its history extends over 40 years. The evolution of solution approaches to this problem can be attributed to increased computer power and advances in geometric techniques as well as more sophisticated and insightful algorithm design. In this paper we will focus on the latter. Our aim is not to give a chronological account or an exhaustive review, but to draw on the literature to describe and evaluate the core approaches. Irregular packing is combinatorial and as a result solution methods are heuristic, save a few notable exceptions. We will explore different ways of representing the problem and mechanisms for moving between solutions. We will also propose where we see the future challenges for researchers in this area.

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

Figure 1
Figure 2
Figure 3
Figure 4
Figure 5
Figure 6
Figure 7
Figure 8
Figure 9
Figure 10
Figure 11
Figure 12
Figure 13
Figure 14
Figure 15
Figure 16
Figure 17
Figure 18

References

  • Agarwal PK, Flato E and Halperin D (2002). Polygon decomposition for efficient construction of Minkowski sums. Comput Geom 21: 39–61.

    Article  Google Scholar 

  • Albano A and Sapuppo G (1980). Optimal allocation of two-dimensional irregular shapes using heuristic search methods. IEEE Trans Syst Man Cybernet 10: 242–248.

    Article  Google Scholar 

  • Art RC (1996). An approach to the two-dimensional, irregular cutting stock problem. Technical Report 36.008, IBM Cambridge Centre.

  • Babu AR and Babu NR (2001). A generic approach for nesting of 2-D parts in 2-D sheets using genetic and heuristic algorithms. Comput Aided Design 33: 879–891.

    Article  Google Scholar 

  • Bennell JA and Dowsland KA (1999). A tabu thresholding implementation for the irregular stock cutting problem. Int J Prod Res 37: 4259–4275.

    Article  Google Scholar 

  • Bennell JA and Dowsland KA (2001). Hybridising tabu search with optimisation techniques for irregular stock cutting. Mngt Sci 47: 1160–1172.

    Article  Google Scholar 

  • Bennell JA and Oliveira JF (2008). The geometry of nesting problems: A tutorial. Eur J Opl Res 184: 397–415.

    Article  Google Scholar 

  • Bennell JA and Song X (2008a). A beam search implementation for the irregular shape packing problem. J Heuristics. Doi: 10.1007/s10732-008-9095-x.

  • Bennell JA and Song X (2008b). A comprehensive and robust procedure for obtaining the nofit polygon using Minkowski sums. Comput OR 35: 267–281.

    Article  Google Scholar 

  • Bennell JA, Scheithauer G, Stoyan Yu and Romanova T (2008). Tools of mathematical modelling of arbitrary object packing problems. Ann Opns Res. Doi: 10.1007/s10479-008-0456-5.

  • Blazewicz J, Hawryluk P and Walkowaik R (1993). Using a tabu search for solving the two-dimensional irregular cutting problem. Ann Opl Res 41: 313–325.

    Article  Google Scholar 

  • Burke E, Hellier RSR, Kendall G and Whitwell G (2006). A new bottom-left-fill heuristic algorithm for the two-dimensional irregular packing problem. Opns Res 54: 587–601.

    Article  Google Scholar 

  • Burke EK, Hellier RSR, Kendall G and Whitwell G (2007). Complete and robust no-fit polygon generation for the irregular stock cutting problem. Eur J Opl Res 179: 27–49.

    Article  Google Scholar 

  • Dowsland KA, Dowsland WB and Bennell JA (1998). Jostle for position: Local improvement for irregular cutting patterns. J Opl Res Soc 49: 647–658.

    Article  Google Scholar 

  • Dowsland KA, Vaid S and Dowsland WB (2002). An algorithm for polygon placement using a bottom-left strategy. Eur J Opl Res 141: 371–381.

    Article  Google Scholar 

  • Dyckhoff H (1990). A typology of cutting and packing problems. Eur J Opl Res 44: 145–159.

    Article  Google Scholar 

  • Egeblad J, Nielsen BK and Odgaard A (2007). Fast neighborhood search for two- and three-dimensional nesting problems. Eur J Opl Res 183: 1249–1266.

    Article  Google Scholar 

  • Ferreira JC, Alves JC, Albuquerque C, Oliveira JF, Ferreira JS and Matos JS (1998). A flexible custom computing machine for nesting problems. Proceedings of XIII DCIS, Madrid, Spain, pp. 348–354.

  • Fowler RJ, Paterson MS and Tanimoto SL (1981). Optimal packing and covering in the plane are NP-complete. Inform Process Lett 12(3): 133–137.

    Article  Google Scholar 

  • Gomes AM and Oliveira JF (1999). Nesting irregular shapes with simulated annealing. In: Ribeiro C (ed). Extended Abstracts of MIC1999—III Metaheuristics International Conference, 19–22 July, Angra dos Reis, Brazil.

  • Gomes AM and Oliveira JF (2002). A 2-exchange heuristic for nesting problems. Eur J Opl Res 141: 359–370.

    Article  Google Scholar 

  • Gomes AM and Oliveira JF (2006). Solving irregular strip packing problems by hybridising simulated annealing and linear programming. Eur J Opl Res 171: 811–829.

    Article  Google Scholar 

  • Heckmann R and Lengauer T (1995). A simulated annealing approach to the nesting problem in the textile manufacturing industry. Ann Opl Res 57: 103–133.

    Article  Google Scholar 

  • Imamichi T, Yagiura M and Nagamochi H (2006). An iterated local search algorithm based on nonlinear programming for the irregular strip packing problem. Proceedings of the Third International Symposium on Scheduling (ISS06), Tokyo, Japan, pp 132–137.

  • Jakobs S (1996). On genetic algorithms for the packing of polygons. Eur J Opl Res 88: 165–181.

    Article  Google Scholar 

  • Konopasek M (1981). Mathematical treatments of some apparel marking and cutting problems. US Department of Commerce Report 99-26-90857-10.

  • Lutfiyya H, McMillin B, Poshyanonada P and Dagli C (1992). Composite stock cutting through simulated annealing. Math Comput Model 16: 57–74.

    Article  Google Scholar 

  • Milenkovic V, Daniels K and Li Z (1992). Placement and compaction of nonconvex polygons for clothing manufacturing. In: Wang CA (Ed.) Fourth Canadian Conference on Computational Geometry, St Johns's, Newfoundland.

  • Oliveira JF and Ferreira JS (1993). Algorithms for nesting problems. In: Vidal R.V.V. (ed). Applied Simulated Annealing. Lecture Notes in Economics and Maths Systems Vol. 396. Springer Verlag: Berlin, pp. 255–274.

    Google Scholar 

  • Oliveira JF, Gomes AM and Ferreira JS (2000). TOPOS—A new constructive algorithm for nesting problems. Opns Res Spec 22: 263–284.

    Google Scholar 

  • Ribeiro C and Carravilla MA (2004). global constraint for nesting problems. In: Régin JC and Buehe M (eds). Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. Lecture Notes in Computer Science, Vol. 3011. Springer: Berlin, pp 256–270.

  • Segenreich SA and Braga LM (1986). Optimal nesting of general plane figures: A Monte Carlo heuristical approach. Comput Graph 10: 229–237.

    Article  Google Scholar 

  • Stoyan YG, Novozhilova MV and Kartashov AV (1996). Mathematical model and method of searching for a local extremum for the non-convex oriented polygons allocation problem. Eur J Opns Res 92: 193–210.

    Article  Google Scholar 

  • Stoyan YG, Terno J, Scheithauer G, Gil N and Romanova T (2001). Phi-functions for primary 2D-objects. Stud Inform Univ 2(1): 1–32.

    Google Scholar 

  • Takahara S, Kusumoto Y and Miyamoto S (2003). Solution for textile nesting problems using adaptive meta-heuristics and grouping. Soft Comput 7: 154–159.

    Article  Google Scholar 

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

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. University of Southampton, Southampton, UK

    J A Bennell

  2. Universidade do Porto, Porto, Portugal

    J F Oliveira

Authors
  1. J A Bennell
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. J F Oliveira
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Bennell, J., Oliveira, J. A tutorial in irregular shape packing problems. J Oper Res Soc 60 (Suppl 1), S93–S105 (2009). https://doi.org/10.1057/jors.2008.169

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1057/jors.2008.169

Keywords

Search

Navigation