矩形排樣綜述

1、目錄1. 矩形件排樣的問(wèn)題描述：12. 算法分類(lèi)22.1. 啟發(fā)式算法22.1.1.基于最低水平線(xiàn)算法. 基于最低水平線(xiàn)的二維搜索算法3. 文獻(xiàn)8.基于二維裝箱問(wèn)題的矩形件排樣算法962.1.2. Best-fit算法.A squeaky wheel optimisation packing methodology（SWP）492.1.3. 分層排布算法. Modified size-alternating stack algorithm(SASm)5.Best fit with stacki

2、ng algorithm (BFS) 5122.1.4. 其他啟發(fā)式算法. 文獻(xiàn)10. 文獻(xiàn)11162.2. 智能算法192.2.1. PSO算法. 文獻(xiàn)12193. 上述算法在矩形排樣件中的應(yīng)用分類(lèi)214. 參考文獻(xiàn)22部分2010年矩形件優(yōu)化排樣算法的研究進(jìn)展1. 矩形件排樣的問(wèn)題描述：參見(jiàn)文獻(xiàn)1: 矩形件排樣題指在給的矩形板材上將一系列矩形零件按最優(yōu)方式進(jìn)行排布。即給定n個(gè)零件R=（R1，R2，Rn)，將零件置于寬度為W0，高度為L(zhǎng)的板材P上，使得板材的利用率最高，并要求滿(mǎn)足下列約束條件:(1)Ri、Rj互不重疊, ij, i, j=

3、1,2,n; (2)Ri能夠且必須放在P內(nèi), i= 1,2,n;(3)滿(mǎn)足一定工藝要求。2. 算法分類(lèi)2.1. 啟發(fā)式算法2.1.1. 基于最低水平線(xiàn)算法. 基于最低水平線(xiàn)的二維搜索算法3為了提高矩形件排樣時(shí)材料的利用率,針對(duì)定序列矩形件優(yōu)化排樣問(wèn)題,本文在基于最低水平線(xiàn)的搜索算法的基礎(chǔ)上,提出了一種改進(jìn)的矩形件優(yōu)化排樣算法基于最低水平線(xiàn)的二維搜索算法.此改進(jìn)算法在基于最低水平線(xiàn)的搜索算法基礎(chǔ)上,進(jìn)行了排樣寬度的二維搜索,即有如下改進(jìn)：基于最低水平線(xiàn)的搜索算法只進(jìn)行入排寬度的搜索(即矩形寬度的搜索)，而本文提出的排樣算法不僅優(yōu)先進(jìn)行入排寬度的搜索，而且在入排寬度均不符合排樣要求

4、時(shí)，還進(jìn)行了待排寬度的搜索(即矩形高度的搜索)。將該改進(jìn)算法與其他算法進(jìn)行實(shí)例排樣比較,排樣結(jié)果表明,改進(jìn)后的排樣算法能有效地利用排樣時(shí)產(chǎn)生的空白區(qū)域,在提高材料利用率上具有可行性和有效性。在排樣方式中，“l(fā)”表示對(duì)應(yīng)的矩形橫放，“一1”表示對(duì)應(yīng)的矩形豎放。此算法將參與排樣的矩形的長(zhǎng)寬根據(jù)排樣方式的要求，劃分為入排寬度數(shù)集Ri和待排寬度數(shù)集Di(其中i為入排矩形件的序列號(hào)，i=1，2，3，4 .)。排樣時(shí)，在本文的使用中，優(yōu)先搜索入排寬度數(shù)集Ri(即矩形寬度搜索)，當(dāng)入排寬度數(shù)集m都不能滿(mǎn)足排樣要求時(shí)，再搜索待排寬度數(shù)集Di(即矩形高度搜索)。具體的算法步驟如下所示：下圖中，XC表示當(dāng)前待排矩

