矩形毛坯排樣中條帶長度的約束處理

摘要:該文的排樣問題是根據剪沖工藝的要求抽象出來的。剪沖工藝是指分兩步將板材分割成毛坯:第一步用平剪床將板材切成條帶;第二步采用剪或沖的方式，將條帶切成毛坯。所考慮的工藝約束包括最小條帶長度約束和最大條帶長度約束，排樣方式中條帶的長度，必須在最小和最大條帶長度約束值之間。該文對基本的動態規劃算法加以改造，使之能夠處理最小和最大條帶長度約束，并在C++環境下，開發出同尺寸矩形毛坯排樣系統UR。利用這個軟件，進行了大量的例題測試，得出對生產實踐具有指導意義的結論。

關鍵詞:排樣;動態規劃;條帶約束

中圖分類號:TP301 文獻標識碼:A 文章編號:1009-3044(2009)15-4066-03

Strip Length Constraints of Rectangle Cutting Patterns

SUN Ying1， CUI Yao-dong2， GAO Yong-li1

(1.Department of Computer Science， Chuxiong Normal University， Chuxiong 675000， China; 2.Department of Computer Science， Guangxi Normal University， Guilin 541004， China)

Abstract: The cutting stock problem discussed comes from the requirement of the shearing and punching process， in which the plate is divided into finished items within two stages. A guillotine shear cuts the plate into strips at the first stage， and a punching press or a guillotine shear cuts the strips into items at the second stage. Constraints are put on the minimum and maximum strip lengths. This paper extends the dynamic programming algorithm， so that it can deal with the strip length constraints. Based on the algorithm， a software system is developed with C++ language. A large number of test problems are used to test the algorithm. Conclusions helpful to the production practice are obtained from the computational results.

Key words: cutting stock; dynamic programming; strip length constraint

1 引言

許多企業或公司都需要將板材切割成小的矩形毛坯，以滿足外部或內部用戶的需求。一些用戶，特別是那些從事大批量生產的用戶，可能需要相同尺寸的大量矩形毛坯。這樣，就只能采用單一排樣方式，即:同一張板材中只允許排入一種尺寸的毛坯。

目前，許多國內外學者對矩形毛坯單一排樣的算法進行了深入的研究，提出了許多優秀的算法，常見的有動態規劃算法、分支定界算法、多項式時間算法、連分數算法、連分數分支定界算法[1-5] 。這些算法可以說各有千秋，算法效率各不相同。在這些算法中，動態規劃算法、多項式時間算法和連分數算法只能實現毛坯數量最優性，不能保證切割工藝最優性;分支定界算法、連分數分支定界算法和改進后的動態規劃算法，能同時實現毛坯數量最優性和切割工藝最優性。

2 條帶長度的約束問題

生產中常采用剪切和沖裁相結合的方式制作零件毛坯，在剪切階段用剪床將板材切成條帶，在沖裁階段用沖床從條帶上沖出毛坯。當條帶長度較小時，條帶數量通常較多，需要頻繁地將條帶供給到沖床的工作臺上(進給條帶)，增加下料工作量;并且在采用手工進給條帶方式時，條帶長度較小，降低了沖裁環節的安全性。當條帶長度較大時，可能增大進給條帶的難度，例如，長度大的條帶剛性差，沖裁時準確定位較困難。因此，剪切或沖裁工藝要求條帶長度在一定范圍內分布，即條帶長度應不小于最小條帶長度約束值，不大于最大條帶長度約束值。

這樣，有兩方面的原因產生條帶最小長度約束。其一是條帶沖裁的安全性;其二是通過條帶最小長度約束減少沖裁時的條帶更換次數。前面提到的各種算法，有些不能處理條帶最小長度約束，有些則需要在修改后，方能處理條帶最小長度約束。

同樣，現有算法也不能直接處理條帶最大長度約束。對剪床刀刃長度約束的處理，已有成熟的算法[6-8]。這些算法不能直接處理條帶最大長度約束。其原因是這些算法假定板材寬度不超過刀刃長度。如果板材寬度超過刀刃長度，則認為不存在可行解。但對于最大條帶長度約束，允許板材寬度超過所允許的最大條帶長度。

對于矩形毛坯，不考慮條帶長度約束得到的排樣方式，如果其中某根條帶超過最大條帶長度約束值，可以用剪床將該條帶分割成二根或多根短條帶，它們的長度都不超過最大條帶長度約束值。也就是說，如果是矩形毛坯，現有算法可以直接生成可行排樣方式，只要允許對長條帶再次剪切分割即可。剪切分割的特點是剪切分割線是直線。本文算法要處理最大條帶長度約束，主要是考慮到所述算法可以推廣到同尺寸沖裁件條帶的剪切排樣問題，而在沖裁件條帶排樣方式中，允許對長條帶進行剪切分割，可能導致條帶中所含毛坯數的減少，因為毛坯在條帶中可能是嵌套排列的(圖1)。這樣就可能降低下料利用率。因此在優化計算過程中，就應該限制所采用的條帶長度都不超過最大條帶長度約束值;而不是先不考慮條帶長度約束得出排樣方式，然后再將長條帶剪切成短條帶。

