Nesting Algorithms for Placement of Regular & Irregular Shaped Parts: A Review

Nesting Algorithms for Placement of Regular & Irregular Shaped Parts: A Review

Nehal I. Joshi*1

Kalol Institute of Technology & Research Centre,Kalol, Gujarat,India

Avadhoot Rajurkar2 Department of Mech Engg, Charotar University of science & Tech., Changa Dist Anand

Ashish M. Desai3 Sankalchand Patel College of Engineering, Visnagar, Gujarat,India.

Abstract

Nesting problem is of great interest to garment, paper, furniture, marble tiles, glass, ship building and sheet metal industries since small improvement of layout can lead to large savings in material. Many effective solutions have been proposed for the case when pieces and containing region are both rectangular. Two dimensional irregular-shaped nesting problems is the problem of finding an efficient arrangement for pieces in a containing region without overlapping, and is aimed at maximizing use of material. This paper systematically reviews the nesting algorithms that were developed to perform various 2-dimensional nesting tasks, and attacks the regular and irregular part nesting problem.

1. Introduction

   Stock Layout has a close relationship with product cost in the vein of how to most efficiently cut the product patterns from raw materials. This is so- called nesting problem. The nesting problem generally refers to the problem of placing a number of shapes within the bounds of some material, typically rectangular, such that no pair of shapes overlaps [1]. Most often, it is also an objective to minimize the size of the material which is equivalent to maximizing the utilization of the material. This problem is also known as the strip nesting problem or the irregular strip packing problem. This occurs frequently in sheet metal and furniture industries, wherein material utilization needs to be maximized. Depending upon the application other constraints like position, orientation and adjacency may also be specified along with the main problem.

