矩形排样综述.doc

《矩形排样综述.doc》由会员分享，可在线阅读，更多相关《矩形排样综述.doc（16页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、【精品文档】如有侵权，请联系网站删除，仅供学习与交流矩形排样综述.精品文档.目 录1. 矩形件排样的问题描述：12. 算法分类22.1. 启发式算法22.1.1. 基于最低水平线算法222.1.1.1. 基于最低水平线的二维搜索算法322.1.1.2. 文献832.1.1.3. 基于二维装箱问题的矩形件排样算法962.1.2. Best-fit算法92.1.2.1. A squeaky wheel optimisation packing methodology（SWP）492.1.3. 分层排布算法112.1.3.1. Modified size-alternating stack algo

2、rithm(SASm)5112.1.3.2. Best fit with stacking algorithm (BFS) 5122.1.4. 其他启发式算法132.1.4.1. 文献10132.1.4.2. 文献11162.2. 智能算法192.2.1. PSO算法192.2.1.1. 文献12193. 上述算法在矩形排样件中的应用分类214. 参考文献22部分2010年矩形件优化排样算法的研究进展1. 矩形件排样的问题描述：参见文献1: 矩形件排样题指在给的矩形板材上将一系列矩形零件按最优方式进行排布。即给定n个零件R=（R1，R2，Rn)，将零件置于宽度为W0，高度为L的板材P上，使得板

3、材的利用率最高，并要求满足下列约束条件:(1)Ri、Rj互不重叠, ij, i, j=1,2,n; (2)Ri能够且必须放在P内, i= 1,2,n;(3)满足一定工艺要求。2. 算法分类2.1. 启发式算法2.1.1. 基于最低水平线算法22.1.1.1. 基于最低水平线的二维搜索算法3 为了提高矩形件排样时材料的利用率,针对定序列矩形件优化排样问题,本文在基于最低水平线的搜索算法的基础上,提出了一种改进的矩形件优化排样算法基于最低水平线的二维搜索算法.此改进算法在基于最低水平线的搜索算法基础上,进行了排样宽度的二维搜索,即有如下改进：基于最低水平线的搜索算法只进行入排宽度的搜索(即矩形宽度

4、的搜索)，而本文提出的排样算法不仅优先进行入排宽度的搜索，而且在入排宽度均不符合排样要求时，还进行了待排宽度的搜索(即矩形高度的搜索)。 将该改进算法与其他算法进行实例排样比较,排样结果表明,改进后的排样算法能有效地利用排样时产生的空白区域,在提高材料利用率上具有可行性和有效性。在排样方式中，“l”表示对应的矩形横放，“一1”表示对应的矩形竖放。 此算法将参与排样的矩形的长宽根据排样方式的要求，划分为入排宽度数集Ri和待排宽度数集Di(其中i为入排矩形件的序列号，i=1，2，3，4 .)。排样时，在本文的使用中，优先搜索入排宽度数集Ri(即矩形宽度搜索)，当入排宽度数集m都不能满足排样要求时，

5、再搜索待排宽度数集Di(即矩形高度搜索)。具体的算法步骤如下所示：下图中，XC表示当前待排矩形件。2.1.1.2. 文献8该分层排样算法以文献9提出的最低轮廓线搜索排样法为基础,讨论的是2SP问题及符合“一刀切”的加工模式。针对在具有宽度一定、长度不限的板材上进行矩形件排样的问题,结合模拟退火算法,设计了一种矩形件分层优化排样算法。该算法以板材宽来分层,层数依据待排零件而定,灵活性强,并且通过算例验证了该算法的有效性和合理性。 算法以零件的长度值(矩形零件较长一边值)来进行排样，更新后的轮廓线段的首末点横坐标值必须在该层宽度所对应线段首末点横坐标值之间。 以板材宽来分层的分层排样方式 根据排样

