Large-scale nesting of irregular patterns using compact neighborhood algorithm.pdf
【机械类毕业论文中英文对照文献翻译】运用紧凑相邻法则对非规则零件图样进行大规模编排
收藏
资源目录
压缩包内文档预览：
编号：77693838
类型：共享资源
大小：1.90MB
格式：RAR
上传时间：2020-05-07
上传人：柒哥
认证信息
个人认证
杨**（实名认证）
湖南
IP属地：湖南
6
积分
- 关 键 词：
-
机械类毕业论文中英文对照文献翻译
机械类
毕业论文
中英文
对照
文献
翻译
运用
紧凑
相邻
法则
规则
零件
图样
进行
大规模
编排
- 资源描述：
-
【机械类毕业论文中英文对照文献翻译】运用紧凑相邻法则对非规则零件图样进行大规模编排,机械类毕业论文中英文对照文献翻译,机械类,毕业论文,中英文,对照,文献,翻译,运用,紧凑,相邻,法则,规则,零件,图样,进行,大规模,编排
- 内容简介：
-
Large-scale nesting of irregular patterns usingcompact neighborhood algorithmS.K. Cheng, K.P. Rao*Department of Manufacturing Engineering and Engineering Management, City University of Hong Kong,Tat Chee Avenue, Kowloon, Hong KongAbstractThe typical nesting technique that 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 layout and, geometrically, itbecomes inefficient when several pattern entities are involved. Also, it is not highly suitable for handling patterns with a range of orientationconstraints. 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 Science S.A. Allrights reserved.Keywords: Cutting stock problem; Nesting; Compact neighborhood algorithm; Genetic algorithm; Orientation constraints1. IntroductionThe cutting stock problem isofinterestto manyindustrieslike 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, Adamowicz 1attempted 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 fitwell together before nesting 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 given stock. For small-scale nesting, we only need tofind the inter-orientation relationship between the selectedcluster and the given stock 4. However, the problembecomes more complicated for large-scale nesting sincethe 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 orthogonal nesting.A typical pattern, shown in Fig. 1a, with both concave andconvex features, is selected to explain these techniques. Thepattern 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 approximationsuggested by Dori and Ben-Bassat 5, the pattern is first 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. 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 efficient 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 consideration of other permissible range of orienta-tions.In the second technique, used by Nee 9, the nestingprocessisachievedbyapproximatingasinglepattern/clusterby a rectangle as shown in Fig. 1d. This rectangle 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 within a certain range whilefitting it on the stock. Like the hexagonal approximation, themain disadvantage of this approach is that the algorithmsperformance is highly dependent on the shape of patterns.Moreover, in the case of multiple orientation constraints, theJournal of Materials Processing Technology 103 (2000) 135140*Corresponding author. Tel.: ?852-2788-8409; fax: ?852-2788-8423.E-mail address: .hk (K.P. Rao)0924-0136/00/$ see front matter # 2000 Elsevier Science S.A. All rights reserved.PII: S0924-0136(00)00402-7time taken to estimate a suitable rotation angle for thepatterns is always much longer.In order to increase the accuracy and speed of nesting,Cheng and Rao 4 proposed a compact neighborhoodalgorithm (CNA) that considers the relationship betweenthe number of neighbors and the sharing space betweenthem. Fig. 1g shows a typical layout generated using CNAwhich 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 with the consideration of fullorientation constraints, and is not ideal for situations wheremore freedom is available in the orientation of patterns.This studyisaimed atimprovingthe flexibilityofCNAbyincorporating the available freedom in the orientation ofpatterns and a genetic algorithm (GA) that follows naturalrules to optimize the generated layouts. The new techniqueis translated into a computer program written in C?object-oriented language. The new algorithm can handlethe problem of nesting two-dimensional flat patterns of anyshape containing line segments and arcs. With the help of atypical example, the enhanced capabilities of CNA and theassociated computer program will be demonstrated in thispaper.2. Description of compact neighborhood algorithm(CNA)A CNA 4 tracks the characteristics of the evolvingneighborhoods when the patterns are moved to formdifferent arrangements, as summarized schematically inFig. 2ac. As the shear displacement increases, the upperand lower neighbors tend to collapse due to the change incrystallization directions. Finally, a most compact structureand a numerical value for material yield, called universalcompact utilization (UCU), can be obtained. No matterFig. 1. (a) The chosen flat pattern for demonstrating the working principle of CNA algorithm; (b) pattern contour obtained by digitizer; (c) hexagonalapproximation; (d) orthogonal approximation; (e) layout generated by using hexagonal approximation yielding a stock utilization of 60.05%; (f) layoutgenerated by using orthogonal approximation yielding a stock utilization of 67.14%; and (g) layout generated by using CNA yielding a stock utilization of74.10%.Fig. 2. Typical neighborhood structures for circular patterns (a) formation of orthogonal packing unit cell with Nn?8 and Au?16r2; (b) shearing of layersleading to sheared orthogonal packing; and (c) best compact structure with hexagonal packing unit cell with Nn?6 and Au? 6?3pr2, where Auis the area of aunit cell, r the radius of circular pattern and Nnis the number of neighbors to construct the unit cell.136S.K. Cheng, K.P. Rao/Journal of Materials Processing Technology 103 (2000) 135140whether 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 stoppingcriteria in the nesting process.The main steps involved in finding the compact neighbor-hood are: (1) generating a self-sliding path or a no-fit-polygon (NFP) 1, as shown in Fig. 3a, which guides therelative movement between two patterns with the considera-tion of no overlapping; and (2) defining the crystallizationdirections,asshowninFig.3b,thatprovideessentialdataforbuilding the whole neighborhood by filling the given stockduring 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 inthis section. A flat pattern can be divided into entities of linesegments and arcs. Polygonal representation methods 2canbeusedtorepresentbothconcaveandconvexarcsassetsof straight lines. The actual number of lines is dependent onthe required accuracy level. Also, clearance or offset gen-eration is an essential step that contributes towards thesuccess of CAD/CAM technology. An algorithm to generatethe required offset, called three point island tracing(TPIT) technique 2, is incorporated in the present nestingsystem.3.1. CNA for large-scale nestingIn the previous section, we have already mentioned thebasic steps involved 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 first pattern andexpand this structure to fill the entire stock. For nesting ofpatterns with full orientation constraint, it is only necessaryto decide a nesting vector CDn that defines where theneighborhood should be translated around the given stock.However,inthe case ofnesting ofpatternswith limitedor noorientation limitations, the problem becomes more compli-cated due toan increase inthe possible combinations thatweneed to consider.In this case,the first step which is globalwith or without orientation limitations is to translate theneighborhood to an arbitrary position inside the given stock,i.e.definingavectorCDn.Afterward,anestingangleynisto be determined so that a good orientation isselected fortheneighborhood to grow. All the required geometrical opera-tions are summarized in Fig. 4.It is critical to optimize CDnand ynwhich can finally leadto a most compact neighborhood structure. It is believed thatthere are no unique mathematical steps to calculate theseparameters for any type of stock. In addition, we cannotaccept an exhaustive search because of the constraints posedon computation time, especially in the case of nesting ofpatterns with too long a computation time, especially whilenesting 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 inthe following section.3.2. GA for optimizing layoutsGA 8 maintains a population of candidate problemsolutions. Based on their performance, the fittest of thesesolutions not only survive, and, analogous to sexual repro-duction, exchangeinformationwith othercandidatestoforma new generation. Before starting any genetic operation, oneneeds to define the fitness function and the coding method.As mentioned earlier, the goal in nesting of patterns is toreduce the scrap by fitting the clusters together so that theyoccupy a minimum area. To represent the compactness of aparticular layout, one can be confident that the most directway is to relate it with the stock yieldf?x;y? ? p ?yx(1)where x is the area of the given stock and y the total area ofthe patterns that could be cut out from the given stock.Coding can directly and indirectly influence the optimi-zation process. This is because our main concern is how tofix the translation position (i.e. nesting vector CDn) and thedegree 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 inthe genetic operators of cross-over and mutation.3.3. The genetic operatorsAs proposed by Holland et al. 8, the GA aims atoptimizing the solution by mimicking natures evolutionaryFig. 3. (a) Steps involved in the generation of self-sliding path to create aneighborhood; and (b) optimal neighborhood structure with hexagonalpacking unit cell with a UCU of 83.07%.S.K. Cheng, K.P. Rao/Journal of Materials Processing Technology 103 (2000) 135140137process. Like human beings a typical GA contains thefollowing genetic operators.3.3.1. InitializationAt the beginning, a population of i genetic solutions (i.e.layouts) are generated by randomly selecting values for allthe parameters (i.e. nesting angle ynand nesting vectorCDn). In real industrial applications, there are usuallysituations that limit the rotation of patterns freely. Forexample, in the design of progressive dies, there are manyrestricted orientation regions as a result of the cost of settingcorresponding pilots, limitations of bending angle for sub-sequent sheet metal operations, and the like. Fig. 5 showstwo typical patterns with different restricted andunrestrictedorientation regions. As a result, the positions that thesepatterns could assume are limited to two limited rangesin the present cases, as shown in the same figure. Hence,after the random generation of a nesting angle yn, thefollowing inequality check has to be satisfied:ypj;kl? yn? ypj;kuwith j; k 2 I; 1 ? j ? Nand1 ? k ? Cpj(2)where N and Cpjare the number of patterns to be nested (i.e.p1, p2,., pN) and the number of restricted orientationregions of pattern pj, respectively.Fig. 4. Translation of the neighborhood to a pre-defined position with nesting vector CDnand subsequent rotation involving a nesting angle yn.Fig. 5. Rotation constraints with respect to the lower bound of the first unrestricted region (a) stationary pattern (p1): yp1,1l?08, yp1,1u?308, yp1,2l?1708,yp1,2u?1908; and (b) movable pattern (p2): yp2,1l?08, yp2,1u?608, yp2,2l?2008, yp2,2u?2308.138S.K. Cheng, K.P. Rao/Journal of Materials Processing Technology 103 (2000) 1351403.3.2. Fitness calculationBy following the fitness function, each generated layout(i) is assigned with a fitness value (pi) that decides the layoutcompactness.Thisvalueisusedinthesubsequentoperationsfor determining the candidate that should be selected in thestep of reproduction.3.3.3. ReproductionAccording to the assigned fitness values p, every indivi-dual has a specific chance to be selected for reproduction inthe subsequent weighted random selection process. It isimportant that better individuals, i.e. higher values of p,have better chance of being selected than less suitableindividuals.3.3.4. Cross-overThisisthemostimportantstepthatdeterminesmembersinthenextgeneration.Thereproducedindividuals,say layouts i and j, are crossed by using the cross-over-operator, which is referred to taking average of their nestingangles ynor vectors CDn. Each new value of ynis subjectto the inequality condition (Eq. (2) to check the availability.3.3.5. MutationIn fact, there are many approaches for implementing thisoperator. In the current system, it is basically achievedthrough an algorithm that rotates the neighborhood ran-domly by 158 with a probability of 1?0.5(pi?pj).3.4. Large-scale nesting with multiple patternsFor the cutting stock problem with multiple patterns,the algorithm mentioned above is still valid. To decreasethe huge search space, a clustering process is first operatedto collect the patterns. For example, the eight patternsshown in Fig. 6a are collected together to form a clustershown in Fig. 6b by using the stringy sliding technique3. After clustering, a grouping process is operated toremove all internal boundaries so that a much faster com-putation speed can be achieved during the subsequent steps.By repeating the same techniques mentioned above, themost compact neighborhood structure, shown in Fig. 6c, canbe finally obtained, which is now suitable for large-scalenesting.Fig. 6. Proposed strategy for solving the cutting stock problem with multiple patterns (a) patterns to be clustered and nested; (b) cluster generated by usingsliding technique; and (c) an hexagonal packing unit cell generated by CNA.Fig. 7. (a) The layout generated by orthogonal approximation with a stock utilization of 72.8%; (b) the best layout among the initial population using CNAwith a stock utilization of 73.9%; and (c) the best layout obtained after five generations using CNA with a stock utilization of 74.3%.S.K. Cheng, K.P. Rao/Journal of Materials Processing Technology 103 (2000) 1351401394. Case studyTotest the efficiency of the proposed techniques for use inlarge-scale nesting, the results obtained are compared withthose obtainable with the traditional nesting technique, i.e.orthogonal approximation, used by Nee 9 in terms of stockutilization (% SU). A stock size of 200?200 units is usedhere. Supposing that we do not have any orientation limita-tions imposed on patterns while nesting, a typical layoutgenerated by using orthogonal approximation and two otherlayouts obtained by the proposed technique are shown inFig. 7ac, respectively. As illustrated, the proposed techni-que can give a better solution than the traditional one evenwith the initial population. Besides, it has been found thatthe solution can quickly reach the most optimal stage withinan acceptable number of generations. This has been parti-cularly true in those cases when the size of stock is largewhen compared with that of patterns. The use of the GA tooptimize the values of nesting vector CDnand nesting angleynbecomes more important as the size of stock decreases.5. ConclusionsAn attempt has been made to improve the effectiveness ofthe clustering and nesting processes, with a rigorous con-sideration of orientation constraints of the patterns. A CNA,which was recently proposed for generating stock layoutswhen there are full orientation constraints, i.e. the nestedpatterns could not be rotated at all, is further developed tosolve the problem of multiple orientation constraints. CNA,with its concept of UCU, guides the user to attain nearoptimum layouts. By using CNA in conjunction with a GA,the best solution can be mathematically obtained, and thetechnique is highly suitable f
- 温馨提示:
1: 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
2: 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
3.本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
人人文库网所有资源均是用户自行上传分享，仅供网友学习交流，未经上传用户书面授权，请勿作他用。
|
2:不支持迅雷下载,请使用浏览器下载
3:不支持QQ浏览器下载,请用其他浏览器
4:下载后的文档和图纸-无水印
5:文档经过压缩，下载后原文更清晰
|
川公网安备: 51019002004831号