外文翻譯--運用緊湊相鄰法則對非規(guī)則零件圖樣進行大規(guī)模編排

1、中文 中文 4740 字出處 出處: Journal of Materials Processing Technology, 2000, 103(1): 135-140Large-scale nesting of irregular patterns using compact neighborhood algorithmS .K. Cheng, K.P. Rao *The typical nesting technique that

2、is widely used is the geometrical tilting of a single pattern or selected cluster step by step from theoriginal position to an orientation of 1808, i.e. orthogonal packing. However, this is a blind search of best stock l

3、ayout and, geometrically, it becomes inef®cient when several pattern entities are involved. Also, it is not highly suitable for handling patterns with a range of orientation constraints. In this paper, an algorithm

4、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 Sc

5、ience S.A. All rights reserved.Keywords: Cutting stock problem; Nesting; Compact neighborhood algorithm; Genetic algorithm; Orientation constraints1. IntroductionThe cutting stock problem is of interest to many industrie

6、slike garment, paper, ship building, and sheet metal indus-tries. Gilmore and Gomory [7] have initiated the researchwork to solve the rectangular cutting stock problem by usinglinear programming. For the irregular case,

7、Adamowicz [1]attempted to use a heuristic approach which divides theproblem into two sub-problems, called clustering and nest-ing. Clustering is to specify a collection of patterns that ®twell together before nestin

8、g onto a given stock. Nesting ofpatterns or clusters can be broadly divided into two broadcategories, namely, small-scale and large-scale. The differ-ence between them is the level of duplication of the clusteron the giv

9、en stock. For small-scale nesting, we only need to®nd the inter-orientation relationship between the selectedcluster and the given stock [4]. However, the problembecomes more complicated for large-scale nesting sinc

10、ethe inter-space relationship between the duplicated clustersshould also be considered. Traditionally, two basic techni-ques are popularly used for generating this type of nesting:``hexagonal approximation'' and

11、``orthogonal nesting''.A typical pattern, shown in Fig. 1a, with both concave andconvex features, is selected to explain these techniques. The* Corresponding author. Tel.: 852-2788-8409; fax:852-2788-8423.E-mail

12、address: mekprao@cityu.edu.hk (K.P. Rao)pattern contour is plotted with the help of a digitizer, asshown in Fig. 1b, and has an area (Ap) of 74.44 sq. units. Inthe ``hexagonal approximation'' suggested by Dori an

13、d Ben-Bassat [5], the pattern is ®rst approximated using a convexpolygon which is further approximated by another convexpolygon with fewer number of entities until an hexagonalenclosure is obtained, as shown in Fig.

14、 1c. The hexagon isthen paved on a given stock with no overlapping of theformer [6]. The resultant layout generated by use ofthis technique is given in Fig. 1e. It is readily evident thatthe technique is not highly ef

15、74;cient due to the poor approx-imation performance, especially in the case of highly irre-gular patterns. Another problem is that the pattern or clustercan assume two positions only (0 or 1808), with no exploita-tion or

16、 consideration of other permissible range of orienta-tions.In the second technique, used by Nee [9], the nestingprocess is achieved by approximating a single pattern/clusterby a rectangle as shown in Fig. 1d. This rectan

17、gle is thenduplicated in an orthogonal way, resulting in the layoutshown in Fig. 1f. This technique can be easily applied whenthere are no- or partial-orientation constraints, i.e. the singlepattern or cluster can rotate

18、 within a certain range while®tting it on the stock. Like the hexagonal approximation, themain disadvantage of this approach is that the algorithm'sperformance is highly dependent on the shape of patterns.Moreov

19、er, in the case of multiple orientation constraints, the0924-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 - 7S.K. Cheng, K.P. Rao / Journal

20、 of Materials Processing Technology 103 (2000) 135±140 137Fig. 3. (a) Steps involved in the generation of self-sliding path to create aneighborhood; and (b) optimal neighborhood structure with hexagonalpacking unit

21、cell with a UCU of 83.07%.whether the pattern can be rotated or not, UCU indicates theupper limit of yield that may be possible with any chosenstock and hence can be regarded as an index for stopping criteria in the nest

22、ing process.The main steps involved in ®nding the compact neighbor-hood are: (1) generating a ``self-sliding path'' or a no-®t-polygon (NFP) [1], as shown in Fig. 3a, which guides therelative movement b

23、etween two patterns with the considera- tion of no overlapping; and (2) de®ning the crystallizationdirections, as shown in Fig. 3b, that provide essential data for building the whole neighborhood by ®lling the

24、given stock during large-scale nesting.3. Proposed algorithm for large-scale nestingThe proposed techniques of enhancing the capabilities ofCNA by taking advantage of a genetic algorithm are dealt in this section. A 

25、5;at pattern can be divided into entities of linesegments and arcs. Polygonal representation methods [2]expand this structure to ®ll the entire stock. For nesting of patterns with full orientation constraint, it is

26、only necessaryto decide a ``nesting vector CDn'' that de®nes where theneighborhood should be translated around the given stock.However, in the case of nesting of patterns with limited or no orientation limit

27、ations, 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 

28、08; is to translate theneighborhood to an arbitrary position inside the given stock,i.e. de®ning a vector CDn. Afterward, a ``nesting angle yn'' is to be determined so that a good orientation is selected for

29、 the neighborhood to grow. All the required geometrical opera- tions are summarized in Fig. 4.It is critical to optimize CDn and ynwhich can ®nally leadto a most compact neighborhood structure. It is believed that t

30、here 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, especially in the case o

31、f 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. T

32、he main principle is provided in the following section. 3.2. GA for optimizing layoutsGA [8] maintains a population of candidate problemsolutions. Based on their performance, the ®ttest of these solutions not only s

33、urvive, and, analogous to sexual repro- duction, exchange information with other candidates to form a new generation. Before starting any genetic operation, one needs to de®ne the ®tness function and the coding

34、 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

35、be con®dent that the most direct way is to relate it with the stock yieldf 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 onthe req

36、uired accuracy level. Also, clearance or offset gen-eration is an essential step that contributes towards the success of CAD/CAM technology. An algorithm to generate the required offset, called ``three point island traci

37、ng(TPIT)'' technique [2], is incorporated in the present nesting system.3.1. CNA for large-scale nestingIn the previous section, we have already mentioned thebasic steps involved in obtaining the best compact nei

38、ghbor- hood, as shown in Fig. 3b. Our next concern is the determi- nation of the best position to place the ®rst pattern andxwhere x is the area of the given stock and y the total area of the patterns that could be

39、cut out from the given stock.Coding can directly and indirectly in¯uence the optimi-zation process. This is because our main concern is how to®x the translation position (i.e. nesting vector CDn) and thedegree

40、of rotation (i.e. nesting angle yn). They are thusselected 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