1、PDF外文：http:/ 中文 4740 字 出处 : Journal of Materials Processing Technology, 2000, 103(1): 135-140 Large-scale nesting of irregular patterns using compact neighborhood algorithm S.K. Cheng, K.P. Rao* The typical nesting technique that is widely used is the geometrical tilting of a single patt
2、ern or selected cluster step by step from the original position to an orientation of 1808, i.e. orthogonal packing. However, this is a blind search of best stock layout and, geometrically, it becomes inefcient when several pattern entities are involved. Also, it is not highly suitable for handling p
3、atterns with a range of orientation constraints. In this paper, an algorithm is proposed which combines the compact neighborhood algorithm (CNA) with the genetic algorithm (GA) to optimize large-scale nesting processes with the consideration of multiple orientation constraints. # 2000 Elsevier Scien
4、ce S.A. All rights reserved. Keywords: Cutting stock problem； Nesting； Compact neighborhood algorithm； Genetic algorithm； Orientation constraints 1. Introduction The cutting stock problem is of interest to many industries like garment, paper, ship building, and sheet metal indus- tries.
5、 Gilmore and Gomory 7 have initiated the research work to solve the rectangular cutting stock problem by using linear programming. For the irregular case, Adamowicz 1 attempted to use a heuristic approach which divides the problem into two sub-problems, called clustering and nest- ing. Clustering is
6、 to specify a collection of patterns that t well together before nesting onto a given stock. Nesting of patterns or clusters can be broadly divided into two broad categories, namely, small-scale and large-scale. The differ- ence between them is the level of duplication of the cluster on the given st
7、ock. For small-scale nesting, we only need to nd the inter-orientation relationship between the selected cluster and the given stock 4. However, the problem becomes more complicated for large-scale nesting since the inter-space relationship between the duplicated clusters should also be considered.
8、Traditionally, two basic techni- ques are popularly used for generating this type of nesting: hexagonal approximation'' and orthogonal nesting''. A typical pattern, shown in Fig. 1a, with both concave and convex features, is selected to explain these techniques. The * Corresponding a
9、uthor. Tel.: 852-2788-8409； fax: 852-2788-8423. E-mail address: mekpraocityu.edu.hk (K.P. Rao) pattern contour is plotted with the help of a digitizer, as shown in Fig. 1b, and has an area (Ap) of 74.44 sq. units. In the hexagonal approximation'' suggested by Dori and Ben- Bassat 5, t
10、he pattern is rst approximated using a convex polygon which is further approximated by another convex polygon with fewer number of entities until an hexagonal enclosure is obtained, as shown in Fig. 1c. The hexagon is then paved on a given stock with no overlapping of the former 6. The resultant lay
11、out generated by use of this technique is given in Fig. 1e. It is readily evident that the technique is not highly efcient due to the poor approx- imation performance, especially in the case of highly irre- gular patterns. Another problem is that the pattern or cluster can assume two positions only
12、(0 or 1808), with no exploita- tion or consideration of other permissible range of orienta- tions. In the second technique, used by Nee 9, the nesting process is achieved by approximating a single pattern/cluster by a rectangle as shown in Fig. 1d. This rectangle is then duplicated in an orthogonal
13、way, resulting in the layout shown in Fig. 1f. This technique can be easily applied when there are no- or partial-orientation constraints, i.e. the single pattern or cluster can rotate within a certain range while tting it on the stock. Like the hexagonal approximation, the main disadvantage of this
14、 approach is that the algorithm's performance is highly dependent on the shape of patterns. Moreover, in the case of multiple orientation constraints, the 0924-0136/00/$ see front matter # 2000 Elsevier Science S.A. All rights reserved. PII: S 0 9 2 4 - 0 1 3 6 ( 0 0 ) 0 0 4 0 2 - 7
15、;136 S.K. Cheng, K.P. Rao / Journal of Materials Processing Technology 103 (2000) 135140 Fig. 1. (a) The chosen at pattern for demonstrating the working principle of CNA algorithm； (b) pattern contour obtained by digi
16、tizer； (c) hexagonal approximation； (d) orthogonal approximation； (e) layout generated by using hexagonal approximation yielding a stock utilization of 60.05%； (f) layout generated by using orthogonal approximation yielding a stock utilization of 67.14%； and (g) layout generated by using CNA yieldin
17、g a stock utilization of 74.10%. time taken to estimate a suitable rotation angle for the patterns is always much longer. In order to increase the accuracy and speed of nesting, Cheng and Rao 4 proposed a compact neighborhood algorithm (CNA) that considers the relationship between the number o
18、f neighbors and the sharing space between them. Fig. 1g shows a typical layout generated using CNA which normally yields higher packing density when com- pared with the orthogonal and hexagonal approximations. However, CNA, in its present form, has been mainly desig- nated for nesting of patterns wi
19、th the consideration of full orientation constraints, and is not ideal for situations where more freedom is available in the orientation of patterns. This study is aimed at improving the exibility of CNA by incorporating the available freedom in the orientation of patterns and a genetic algorithm (G
20、A) that follows natural rules to optimize the generated layouts. The new technique is translated into a computer program written in C object-oriented language. The new algorithm can handle the problem of nesting two-dimensional at patterns of any shape containing line segments and arcs. With t
21、he help of a typical example, the enhanced capabilities of CNA and the associated computer program will be demonstrated in this paper. 2. Description of compact neighborhood algorithm (CNA) A CNA 4 tracks the characteristics of the evolving neighborhoods when the patterns are moved to form dif
22、ferent arrangements, as summarized schematically in Fig. 2ac. As the shear displacement increases, the upper and lower neighbors tend to collapse due to the change in crystallization directions. Finally, a most compact structure and a numerical value for material yield, called universal compact util
23、ization (UCU)'', can be obtained. No matter Fig. 2. Typical neighborhood structures for circular patterns (a) formation of orthogonal packing unit cell with Nn 8 and Apu 16r2； (b) shearing of layers leading to sheared orthogonal packing； and (
24、c) best compact structure with hexagonal packing unit cell with Nn 6 and Au 6 3r2, where Au is the area of a unit cell, r the radius of circular pattern and Nn is the number of neighbors to construct the unit cell. S.K. Cheng, K.P. Rao / Journal of Materials Processing Technology 103 (2
25、000) 135140 137 Fig. 3. (a) Steps involved in the generation of self-sliding path to create a neighborhood； and (b) optimal neighborhood structure with hexagonal packing unit cell with a UCU of 83.07%. whe
26、ther the pattern can be rotated or not, UCU indicates the upper limit of yield that may be possible with any chosen stock and hence can be regarded as an index for stopping criteria in the nesting process. The main steps involved in nding the compact neighbor- hood are: (1) generating a self-sliding
27、 path'' or a no-t- polygon (NFP) 1, as shown in Fig. 3a, which guides the relative movement between two patterns with the considera- tion of no overlapping； and (2) dening the crystallization directions, as shown in Fig. 3b, that provide essential data for building the whole neighborhood by
28、lling the given stock during large-scale nesting. 3. Proposed algorithm for large-scale nesting The proposed techniques of enhancing the capabilities of CNA by taking advantage of a genetic algorithm are dealt in this section. A at pattern can be divided into entities of line segments and arcs
29、. Polygonal representation methods 2 expand this structure to ll the entire stock. For nesting of patterns with full orientation constraint, it is only necessary to decide a nesting vector CDn'' that denes where the neighborhood should be translated around the given stock. However, in
30、the case of nesting of patterns with limited or no orientation limitations, the problem becomes more compli- cated due to an increase in the possible combinations that we need to consider. In this case, the rst step which is global with or without orientation limitations is to translate the neighbor
31、hood to an arbitrary position inside the given stock, i.e. dening a vector CDn. Afterward, a nesting angle yn'' is to be determined so that a good orientation is selected for the neighborhood to grow. All the required geometrical opera- tions are summarized in Fig. 4. It is critical to optim
32、ize CDn and ynwhich can nally lead to a most compact neighborhood structure. It is believed that there are no unique mathematical steps to calculate these parameters for any type of stock. In addition, we cannot accept an exhaustive search because of the constraints posed on computation time, especi
33、ally in the case of nesting of patterns with too long a computation time, especially while nesting patterns with many entities and concave features. Hence, in this study, a recent popular optimization techni- que, called GA, is applied. The main principle is provided in the following section. 3.2. G
34、A for optimizing layouts GA 8 maintains a population of candidate problem solutions. Based on their performance, the ttest of these solutions not only survive, and, analogous to sexual repro- duction, exchange information with other candidates to form a new generation. Before starting any genetic op
35、eration, one needs to dene the tness function and the coding method. As mentioned earlier, the goal in nesting of patterns is to reduce the scrap by tting the clusters together so that they occupy a minimum area. To represent the compactness of a particular layout, one can be condent that the most d
36、irect way is to relate it with the stock yield f xY y py(1) can be used to represent both concave and convex arcs as sets of straight lines. The actual number of lines is dependent on the required accuracy level. Also, clearance or offset gen- eration is an essential step that contributes towards th
37、e success of CAD/CAM technology. An algorithm to generate the required offset, called three point island tracing (TPIT)'' technique 2, is incorporated in the present nesting system. 3.1. CNA for large-scale nesting In the previous section, we have already mentioned the basic steps invo
38、lved in obtaining the best compact neighbor- hood, as shown in Fig. 3b. Our next concern is the determi- nation of the best position to place the rst pattern and x where x is the area of the given stock and y the total area of the patterns that could be cut out from the given stock. Coding can direc
39、tly and indirectly inuence the optimi- zation process. This is because our main concern is how to x the translation position (i.e. nesting vector CDn) and the degree of rotation (i.e. nesting angle yn). They are thus selected as the coding parameters that guide the properties (i.e. corresponding to natural chromosomes) for exchange in the genetic operators of cross-over and mutation. 3.3. The genetic operators As proposed by Holland et al. 8, the GA aims at optimizing the solution by mimicking nature's evolutionary