5、形件。. 文獻(xiàn)8該分層排樣算法以文獻(xiàn)9提出的最低輪廓線(xiàn)搜索排樣法為基礎(chǔ),討論的是2SP問(wèn)題及符合“一刀切”的加工模式。針對(duì)在具有寬度一定、長(zhǎng)度不限的板材上進(jìn)行矩形件排樣的問(wèn)題,結(jié)合模擬退火算法,設(shè)計(jì)了一種矩形件分層優(yōu)化排樣算法。該算法以板材寬來(lái)分層,層數(shù)依據(jù)待排零件而定,靈活性強(qiáng),并且通過(guò)算例驗(yàn)證了該算法的有效性和合理性。算法以零件的長(zhǎng)度值(矩形零件較長(zhǎng)一邊值)來(lái)進(jìn)行排樣，更新后的輪廓線(xiàn)段的首末點(diǎn)橫坐標(biāo)值必須在該層寬度所對(duì)應(yīng)線(xiàn)段首末點(diǎn)橫坐標(biāo)值之間。 以板材寬來(lái)分層的分層排樣方式根據(jù)排樣結(jié)果顯示，該算法思想滿(mǎn)足先前提出的“一刀切”工藝要求，且排樣板材利用率在91以上?；谧畹洼喞€(xiàn)

6、分層排樣算法程序流程圖如下：其中l(wèi)min存儲(chǔ)剩余待排零件中的長(zhǎng)度最小值，Rc為當(dāng)前待排序列中的第一個(gè)零件。在結(jié)合模擬退火算法時(shí)，按待排零件的長(zhǎng)度優(yōu)先、面積次先的原則所排的順序?yàn)槌跏柬樞?，并且按此順序把可以先排滿(mǎn)板材最底端的零件排到板材上。然后將剩下的零件采用十進(jìn)制編碼方式將每一個(gè)零件進(jìn)行編號(hào)，用零件的長(zhǎng)度信息進(jìn)行排樣。初始化x0為初始導(dǎo)入的排樣順序，之后在TK下不斷產(chǎn)生在解x的鄰域中產(chǎn)生新的可行解x。結(jié)合后流程圖如下：分層排樣算法結(jié)合模擬退火算法的流程圖. 基于二維裝箱問(wèn)題的矩形件排樣算法9針對(duì)在具有一定長(zhǎng)寬尺寸的板材上進(jìn)行矩形件排樣的問(wèn)題,結(jié)合遺傳算法,設(shè)計(jì)了一種矩形件優(yōu)化排樣

7、算法.該算法考慮到排樣高度不超過(guò)板材長(zhǎng)度的要求,可以實(shí)現(xiàn)換板,使剩余待排矩形件在新板材上繼續(xù)排放.通過(guò)算例驗(yàn)證了該算法的有效性和合理性. 針對(duì)2BP問(wèn)題。 換板示意圖設(shè)待排的矩形零件分別有R1，R2，R3，. ，Rk, . , 其中Rc表示當(dāng)前待排零件。以零件的長(zhǎng)度值(矩形零件較長(zhǎng)一邊值)來(lái)進(jìn)行排樣。算法的具體程序流程如圖3所示，其中l(wèi)min存儲(chǔ)剩余待排零件中的長(zhǎng)度最小值，會(huì)隨排樣過(guò)程動(dòng)態(tài)變化；hnew表示排放當(dāng)前矩形零件后該零件頂端的高度值，用于判斷該零件排放是否會(huì)超出板材高度。以下為基于二維裝箱問(wèn)題的矩形件排樣算法程序流程圖：上述算法與遺傳算法結(jié)合使用尋求一種較優(yōu)的排樣順序，具體交叉及變異

8、方法參照本算法文中提及的。以下基于遺傳算法的優(yōu)化排樣算法流程圖：基于遺傳算法的優(yōu)化排樣算法流程圖 通過(guò)文中自帶的算例，用本文算法與基于最低輪廓線(xiàn)搜索排放算法比較，在應(yīng)用于2BP問(wèn)題時(shí)的板材利用率有所提高。2.1.2. Best-fit算法. A squeaky wheel optimisationpacking methodology（SWP）4SWP算法采取迭代的方式尋求矩形件排放的優(yōu)化，在迭代的過(guò)程中能夠找尋到使排樣效果變差的矩形，將它們優(yōu)先排放以達(dá)到優(yōu)化的效果。每一次迭代都表示一個(gè)完整的排樣過(guò)程。在每一次運(yùn)行時(shí)，每一個(gè)矩形件的初始懲罰值為0，在每一次迭代后，超出排樣實(shí)例最低

