【作者】 李兵；

【导师】 郑午；

【作者基本信息】 吉林大学 ， 工业工程， 2012， 硕士

【摘要】 二维不规则零件排样问题，是NP类问题中非常重要的一类，这类问题很难进行求解。然而，由于该问题理论意义和实际意义的重要性，使得该问题成为了最优化问题中一个极其重要的分支。到目前为止，对于这类问题的求解主要基于两种思路：一种是对这类零件直接在原材料上进行排放；另一种则是将不规则零件转化为规则矩形件，然后按照矩形件进行排样优化。本文采用第二种方法，所做的具体工作如下：由于本文的主要研究对象是二维不规则零件，因此，首先要将二维不规则零件转化为规则零件（即矩形零件）。本文在采用矩形包络法的基础上，提出了另外两种将其规则化的方法：“三角组矩法”和“梯形组矩法”。“三角组矩法”的主要思想是将两个或多个相同的三角形零件组合成平行四边形，然后再进一步转化为矩形；而“梯形组矩法”的研究对象则比较宽泛，四边形、五边形及多边形都可以；这种方法是先将这些不规则零件转化为包络这些不规则零件的最小梯形，然后将两个或多个相同的梯形进行平行排列，最终同样转化为矩形进行排列。这样使得所有的零件都可以按照矩形的排样方式进行排放，极大的缩短了排放的时间，提高了排样的效率。在将不规则零件规则化后，本文对矩形件进行排样的各种排样算法进行了分析和研究，这些算法主要包括：BL算法、基于最低水平线的搜索算法和剩余矩形匹配算法等；对这些算法进行综合比较后，本文选择了剩余矩形匹配算法来对规则化后的矩形件进行排样。由于以上各种排样算法都是定序列的排样算法，很难直接得到最优或满意的排样效果图；因此该算法必须和某种具备全局搜索能力的算法结合起来使用，才能达到我们想要得到的结果。遗传算法以达尔文的生物进化论为基础而创建，通过选择、交叉和变异等操作来逼近最优解。本文采用轮盘赌策略来进行选择，通过双点交叉算子来进行交叉操作，并应用交换变异、旋转变异和位置变异三种变异算子来进行变异操作，最后得到问题的最优解或满意解，并通过例子来验证可行性。更多还原

【Abstract】 The packing problem of two-dimensional irregular shapes belongs to one of the NP-hardproblems. It is very important and difficult to solve. It has great complexity of computation.For this problem, it hardly can be solved. But, because of the great theoretical and practicalsignificance for the problem, it has become an extremely important branch in the optimizationproblem. So far, the solving methods for the problem has two ways: the first is directlyirregular parts nesting processing in the material, the second is turning the irregular parts intoregular parts (rectangular parts), and then nesting. The paper uses the second method, themain work in the paper is as follows:The main research object in the paper is two-dimensional irregular parts, so we have tochange the irregular parts to regular parts. Based on using the rectangular envelope method,we put forward another two methods: Tri-rectangle method and trap-rectangle method.Tri-rectangle method’s main idea is making two or several same triangle parts turn toparallelogram, and then turning the parallelogram into rectangle; In comparison, the researchobject for the trap-rectangle method is relatively broad, it can be quadrilateral, pentagon,polygon and so on. For this method, first, turn the irregular parts to the smallest trapezoidal,and then turn the two or several same trapezoidal to rectangle. As above, this will make all theirregular parts can be carried out in accordance with the rectangle parts, it will reduce the timefor packing, improving the efficiency.After the regularization of irregular parts, the paper does research on the nestingalgorithms. These algorithms mainly include: BL algorithm, searching algorithm based on theminimum horizon and remaining rectangle matching algorithms. After comparing to thesealgorithms, we select the remaining rectangle matching algorithm to pack the regular partsafter regularization.The nesting algorithms above are algorithms given the sequence of the parts. It isdifficult to directly get the optimal or satisfactory renderings; so we must combine thealgorithm and the algorithm that has the global search ability, only this, can we get the result we want. The genetic algorithm is created based on the Darwin’s biological evolution theory.In this paper, it uses the roulette strategy for selection and chooses the cross-operating throughthe two-point crossover operator. In addition, it use exchange variation, rotation variation andposition variation. After that, we can get the optimal solution or near-optimal solution for theproblem and through the example we can verify its feasibility.更多还原