李秀麗,董春江

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

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

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

本文從實際工程的角度出發(fā)提出一種針對多規(guī)格切割問題的計算方法,利用該方法能夠快速求解出一維下料問題的近似最優(yōu)解,從而實現(xiàn)解決實際工程中一維下料問題的目標(biāo)。

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

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

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

數(shù)學(xué)模型1為以原材料消耗的根數(shù)最少為目標(biāo),具體如下:

(1)

(2)

(3)

數(shù)學(xué)模型2以余料最少為目標(biāo),具體如下:

(4)

(5)

(6)

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

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

2 計算方法

2.1 算法

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

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

(7)

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

(8)

(9)

(10)

(11)

(12)

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

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

圖1 算法的流程圖

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

定義參數(shù)λi為全部切割模式中切割出來的第i種零件出現(xiàn)的次數(shù)。

定義函數(shù)f如下:

(13)

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

(14)

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

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

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

(15)

式中,M0為求解的原材料數(shù)量。

3 算例分析

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

表1 零件的尺寸和數(shù)量

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

表2 計算的切割方案

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

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

表3 最終的切割方案

4 結(jié)語

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

1)本文采用方法結(jié)構(gòu)簡明,易于編程實現(xiàn),對單一原材料問題均能在短時間內(nèi)得到精度較高的近似最優(yōu)解。本文的方法已經(jīng)過實際工程的驗證,可以用于一維下料問題。

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