2. Nesting Algorithms

   Nesting is a classic problem of finding the most efficient layout for cutting parts out of a given sheet with minimum waste material. The number of

   applications, e.g. steel, clothing, shipbuilding, and furniture industry is numerous [1]. Manual methods are used to determine the arrangement in some industries. Operators decide the layout from their experience, but this is not an efficient method because it is time- consuming and the results do not efficiently utilize the raw material. It is challenging to obtain an efficient solution in a reasonable time when there are number of parts.

   While investigating for the solution to nesting problem for regular and irregular shapes, many researchers have gone for mathematical programming. However, mathematical programming is not suitable in case of all kinds of shapes. Some researchers address the nesting problem to a search space process using heuristic methods. Many meta-heuristic methods have been attempted to solve nesting problems, such as Simulated Annealing by Lutfiyya et al. [2], tabu search by Bennell and Dowsland [3], and Genetic Algorithms by Anand et al. [4] Even though these approaches can find efficient layouts, they are also similarly time- consuming like manual solutions by human operators.

   Lee et. al. [5] proposed the heuristic algorithm, quick location and movement (QLM), to solve nesting problems for multiple two-dimensional complex irregular parts on two-dimensional complex irregular sheets. Irregular shaped parts have been transformed to polygons and the parts were nested by a step by step procedure. The algorithm has been developed using C++ programming and shape files were handled with AutoCAD in .DXF format.

   In the area of CAD/CAM, the feature-based method is often applied to the flat pattern development for sheet metal parts. A knowledge based system has been developed by Pan and Rao [6] for solving the nesting problem of sheet metal cutting and punching. The whole system comprised of five functional modules, i.e., modeling, nesting, process planning, NC- programming & simulation and reporting module. These modules share a unified object-oriented data

   structure, so that they were integrated seamlessly in terms of data processing.

   The knowledge for the process planning module comprises the punching tool sequencing algorithm and the cutting sequencing algorithm in the Optimization Algorithm Library (OAL) and the cutting/ punching process rules in the Process Rules Base (PRB). Some process rules are experiment-based (e.g. the rules for deciding cutting speed) while some are mainly empirical (e.g. the rules for deciding the type or length of an auxiliary cutting path).

   In the same line, Kumar and Singh [7] proposed a system, developed using the production rule-based expert system approach of Artificial Intelligence (AI). It comprised six modules to impart expert advice to the user for identifying sheet metal operations, sequencing of operations, selection of proper piloting scheme, number of stations, staging of operations on progressive die and selection of proper dimensions of stock strip. Finally, the system models the strip-layout automatically in the drawing editor of AutoCAD using the output data files of other modules.

   Yaodong Cui [8] has developed an exact algorithm for generating two segment cutting patterns of punched strips. The algorithm uses dynamic programming techniques to determine the optimal strip layouts on segments of various lengths, and selects two segments to appear in the optimal pattern

   Yaodong Cui and Yiping Lu [9] have developed a heuristic algorithm for cutting stock problem in steel bridge construction. The algorithm uses both recursive and dynamic programming techniques to generate patterns.

   Cheng and Rao [10] have demonstrated that the large scale nesting of irregular patterns is possible using compact neighborhood algorithm. The nesting of geometrical shapes is performed by compact neighborhood algorithm (CNA) and the layout is optimized by using Genetic Algorithm (GA).

   Chow [11] has found an approach for nesting shapes in a single or double row on a flat strip. He has presented three different procedures. Nee [12] has also reported a simple microcomputer based strip layout solution for a single row layout and pair wise clustered layout.

   Rectangular shape cutting stock problem has been studied by many researchers. Glimore P C and Gomory R E [13, 14, 15, 16, 17 & 18] have resolved the rectangular cutting stock problem by the way of linear programming using the algorithm of knapsack problem which applies to a guillotine cutting of the material in order to give rectangular shapes. Christofides and Whitlock [19] presented a tree search algorithm for the rectangular cutting stock problem in which there exist

   constraints on the maximum number of each type of piece and all cuts are of guillotine type. Their algorithm however is inefficient in terms of computational time in situations where a large size problem is to be solved. Adamowicz and Albano [20, 21, 22] found an approach for guillotine cutting using dynamic programming. Albano and Orisini [23, 24] improved their own proposal of a heuristic tree search approach to knapsack problem for guillotine cutting. Their algorithm is efficient in terms of computer time for computing near an optimal solution. Beasley [25, 26, 27] has presented both heuristic and exact algorithm based on dynamic programming for staged as well non-staged version of the problem. His algorithms are capable of dealing a large problem.

   Admowicz and Albano [22] have studied nesting of the irregular geometrical shapes n a rectangular stock. The solution proposed, consists of enclosing irregular shapes, singly or in combination, in a minimum area enclosing rectangle called modules. The modules are then packed on to the given rectangular stock using dynamic programming algorithm. The effectiveness of the algorithm was shown by comparing the results with those obtained by using manual methods. Albano [28] therefore later proposed a system where a tentative solution is generated and then interactive improvements are allowed. Although these investigations have been successful in handing some subsets of two dimensional allocation problem, their approach, however has resulted in procedure that are marginally useful for applications with a small number of pieces where an exact ordering of the pieces is required.

   Albano and Sapupoo [29] have used heuristic search methods for two dimensional layouts of irregular shapes on rectangular stock sheet. The problem is reduced to the search of an optimal path in a graph and using a heuristic search method, an approximate solution which proves to be of a good quality and efficient in terms of computational time can be obtained. In their approach a proper choice of cost estimate functions h[n] in evaluation function f[n] = g[n] + h [n] is very important as it has direct bearing on the amount of time it takes for the solution. Here h[n] is an estimate of expected waste and it should always be lower than the waste that would result in the optimal solution if the piece in question were to be included in the algorithm will execute fairly efficiently most of the time otherwise more search is required and if h[n] is an overestimate then it may lose the optimal path. A proper choice of h[n] is however rather difficult to decide and therefore need for other method arises.

   Chung Jason et. al [30], Dagli [31] has applied the rule based methodology to arrive at an intelligent two dimensional nesting on an irregular resource. Dagli

   [31] applied a knowledge based system to assist optimal cutting of stocks. Cai Y et.al [32] developed an expert system for automated allocation of 2D irregular shapes. Han et. al [33] and Poshyaninda Pipatpong et.al
   [34] applied neural network for the solution of optimal stock cutting problems.

   Fujita Kikuo et. al [35] have applied genetic algorithm and local minimization techniques to arrive at optimal nesting solution.

   Xie et. al [36] have reported an intelligent computer- aided nesting (CAN) system for optimal nesting of two- dimensional parts, especially parts with complicated shapes, with the objective of effectively improving the utilization ratio of sheet materials. Efforts have been devoted to improving the nesting efficiency of the existing algorithms and developing new nesting algorithms.

   Herrmann and Delalio [37] have described models that estimate the cost and time of sheet metal punching when nesting (batching) orders. The models are use to evaluate the sensitivity of the nesting policy to manufacturing parameters. Dynamic Nesting can reduce the capacity requirements, material requirements, and costs of a given set of orders and nests.

   Dowsland et. al [38] have described a fast and efficient implementation of a bottom-left (BL) placement algorithm for polygon packing. The algorithm allows pieces to be nested within the partial layout produced by previously placed pieces, and produces an optimal BL layout in the sense that the positions considered are guaranteed to contain the bottom-left position of the infinite set of possibilities.

   Pradeep Kumar Tallogu [39] has describes the problem of nesting d-dimensional boxes using a criterion that defines nesting. Work includes an approach that reduces it into a Single-Source Shortest Paths problem and presents an algorithm. The performance of this algorithm is analyzed and the time complexity is calculated.

   Liu Hu-yao et. al [40] has proposed a new scheme is based on the NFP (No Fit Polygon) algorithm and a new placement principle for pieces. The novel placement principle is to place a piece to the position with lowest gravity centre based on NFP. A recursive algorithm and a GA are proposed to search for an effective nesting sequence. Based on these proposed algorithms, the new nesting scheme achieved competitive results in nesting pattern height, material utilization percentage and computation time. In addition, it works well for pieces with arbitrary rotation and containing region with holes.

   Nye T. J. [41] has presented an exact algorithm for orienting the part on the strip to maximize material

   utilization. The algorithm optimally nests convex or nonconvex blanks on a strip and predicts both the orientation and strip width that minimize material usage. Technological constraints, such as blank orientation constraints due to planar anisotropy, are also incorporated into the algorithm.

   Anand Uday et. al [42] has described a hybrid (or memetic) approach, which uses a parallel genetic algorithm and a heuristic based on shape information in the form of feature matching. The use of shape information and feature matching helped in finding feasible solutions very effectively. It made the search more efficient by doing local search within each evaluation of the GA. The computational intensity of this approach makes it inappropriate for real-time decision making on less costly nesting problems.

   BURKE et.al [43] have presented a new heuristic algorithm for the two-dimensional irregular stock cutting problem, which generates significantly better results than the previous state of the art on a wide range of established benchmark problems. The developed algorithm is able to pack shapes with a traditional line representation, and it can also pack shapes that incorporate circular arcs and holes.

   Dr. Bhatt A. D. [44] deals with nesting of two- dimensional objects (regular and irregular, convex and non- convex) on two dimensional rectangular stocks. Here, first ranked the objects according to a sequencing policy and then placed the sequenced objects using bottom left placement heuristic. Finally interactive nesting strategy is used to get closed and compact nesting on results obtained by automatic nesting. The proposed methodology has been implemented in the form of a menu driven program using MATLAB & GUI has been developed to interact user with different modules of the software as shown in fig. 1

   Benny K. Nielsen [45] has presented an efficient heuristic solution method which can construct very good solutions for strip nesting problems in which the solution is going to be repeated either horizontally or horizontally and vertically. Results are given for fairly large instances and they strongly indicate that this can give a considerable reduction of wastage for problem instances in the garment industry.

   Nye T. J. [46] has describes a new algorithm for optimizing the layout of an irregular convex polygonal blank in a strip. This algorithm orients a single blank such that the utilization of the strip material is maximized. It is efficient, running in (n2) time, and exact, producing orientation solutions which globally maximize material utilization. The utility of such an algorithm is that it may be incorporated into a computer-aided engineering (CAE) system for

   automated design and optimization of parts made from sheet materials.

   Nested Objects

   Sequencing

   Prasad Y.K.D.V. [47] has developed a set of nesting algorithms to find all the feasible arrangements in such a manner that arbitrary blanks do not overlap or intersect by considering the constraints of sheet metal stamping operation, such as bridge width and grain orientation and to satisfy the design requirements, such as maximizing the strength of the blank when bending is involved as a subsequent operation.

   User

   Graphical User Interface (GUI)

   Input

   Process

   Output

   .dat /.txt File

   Vertices Informatio		Inflation
   Edges Informatio

   AutoCAD Drawing

   .dxf file

   Object

   Stock Length and Width

   .dat /.txt File

   Back Filling

   Stock

   Graphical display

   Bottom Left Placement

   Figure 1. Block Diagram of Nesting Software

   Henry Lamousin and Warren N Waggenspack, Jr

   [48] have outlined a technique for the allocation or

   nesting of irregular parts into arbitrarily shaped resources. Placements are generated by matching complementary shapes between the unplaced parts and the remaining areas of the stock material. The part and resource profiles are characterized by varying levels of detail using geometric features at each stage of processing to intelligently select and place parts of the resource.

   R. Venkata Rao [49] has proposed procedure is based on an AHP method and it helps in selection of a suitable strip-layout from amongst a large number of available strip-layouts for a given metal stamping operation. The methodology is capable of taking into account important requirements of metal stampings and

   it strengthens the existing procedure by proposing a logical and rational method of strip-layout evaluation and selection.

   Hopper and Turton [50] have developed meta- heuristic algorithms to solve 2D packing problems. As packing tasks are combinatorial problems with very large search spaces, the recent literature encourages the use of meta-heuristic search methods, in particular genetic algorithms. Their objective was to present and categories the solution approaches in the literature for 2D regular and irregular strip packing problems. The focus was hereby on the analysis of the methods involving genetic algorithms.