9、邊界的矩形件的懲罰值將增加。而每次累積的懲罰值將影響到到下一次迭代的排放選擇，懲罰值越高的矩形件下次迭代時(shí)將被優(yōu)先排放。在排放搜索時(shí)，若能放入當(dāng)前槽的矩形件懲罰值相同，則以寬度長(zhǎng)者優(yōu)先；若寬度相同，則以長(zhǎng)度長(zhǎng)者優(yōu)先。 Without penalty values, the constructive heuristic performs iden- tically to the best-fit heuristic with the tallest neighbourplace- ment policy 5. The addition of penalty values is a minor b

10、ut fundamental change, which allows the heuristic to learn which pieces are more difficult to allocate, over many iterations.(若該算法沒(méi)有懲罰值，則這個(gè)結(jié)構(gòu)化的啟發(fā)式算法與“靠最高的邊排放”的best-fit算法是一樣的效果。）即SWP算法的改進(jìn)就是加入了懲罰值以達(dá)到更好的排樣效果。 The addition of penalty values is a minor but fundamental change, which allows the heuristic t

11、o learn which pieces are more difficult to allocate, over many iterations. (加入懲罰值以后是對(duì)best-fit算法的一個(gè)較小的但根本的變化，使啟發(fā)式算法在多次迭代后能夠知道哪些矩形件較難調(diào)配，以達(dá)到優(yōu)化排放效果的目的。)SWP算法的偽代碼如下：初始化每一個(gè)樣件的懲罰值為0while 經(jīng)過(guò)時(shí)間<限定時(shí)間 do while 還有樣件未被排入 do 找到最低的槽'S' if S對(duì)于未排樣的任一樣件都不合適 Then 把S的高度提升到最低的臨層高度并合并 else 從可以排入S的樣件中找到有最高懲罰值的樣

12、件， 緊靠S邊上最高的層，放入S中 end if end while for 對(duì)當(dāng)前實(shí)例中所有樣件 pdo if p.lower -edge -y -coordinate+p.height>instance lowerbound then p.penalty =p.penalty + p.height end if end for end while return best solution found 在測(cè)試算法時(shí)使用的lower bound是以本次實(shí)例的情況而定的。若此例為已知的測(cè)試用例，則以其zero-waste時(shí)排放的高度為lower bound，若是隨機(jī)產(chǎn)生的實(shí)例，則用簡(jiǎn)單的

13、continuous lower bound 和與31相同的更復(fù)雜一些的 lower bound 計(jì)算。（注：31 Martello S, Monaci M, Vigo D. An exact approach to the strip-packing problem. INFORMS Journal on Computing 2003;15(3):3109. ）2.1.3. 分層排布算法. Modified size-alternating stack algorithm(SASm)5SASm算法改進(jìn)自SAS算法6 。因此簡(jiǎn)介SAS算法如下：FFDH在矩形件高度相差懸殊的時(shí)候，

14、效果是很差的。于是促使了SAS算法的誕生。SAS算法研究范圍如下： 把待排矩形分成兩個(gè)集合。L1：h>w，L2：w>=h。因而L1集中的矩形被稱(chēng)為窄矩形，L2集中矩形被稱(chēng)為寬矩形。L1以DH方式，L2以DW方式排序。每初始化一層，都比較兩集合中的第一個(gè)矩形件，以其中最高的矩形（具有相等高度的矩形可能有多個(gè)）初始化層。排放規(guī)則如下：如果初始化該層的矩形件來(lái)自于L1，則將被排放列表設(shè)為L(zhǎng)2，反之亦然。當(dāng)將被排放的矩形所在列表已經(jīng)確定，則開(kāi)始排放該列表中的矩形。排放的時(shí)候，從層底往層的上界堆疊排放，直到觸到層的上界或無(wú)法再放入該列表的矩形為止。此時(shí)再交換下一個(gè)列表的矩形在該層排放。如此反

15、復(fù)至該層的右邊界與已排的矩形件右邊界之間再也放不下L1或L2中的矩形件。 在排放寬矩形件時(shí)，可能會(huì)出現(xiàn)如下圖所示的區(qū)域R1，則此區(qū)域?qū)⒄{(diào)用窄矩形排放，先選擇寬度最適合的窄矩形件排放，之后只要有合適的垂直和水平空間，就選擇其寬度不超過(guò)最底端的窄矩形件，且高度不超過(guò)該層上界的窄矩形件。進(jìn)行排放。 排放寬矩形件產(chǎn)生空白區(qū)域 用窄矩形件填充空白區(qū)域SASm中對(duì)SAS改進(jìn)的部分有：1) 當(dāng)初始化一層的時(shí)候，找出寬矩形集L2（或W）中的最高者與窄矩形集L1（或N）中的 第一個(gè)矩形件進(jìn)行比較，而不是L2中的每一個(gè)矩形件。這樣可優(yōu)化層的創(chuàng)建。2) 在填充排放寬矩形件產(chǎn)生的空白空間時(shí)，選取了第一個(gè)窄矩形件之后，