6、结果显示，该算法思想满足先前提出的“一刀切”工艺要求，且排样板材利用率在91以上。基于最低轮廓线分层排样算法程序流程图如下：其中lmin存储剩余待排零件中的长度最小值，Rc为当前待排序列中的第一个零件。 在结合模拟退火算法时，按待排零件的长度优先、面积次先的原则所排的顺序为初始顺序，并且按此顺序把可以先排满板材最底端的零件排到板材上。然后将剩下的零件采用十进制编码方式将每一个零件进行编号，用零件的长度信息进行排样。初始化x0为初始导入的排样顺序，之后在TK下不断产生在解x的邻域中产生新的可行解x。结合后流程图如下：分层排样算法结合模拟退火算法的流程图2.1.1.3. 基于二维装箱问题的矩形件排

7、样算法9针对在具有一定长宽尺寸的板材上进行矩形件排样的问题,结合遗传算法,设计了一种矩形件优化排样算法.该算法考虑到排样高度不超过板材长度的要求,可以实现换板,使剩余待排矩形件在新板材上继续排放.通过算例验证了该算法的有效性和合理性. 针对2BP问题。 换板示意图 设待排的矩形零件分别有R1，R2，R3，. ，Rk, . , 其中Rc表示当前待排零件。以零件的长度值(矩形零件较长一边值)来进行排样。算法的具体程序流程如图3所示，其中lmin存储剩余待排零件中的长度最小值，会随排样过程动态变化；hnew表示排放当前矩形零件后该零件顶端的高度值，用于判断该零件排放是否会超出板材高度。以下为基于二维

8、装箱问题的矩形件排样算法程序流程图： 上述算法与遗传算法结合使用寻求一种较优的排样顺序，具体交叉及变异方法参照本算法文中提及的。以下基于遗传算法的优化排样算法流程图： 基于遗传算法的优化排样算法流程图 通过文中自带的算例，用本文算法与基于最低轮廓线搜索排放算法比较，在应用于2BP问题时的板材利用率有所提高。2.1.2. Best-fit算法2.1.2.1. A squeaky wheel optimisation packing methodology（SWP）4 SWP算法采取迭代的方式寻求矩形件排放的优化，在迭代的过程中能够找寻到使排样效果变差的矩形，将它们优先排放以达到优化的效果。每一次

9、迭代都表示一个完整的排样过程。在每一次运行时，每一个矩形件的初始惩罚值为0，在每一次迭代后，超出排样实例最低边界的矩形件的惩罚值将增加。而每次累积的惩罚值将影响到到下一次迭代的排放选择，惩罚值越高的矩形件下次迭代时将被优先排放。在排放搜索时，若能放入当前槽的矩形件惩罚值相同，则以宽度长者优先；若宽度相同，则以长度长者优先。 Without penalty values, the constructive heuristic performs iden- tically to the best-fit heuristic with the tallest neighbourplace- ment

