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

齊中娟

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

關鍵詞：一刀切 排樣 丁字尺算法 模擬退火算法

中圖分類號：TH162 文獻標識碼：A 文章編號：1672-3791（2014）06（a）-0095-02

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

1 定義

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

2 算法

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

2.1 丁字尺法

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

2.1.1 數學模型

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

式中x，y是li和lj的函數，所以目標函數的決策變量是li、lj和lk。

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

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

2.2 十字線法

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

2.3 模擬退火算法

模擬退火算法相對于以上介紹的兩種算法，增加了解的空間，在一定程度上接受劣質解，提高全局的搜索能力，近似達到全局最優解。該算法是一種解決組合優化問題的隨機搜索技術，利用一個新解產生裝置和接受準則，不斷對當前解迭代，從而達到目標函數最優。

毛坯排樣的目標函數：

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

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

2.4 分層排樣算法

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

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

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

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

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

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

2.4.1 最低輪廓線的分層排樣

設待排矩形零件分別為R1，R2，R3…Rc，以零件的長度值來進行排樣，算法實現步驟：

（1）按零件長度優先，面積次之，從大到小的排序規則進行排樣。

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

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

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

2.5 遺傳算法和蟻群算法

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

3 結語

本文給出的算法容易理解、實用性強，程序實現相對容易，能夠得到相對理想的矩形排樣方式，根據操作實例排樣后，其排樣板材的利用率均可到達90%以上。根據相關文獻，任何算法都有效果不佳的問題存在，針對矩形件排樣，復合算法（排布和搜索算法相結合）的結果比單純排樣的算法好。總之，對矩形件排樣目前還沒有完全理想的方法。人工神經網絡、遺傳算法、模糊系統等一些新穎的優化算法，隨著計算機優化技術的發展與智能優化算法的深入探討，在排樣問題的應用與研究會愈來愈深入，排樣效果也會更理想！

參考文獻

[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].武漢：中國機械工程，1994，5（2）.endprint

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

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

2.5 遺傳算法和蟻群算法

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

3 結語

本文給出的算法容易理解、實用性強，程序實現相對容易，能夠得到相對理想的矩形排樣方式，根據操作實例排樣后，其排樣板材的利用率均可到達90%以上。根據相關文獻，任何算法都有效果不佳的問題存在，針對矩形件排樣，復合算法（排布和搜索算法相結合）的結果比單純排樣的算法好。總之，對矩形件排樣目前還沒有完全理想的方法。人工神經網絡、遺傳算法、模糊系統等一些新穎的優化算法，隨著計算機優化技術的發展與智能優化算法的深入探討，在排樣問題的應用與研究會愈來愈深入，排樣效果也會更理想！

參考文獻

[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].武漢：中國機械工程，1994，5（2）.endprint

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

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

2.5 遺傳算法和蟻群算法

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

3 結語

本文給出的算法容易理解、實用性強，程序實現相對容易，能夠得到相對理想的矩形排樣方式，根據操作實例排樣后，其排樣板材的利用率均可到達90%以上。根據相關文獻，任何算法都有效果不佳的問題存在，針對矩形件排樣，復合算法（排布和搜索算法相結合）的結果比單純排樣的算法好。總之，對矩形件排樣目前還沒有完全理想的方法。人工神經網絡、遺傳算法、模糊系統等一些新穎的優化算法，隨著計算機優化技術的發展與智能優化算法的深入探討，在排樣問題的應用與研究會愈來愈深入，排樣效果也會更理想！

參考文獻

[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].武漢：中國機械工程，1994，5（2）.endprint