一維下料問(wèn)題的快速計(jì)算方法研究

李秀麗,董春江

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

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

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

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

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

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

一維下料問(wèn)題的數(shù)學(xué)模型總結(jié)歸納起來(lái)可以分為兩類:一類是以原材料消耗的總根數(shù)最少為目標(biāo)函數(shù),另一類是以余料總長(zhǎng)度最短為目標(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ù)量。

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

2 計(jì)算方法

2.1 算法

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

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

(7)

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

(8)

(9)

(10)

(11)

(12)

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

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

圖1 算法的流程圖

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

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

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

(13)

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

(14)

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

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

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

(15)

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

3 算例分析

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

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

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

表2 計(jì)算的切割方案

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

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

表3 最終的切割方案

4 結(jié)語(yǔ)

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

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

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