適合“一刀切”剪切方式的矩形件排樣算法

齊中娟

摘 要：本文以滿足剪板機(jī)加工工藝要求，提高板材的利用率為出發(fā)點，研究了大量國內(nèi)外有關(guān)矩形件排樣的各種算法，總結(jié)了適合普通剪床“一刀切”剪切方式的丁字尺算法，模擬退火算法，分層排樣算法，并給出了算法的實現(xiàn)過程，方法簡單易懂易編程，適合大規(guī)模矩形件排樣，能提高材料利用率和下料效率，期待這些排樣算法能為進(jìn)行矩形排樣的學(xué)者和從事生產(chǎn)實踐的技術(shù)人員提供參考價值。

關(guān)鍵詞：一刀切 排樣 丁字尺算法 模擬退火算法

中圖分類號：TH162 文獻(xiàn)標(biāo)識碼：A 文章編號：1672-3791（2014）06（a）-0095-02

在航空航天領(lǐng)域中各種復(fù)合材料和板材的性能獨特，而且應(yīng)用廣泛，價格昂貴，下料是零件加工的首道工序，是浪費的源頭，也可以說是節(jié)約成本的起點。因此如何進(jìn)行板材排樣下料，以減少廢料、降低成本是航空業(yè)迫切需要解決的問題。矩形件排樣是指在給定的矩形板材上將一系列矩形零件按最優(yōu)方式進(jìn)行排布，以使材料的利用率達(dá)到最高。矩形件排樣優(yōu)化問題是具有最高計算復(fù)雜度的一類問題—— NP完全問題。對于NP完全問題，國內(nèi)外不少學(xué)者也進(jìn)行了大量的研究，至今未找到最優(yōu)算法，因而只能采用有效的近似算法求解。曹炬提出了背包算法，能夠快速地找到近似最優(yōu)解。賈志欣提出了最低水平線排放算法與模擬退火算法相結(jié)合的方法，Jakobs最早提出了遺傳算法，但是這些方法不適用于“一刀切”的矩形件排樣。

1 定義

設(shè)排樣所用的板材的長為L、寬為W，板材的數(shù)量足以排下所有要排的矩形件。待排矩形件簡稱樣件，排樣所用原材料稱板材，待排件數(shù)量記作n，每個樣件記為Ri（i=1，2，…，n）。矩形件排樣問題通常是指將一系列矩形零件R=（R1，R2，…，Rn）排布在一寬為W，長（高）為L的矩形板材P上，使得排放區(qū)域的廢料盡可能少，并要滿足以下約束：（1）Ri、Rj互不重疊，i≠j，i，j=1，2，…，n；（2）Ri能夠且必須放在P內(nèi)，i=1，2，…，n；（3）滿足一定工藝要求。

2 算法

任何一種優(yōu)越的算法都是為了更好地滿足生產(chǎn)需求，單純考慮材料的利用率，就會增加零件排樣的復(fù)雜度，影響下料的時間，所以，對于排樣算法的研究，就要兼顧材料利用率，又要考慮下料的效率，同時也要符合加工設(shè)備的工藝要求，下面介紹幾種符合剪板機(jī)“一刀切”剪切方式的算法。

2.1 丁字尺法

為提高生產(chǎn)效率，要求在一塊板材上下料的矩形件不超過3種（見圖1），直線TB，MR將矩形板材分成三塊，分別為S1，S2，S3。對于大型企業(yè)的大規(guī)模矩形件生產(chǎn)加工效果比較好，能夠加快工人的下料效率，可在生產(chǎn)中推廣應(yīng)用。

2.1.1 數(shù)學(xué)模型

設(shè)板材長和寬分別為L、W，有N種零件，其長、寬、數(shù)量分別為li、Wi和ni（1≤i≤N），ni為一個很大的數(shù)目。每一行（列）上的零件只能橫放或者豎放，假設(shè)板材的數(shù)量是足夠的。將一個矩形件（li，Wi）看作（li，Wi）和（Wi，li）兩種零件考慮，且有l(wèi)i+N=Wi。