16、之后排放的窄矩形件可以相臨并列排放，而不只是局限于堆疊式的排放，這樣可以減少如下圖的空間浪費(fèi)。此方法可在排放了第一個(gè)窄矩形件后，采用FFDH的方式排放其他的窄矩形件于其上的空白區(qū)域來(lái)達(dá)成。. Best fit with stacking algorithm (BFS) 5 BFS算法對(duì)BFDH*7進(jìn)行改進(jìn)，BFDH*簡(jiǎn)介如下：BFDH*：對(duì)BFDH算法進(jìn)行了改進(jìn)，有如下兩點(diǎn)：1) 在排放時(shí)，對(duì)當(dāng)前存在的所有層，BFDH的矩形件方向是不允許旋轉(zhuǎn)的，而B(niǎo)FDH*算法在排放當(dāng)前矩形件時(shí)，都嘗試該矩形件的兩種方向。若所有層都不適合當(dāng)前矩形件，則以該矩形件width height的方向初始

17、化新層。2) 提高空間的利用率。等該層底部排好后，將排入該層的矩形件如下圖從左至右排序(由于第一個(gè)改進(jìn)會(huì)破壞這種次序，因而重新排序)，如此就會(huì)產(chǎn)生圖中所示的一些空白區(qū)域，這些空白區(qū)從左到右解決。對(duì)于每一個(gè)空白區(qū)域，選取面積最大的樣件以最合適的方向和BL的方式排入空白區(qū)，此時(shí)空白區(qū)的左邊界更新至填充矩形件的右邊界，因此一個(gè)空白區(qū)域的填充可能是由幾個(gè)并排的矩形件完成的。BFS：改進(jìn)了BFDH*算法，有如下幾點(diǎn)：1) 初始化的時(shí)候，BFDH*采用DH方式排序，BFS采用DHDW方式排序。2) 與BFDH*算法不同，BFS算法不必等到層的底部被排滿(mǎn)時(shí)再進(jìn)行空白區(qū)填充。在將一塊矩形件排入該層底部后，以該

18、矩形件寬為寬，矩形件高至層高的差度為高的矩形空白區(qū)產(chǎn)生，此時(shí)采用FFDH的方式將待排矩形件填充入此空白矩形區(qū)域中。若排入底部的矩形件的右邊空白區(qū)域?qū)挾忍《鵁o(wú)法放入所有待排矩形，則該底部矩形件產(chǎn)生的空白區(qū)的右邊界擴(kuò)展至為條帶的右邊界。2.1.4. 其他啟發(fā)式算法. 文獻(xiàn)10對(duì)大規(guī)模矩形件正交排樣問(wèn)題,提出了一種快速高效的啟發(fā)式排放算法。對(duì)當(dāng)前的可排放位置（水平線(xiàn)）,用貪婪算法從未排矩形件中選擇可排放于該水平線(xiàn)的最優(yōu)矩形件組合塊;根據(jù)各個(gè)排放位置與其對(duì)應(yīng)的矩形件組合塊的匹配程度,選擇最優(yōu)的可排放位置（最優(yōu)水平線(xiàn)）優(yōu)先排放。在排放時(shí),為了便于后續(xù)排放,先將待排放位置對(duì)應(yīng)的矩形件組合塊