3. Conclusion

   Since Nesting is a non-probabilistic hard problem, exact solution to given scenario is difficult. Researchers have developed different solution for regular and irregular shape nesting like rule based expert system, applied neural network for nesting with use of linear programming, recursive and dynamic programming techniques.

   Parts are placed with different positioning strategies. Nesting Algorithms and placement principles are based on the meta-heuristic techniques, positioning with lowest gravity centre based on No Fit Polygon, Genetic algorithm, simulated annealing, heuristic techniques, quick location and movement, polygon packing, compact neighbourhood, bottom-left (BL) placement etc.

   Considering the complexity of shape, density of parts and percentage of utilization, it is difficult to decide which method is better suited to approach 2- dimensional nesting problems. To-date only a few attempts have been made to compare different nesting algorithms.

4. References

1. Wen-Chen Lee, Heng Mab, Bor-Wen Cheng, A heuristic for nesting problems of irregular shapes, Computer-Aided Design, 40 (2008), 625633

2. Lutfiyya H, Mcmillan B, Poshyanon DAP, Dagli C. Composite stock cutting through simulated annealing.

   Mathematical Computer Modelling 1992; 16:57- 74

3. Bennell J A, Dowsland KA. A tabu thresholding implementation for the irregular stock cutting problem. International Journal of Production Research 1999; 37: 4259- 75.

