一維下料問題的快速計算方法研究

李秀麗,董春江

(1.青中景建設(青島)有限公司,山東 青島 266033;2.青島新華友建工集團股份有限公司,山東 青島 266101)

一維下料問題在機械、水利、電力、土木工程、航空航天等工程技術和工業生產領域有著重要和廣泛的應用[1-2]。例如,機械工程中鋁合金和棒材的下料、建筑行業中鋼筋和型材的下料、家具制造業中板材的下料等。一種好的下料方案可以減少原材料的損耗,進而降低企業的生產成本。

近年來,隨著計算機技術的發展和優化算法的進步,一維下料問題的研究也在不斷深入[3-5]。針對不同工程問題,研究人員采用不同的優化算法來解決下料問題,目前已取得明顯效果[6-9]。目前,許多學者研究方向主要針對零件種類和數量較少的問題。當切割規格較多或者切割數量較大時,切割方式數量呈爆炸增長,問題的復雜性劇增,計算機的計算量是巨大的,不能在極短的時間內找到最優解。因此,如何采用近似算法快速求解滿意解或者近似最優解成為一維下料問題研究的一個重要方向[10]。

本文從實際工程的角度出發提出一種針對多規格切割問題的計算方法,利用該方法能夠快速求解出一維下料問題的近似最優解,從而實現解決實際工程中一維下料問題的目標。

1 數學模型

單一規格原材料的一維下料問題具體數學描述如下:假設有足夠多的長度為L的某種原材料,現需要切割n種數量不等的零件,長度為li的零件數量為bi,其中,i=1,2,…,n。求解如何下料使得所使用的原材料的數量最少。其中,L>max{li},i=1,2,…,n。Xj為第j種切割方式重復的次數,Aij為第j種切割模式切割出來第i種零件的數量。

一維下料問題的數學模型總結歸納起來可以分為兩類:一類是以原材料消耗的總根數最少為目標函數,另一類是以余料總長度最短為目標函數。目前,各種數學模型大多是在這兩類模型的基礎上建立的。

數學模型1為以原材料消耗的根數最少為目標,具體如下:

(1)

(2)

(3)

數學模型2以余料最少為目標,具體如下:

(4)

(5)

(6)

式中,Xj≥0且Xj∈n,j=1,2,…,M;M為切割模式的種類;n為所需零件的數量。

對于所需零件的數量n較小的問題,數學模型1和數學模型2的直接求解還是比較簡單的。但當所需零件的數量n較大時,也就是說切割模式的種類十分巨大時,要直接求解上述問題是十分困難的。本文通過對上述數學模型1進行改進,從而求解出一維下料問題的近似最優解。

2 計算方法

2.1 算法

從工程項目的實際考慮,當所需零件的數量n較大時,單根原材料的切割種類不能太多。如果單根原材料的切割種類不限制,一方面會導致切割過程的操作過于復雜,另一方面會極大地增加原材料加工的切割方式,這樣都會極大地增加實際的加工成本。為限制單根原材料的切割種類,設置參數切割模式限值為NC,用于控制單根原材料的切割種類。切割材料時單根材料的余料不能過多,為限制單根原材料的余料,設置參數余料限值L0,用于控制單根原材料的余料值。

定義一個參數δj(i),使其滿足如下條件:

(7)

對數學模型1進行改進,增加合理的約束條件,具體數學模型公式如下:

(8)

(9)

(10)

(11)

(12)

式中,L0是單根原材料的余料限值;NC是單根原材料切割模式限值。

具體的算法流程圖如圖1所示。

圖1 算法的流程圖

2.2 余料限值L0和切割模式限值NC

定義參數λi為全部切割模式中切割出來的第i種零件出現的次數。

定義函數f如下:

(13)

Nl=max{L-[L/l]·li}

(14)

式中,[L/l]是L/li的整數部分。

余料限值L0是優化算法中一個重要的參數,如果L0的取值過小,會導致篩選出的切割模式不能包含全部的切割零件;如果L0的取值過大,會導致篩選出的切割模式過多,會極大地增加計算量。在進行L0的取值時可以參考Nl的數值進行選取。

定義下料方案的原材料利用率為η,即

(15)

式中,M0為求解的原材料數量。

3 算例分析

某一實際工程項目需要切割一批鋼管,所需鋼管的尺寸和數量見表1,現庫存有充足的長度為6 m的原材料,要求給出精確的下料方案(不考慮切開損失)。

表1 零件的尺寸和數量

當分別選取NC為1、2、3時,選取不同的參數L0獲得15種不同的切割方案,切割方案見表2。從表2中可知,當L0的取值較小時,本文的方法會出現無解的情況,主要的原因是獲得切割模式未包含全部零件。從表2中不難發現,隨著L0取值的增加,切割模式的數量會增加,當L0增加到一定數值時,原材料利用率η不再增加。隨著NC取值的增加,原材料利用率η不會增加,當NC選取1、2、3時,原材料利用率η分別為69.4%、94.5%和97.9%。

表2 計算的切割方案

通過上述分析,當NC為1和2時,原材料利用率η還沒有達到最優,在實際使用本文方法切割下料時,建議NC的取值為3。當L0的取值較小時,計算會出現無解的情況,當L0的取值較大時,計算量會增加。因此,建議L0的取值策略如下:初始選取L0為100 mm,若經計算后f的數值為0,則依次選取L0為200 mm、300 mm……直到f的數值為1。

當NC選取3時,選取的L0不同會得到不同的切割方案,比較表2中的5種方案,當L0選取200 mm時得到的切割方案的模式數量最少為18種,是5種方案中切割模式種類數量最少的,可以減少切割的工藝。因此,在實際工程中可以選取方案13作為工程中的最終切割方案,最終的下料切割方案見表3。

表3 最終的切割方案

4 結語

本文結合實際工程通過改進原有的一維下料問題的數學模型,在滿足零件需求量的情況下,使原材料的使用量最少。

1)本文采用方法結構簡明,易于編程實現,對單一原材料問題均能在短時間內得到精度較高的近似最優解。本文的方法已經過實際工程的驗證,可以用于一維下料問題。

2)實際應用效果表明,本文方法能夠明顯提高材料的利用率,是企業降低成本的有效途徑,能夠很好地指導現場生產,在土木、機械、電力、航空航天等領域具備廣闊的市場應用前景和潛在經濟效益。