19、從高到低進(jìn)行排序,再排放。對(duì)E.Hopper提供的規(guī)模最大的一類(lèi)實(shí)例進(jìn)行計(jì)算,排樣率都在99%以上,平均排樣率達(dá)到了99.38%,平均計(jì)算時(shí)間只用了1.12秒。由于之前已提出的排放算法雖然取得了一定的效果，但當(dāng)問(wèn)題規(guī)模較大時(shí)，計(jì)算時(shí)間仍然較長(zhǎng)。因此，一種高效的針對(duì)大規(guī)模矩形件的優(yōu)化排樣方法的產(chǎn)生意義重大。 在具體做法上，與一般文獻(xiàn)中將矩形件選擇和位置選擇分成兩步或者每次考慮一個(gè)未排矩形件不同，該文將矩形件的選擇和位置的選擇結(jié)合起來(lái)考慮，利用貪婪算法，對(duì)各個(gè)可排位置選擇出最合適的一組矩形件，即最優(yōu)矩形件組合。根據(jù)各可排位置與其最優(yōu)矩形件組合的匹配程度，選擇最優(yōu)的排放位置（最優(yōu)水平線(xiàn)）優(yōu)先排放，這

20、使得當(dāng)前排放矩形件與已排矩形件盡可能緊湊。為了使當(dāng)前排放有利于后續(xù)排放，將排放位置對(duì)應(yīng)的矩形件組合塊按低到高排序后再進(jìn)行排放。按照此排放過(guò)程，直到排完所有的矩形件或者無(wú)法排放為止。 在圖2中，矩形1和4上方的水平線(xiàn)為槽形水平線(xiàn)；矩形2的為凸形水平線(xiàn)；矩形3與5上的為梯形水平線(xiàn)。初始排放狀態(tài)下，大矩形件的底邊為槽形水平線(xiàn)，其相鄰的左右水平線(xiàn)，看成高為H的梯形水平線(xiàn)。圖 2 水平線(xiàn)圖 另外，文中提出相應(yīng)的最優(yōu)組合算法與排放算法輔助選出最優(yōu)矩形組合及優(yōu)化排放效果（見(jiàn)文獻(xiàn)中）。由于文中敘述步驟過(guò)多，以下為該算法的簡(jiǎn)要步驟：1 若當(dāng)前最低槽形水平線(xiàn)的高h(yuǎn)minH，或所有小矩形件均被排放完，則轉(zhuǎn)步 驟6；

