矩形排样综述.docx

目录

TOC\o"1-4"\h\uHYPERLINK\l"_Toc13541"1.矩形件排样的问题描述： PAGEREF_Toc135411
HYPERLINK\l"_Toc5226"2.算法分类 PAGEREF_Toc52262
HYPERLINK\l"_Toc12289"2.1.启发式算法 PAGEREF_Toc122892
HYPERLINK\l"_Toc31484"2.1.1.基于最低水平线算法[2] PAGEREF_Toc314842
HYPERLINK\l"_Toc7225"2.1.1.1.基于最低水平线的二维搜索算法[3] PAGEREF_Toc72252
HYPERLINK\l"_Toc24483"2.1.1.2.文献[8] PAGEREF_Toc244833
HYPERLINK\l"_Toc22258"2.1.1.3.基于二维装箱问题的矩形件排样算法[9] PAGEREF_Toc222586
HYPERLINK\l"_Toc18318"2.1.2.Best-fit算法 PAGEREF_Toc183189
HYPERLINK\l"_Toc24720"2.1.2.1.Asqueakywheeloptimisationpackingmethodology（SWP）[4] PAGEREF_Toc247209
HYPERLINK\l"_Toc18875"2.1.3.分层排布算法 PAGEREF_Toc1887511
HYPERLINK\l"_Toc21402"2.1.3.1.Modifiedsize-alternatingstackalgorithm(SASm)[5] PAGEREF_Toc2140211
HYPERLINK\l"_Toc11"2.1.3.2.Bestfitwithstackingalgorithm(BFS)[5] PAGEREF_Toc1112
HYPERLINK\l"_Toc3581"2.1.4.其他启发式算法 PAGEREF_Toc358113
HYPERLINK\l"_Toc5635"2.1.4.1.文献[10] PAGEREF_Toc563513
HYPERLINK\l"_Toc25937"2.1.4.2.文献[11] PAGEREF_Toc2593716
HYPERLINK\l"_Toc2679"2.2.智能算法 PAGEREF_Toc267919
HYPERLINK\l"_Toc17993"2.2.1.PSO算法 PAGEREF_Toc1799319
HYPERLINK\l"_Toc9140"2.2.1.1.文献[12] PAGEREF_Toc914019
HYPERLINK\l"_Toc24766"3.上述算法在矩形排样件中的应用分类 PAGEREF_Toc2476621
HYPERLINK\l"_Toc20971"4.参考文献 PAGEREF_Toc2097122


部分2010年矩形件优化排样算法的研究进展
矩形件排样的问题描述：
参见文献[1]:
矩形件排样题指在给的矩形板材上将一系列矩形零件按最优方式进行排布。
即给定n个零件R=（R1，R2，，…，Rn)，将零件置于宽度为W0，高度为L的板材P上，使得板材的利用率最高，并要求满足下列约束条件:
(1)Ri、Rj互不重叠,i≠j,i,j=1,2,…,n;
(2)Ri能够且必须放在P内,i=1,2,…,n;
(3)满足一定工艺要求。

算法分类
启发式算法
基于最低水平线算法[2]
基于最低水平线的二维搜索算法[3]
为了提高矩形件排样时材料的利用率,针对定序列矩形件优化排样问题,本文在＂基于最低水平线的搜索算法＂的基础上,提出了一种改进的矩形件优化排样算法——基于最低水平线的二维搜索算法.此改进算法在＂基于最低水平线的搜索算法＂基础上,进行了排样宽度的二维搜索,即有如下改进：基于最低水平线的搜索算法只进行入排宽度的搜索(即矩形宽度的搜索)，而本文提出的排样算法不仅优先进行入排宽度的搜索，而且在入排宽度均不符合排样要求时，还进行了待排宽度的搜索(即矩形高度的搜索)。
将该改进算法与其他算法进行实例排样比较,排样结果表明,改进后的排样算法能有效地利用排样时产生的空白区域,在提高材料利用率上具有可行性和有效性。在排样方式中，“l”表示对应的矩形横放，“一1”表示对应的矩形竖放。
此算法将参与排样的矩形的长宽根据排样方式的要求，划分为入排宽度数集Ri和待排宽度数集Di(其中i为入排矩形