復合勻質塊排樣方式及其生成算法

李華

摘要：討論矩形毛坯無約束的二維排樣問題，提出了復合勻質塊排樣方式及其生成算法，算法設計簡單。排樣時通過枚舉剪切線的位置，將板材分為兩段，每段采用勻質條帶規范排樣方式及其動態規劃算法生成條帶最優布局。通過枚舉法確定板材中段的最優組合，從而使板材的利用率達到最高。采用大量的例題測試，實驗計算結果表明：使用復合勻質塊排樣方式及其生成算法在利用率和計算時間兩方面均有效。

關鍵詞：二維排樣;枚舉;動態規劃;復合勻質塊

0、引言

許多行業如制造業、木材加工業以及金屬板或玻璃板的切割加工業等，都會涉及到材料的分割問題，而矩形零部件排樣是制造行業經常涉及的問題。本文提出一種生成復合勻質塊排樣方式算法。實驗結果表明，本算法在計算時間能夠滿足實際的需要同時，可有效的提高資源的利用率，且采用“一刀切”的切割工藝，與同形塊兩階段排樣方式相比，不會額外增加切割刀數，切割工藝較為簡單。

1、排樣問題的數學模型及相關概念

1.1數學模型

本文討論矩形毛坯無約束的二維棑樣問題（unconstrained two-dimensional cutting problems， UTDC）：采用剪切方式，將的板材切出種毛坯，每種毛坯在板材中出現的次數無約束，第種毛坯的尺寸大小為，價值為（），優化排樣的目標是單張板材所含有的毛坯總價值達到最大。設可行的排樣方式（排樣圖）中含有第種毛坯個，板材和毛坯的尺寸均為整數，為自然數的集合，UTDC的數學模型如下：

UTDC算法與二維下料問題密切相關。針對大規模下料問題，通常采用UTDC算法與線性規劃相結合來求解。所謂二維矩形下料問題（Cutting Stock Problem）是指從已知尺寸的板材中切割出滿足給定尺寸和需求量的一組不同規格矩形毛坯，并使得消耗的板材數達到最小。在確定棑樣方案的過程中，要反復調用UTDC算法，生成排樣方案中的一個或多個排樣方式。因此，要求在合理的計算時間內，UTDC算法能給出高質量的解。

1.2相關概念

1.2.1 同質條帶

同質條帶是指一根條帶中只含有尺寸和方向均相同的毛坯。同質條帶分為水平條帶或豎直條帶，剪切時每一刀從板材上剪切一根水平（X向）或豎直（Y向）條帶。

1.2.2 勻質塊方式

勻質塊的排樣方式，由一組水平和豎直的同質條帶組成。切割的過程分為兩個階段：首先對板材進行一系列條帶切割，剪切時每一刀從板材切下一根水平（X向）或豎直（Y向）條帶。然后，將條帶切割成毛坯。

1.2.3 復合勻質塊方式

復合勻質塊是在勻質塊的基礎進行擴展，用枚舉法確定剪切線的位置，將板材分為上下兩個區域，用動態規劃遞推算法確定每個區域勻質塊的排樣最優布局。

2、算法原理及實現過程

2.1算法原理

動態規劃是處理多階段決策過程最優化的重要的方法，其目標是實現整個過程的整體效果最優。

2.2運用動態規劃實現勻質塊排樣的價值

勻質塊排樣方式是一種剪切的排樣方式，從板材上切下一根X或Y向條帶，將條帶分割成毛坯。排樣過程是切割的逆過程，是條帶拼接的過程，每次總是沿子板材的X向邊或Y向邊拼接上一根條帶，最終形成段的最優布局。

遞推思想：要從板塊上切下一根同質條帶，滿足板塊的所含毛坯總價值最大。為此需要考察所有條帶，按價值最大的原則，選取所需拼接的X向或Y向條帶。

2.3生成復合勻質塊排樣的價值

運用動態規劃原理，求解一維背包問題，確定上下兩段的最優組合，使板材所含毛坯的總價值達到最大。當板材水平放置時，Subject to：P采用勻質塊排樣方式，其中，為排樣方式P含有的第種毛坯的數目，為自然數的集合。要求排放的毛坯互不重疊且不超過板材的邊界。算法2為生成復合勻質塊排樣方式的算法。

其中，為板材所水平放置時所含毛坯的最大價值。通過枚舉水平分割線的位置，將板材分為上下兩段，然后，上下兩段分別調用勻質塊生成算法獲取上下兩段對應的勻質塊的價值，將兩者求和得到當前板材所含毛坯的總價值，若則更新的值，依次進行，最終確定板材的最優布局。

2.4板材復合勻質塊排樣方式算法設計思路

Step1?輸入板材和毛坯的數據

Step2?結合枚舉算法和動態規劃遞推算法，生成復合勻質塊排樣方式算法。

Step3將板材水平放置，調用復合勻質塊排樣方式生成算法，獲取板材包含毛坯的最大價值。

Step4根據板材（水平或豎直放置時）的排樣過程，反向追蹤，獲取復合勻質塊排樣方式中毛坯的最優布局。

3、實驗計算結果

實驗采用Pentium（R） Dual-Core CUP?E5700，主頻3.00GHz，內存2.0GB的計算機進行測試。

3.1 毛坯、板材方向固定

假定毛坯和方向固定的情況下，采用文獻[3-4]中的50道例題作為實驗數據，每題包含30種毛坯，板材的尺寸為，毛坯的長度和寬度均在內均勻分布，每種毛坯的單價等于其面積。用材料的利用率衡量排樣方式的質量（它等于排樣方式中所含毛坯的總面積與板材的面積之比）。

4、結束語

本文給出了枚舉和遞推技術相結合的復合勻質塊排樣算法，考慮了毛坯和板材方向固定以及同時旋轉90°情況下，板材所含毛坯的最大價值，算法設計思想簡單，在合理的計算時間內，提高了材料利用率。綜合實際的應用需求，將本算法與線性規劃相結合，可以求解矩形毛坯的下料問題。

參考文獻：

[1]崔耀東.生成矩形毛坯最優T形排樣方式的遞歸算法[J]. 計算機輔助設計與圖形學學報.2006，18 （1）：125-127

[2]崔耀東，季君，曾窕俊.生成矩形毛坯最優兩段排樣方式的遞歸算法[J].南京航天航空大學學報.2006，38 （1）： 112-114.

[3][黃玲，崔耀東.矩形毛坯勻質條帶排樣方式及其生成算法 [J]. 桂林理工大學學報，2010，30 （2）：292-295]