式中x，y是li和lj的函數(shù)，所以目標(biāo)函數(shù)的決策變量是li、lj和lk。

2.1.2 對模型的搜索算法求解步驟

（1）對整塊板材利用搜索算法，尋找余料最少的零件組合。（2）設(shè)定一個能夠接受的材料利用率ratio，當(dāng)零件組合后的利用率大于ratio，則接受組合，否則轉(zhuǎn)下一步。（3）當(dāng)任意零件組合的利用率都小于ratio，根據(jù)利用率大小，可以將板材利用二分法縱向分成小塊。（4）對分塊后的小塊板材繼續(xù)執(zhí)行（1）。

2.2 十字線法

該種方法同樣是在考慮材料利用率前提下，兼顧生產(chǎn)時下料的效率。通過劃十字線將第一塊板材分成A、B、C、D四個部分（見圖2），從板材的左下角出發(fā)，隨著P（x，y）的變化尋找合適的x，y使得在區(qū)域A、B、C、D中排下足夠多的零件，最后計算板材剩余面積最小，該種方法仍可以參照丁字尺法，采用搜索算法，尋找零件的最優(yōu)組合。

2.3 模擬退火算法

模擬退火算法相對于以上介紹的兩種算法，增加了解的空間，在一定程度上接受劣質(zhì)解，提高全局的搜索能力，近似達(dá)到全局最優(yōu)解。該算法是一種解決組合優(yōu)化問題的隨機(jī)搜索技術(shù)，利用一個新解產(chǎn)生裝置和接受準(zhǔn)則，不斷對當(dāng)前解迭代，從而達(dá)到目標(biāo)函數(shù)最優(yōu)。

毛坯排樣的目標(biāo)函數(shù)：

板材長度Lenghth，寬度Width，工件種類數(shù)n。第i種工件的長寬和數(shù)量分別為Rect[i].l、Rect[i].w、Rect[i].n.

模擬退火算法通過調(diào)用“最小寬度算法”，同時在最小寬度算法中分別調(diào)用條料生成算法和空白矩形的填充算法，實現(xiàn)了最小寬度算法和模擬退火算法的結(jié)合，跳出了以往算法局部搜索的局限，并且適合“一刀切”的下料工藝要求。

2.4 分層排樣算法

分層排樣方式是一種剪切排樣方式，適合用普通剪床剪切毛坯件。圖3中三條線將板材分成四層，層數(shù)和層的高度隨待排零件的不同而不同，層的高度也隨著排入的待排零件的增加而動態(tài)變化，也是決定最終排樣優(yōu)劣的一個重要指標(biāo)。

該種排樣方式必須滿足的約束條件：

（1）方案要滿足剪切方式的“一刀切”工藝要求。

（2）排放在板材最底端的零件必須在所有待排零件中長度最長。

（3）零件互相緊靠，互不重疊，排列不能超出板材之外。

（4）對已經(jīng)排好的零件，排放下一個零件時，其位置保持不變。

2.4.1 最低輪廓線的分層排樣

設(shè)待排矩形零件分別為R1，R2，R3…Rc，以零件的長度值來進(jìn)行排樣，算法實現(xiàn)步驟：

（1）按零件長度優(yōu)先，面積次之，從大到小的排序規(guī)則進(jìn)行排樣。

（2）排放R1在第一塊板材的左下角，形成的可排輪廓由兩條輪廓線段組成，并且記好每次排樣點的坐標(biāo)和待排零件的長度值與寬度值。endprint

（3）排放最后Rc時搜索高度最低的水平輪廓線段進(jìn)行排放。

若只有一條最低水平輪廓線，要在剩余待排零件中搜索長度最合適的零件，并將其調(diào)到Rc之前排列。當(dāng)所有最低水平輪廓線段不能放下Rc時，要進(jìn)行搜索，當(dāng)不符合條件時，可以將零件進(jìn)行90°旋轉(zhuǎn)，再進(jìn)行排列，每次排放都要搜索高度最低的水平線，直到排完所有的零件。

2.5 遺傳算法和蟻群算法