21、否則，轉(zhuǎn)步驟2。2 在當(dāng)前排放狀態(tài)下，找出槽形水平線(xiàn)對(duì)應(yīng)的最優(yōu)組合矩形，計(jì)算第i條槽形水平線(xiàn)的長(zhǎng)度與組合矩形總寬度之差dij。找出最小差度dmin的集合I。3 判斷是否存在最優(yōu)槽形水平線(xiàn)(該槽形水平線(xiàn)對(duì)應(yīng)的矩形組合塊與該槽形水平線(xiàn)匹配得最好，以dmin=0為標(biāo)準(zhǔn)）。若只有一個(gè)最優(yōu)槽形水平線(xiàn)，則用其對(duì)應(yīng)的矩形組合塊進(jìn)行排放；若有多條，則按文中規(guī)定的規(guī)則選擇其中一條進(jìn)行排放。排放完成后返回步驟1；若無(wú)最優(yōu)槽形水平線(xiàn)，則轉(zhuǎn)至步驟4。4 判斷是否存在最優(yōu)梯形水平線(xiàn)(存在某未排矩形件排放于此，剛好能填充滿(mǎn)該水平線(xiàn))。若存在這樣的梯形水平線(xiàn)，且只有一條，則直接排入。有多條，則按文中規(guī)定的規(guī)則選擇其中一條進(jìn)

22、行排放。返回步驟1；若不存在，則否則轉(zhuǎn)步驟5。5 到這一步，表明I中無(wú)最優(yōu)槽形水平線(xiàn)，且找不到最優(yōu)梯形水平線(xiàn)。則考慮I中的槽形水平線(xiàn)。若|I|=1，則對(duì)這條水平線(xiàn)對(duì)應(yīng)的最優(yōu)組合矩形塊進(jìn)行排放；若|I|>1，則按文中規(guī)定的規(guī)則進(jìn)行選擇并排放。返回步驟1。輸出排放圖。 文中與相關(guān)文獻(xiàn)最好結(jié)果進(jìn)行了比較,結(jié)果表明該文算法解決大規(guī)模的矩形件排樣具有高效性。. 文獻(xiàn)11為了有效地解決有約束的矩形件優(yōu)化排樣問(wèn)題，本文提出一種快速的求解算法。通過(guò)比較待排樣矩形件的不同排樣模式，選擇最優(yōu)排樣方案。算法完全基于解析計(jì)算，雖不能尋找理論最優(yōu)解，但相比于各種啟發(fā)式算法大大提高了排樣速度。實(shí)驗(yàn)結(jié)果

23、表明，算法能夠在較短的計(jì)算時(shí)間內(nèi)獲得滿(mǎn)意的排樣效果，是一種效率較高的有約束矩形件排樣算法，應(yīng)用于2BP問(wèn)題和“一刀切”的加工模式。 算法基本思想如下：如下圖，將矩形件排放左下角，有旋轉(zhuǎn)和不旋轉(zhuǎn)兩種旋轉(zhuǎn)方式。另外，在放好左下角的矩形件后切割的方式又可以分為橫切和豎切兩種，所以總共有4種排樣模式。其中R1，R2，R3，R4為切割后產(chǎn)生的子板材。一個(gè)待排矩形件的排樣模式圖 因此，對(duì)一塊板材進(jìn)行排樣，首先從這塊板材的左下角開(kāi)始試探地排放待排矩形件，對(duì)它的4 種排樣模式用某種評(píng)價(jià)標(biāo)準(zhǔn)進(jìn)行評(píng)估，選出評(píng)價(jià)最好的那種模式，再將這個(gè)評(píng)估值與其他所有待排矩形件的較好評(píng)估值進(jìn)行比較，選出最好的排樣模式，并按該排樣模

24、式進(jìn)行板材切割。然后按深度優(yōu)先的原則不斷地對(duì)一刀切產(chǎn)生的兩塊新的子板材重復(fù)上述過(guò)程，最終完成一塊板材的全部排樣。由于算法完全是解析計(jì)算，不存在尋優(yōu)過(guò)程，雖不能獲得理論最優(yōu)解，但運(yùn)行效率大大提高。 如下所述，則可計(jì)算評(píng)價(jià)函數(shù)BK（R），為該算法奠定評(píng)價(jià)基礎(chǔ)，BK（R）可以用快速貪婪法近似解決：步驟1 初始化： 設(shè)z=0，z 為排樣的總有效面積，它的最后結(jié)果即為評(píng)價(jià)函數(shù)值BK（R）。 c=LW，c為未排樣空間的面積大小。 矩形零件集合中的元素按面積從大到小排列。 設(shè)j=1，j為當(dāng)前時(shí)刻考慮的矩形零件的編號(hào)。 z*=0，只排一種矩形零件（編號(hào)為j*）能排放的最大有效面積。步驟2 BK（R）計(jì)算： u

25、j =min bj - nj ， ， xj =minuj ， z = z + vj xj c = c - vj xj 如果vj xj> z* ，z* = vjuj ，j* = j。步驟3 如果j<m，j=j+1，跳轉(zhuǎn)到步驟2。步驟4 如果z*>z，z=z*，返回最終的z 值為評(píng)價(jià)函數(shù)值BK（R）。有了以上計(jì)算評(píng)價(jià)函數(shù)BK（R）算法的基礎(chǔ)后，排放算法的詳細(xì)步驟如下所述：初始化：設(shè)L=R，為待排樣的板材集合。 設(shè)P=，為已排樣的矩形件鏈表集合。 設(shè)VT = 0，為已排樣的總有效面積。 待排樣的矩形件集合S 按照其面積從大到小排序，面積相同的則 將長(zhǎng)和寬之差的絕對(duì)值大的排在前面。

26、每種待排矩形件i已排數(shù)量ni = 0。步驟1 如果L，取出一種板材(Lk ,Wk ,Nk) ，并將其加入堆棧C。步驟2 如果C=，則回步驟1。否則： 從C中取出一個(gè)元素（L，W）作為將被切割的板材。 對(duì)于每種待排矩形件i，i=1，2，m，進(jìn)行如下循環(huán)： 如果，待排矩形件i有紋理方向要求（即不能旋轉(zhuǎn)），則 如果 li L，wi W，ni < bi，則 用算法中的評(píng)價(jià)函數(shù)BK（R）計(jì)算以下評(píng)價(jià)函數(shù)值： e1 = BK（R1），e2 = BK（R2），h1 = BK（R3），h2 = BK（R4） 比較豎切與橫切的總評(píng)價(jià)函數(shù)值Bi，并取數(shù)值大的， Bi = vi + maxe1 + e2，h1

27、 + h2 ，其中vi為當(dāng)前矩形件R的面積。 否則 Bi = 0。 如果，待排矩形件i 無(wú)紋理方向要求（可旋轉(zhuǎn)），則還要計(jì)算 其旋轉(zhuǎn)后的豎切與橫切的總評(píng)價(jià)函數(shù)值Bi，最后選取最大值。 i+。 步驟3 在所有矩形件排放在左下角后可得到的總評(píng)價(jià)函數(shù)值Bi， 找到其中最大的那個(gè)評(píng)價(jià)函數(shù)值Bj =maxBi | i = 1 , 2 , . , m。 如果，Bj > 0，則按照Bj 所確定的排樣模式進(jìn)行排樣切割。將切 割后產(chǎn)生的兩塊子板材R1、R2 或R3、R4 加入C。 否則，Bj = 0，說(shuō)明當(dāng)前的子板材（L，W）放不下任何待排矩形件， 所以將它當(dāng)作余料或廢料處理，加入余料列表。 返回步驟2。

28、結(jié)果對(duì)比：表中所指文獻(xiàn)為：8 Mhand H.Exact algorithms for the guillotine strip cutting/packingproblemJ.Computers and Operations Research，1998，25：925-940.10 馬廣焜，劉嘉敏，黃有群，等.一種有約束矩形排樣問(wèn)題的求解算法J.沈陽(yáng)工業(yè)大學(xué)學(xué)報(bào)，2006，28（4）：449-453.2.2. 智能算法2.2.1. PSO算法. 文獻(xiàn)12本文的算法是一種改進(jìn)基于最低水平線(xiàn)搜索算法，結(jié)合GA算法產(chǎn)生的改進(jìn)粒子群優(yōu)化算法。在本文應(yīng)用最低水平線(xiàn)搜索算法時(shí)，若有多個(gè)矩形件

29、適合最低水平線(xiàn)，則從中選取長(zhǎng)度或?qū)挾茸钸m合最低水平線(xiàn)寬度的矩形件進(jìn)行排放。 算法提出者考慮到用標(biāo)準(zhǔn)的PSO算法來(lái)更新原子比較困難，故利用GA的算法特點(diǎn)，結(jié)合GA改進(jìn)了PSO算法： 通過(guò)GA的交叉和變異來(lái)更新原子。在交叉時(shí)，當(dāng)前解將和個(gè)體最佳及全局最佳進(jìn)行交叉，產(chǎn)生的新解將決定原子在解空間的新位置。交叉的時(shí)候運(yùn)用的是文獻(xiàn)13里的交叉算法步驟如下：先選擇一個(gè)固定的交叉位置，該點(diǎn)前的基因保持不變，其后的基因進(jìn)行交叉操作。比較兩條染色體非交叉部分的基因，除去兩者中相同的基因；將兩條染色體不交叉部分余下的基因按原序保存在數(shù)組p 和q 當(dāng)中；進(jìn)行交叉時(shí)，將兩染色體交叉部分的基因和數(shù)組p 或q 中的基因進(jìn)行