4. Anand Uday et. al , Nesting of Irregular Shapes Using Feature Matching and Parallel Genetic Algorithms,

5. Wen-Chen Lee et. al, A heuristic for nesting problems of irregular shapes, Computer-Aided Design, 40 (2008), 625 633

6. M. Pan and Y. Rao, An integrated knowledge based system for sheet metal cuttingpunching combination processing, doi: 10.1016/ j.knosys. 2009.02.

7. S. Kumara and R. Singh, Automation of strip-layout design for sheet metal work on progressive die, Journal of materials processing technology, 195 (2008), 94100.

8. Yaodong Cui, Exact algorithm for generating two- segment cutting patterns of punched strips, Applied Mathematical Modelling, 31 (2007), 18651873.

9. Yaodong Cui and Yiping Lu, Heuristic algorithm for a cutting stock problem in the steel bridge construction, Computers & Operations Research, 36 (2009), 612 622.

10. S.K. Cheng and K.P. Rao, Large-scale nesting of irregular patterns using compact neighborhood algorithm, Journal of Materials Processing Technology, 103 (2000), 135

    -140.

11. Chow W W, Nesting of a single shape on a strip, International Journal of Production Research, Vol. 17, No. 4, 1979

12. A.Y.C. Nee, Computer aided nesting of similar Blanks SME Technical Paper MS83-925, Society of Manufacturing Engineers, Dearborn, Michigan 1983.