遺傳算法是將零件的排放序列作為排列組合問題并按給定的序列排放，獲得排樣圖，遺傳算法的全局搜索能力比較強(qiáng)，找到最優(yōu)解的概率比較大，具有很強(qiáng)得魯棒性，很適合求解組合優(yōu)化問題，有可能發(fā)生早熟現(xiàn)象，但是如果合理的設(shè)計初始群體可以避免早熟現(xiàn)象的發(fā)生。蟻群算法與其它算法相比，在求解性能上，具有很強(qiáng)的魯棒性和通用性，只要稍加修改就可以應(yīng)用到其他領(lǐng)域。該算法存在收斂速度慢，并且全局搜索能力較低的缺陷。

3 結(jié)語

本文給出的算法容易理解、實用性強(qiáng)，程序?qū)崿F(xiàn)相對容易，能夠得到相對理想的矩形排樣方式，根據(jù)操作實例排樣后，其排樣板材的利用率均可到達(dá)90%以上。根據(jù)相關(guān)文獻(xiàn)，任何算法都有效果不佳的問題存在，針對矩形件排樣，復(fù)合算法（排布和搜索算法相結(jié)合）的結(jié)果比單純排樣的算法好。總之，對矩形件排樣目前還沒有完全理想的方法。人工神經(jīng)網(wǎng)絡(luò)、遺傳算法、模糊系統(tǒng)等一些新穎的優(yōu)化算法，隨著計算機(jī)優(yōu)化技術(shù)的發(fā)展與智能優(yōu)化算法的深入探討，在排樣問題的應(yīng)用與研究會愈來愈深入，排樣效果也會更理想！

參考文獻(xiàn)

[1] Gilmore P C，Gomory R E.A linear programming approach to the cutting-stock problem（Part 1）[J].Operations Research，1961（9）：849-859.

[2] Gilmore P C，Gomory R E.A linear programming approach to the cutting-stock problem（Part 2）[J].Operations Research，1963（11）：863-888.

[3] Gilmore P C.Gomory R E.Multistage cuRing-stock problems of two and more dimensions[J].Operations Research，1965（13）：94-120.

[4] 曹炬，周濟(jì)，余俊.矩形件排樣優(yōu)化的背包算法[J].武漢：中國機(jī)械工程，1994，5（2）.endprint

（3）排放最后Rc時搜索高度最低的水平輪廓線段進(jìn)行排放。

若只有一條最低水平輪廓線，要在剩余待排零件中搜索長度最合適的零件，并將其調(diào)到Rc之前排列。當(dāng)所有最低水平輪廓線段不能放下Rc時，要進(jìn)行搜索，當(dāng)不符合條件時，可以將零件進(jìn)行90°旋轉(zhuǎn)，再進(jìn)行排列，每次排放都要搜索高度最低的水平線，直到排完所有的零件。

2.5 遺傳算法和蟻群算法

遺傳算法是將零件的排放序列作為排列組合問題并按給定的序列排放，獲得排樣圖，遺傳算法的全局搜索能力比較強(qiáng)，找到最優(yōu)解的概率比較大，具有很強(qiáng)得魯棒性，很適合求解組合優(yōu)化問題，有可能發(fā)生早熟現(xiàn)象，但是如果合理的設(shè)計初始群體可以避免早熟現(xiàn)象的發(fā)生。蟻群算法與其它算法相比，在求解性能上，具有很強(qiáng)的魯棒性和通用性，只要稍加修改就可以應(yīng)用到其他領(lǐng)域。該算法存在收斂速度慢，并且全局搜索能力較低的缺陷。

3 結(jié)語