30、對(duì)比，若不相同，則直接交換；否則用對(duì)應(yīng)數(shù)組p 或q 中的基因替換后，再交換兩染色體交叉的部分；完成染色體的交叉操作。例如：染色體A= 3,2,4,5,9,8,7,6,1,10 ,B= 9,1,10,3,2,5,4,6,7,8 .執(zhí)行交換時(shí)，產(chǎn)生交叉點(diǎn)：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。將兩染色體交叉部分的基因和數(shù)組p 或q 中的基因進(jìn)行對(duì)比后：A= 3,2,4,5,9,|8,7,6,4,5 ,B= 9,1,10,3,2,|10,1,6,7,8最后，交換兩染色體中交叉部分，則形成新的染色體A=3

31、,2,4,5,9,|10,1,6,7,8，B=9,1,10,3,2,|8,7,6,4,5適應(yīng)度函數(shù)： f=h/l （h=(w.h)/W，l為排放完成后的最大長(zhǎng)度）混合了GA的改進(jìn)PSO算法描述如下：Xtj 為原子j的當(dāng)前位置，f(Xtj )為適應(yīng)度，gbest為當(dāng)前所有原子的最佳，pbestj為原子j當(dāng)前最佳。for(i=O;i < tmax;i+ +)for(j= 0; j < n; j + +)Cross X'tj and pbestj to get X''tj; Cross X'tj and gbest to get X''tj