10、 policy 5. The addition of penalty values is a minor but fundamental change, which allows the heuristic to learn which pieces are more difficult to allocate, over many iterations.(若该算法没有惩罚值，则这个结构化的启发式算法与“靠最高的边排放”的best-fit算法是一样的效果。）即SWP算法的改进就是加入了惩罚值以达到更好的排样效果。 The addition of penalty values is a mino

11、r but fundamental change, which allows the heuristic to learn which pieces are more difficult to allocate, over many iterations. (加入惩罚值以后是对best-fit算法的一个较小的但根本的变化，使启发式算法在多次迭代后能够知道哪些矩形件较难调配，以达到优化排放效果的目的。)SWP算法的伪代码如下：初始化每一个样件的惩罚值为0while 经过时间instance lowerbound then p.penalty =p.penalty + p.height end i

12、f end for end while return best solution found 在测试算法时使用的lower bound是以本次实例的情况而定的。若此例为已知的测试用例，则以其zero-waste时排放的高度为lower bound，若是随机产生的实例，则用简单的 continuous lower bound 和与31相同的更复杂一些的 lower bound 计算。（注：31 Martello S, Monaci M, Vigo D. An exact approach to the strip-packing problem. INFORMS Journal on Compu

13、ting 2003;15(3):3109. ）2.1.3. 分层排布算法2.1.3.1. Modified size-alternating stack algorithm(SASm)5SASm算法改进自SAS算法6 。因此简介SAS算法如下：FFDH在矩形件高度相差悬殊的时候，效果是很差的。于是促使了SAS算法的诞生。SAS算法研究范围如下： 把待排矩形分成两个集合。L1：hw，L2：w=h。因而L1集中的矩形被称为窄矩形，L2集中矩形被称为宽矩形。L1以DH方式，L2以DW方式排序。每初始化一层，都比较两集合中的第一个矩形件，以其中最高的矩形（具有相等高度的矩形可能有多个）初始化层。排放规

14、则如下：如果初始化该层的矩形件来自于L1，则将被排放列表设为L2，反之亦然。当将被排放的矩形所在列表已经确定，则开始排放该列表中的矩形。排放的时候，从层底往层的上界堆叠排放，直到触到层的上界或无法再放入该列表的矩形为止。此时再交换下一个列表的矩形在该层排放。如此反复至该层的右边界与已排的矩形件右边界之间再也放不下L1或L2中的矩形件。 在排放宽矩形件时，可能会出现如下图所示的区域R1，则此区域将调用窄矩形排放，先选择宽度最适合的窄矩形件排放，之后只要有合适的垂直和水平空间，就选择其宽度不超过最底端的窄矩形件，且高度不超过该层上界的窄矩形件。进行排放。 排放宽矩形件产生空白区域 用窄矩形件填充空

15、白区域SASm中对SAS改进的部分有：1) 当初始化一层的时候，找出宽矩形集L2（或W）中的最高者与窄矩形集L1（或N）中的 第一个矩形件进行比较，而不是L2中的每一个矩形件。这样可优化层的创建。2) 在填充排放宽矩形件产生的空白空间时，选取了第一个窄矩形件之后，之后排放的窄矩形件可以相临并列排放，而不只是局限于堆叠式的排放，这样可以减少如下图的空间浪费。此方法可在排放了第一个窄矩形件后，采用FFDH的方式排放其他的窄矩形件于其上的空白区域来达成。2.1.3.2. Best fit with stacking algorithm (BFS) 5 BFS算法对BFDH*7进行改进，BFDH*简介

16、如下：BFDH*：对BFDH算法进行了改进，有如下两点：1) 在排放时，对当前存在的所有层，BFDH的矩形件方向是不允许旋转的，而BFDH*算法在排放当前矩形件时，都尝试该矩形件的两种方向。若所有层都不适合当前矩形件，则以该矩形件width height的方向初始化新层。2) 提高空间的利用率。等该层底部排好后，将排入该层的矩形件如下图从左至右排序(由于第一个改进会破坏这种次序，因而重新排序)，如此就会产生图中所示的一些空白区域，这些空白区从左到右解决。对于每一个空白区域，选取面积最大的样件以最合适的方向和BL的方式排入空白区，此时空白区的左边界更新至填充矩形件的右边界，因此一个空白区域的填充

17、可能是由几个并排的矩形件完成的。BFS：改进了BFDH*算法，有如下几点：1) 初始化的时候，BFDH*采用DH方式排序，BFS采用DHDW方式排序。2) 与BFDH*算法不同，BFS算法不必等到层的底部被排满时再进行空白区填充。在将一块矩形件排入该层底部后，以该矩形件宽为宽，矩形件高至层高的差度为高的矩形空白区产生，此时采用FFDH的方式将待排矩形件填充入此空白矩形区域中。若排入底部的矩形件的右边空白区域宽度太小而无法放入所有待排矩形，则该底部矩形件产生的空白区的右边界扩展至为条带的右边界。2.1.4. 其他启发式算法2.1.4.1. 文献10 对大规模矩形件正交排样问题,提出了一种快速高效

18、的启发式排放算法。对当前的可排放位置（水平线）,用贪婪算法从未排矩形件中选择可排放于该水平线的最优矩形件组合块;根据各个排放位置与其对应的矩形件组合块的匹配程度,选择最优的可排放位置（最优水平线）优先排放。在排放时,为了便于后续排放,先将待排放位置对应的矩形件组合块从高到低进行排序,再排放。对E.Hopper提供的规模最大的一类实例进行计算,排样率都在99%以上,平均排样率达到了99.38%,平均计算时间只用了1.12秒。 由于之前已提出的排放算法虽然取得了一定的效果，但当问题规模较大时，计算时间仍然较长。因此，一种高效的针对大规模矩形件的优化排样方法的产生意义重大。 在具体做法上，与一般文献