13. Gilmore P C and Gomery R. E, Multistage cutting stock problem of two or more dimensions, Operations Research, 13, 1965, 94-120.

14. Gilmore P C and Gomery R E, A Linear Programming approach to the cutting stock problem, Operations Research, Vol. 9, Nov-Dec 1961, 849-859.

15. Gilmore P C and Gomery R E, A Linear Programming approach to the cutting stock problem, Part I, Operations Research, 9, 1961, 849-859.

16. Gilmore P C and Gomery R E, A Linear Programming approach to the cutting stock problem, Part II, Operations Research, Vol. II No.6, Nov-Dec 1963, 863-888.

17. Gilmore P C and Gomery R E, The theory and computation of knapsack functions, Operations Research, 14, 1966, 1045-1074.

18. Gilmore P C Cutting stock linear programming: Some interactions, Annals of Discrete Mathematics, 4, 217-235, 1979.

19. Christofides and Whitlock, An Algorithm for Two Dimension Cutting Problems, Operation Research, Vol. 25, No. 1, Jan-Feb 1977, 30-44.

20. Adamowicz and Albano, A two stage solution of the cutting stock problem, Information Processing 71, North Holland, 1086 1091

21. Adamowicz and Albano, Nesting two Dimensional Shapes In rectangular Modules, Computer Aided Design,

    Vol. 8, No. 1, January 1976, 27- 33

22. Adamowicz and Albano, A Solution of the rectangular cutting Stock Problem, IEEE transactions on System Science and Cyber, Vol-SMC-6, No.4, April 1976, 302-310

23. Albono and Orsini, A Heuristic solution of the rectangular Cutting Stock Problems, The Computer Journal, Vol. 23, No.4, Nov. 1980, 338- 343.

24. Albono and Orsini, A Tree Search approach to the M- Partition and knapsack Problem The Computer Journal, Vol. 23, No.4, Nov. 1980, 256- 261.

25. Beasley J E, An exact two dimensional non guillotine cutting tree search procedure , Operations Research, 33, 1985, 49-44.

26. Beasley J E, Algorithms for unconstrained two dimensional guillotine cutting, Operations Research Society, 36, 1985c, 297-306.

27. Beasley J C, Bounds for two dimensional cutting, Journal of the Operations Research Society, 36, 1985b, 1051- 1056.

28. Albano A, A Method to Improve Two Dimensional Layout Computer Aided Design. Vol. 9, No. 1 January 1977, 48-52

29. Albano, A. and Sapuppo, G., 1980, Optimal allocation of two-dimensional irregular shapes using heuristic search methods. IEEE Transactions on Systems, Man and Cybernetics, SMC-10, 242-248