32、; Mutate X''tj to get Xt+1j ; According to the improved lowest horizontal searchalgorithm prposed above, compute the fitness f(Xt+1j) ;if (f(Xt+1j)>pbestj) pbestj=f(Xt+1j); for(k= O;k < n;k + +) if(f(pbestk) > f(gbest) gbest = pbestk; 3. 上述算法在矩形排樣件中的應(yīng)用分類(lèi)序號(hào)作者算法名研究類(lèi)型1楊傳華，李亞芹等基于最低水平線(xiàn)的二

33、維搜索算法3RF ,2SP2EdmundK.Burke,MatthewR.Hyde*,GrahamKendall A squeaky wheel optimisation （SWP）4OF ,2SP3FrankG.Ortmann, Nthabiseng Ntene, Jan H. van Vuuren *Modified size-alternating stack algorithm(SASm)5RG ,2SP4FrankG.Ortmann, Nthabiseng Ntene, Jan H. van Vuuren *Best fit with stacking algorithm (BFS)

34、 5RG ,2SP5張偉，安魯陵，邵曉明,鄭盈盈.一種矩形件分層排樣算法8RG ,2SP6張偉,安魯陵,孫金虎基于二維裝箱問(wèn)題的矩形件排樣算法10RF ,2BP7陳仕軍，曹矩矩形件優(yōu)化排樣的一種啟發(fā)式算法11OF ,2SP8彭文一種快速的有約束矩形件的優(yōu)化排樣模型12RG ,2SP9QI Ji, HUANG Lan, TAN YingImproved Particle Swarm Optimization Algorithmfor Rectangular Cutting-Stock Problem13OF ,2SP4. 參考文獻(xiàn)1 鄧東梅，周來(lái)水.矩形件排樣的研究進(jìn)展.AEROSPACE MATERIALS & TECHNOLOGY.2006 36(5).2 趙曉東.矩形件優(yōu)化排樣算法的研究與實(shí)現(xiàn).大連交通大學(xué)碩士學(xué)位論文, 20023. 楊傳華，吳錦文，李亞匠，郭士清，康金波，姜東化.定序列矩形件優(yōu)化排樣的二維搜索算法.佳木斯大學(xué)學(xué)報(bào)(自然科學(xué)版),2010 28(3).4. EdmundK.Burke,MatthewR.Hyde*,GrahamKendall.A squeaky wheel optimisation methodology for two-dimensional strip packing.5. Frank G. Ortmann, Nt