一种解决二维不规则零件下料问题的新的启发式算法
摘要
本文主要针对二维切割下料问题，研究对不同尺寸样料的排样可行方法。本文基于树的新的启发式算法来讨论这个问题。这种算法由两部分组成：第一部分是切割下料问题，其中有对板料无缺陷的初始解;第二部分是考虑了第一部分所述缺陷后的优化解决方案。本文还评估了算法的性能。实验结果表明，该算法能够解决二维缺陷的有效性下料问题，并表明，该算法不仅可以提高板料的利用率，而且还避免余料破碎。
关键词：排样优化;切割和包装;缺陷;启发式算法
1绪论
给定一组矩形的零件和几个相同的长方形板料，二维下料问题（2DCSP）需要通过使用最小数目的板料，等价地，或者是通过切割最少的板料。如果板料是不相同的，那它就是二维下料问题中的不规则排样问题（MS2DSP）。然而，在翻卷过程中，板料会存在一些缺陷，如缝隙，节孔，收缩等。因此，2DCSP和MS2DCSP往往不适合于实际应用。本文考虑多种板料的大小的二维切割问题（MS2DDSGCSP），也就是说：（1）只有铡切是允许的。即从一个矩形两对相对的边缘中的一个边缘到对面的边缘的切割，平行于另外两个边缘。（2）允许存在不同尺寸的板料。 （3）零件可以正交旋转。（4）某些板料有缺陷。可能有在板料和零件中存在一些缺陷可以避免其他的缺陷。2DCSP，MS2DCSP和MS2DDSGCSP是基于一维下料问题出现的NP完全难题。
二维下料问题由Gilmore和Gomory（1965）[1]提出。然后Lodi等人（2002）[2]提出该问题的概述和它的一些变体。针对此类问题几个确切方法和下限已经被提出。Christofides和Whitloek（1977）[3]利用树搜索方法来得到了一个确切的算法，并提出了用动态规划解决实际问题。然后，更确切的算法已被提议为2DGC-SP[4-8]。此外，一些精确的算法已经被提出用于二维切割问题[9-12]。
然而，由于2DCSP和MS2DCSP是NP完全难题，确切的算法需要更多的时间来找到解决方案，因此，用启发式算法来解决实践中遇到的问题得到了广泛的运用[13]。各种不同的启发式算法的提出了解决这些问题，如最佳拟合（BF）方法及其增强算法[14,15]，智能搜索算法和混合模拟退火算法[16,17]，并行算法[18]、顺序编组启发式算法[19,20]等。
二维缺陷板料切割下料问题（2DDSGCSP）相比而言并没有得到充分研究，尽管研究了一些相关的变异体。Gilmore和Gomory（1965，1966）[1,21]开发了一种基于根本解决策略的列生殖技术。Hahm（1968）[22]是第一个考虑在矩形缺陷板料上切割矩形件的人，随后Scheithauer和Terno（1988）[23]改善了解决方案的过程，但这些研究是不充分的。之后，Twisselmann（1999）[24]提出了一种有效的算法来找到所有可用受限制的矩形，而不只是最大的空矩形。最近，Neidlein等人（2008）[25]提出的AND/OR-graph的若干修改办法能够处理包含单个缺陷的板料。下面的符号被用于在二维切割问题的数学建模中：
（h;w）：零件的高度和宽度。
（H;W）：板料的高度和宽度。
I：相同大小的板料的数量。
Y：相同尺寸的零件的数量。
B ={lt;Wi，Higt;|iisin;I}：板料集合。
A ={lt;wj，hjgt;|jisin;J}：零件集合。
Dlm:第m个缺陷l。
(wj, hj):零件j的坐标。
(wl, hl):缺陷l的坐标。
nj:：零件数目j。
nij:在板料i上的零件j的数目。
(xi0jk, yi0jk): 在板料i上的第k个零件j的右上角坐标。
(xi1jk; yi1jk): 在板料i上的第k个零件j的左下角坐标。
dx: 零件左下角与右上角之间的水平距离。
dy: 零件左下角与右上角之间的垂直距离。
pijk:在板料i上的第k个零件i的布局模式。
p jk=0, 竖放; p jk= 1, 横放。
有关二维切割问题的文献仅涉及单一板料或单个缺陷，但在实际应用中，这种情况是不常见的。本文提出了一种新的启发式算法研究二维切割问题。本文对解决此类问题主要有两个帮助。首先，劈和摇的操作的提出能够减少余料的破碎，这不仅可以提高板料的利用率，而且提高了余料的复用率。其次，板料的缺陷也被纳入考虑，二维切割问题中板料的不同尺寸的缺陷也被提到。
本文的余下章节安排如下：
第2节建立了二维切割问题的一个数学模型。
第3节提出了一种启发式算法作为所研究的问题的解决方法。
第4节列出研究结果。
最后，在第5节阐述本文得出的一些结论，并展望进一步的研究。
2阐述问题
在本节中，二维切割问题被论述。
2.1约束
切割问题在实际应用中有许多特征和一些限制，这些在数学上的描述如下。
(1)零件尺寸约束
xi1jk=xi0jk pijkwj (1-pijk)hj, (1)
yi1jk=yi0jk pijkhj (1-pijk)wj. （2）
(2) 零件交叉约束。所有零件都不能与其他零件重叠。
如果yi0trlt;yi1jk,则xi0trge;xi1jk
( t, jisin;J;risin;n t;kisin;nj)， （3）
如果xi0trlt;xi1jk，则yi0trge;yi1jk
( t, jisin;J;risin;n t;kisin;nj). （4）
(3)对于板料的限制。零件不能超出板料的范围。
max{ xi1jk}le;Wi, (5)
max{ yi1jk }le;Hi (6)
(4)对零件数量的约束。零件的总数等于nj.
(5) 缺陷约束。所有零件不能同缺陷重叠。
dx gt;wj wl (8)
dygt; hj hy (9)
2.2目标函数
解决切割下料问题的主要目的是要将板料的利用率最大化。本文试图尽量减小最大矩形包络线，即最大矩形包络线是包含对所有零件的最小矩形，表示如下：
3启发式算法
本节分两个部分，提出了一个能有效解决二维切割问题的启发式算法。第一部分主要研究了二维切割算法，而第二部分在第一部分的基础上提出了初步的解决方案，并得到最终的解决方案。最后考虑和处理在板料中的缺陷。在此过程中呈现一个流程图来表示算法的过程。
3.1 算法流程图
启发式算法可以显示在流程图中（如图3所示）。第一部分，包括前三个步骤，研究2DGCSP。第二部分是由后两个步骤组成，主要是处理缺陷：
图1 动态优化算法流程图
步骤1，板料的选择。据的最大边，将可选的板料以升序排列，同时将等待排样的零件以降序排列。选择板料里最小的一个板料去排列最大的零件。如果板料的大小不够，则选择其他板料。
步骤2，初始排列方案。根据最低高度法则和左下方法则，可以得出一个可行的排列方案。当排入一个零件时，就可以找出第一种类型的样料进行合并，并获得初始排列方案，直到有没有等待排列或者可以被排入的零件。
步骤3，动态优化。在最初的包装解决方案发现的特殊的第二类样料将会被合并。随后劈和摇的操作来聚集并移动样料到板料顶部右上角。然后在等待排列的零件中寻找能够陷入样料的零件。如果零件存在，将零件嵌入;如果没有继续寻找合适的样料去排入直到它不能满足被排入，那么就得到了对单个板料的排样优化方案。
步骤4，消除零件与缺陷的重叠。本文搜索对整个板料并判断零件是否与缺陷重叠。一旦与缺陷重叠，该零件将立即消除。重复操作，直到没有零件与缺陷重叠。
步骤5，爆炸操作。本文设计了爆炸操作使零件尽可能的远离缺陷。搜索缺陷的边界，聚集、合并相邻的样料，然后插入新零件。
将上述流程中的排列后剩余板料解决退回备选板料库。开始下一轮的排样，第一部分一直到所有的代切割的零件项目全部排入。
3.2 第一部分：基于树的二进制启发式算法
本节提出二进制基于树的启发式算法2DGC-SP。相关切割的规则在3.2.1节中
已介绍。在3.2.2节，二进制树优化思想应用于表达铡切。最后，在3.2.3节，提出一系列的排样操作方法。
3.2.1 切割的基本法则
排入规则：最小的样料对应最大的零件
大边：板料（或零件）的高度和宽度之间的较大边
最大的零件：等待排样的有最长边的零件
排入法则用于选择板料。以待排零件的大边按降序来确定零件的顺序;以待切板料的大边按升序来确定板料的顺序。然后设置，在新一轮的排样过程中，待排零件中最大的零件将被选择。搜索样料列表，然后选择满足零件尺寸的最小样料。因此，本文提出的启发式算法将适用于多个板料的切割问题。
放置法则：初始切割方案是将样料放在左下角，待排零件中最大宽度和最小高度的零件将被选中放在左下方。
轮换规则：模数法设置的样料的小边为x =min（W，H），其中W和H分别是样料的宽度和高度。记w,h由排入法则和放置法则选定的零件的宽度和高度。因此，x，w和h的存在下面的线性关系：x=a·w d1; x=b·h d2。如果d1lt; d2。放置零件为w|| x或为w|| x(w|| x表示该零件的宽度是平行于样料的小边）。
切割法则：完整点切割。
定义1:连接样料：如果有两个或更多可合并的第二类样料（参见3.2.3节）的排样方案，除去样料之间的公共边缘组成未切割的样料，该样料被称为连接的样料（示于图6b-6C）。
定义2:完整点坐标：被排入零件的左下角和右上角坐标由笛卡尔直角坐标系表示，同时它们都位于连接腔中。
为了满足切割约束，被用于填充样料的零件的左下角坐标应位于完整点坐标，并且被选中的零件的尺寸要使连接腔的利用率最大化。
3.2.2二进制树优化
我们使用二进制树的生成过程来描述板料的切割过程，然后二进制树的生成过程中含有一个排样结果，意味着获得一个通用的排样解决方案。
定义3:近似解决方案：记I ={lt;N，Ggt;| N ={nj} ;G={gj}, J= 1; 2 ...}作为通用排样解决方案，其中N表示该组所有零件的编号，G代表一组零件的尺寸。exist;i={lt;Ni，Gigt;|Nisube;N，Gisube;G}是
剩余内容已隐藏，支付完成后下载完整资料
英语原文共 10 页，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[147935]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
