徐宗煌,徐劍莆,李世龍,林慧雅,許美燕
(1.福州理工學(xué)院 應(yīng)用科學(xué)與工程學(xué)院,福建 福州 350506;2.福州理工學(xué)院 計(jì)算與信息科學(xué)學(xué)院,福建 福州 350506;3.福州理工學(xué)院 商學(xué)院,福建 福州 350506 )
本文討論的問(wèn)題和應(yīng)用的數(shù)據(jù)均來(lái)源于2019 年第十六屆五一數(shù)學(xué)建模競(jìng)賽B 題.木板切割,實(shí)際上是屬于二維下料優(yōu)化問(wèn)題,其主要應(yīng)用在機(jī)械加工、切割下料以及工廠車間布局等制造生產(chǎn)加工領(lǐng)域[1].由于二維下料優(yōu)化問(wèn)題自身的復(fù)雜性,在實(shí)際生產(chǎn)應(yīng)用中,往往會(huì)造成原料的大量浪費(fèi),從而提高產(chǎn)品成本.因此,如何提高原材料的利用率而節(jié)省產(chǎn)品加工成本,具有非常重要的實(shí)用價(jià)值.
從數(shù)學(xué)計(jì)算復(fù)雜性理論看,木板切割的優(yōu)化問(wèn)題屬于NP 完全問(wèn)題[2].目前,國(guó)內(nèi)外許多學(xué)者對(duì)二維下料優(yōu)化問(wèn)題進(jìn)行了諸多研究,主要是采用啟發(fā)式算法、禁忌搜索算法、遺傳算法以及模擬退火算法等大量的優(yōu)化方法.本文基于循環(huán)嵌套啟發(fā)式貪心算法、遺傳模擬退火算法以及價(jià)值修正的順序啟發(fā)式算法等優(yōu)化方法,分別對(duì)切割單個(gè)產(chǎn)品、多個(gè)產(chǎn)品以及考慮生產(chǎn)任務(wù)需求的木板切割優(yōu)化方案進(jìn)行了探究分析.
在問(wèn)題求解過(guò)程中,考慮到實(shí)際情況與簡(jiǎn)化計(jì)算的需要,提出以下假設(shè):1)將木板和產(chǎn)品的長(zhǎng)度和寬度均看作是矩形;2)在切割過(guò)程中,木板厚度和割縫寬度忽略不計(jì);3)該批木板的材質(zhì)分布均勻,不會(huì)影響切割產(chǎn)品的效果;4)所給的木板和產(chǎn)品尺寸均為真實(shí)有效.
在一塊木板上只切割P1 產(chǎn)品,首先利用循環(huán)嵌套式的啟發(fā)式算法,使得沿木板四條邊方向上的利用率達(dá)到最優(yōu);再結(jié)合Packing 問(wèn)題的貪心算法,以木板利用率最高為優(yōu)化目標(biāo),逐層優(yōu)化,最終得到單個(gè)產(chǎn)品的最優(yōu)切割方案.
設(shè)木板尺寸為L(zhǎng)×W,P1 產(chǎn)品尺寸為l×w,要使木板切割盡可能多的P1,應(yīng)盡量利用l 和w 的各種組合,使得L 和W 方向上的利用率盡可能高,即對(duì)L 和W 邊上同時(shí)對(duì)l 和w 進(jìn)行組合優(yōu)化[3],使得木板四條邊的尺寸利用達(dá)到最優(yōu).其優(yōu)化示意圖如圖1.
圖1 基于循環(huán)嵌套啟發(fā)式算法的優(yōu)化示意圖
2.2.1 確定目標(biāo)函數(shù) 顯然,最優(yōu)切割方案的目的是為了使木板的利用率最高,令μ 為木板的利用率;N 為木板切割P1 產(chǎn)品的數(shù)量,則P1 產(chǎn)品的最優(yōu)切割方案的目標(biāo)函數(shù)為
2.2.2 確定約束條件 如圖1 所示,當(dāng)木板上L 邊上切割了m 個(gè)l 邊,則可以再切割n=[(L-ml)/w]個(gè)w邊;而當(dāng)右W 邊上切割了i 個(gè)l 邊,則還可切割w 邊的個(gè)數(shù)為j=[(W-il)/w];同理,可根據(jù)木板上L 邊上l 的個(gè)數(shù)p 和右W 邊上l 的個(gè)數(shù)s 分別確定各自邊上w 的個(gè)數(shù)q 和t,結(jié)合問(wèn)題的要求與已知條件,主要考慮以下3 個(gè)約束條件.
1) 約束條件1
基于保證木板在L 邊和W 邊的利用率,即要保證木板四條邊上所留的空隙不能再放入P1 產(chǎn)品的較小邊,即w 邊,則該約束條件為
2) 約束條件2
基于i 和t 以及p 和n 之間的約束條件為
式(3)中,“[ ]”表示取整符號(hào).
3) 約束條件3
基于保證在切割時(shí)不能出現(xiàn)P1 產(chǎn)品之間發(fā)生干涉的情況,該約束條件為
基于以上分析,利用在貨物裝載和木材下料等領(lǐng)域應(yīng)用廣泛的二維矩形Packing 問(wèn)題的貪心算法[4-7],同時(shí)結(jié)合循環(huán)嵌套式的啟發(fā)式算法[8-9],以木板利用率最高為優(yōu)化目標(biāo),由外及里,逐層優(yōu)化,如圖2 所示.利用MATLAB 編程得到P1 產(chǎn)品的最優(yōu)方案切割圖,如圖3 所示.最優(yōu)的切割方案為:P1 產(chǎn)品的數(shù)量為59 件,木板利用率為98.297 9%.
圖2 模型主程序流程圖
圖3 P1 產(chǎn)品的最優(yōu)方案切割圖
考慮到P1 和P3 產(chǎn)品的切割次序和切割方向是影響木板切割利用率最重要的因素,將遺傳算法和模擬退火算法結(jié)合起來(lái)形成自適應(yīng)遺傳模擬退火算法[10-11].這樣不僅可以大大提高計(jì)算的效率,而且可以避免陷入局部最優(yōu),從而在木板上切割P1 和P3 產(chǎn)品可以取得比較理想的結(jié)果,同時(shí)給出木板利用率由高到低排序的前3 種切割方案.
3.2.1 確定目標(biāo)函數(shù) 通過(guò)以上分析,顯然,最優(yōu)切割方案使木板的利用率最高.令μ為木板的利用率,Ni為切割第i 種產(chǎn)品的數(shù)量,則最優(yōu)切割方案的目標(biāo)函數(shù)為
3.2.2 確定約束條件 同樣的,已知木板尺寸為L(zhǎng)×W,產(chǎn)品尺寸為li×wi(i=1,3),即P1 產(chǎn)品尺寸為l1×w1,P3 產(chǎn)品尺寸為l3×w3,Ni為切割第i 種產(chǎn)品的數(shù)量.而mi表示第i 種產(chǎn)品橫放時(shí)所需的行數(shù),ni表示第i種產(chǎn)品豎放時(shí)所需的行數(shù),xi表示豎放時(shí)一行的產(chǎn)品個(gè)數(shù),yi表示橫放時(shí)一行的產(chǎn)品個(gè)數(shù),ri=0 表示該產(chǎn)品的豎放方式,ri=1 表示該產(chǎn)品的橫放方式.結(jié)合問(wèn)題的要求與已知條件,主要考慮以下兩個(gè)約束條件.
1) 約束條件1
基于保證木板在L 邊和W 邊方向上,P1 和P3 產(chǎn)品尺寸和不能超過(guò)木板尺寸,則該約束條件為
式(6)中,k 表示有k 種產(chǎn)品.
2) 約束條件2
基于在切割P1 和P3 產(chǎn)品時(shí),其數(shù)量關(guān)系必須滿足以下限制約束條件
利用自適應(yīng)遺傳模擬退火算法[12]從一組隨機(jī)產(chǎn)生的初始解(初始群體)開始全局最優(yōu)解的搜索來(lái)產(chǎn)生P1 和P3 產(chǎn)品的切割次序以及切割方向,其主要步驟如下.
3.3.1 設(shè)計(jì)基因編碼 為降低算法復(fù)雜性,采用十進(jìn)制編碼方式對(duì)木板切割進(jìn)行優(yōu)化,設(shè)有n 個(gè)切割產(chǎn)品,則切割產(chǎn)品次序編號(hào)為1,2,…,n,第i 個(gè)切割產(chǎn)品的編號(hào)為i,則這n 個(gè)待切割產(chǎn)品的一個(gè)排列為δ=[x1,x2,…,xn],其中xi表示排列δ 中第i 個(gè)切割產(chǎn)品的編號(hào).由于各個(gè)產(chǎn)品在切割過(guò)程中可以90°旋轉(zhuǎn),因此在排列δ 中為各個(gè)切割產(chǎn)品增加旋轉(zhuǎn)變量ri,即
3.3.2 設(shè)計(jì)適應(yīng)度函數(shù) 問(wèn)題的目標(biāo)在于提高木板的利用率,因此采用最優(yōu)切割方案的目標(biāo)函數(shù)式(5)作為適應(yīng)度函數(shù),即
式(9)中,Xi為種群中的某一個(gè)個(gè)體,代表唯一的產(chǎn)品切割方案,因此f(Xi)即為切割序列Xi的木板利用率,f(Xi)值越大,表明木板切割方案最優(yōu).
3.3.3 交叉和變異操作 采用一種自適應(yīng)調(diào)整交叉和變異概率的方法來(lái)改善算法的行為和性能,同時(shí)利用以下概率調(diào)整公式
來(lái)調(diào)整種群中的某一個(gè)個(gè)體Xi的交叉和變異概率.式(10)中:Pc和Pm分別為該算法的交叉和變異概率;fb(X)、fw(X)和f(Xi)分別表示每一代所有個(gè)體中最優(yōu)、最差個(gè)體以及Xi的適應(yīng)度值.
3.3.4 模擬退火操作 對(duì)經(jīng)過(guò)交叉和變異操作后生成的新種群個(gè)體Xi,基于Metropolis 的接受準(zhǔn)則,計(jì)算新個(gè)體被接受的概率,其接受準(zhǔn)則為
式(11)中,fi(T)為個(gè)體基本變換前適應(yīng)度;fj(T)為個(gè)體基本變換后適應(yīng)度;T 為當(dāng)前溫度.
3.3.5 構(gòu)造初始種群的個(gè)體 一半通過(guò)優(yōu)先級(jí)函數(shù)產(chǎn)生,一半通過(guò)隨機(jī)數(shù)作為優(yōu)先級(jí)產(chǎn)生,優(yōu)先級(jí)函數(shù)公式為
式(12)中,Pi為第i 個(gè)產(chǎn)品基因優(yōu)先級(jí);pr為該產(chǎn)品長(zhǎng)寬比值所占權(quán)重;ps為產(chǎn)品面積所占權(quán)重且滿足pr+ps=1;函數(shù)生成的隨機(jī)數(shù)Ri∈(0,1).
利用MATLAB 編程,將木板、P1 和P3 產(chǎn)品的尺寸輸入,可得到P1 和P3 產(chǎn)品的切割方案,圖4 所示為木板利用率由高到低排序的前3 種方案切割圖.木板利用率前3 的切割方案為:1) P1 產(chǎn)品的數(shù)量為0件,P3 產(chǎn)品的數(shù)量為48 件,木板利用率為99.172 3%;2) P1 產(chǎn)品的數(shù)量為43 件,P3 產(chǎn)品的數(shù)量為13件,木板利用率為98.500 0%;3)P1 產(chǎn)品的數(shù)量為59 件,P3 產(chǎn)品的數(shù)量為0 件,木板利用率為98.297 9%.
在生產(chǎn)任務(wù)需求一定的情況下,考慮到順序啟發(fā)式算法可以在木板切割產(chǎn)品過(guò)程中,隨著產(chǎn)品的生成數(shù)量不斷的增加,其切割所需剩余量也發(fā)生相應(yīng)變化.但傳統(tǒng)的SHP 算法[13-14]在生成木板切割方案時(shí)存在一定的缺陷,它容易使得好的切割方案在前面出現(xiàn),而導(dǎo)致后面的切割方案的材料利用率偏低.采用順序價(jià)值修正策略[15-17],依次生成各個(gè)切割方案,并根據(jù)該切割方案中產(chǎn)生的產(chǎn)品數(shù)來(lái)修正產(chǎn)品生產(chǎn)任務(wù)剩余量,重復(fù)此過(guò)程,直至所有產(chǎn)品剩余的生產(chǎn)任務(wù)均為零,從而得到木板總利用率最高的切割方案,其主要流程圖如圖5 所示.
圖5 順序啟發(fā)式算法流程圖
假設(shè)初始化各個(gè)產(chǎn)品的價(jià)值為產(chǎn)品各自的面積,則生成切割方案可根據(jù)單位面積價(jià)值的大小確定,且產(chǎn)品的當(dāng)前待切割方案為Pj=[a1j,a2j,…,anj],aij為該方式中含產(chǎn)品i 的個(gè)數(shù),i=1,2,…,n.而每生成一個(gè)切割方案都通過(guò)
式(13)中aij>0,si為產(chǎn)品i 的面積;p>1 為控制參數(shù);g1和g2為價(jià)值修正的控制系數(shù),g1+g2=1,且滿足
式(14)中,di為產(chǎn)品i 的生產(chǎn)任務(wù)為產(chǎn)品i 剩余的工作任務(wù)需求;Ω 為隨機(jī)產(chǎn)生,Ω?且
式(13)可寫成
通過(guò)以上分析,利用MATLAB 編程,將木板的尺寸、P1~P4 產(chǎn)品的尺寸以及生產(chǎn)任務(wù)輸入,得到木板總利用率最高的切割方案,圖6 所示為完成P1~P4 產(chǎn)品生產(chǎn)任務(wù)的木板切割方案圖.表1 為考慮生產(chǎn)任務(wù)需求的最優(yōu)切割方案.
圖6 最優(yōu)方案切割圖
表1 考慮生產(chǎn)任務(wù)需求的最優(yōu)切割方案
由表1 可以看出,當(dāng)需要同時(shí)完成P1~P4 產(chǎn)品的生產(chǎn)任務(wù)時(shí),需要7 種切割方案才能使木板的總利用率最高.此時(shí)木板的數(shù)量為139 塊,總利用率為97.757 7%.
本文基于循環(huán)嵌套啟發(fā)式貪心算法、遺傳模擬退火算法以及價(jià)值修正的順序啟發(fā)式算法等優(yōu)化方法,分別對(duì)切割單個(gè)產(chǎn)品、多個(gè)產(chǎn)品以及考慮生產(chǎn)任務(wù)需求的木板切割優(yōu)化方案進(jìn)行了探究分析.在保證思路嚴(yán)謹(jǐn)?shù)那疤嵯?,基于啟發(fā)式算法化繁為簡(jiǎn),大大降低了算法的計(jì)算復(fù)雜度,可操作性強(qiáng),最終得到較為理想的切割方案,對(duì)機(jī)械加工、切割下料以及工廠車間布局等制造生產(chǎn)加工的過(guò)程有一定理論指導(dǎo)和參考價(jià)值.
寧德師范學(xué)院學(xué)報(bào)(自然科學(xué)版)2021年1期