3 能夠處理條帶長度約束問題的動態規劃算法

動態規劃算法以其簡單，容易實現而經常被使用，而且在計算中比其它算法具有一定的優勢。在基本的動態規劃算法中，沒有考慮條帶長度約束。但是，在實際生產中采取剪沖工藝下料時，會對條帶提出最小和最大長度約束。本論文所研究的問題也是采用動態規劃算法，下面就對動態規劃算法和如何利用動態規劃算法來進行條帶長度的約束處理作介紹。

3.1 基本動態規劃模型

文獻[1]中給出如下基本動態規劃遞推公式，可用于確定最優排樣方式，使整張板材中所含毛坯數達到最大:

式中l和w分別表示毛坯的長度和寬度，F(x，y)表示矩形x×y中所能包含的最大毛坯數。

上式給出最優規范多級方式。根據規范多級方式的概念，每一刀都從當前板材上切下一根水平或豎直的條帶。公式(1)的含義是，為使矩形x×y中所能包含的毛坯數達到最大，可以考慮如下兩種情況:

情況1):從上邊切去一根長為x的條帶，其中所含毛坯數為int(x/w)。切下這根條帶后的剩余矩形尺寸為x×(y-l)，含毛坯F(x，y-l)個。按這種切割方式，當前矩形x×y中含毛坯F(x，y-l)+int(x/w)。

情況2):從右邊切去一根長為y的條帶，其中所含毛坯數為int(y/w)。切下這根條帶后的剩余矩形尺寸為(x-l)×y，含毛坯F(x-l，y)個。按這種切割方式，當前矩形x×y中含毛坯F(x-l，y)+int(y/w)。

取上述兩種切割方式中含毛坯數較多的，就是當前矩形所含毛坯數的最大值。下面設n(x)表示長為x的條帶中所含毛坯數，則公式(1)可重寫為:

(x，y)=max{F(x，y-l)+n(x)，F(x-l，y)+n(y)}(2)

其中函數n(x)由下式確定:

n(x)=int(x/w)

3.2 條帶長度約束的處理

設hmin和hmax分別為最小和最大條帶長度約束值。為處理條帶長度約束，按下式定義函數n(x):

n(x)=0，若x

公式(3)的含義是，如果條帶長度小于最小條帶長度，其中不能排入毛坯，可通過令n(x)=0實現這一控制;如果條帶長度在最小條帶長度和最大條帶長度約束值之間，就讓這根條帶所含毛坯數n(x)=int(x/w)，表示其中實際可排入的毛坯數;如果條帶長度大于最大條帶長度，假定下料時可將其修剪成為等于最大條帶約束值的條帶，其中所含毛坯數n(x)=int(hmax/w)。進行上述處理后，就可以按遞推公式(1)確定最優規范排樣方式。

4 例題計算結果

在這里，統一設板材尺寸3000×2400，毛坯尺寸 245×180，單位為mm。

4.1 例題數據說明

本節測試題共20道，見表1。這些例題數據均來源于文獻[7]中的表3，也可以通過如下網址下載:

http://www.gxnu.edu.cn/Personal/ydcui/English/AMM3547.htm

在這里，均用ID來表示測試問題序號，l表示毛坯長度，w表示毛坯寬度，L表示板材長度，W表示板材寬度。排樣方式中所含毛坯數為n0，所含條帶數為ns，Smin表示排樣方式中所含最少條帶數，Smax表示排樣方式中所含最多條帶數，下料利用率為u。

4.2 最小條帶長度約束的影響

4.2.1 最小條帶長度約束的例題測試

首先，我們用上述20個題進行測試，分別給出最小條帶為0、100、200、300、400、500時，在相應的板材上所能切割的最大毛坯數目和板材的下料利用率，用此來分析和觀察最小條帶長度約束對同尺寸矩形毛坯排樣結果的影響，此時沒有最大條帶長度的約束。

4.2.2 最小長度約束例題測試結果分析

利用上述實驗得到的數據，統計出最小條帶變化的6個階段的平均下料利用率和平均條帶數，見表2。其中，平均下料利用率的計算公式用下面的公式(4)。

在處理條帶長度約束時，當條帶長度超過最大條帶約束值時，無論該條帶有多長，其中毛坯數都規定為n(x)=int(hmax/w)。為了說明分段排樣的必要性，首先引入下料利用率的定義:

式中u為下料利用率，n0為板材中所含毛坯數。

從表2，我們可以看到，隨著最小條帶長度約束的增加，板材的下料利用率有所下降。但最小條帶長度從0到500的變化過程中，下料利用率的變化不是很大。平均條帶數目隨著條帶最小長度約束值的增加而有所減少。

4.3 最大條帶長度約束的影響

4.3.1 最大長度約束的例題測試

下面仍然取上述20個問題，在沒有最小條帶約束的情況下，讓最大條帶依次為800、1200、1600、2000、2500、3000、4000和5000，給出在相應的板材上所能切割的最大毛坯數目，并計算出板材的下料利用率，用此來分析和觀察最大條帶長度的約束對同尺寸矩形毛坯排樣結果的影響。

4.3.2最大長度約束例題測試結果分析

利用上述實驗中所測試的詳細數據，統計出最大條帶變化的8個階段的平均下料利用率和平均條帶數，見下表3。其中，平均下料利用率的計算公式仍然用公式(5)。

從表3，我們能得出:隨著最大條帶長度約束值的增加，板材的利用率有所提高，最大條帶長度的約束為800時，利用率為最低，最大條帶長度的約束為5000時，利用率最高，當超過5000時，就不會再起作用了，因為這里所用的20個測試題，板材長度都小于5000，不可能出現長度達到5000及以上的條帶。在最大條帶長度約束從800到5000的間斷變化過程中，約束長度為800，1200和1600時，板材的利用率受到一定程度的影響，而超過了1600后影響就很小了，基本上趨于穩定。同時，表3中也統計出了與最大條帶長度約束值相對應的平均條帶數，隨著約束長度的增加，平均條帶數減少了。

4.4 同時有最小條帶和最大條帶長度的約束時的排樣情況

下面，我們給出當最小條帶長度為500，最大條帶長度為2000時的排樣結果。板材尺寸3330×1539，毛坯尺寸162×80，分2段2000×1330，輸出排樣圖為圖3。板材尺寸4804×1918，毛坯尺寸180×103，分3段2000×1980×824，輸出排樣圖為4。

5 結論

通過對本論文實驗計算結果進行分析，可以得出如下對生產實踐具有指導意義的結論:

1) 條帶長度約束的存在，會使下料利用率下降。這一結論很容易理解，因為約束的存在，只會使排樣方式中所含毛坯數不變或下降，而不會引起毛坯數的增加。在實際生產活動中，應注意改進下料工藝，盡量不對條帶長度形成約束。

2) 最小條帶長度約束值增加，會使排樣方式中所含毛坯數下降，但其在一定范圍內變化時(例如0-500)，對下料利用率的影響不大。因此，實際生產中為保證沖裁工藝的安全性，可以對最小條帶長度施加約束。

3) 最大條帶長度約束值減小，會使排樣方式中所含毛坯數下降。特別是當減小到一定值時，會引起下料利用率的明顯下降。對于本論文例題，最大條帶長度約束值以不小于1600為好。對于實際生產，通過改進下料工藝，可以改變最大條帶長度約束值。因此，可以應用本文算法進行分析，確定合適的最大條帶長度約束值。通過權衡改過工藝的費用和因下料利用率提高所得到的收益，進行改進工藝的投資決策。

參考文獻:

[1] 崔耀東.計算機排樣技術及其應用[M].北京:機械工業出版社，2004:317.

[2] Agrawal P K.Minimizing trim loss in cutting rectangular blanks of a single size form a rectangular sheet using orthogonal guillotine cuts[J].European Journal of Operational Research，1993，64(3):410-422.

[3] Arslanov M Z.Continued fractions in optimal cutting of a rectangular sheet into equal smallrectangles[J].European Journal of Operational Research，2000，125:239-248.

[4] Cui Y，Zhou R.Generating optimal cutting patterns for rectangular blanks of a singleSize[J].Journal of the Operational Research Society，2002(53):1338-1346.

[5] Tarnowski A G，Terno J and Scheithauer G.A polynomial Time Algorithm for the guillotinepallet loading problem[J].INFOR，1994(32):275-287.

[6] 崔耀東，周儒榮.單一尺寸矩形毛坯排樣時長板的最優分割[J].計算機輔助設計與圖形學學報，2001，13(5):434-437.

[7] Cui Y D.Dynamic programming algorithms for the optimal cutting of equal rectangles[J].Applied Mathematical Modelling，2005(29):1040-1053.

[8] 崔耀東，張春玲，趙誼.同尺寸矩形毛坯排樣的連分數分支定界算法[J].計算機輔助設計與圖形學學報，2004(2).