本文給出的算法容易理解、實用性強(qiáng)，程序?qū)崿F(xiàn)相對容易，能夠得到相對理想的矩形排樣方式，根據(jù)操作實例排樣后，其排樣板材的利用率均可到達(dá)90%以上。根據(jù)相關(guān)文獻(xiàn)，任何算法都有效果不佳的問題存在，針對矩形件排樣，復(fù)合算法（排布和搜索算法相結(jié)合）的結(jié)果比單純排樣的算法好?？傊瑢匦渭艠幽壳斑€沒有完全理想的方法。人工神經(jīng)網(wǎng)絡(luò)、遺傳算法、模糊系統(tǒng)等一些新穎的優(yōu)化算法，隨著計算機(jī)優(yōu)化技術(shù)的發(fā)展與智能優(yōu)化算法的深入探討，在排樣問題的應(yīng)用與研究會愈來愈深入，排樣效果也會更理想！

參考文獻(xiàn)

[1] Gilmore P C，Gomory R E.A linear programming approach to the cutting-stock problem（Part 1）[J].Operations Research，1961（9）：849-859.

[2] Gilmore P C，Gomory R E.A linear programming approach to the cutting-stock problem（Part 2）[J].Operations Research，1963（11）：863-888.

[3] Gilmore P C.Gomory R E.Multistage cuRing-stock problems of two and more dimensions[J].Operations Research，1965（13）：94-120.

[4] 曹炬，周濟(jì)，余俊.矩形件排樣優(yōu)化的背包算法[J].武漢：中國機(jī)械工程，1994，5（2）.endprint

（3）排放最后Rc時搜索高度最低的水平輪廓線段進(jìn)行排放。

若只有一條最低水平輪廓線，要在剩余待排零件中搜索長度最合適的零件，并將其調(diào)到Rc之前排列。當(dāng)所有最低水平輪廓線段不能放下Rc時，要進(jìn)行搜索，當(dāng)不符合條件時，可以將零件進(jìn)行90°旋轉(zhuǎn)，再進(jìn)行排列，每次排放都要搜索高度最低的水平線，直到排完所有的零件。

2.5 遺傳算法和蟻群算法

遺傳算法是將零件的排放序列作為排列組合問題并按給定的序列排放，獲得排樣圖，遺傳算法的全局搜索能力比較強(qiáng)，找到最優(yōu)解的概率比較大，具有很強(qiáng)得魯棒性，很適合求解組合優(yōu)化問題，有可能發(fā)生早熟現(xiàn)象，但是如果合理的設(shè)計初始群體可以避免早熟現(xiàn)象的發(fā)生。蟻群算法與其它算法相比，在求解性能上，具有很強(qiáng)的魯棒性和通用性，只要稍加修改就可以應(yīng)用到其他領(lǐng)域。該算法存在收斂速度慢，并且全局搜索能力較低的缺陷。

3 結(jié)語

本文給出的算法容易理解、實用性強(qiáng)，程序?qū)崿F(xiàn)相對容易，能夠得到相對理想的矩形排樣方式，根據(jù)操作實例排樣后，其排樣板材的利用率均可到達(dá)90%以上。根據(jù)相關(guān)文獻(xiàn)，任何算法都有效果不佳的問題存在，針對矩形件排樣，復(fù)合算法（排布和搜索算法相結(jié)合）的結(jié)果比單純排樣的算法好。總之，對矩形件排樣目前還沒有完全理想的方法。人工神經(jīng)網(wǎng)絡(luò)、遺傳算法、模糊系統(tǒng)等一些新穎的優(yōu)化算法，隨著計算機(jī)優(yōu)化技術(shù)的發(fā)展與智能優(yōu)化算法的深入探討，在排樣問題的應(yīng)用與研究會愈來愈深入，排樣效果也會更理想！

參考文獻(xiàn)

[1] Gilmore P C，Gomory R E.A linear programming approach to the cutting-stock problem（Part 1）[J].Operations Research，1961（9）：849-859.

[2] Gilmore P C，Gomory R E.A linear programming approach to the cutting-stock problem（Part 2）[J].Operations Research，1963（11）：863-888.

[3] Gilmore P C.Gomory R E.Multistage cuRing-stock problems of two and more dimensions[J].Operations Research，1965（13）：94-120.

[4] 曹炬，周濟(jì)，余俊.矩形件排樣優(yōu)化的背包算法[J].武漢：中國機(jī)械工程，1994，5（2）.endprint