19、中将矩形件选择和位置选择分成两步或者每次考虑一个未排矩形件不同，该文将矩形件的选择和位置的选择结合起来考虑，利用贪婪算法，对各个可排位置选择出最合适的一组矩形件，即最优矩形件组合。根据各可排位置与其最优矩形件组合的匹配程度，选择最优的排放位置（最优水平线）优先排放，这使得当前排放矩形件与已排矩形件尽可能紧凑。为了使当前排放有利于后续排放，将排放位置对应的矩形件组合块按低到高排序后再进行排放。按照此排放过程，直到排完所有的矩形件或者无法排放为止。 在图2中，矩形1和4上方的水平线为槽形水平线；矩形2的为凸形水平线；矩形3与5上的为梯形水平线。初始排放状态下，大矩形件的底边为槽形水平线，其相邻的左

20、右水平线，看成高为H的梯形水平线。 图 2 水平线图 另外，文中提出相应的最优组合算法与排放算法辅助选出最优矩形组合及优化排放效果（见文献中）。由于文中叙述步骤过多，以下为该算法的简要步骤：1 若当前最低槽形水平线的高hminH，或所有小矩形件均被排放完，则转步 骤6；否则，转步骤2。2 在当前排放状态下，找出槽形水平线对应的最优组合矩形，计算第i条槽形水平线的长度与组合矩形总宽度之差dij。找出最小差度dmin的集合I。3 判断是否存在最优槽形水平线(该槽形水平线对应的矩形组合块与该槽形水平线匹配得最好，以dmin=0为标准）。若只有一个最优槽形水平线，则用其对应的矩形组合块进行排放；若有多

21、条，则按文中规定的规则选择其中一条进行排放。排放完成后返回步骤1；若无最优槽形水平线，则转至步骤4。4 判断是否存在最优梯形水平线(存在某未排矩形件排放于此，刚好能填充满该水平线)。若存在这样的梯形水平线，且只有一条，则直接排入。有多条，则按文中规定的规则选择其中一条进行排放。返回步骤1；若不存在，则否则转步骤5。5 到这一步，表明I中无最优槽形水平线，且找不到最优梯形水平线。则考虑I中的槽形水平线。若|I|=1，则对这条水平线对应的最优组合矩形块进行排放；若|I|1，则按文中规定的规则进行选择并排放。返回步骤1。输出排放图。 文中与相关文献最好结果进行了比较,结果表明该文算法解决大规模的矩形

22、件排样具有高效性。2.1.4.2. 文献11 为了有效地解决有约束的矩形件优化排样问题，本文提出一种快速的求解算法。通过比较待排样矩形件的不同排样模式，选择最优排样方案。算法完全基于解析计算，虽不能寻找理论最优解，但相比于各种启发式算法大大提高了排样速度。实验结果表明，算法能够在较短的计算时间内获得满意的排样效果，是一种效率较高的有约束矩形件排样算法，应用于2BP问题和“一刀切”的加工模式。 算法基本思想如下：如下图，将矩形件排放左下角，有旋转和不旋转两种旋转方式。另外，在放好左下角的矩形件后切割的方式又可以分为横切和竖切两种，所以总共有4种排样模式。其中R1，R2，R3，R4为切割后产生的子

23、板材。 一个待排矩形件的排样模式图 因此，对一块板材进行排样，首先从这块板材的左下角开始试探地排放待排矩形件，对它的4 种排样模式用某种评价标准进行评估，选出评价最好的那种模式，再将这个评估值与其他所有待排矩形件的较好评估值进行比较，选出最好的排样模式，并按该排样模式进行板材切割。然后按深度优先的原则不断地对一刀切产生的两块新的子板材重复上述过程，最终完成一块板材的全部排样。由于算法完全是解析计算，不存在寻优过程，虽不能获得理论最优解，但运行效率大大提高。 如下所述，则可计算评价函数BK（R），为该算法奠定评价基础，BK（R）可以用快速贪婪法近似解决：步骤1 初始化： 设z=0，z 为排样的总

24、有效面积，它的最后结果即为评价函数值BK（R）。 c=LW，c为未排样空间的面积大小。 矩形零件集合中的元素按面积从大到小排列。 设j=1，j为当前时刻考虑的矩形零件的编号。 z*=0，只排一种矩形零件（编号为j*）能排放的最大有效面积。步骤2 BK（R）计算： uj =min bj - nj ， ， xj =minuj ， z = z + vj xj c = c - vj xj 如果vj xj z* ，z* = vjuj ，j* = j。步骤3 如果jz，z=z*，返回最终的z 值为评价函数值BK（R）。有了以上计算评价函数BK（R）算法的基础后，排放算法的详细步骤如下所述：初始化：设L=R

25、，为待排样的板材集合。 设P=，为已排样的矩形件链表集合。 设VT = 0，为已排样的总有效面积。 待排样的矩形件集合S 按照其面积从大到小排序，面积相同的则 将长和宽之差的绝对值大的排在前面。 每种待排矩形件i已排数量ni = 0。步骤1 如果L，取出一种板材(Lk ,Wk ,Nk) ，并将其加入堆栈C。步骤2 如果C=，则回步骤1。否则： 从C中取出一个元素（L，W）作为将被切割的板材。 对于每种待排矩形件i，i=1，2，m，进行如下循环： 如果，待排矩形件i有纹理方向要求（即不能旋转），则 如果 li L，wi W，ni 0，则按照Bj 所确定的排样模式进行排样切割。将切 割后产生的两块

26、子板材R1、R2 或R3、R4 加入C。 否则，Bj = 0，说明当前的子板材（L，W）放不下任何待排矩形件， 所以将它当作余料或废料处理，加入余料列表。 返回步骤2。结果对比：表中所指文献为：8 Mhand H.Exact algorithms for the guillotine strip cutting/packingproblemJ.Computers and Operations Research，1998，25：925-940.10 马广焜，刘嘉敏，黄有群，等.一种有约束矩形排样问题的求解算法J.沈阳工业大学学报，2006，28（4）：449-453.2.2. 智能算法2.2.1

27、. PSO算法2.2.1.1. 文献12 本文的算法是一种改进基于最低水平线搜索算法，结合GA算法产生的改进粒子群优化算法。在本文应用最低水平线搜索算法时，若有多个矩形件适合最低水平线，则从中选取长度或宽度最适合最低水平线宽度的矩形件进行排放。 算法提出者考虑到用标准的PSO算法来更新原子比较困难，故利用GA的算法特点，结合GA改进了PSO算法： 通过GA的交叉和变异来更新原子。在交叉时，当前解将和个体最佳及全局最佳进行交叉，产生的新解将决定原子在解空间的新位置。交叉的时候运用的是文献13里的交叉算法步骤如下：先选择一个固定的交叉位置，该点前的基因保持不变，其后的基因进行交叉操作。比较两条染色

28、体非交叉部分的基因，除去两者中相同的基因；将两条染色体不交叉部分余下的基因按原序保存在数组p 和q 当中；进行交叉时，将两染色体交叉部分的基因和数组p 或q 中的基因进行对比，若不相同，则直接交换；否则用对应数组p 或q 中的基因替换后，再交换两染色体交叉的部分；完成染色体的交叉操作。例如：染色体A= 3,2,4,5,9,8,7,6,1,10 ,B= 9,1,10,3,2,5,4,6,7,8 .执行交换时，产生交叉点：A= 3,2,4,5,9,|8,7,6,1,10 ,B= 9,1,10,3,2,|5,4,6,7,8，有P=4,5，q = 1, 10。将两染色体交叉部分的基因和数组p 或q 中

29、的基因进行对比后：A= 3,2,4,5,9,|8,7,6,4,5 ,B= 9,1,10,3,2,|10,1,6,7,8最后，交换两染色体中交叉部分，则形成新的染色体A=3,2,4,5,9,|10,1,6,7,8，B=9,1,10,3,2,|8,7,6,4,5适应度函数： f=h/l （h=(w.h)/W，l为排放完成后的最大长度）混合了GA的改进PSO算法描述如下：Xtj 为原子j的当前位置，f(Xtj )为适应度，gbest为当前所有原子的最佳，pbestj 为原子j当前最佳。for(i=O;i tmax;i+ +) for(j= 0; j pbestj) pbestj=f(Xt+1j);

30、for(k= O;k f(gbest) gbest = pbestk;3. 上述算法在矩形排样件中的应用分类序号作者算法名研究类型1杨传华，李亚芹等基于最低水平线的二维搜索算法3RF ,2SP2Edmund K.Burke,MatthewR.Hyde*,Graham Kendall A squeaky wheel optimisation （SWP）4OF ,2SP3FrankG.Ortmann, Nthabiseng Ntene, Jan H. van Vuuren *Modified size-alternating stack algorithm(SASm)5RG ,2SP4FrankG

31、.Ortmann, Nthabiseng Ntene, Jan H. van Vuuren *Best fit with stacking algorithm (BFS) 5RG ,2SP5张伟，安鲁陵，邵晓明,郑盈盈.一种矩形件分层排样算法8RG ,2SP6张伟,安鲁陵,孙金虎基于二维装箱问题的矩形件排样算法10RF ,2BP7陈仕军，曹矩矩形件优化排样的一种启发式算法11OF ,2SP8彭文一种快速的有约束矩形件的优化排样模型12RG ,2SP9QI Ji, HUANG Lan, TAN YingImproved Particle Swarm Optimization Algorithm

32、for Rectangular Cutting-Stock Problem13OF ,2SP4. 参考文献1 邓东梅，周来水.矩形件排样的研究进展.AEROSPACE MATERIALS & TECHNOLOGY.2006 36(5).2 赵晓东.矩形件优化排样算法的研究与实现.大连交通大学硕士学位论文, 20023. 杨传华，吴锦文，李亚匠，郭士清，康金波，姜东化.定序列矩形件优化排样的二维搜索算法.佳木斯大学学报(自然科学版),2010 28(3).4. Edmund K.Burke, MatthewR.Hyde* ,Graham Kendall.A squeaky wheel optim

33、isation methodology for two-dimensional strip packing.Computers and Operations Research (2010), doi:10.1016/j.cor.2010.10.0055. Frank G. Ortmann, Nthabiseng Ntene ,Jan H. van Vuuren. New and improved level heuristics for the rectangular strip packing and variable-sized bin packing problems.European

34、Journal of Operational Research Volume 203, Issue 2, 1 June 2010, Pages 306-315.6. Nthabiseng Ntene.An Algorithmic Approach to the 2DOriented Strip Packing Problem.PhD thesis of University of Stellenbosch,2007.7. Andreas Bortfeldt .A genetic algorithm for the two-dimensional strip packing problem wi

35、th rectangular pieces.European Journal of Operational Research Volume 172, Issue 3, 1 August 2006, Pages 814-837.8. 张伟，安鲁陵，邵晓明,郑盈盈.一种矩形件分层排样算法.宇航材料工艺, 2010 .9. 张伟，安鲁陵 ,孙金虎.一种矩形件优化排样算法的研究.宇航材料工艺, 2010 .10. 陈仕军，曹矩.矩形件优化排样的一种启发式算法.计算机工程与应用, 2010 11. 彭文.一种快速的有约束矩形件的优化排样模型.Computer Engineering and Applic

36、ations，2010，46（27）：214-216.12. QI Ji, HUANG Lan, TAN Ying.Improved Particle Swarm Optimization Algorithm for Rectangular Cutting-Stock Problem.Multimedia Technology and its Applications (IDC), 2010 6th International Conference13. Yang Wei; Luo Yang; Liu Shengqing. Genetic Algorithm for LargeScale Rectangular Object Optimal Embed Placement 1. Journal ofSichuan University (Engineering Science Edition), 2001.33(5):59-62.