30. Chung Jason Hillman Donald J., Title Intelligent nesting system on two-dimensional highly irregular resources, International Society for optical Engineering, Bellingham, WA, USA, 1990, v 1293, p 472-483.

31. Dagli C H, Knowledge based systems for cutting stock problem, Journal of the Operations Research Society, 44, 1990, 160-166.

32. Cai Y et. al, An expert System for automatic allocation of 2D irregular shapes , Expert Systems in Computer- Aided-Design , 1987, p-407, North Holland.

33. Han et. al, Multi-stage solution for nesting in two- dimensional cutting problems using neural networks, Proceedings of the International Conference on Advanced Techniques andLow Cost Automation, Beijing, CHINA v34 Sept. 1994.p 409-410

34. Poshyanonda Pipatpong et. al, Artificial Neural networks in stock cutting problem, neural Networks in Manufacturing and Robotics American Society of Mechanical Engineers, v 57. Publ by ASME, NY, USA. p 143-153, 1992

35. Fujita Kikuo et. al, Hybrid approach for optimal nesting using a genetic algorithm and a local minimization algorithm,Proceeding of the 19th Annual ASME Design Automation Conference. Part 1 (of 2) DE v 65 pt, 1993, NY,

    USA. p 477-484

36. S.Q.XIE et. al, Nesting of two-dimensional irregular parts:an integrated approach, International Journal of Computer Integrated Manufacturing, Vol.20, No.8, December 2007, 741756.

37. Jeffrey W. Herrmann and David R. Delalio, Evaluating Sheet Metal Nesting Decisions, Institute for Systems Research, April27, 1998.

38. Kathryn A. Dowsland et. al, Analgorithm for polygon placement using a bottom-left strategy, European Journal of Operational Research 141 (2002) 371381.

39. Pradeep Kumar Tallogu, Nesting multiple d- dimensional boxes

40. LIU Hu-yao and H E Yuan-jun, Algorithm for 2D irregular-shaped nesting problem based on the NFP algorithm and lowest-gravity-center principle, Journal of Zhejiang University Science an ISSN 1009-3095, ISSN- 1862-1775.

41. T. J. Nye, Stamping Strip Layout for Optimal Raw Material Utilization, Journal of Manufacturing Systems Vol. 19/No. 4 2000

42. Anand Uday et. al , Nesting of Irregular Shapes Using Feature Matching and Parallel Genetic Algorithms,

43. E.K. Burke, Hellier R.S.R., Kendall G. and Whitwell G. A New Bottom-Left-Fill Heuristic Algorithm for the Two- Dimensional Irregular Packing Problem Volume 54, No. 3, pp 587-601, May-June 2006.

44. Dr. A. D. Bhatt, Development of flat pattern Nesting Software.

45. Benny K. Nielsen, An efficient solution method for relaxed variants of the nesting problem, Theory of computing – Volume 65,123-130, 2007.

.[46] T. J. Nye, Optimal Nesting of irregular convex blanks in strips via an exact algorithm, International Journal of machine Tools & Manufacture 41 (2001) 991-1002.

1. Y. K. D. V. Prasad, A set of heuristic algorithms for optimal Nesting of two-dimensional irregular shaped sheet metal blanks, computers in Industry 24, 55-70, 1994.

2. Henry Lamousin and Warren N. Waggenspack, Jr, Practice & Experience: Nesting of two-Dimensional irregular parts using a shape reasoning heuristic, PII: 50010-4485 (96) 00065-6

3. R. Venkata Rao, Evaluation of sheet metal stamping layouts using an analytic hierarchy process Method, Journal of Material processing technology, 152, 7176,2004

4. E. Hopper and B. C. H. Turton, A Review of the Application of Meta-Heuristic Algorithms to 2D Strip Packing Problems, Artificial Intelligence Review, vol. 16, 257 300, 2001.