吳青松, 楊宏兵, 陳睿卿
(蘇州大學(xué) 機(jī)電工程學(xué)院, 江蘇 蘇州 215137)
隨著紙板行業(yè)自動(dòng)化控制技術(shù)的快速發(fā)展[1-2],原料和人力成本的急劇增加,如何制訂最優(yōu)的切割下料(rectangles coil cutting,RCC)方案以最大程度地降低原紙損耗率已成為紙板加工業(yè)管控的難點(diǎn)。類似問題也廣泛存在于如皮革切割、型材切割等加工領(lǐng)域[3]。切割下料關(guān)鍵點(diǎn)是如何在原材料上合理地排布矩形件(如不同規(guī)格紙板等)的位置,從而在滿足客戶訂單要求的前提下,達(dá)到原材料消耗最小,加工時(shí)間最短,操作復(fù)雜度最小等目標(biāo)。與板材下料不同的是,RCC問題中各卷材的寬度為固定值,但長度視為無限。該問題歸屬于二維開放布局問題[4-5],具備NP難計(jì)算復(fù)雜度。
在多品種、大批量訂單的生產(chǎn)背景下,受限于加工便利性和可行性要求,RCC問題往往采用2階段切割模式(exact 2-stage guillotine cutting pattern)[6],其解稱為下料方案,由一組排樣方式按照一定數(shù)量、一定順序組合而成。排樣方式的寬度等于選用卷材的寬度。各排樣方式由多條條帶平行拼接組成,各條帶采用同質(zhì)帶構(gòu)造方法,即每條條帶內(nèi)僅能同向排布一個(gè)訂單的矩形件。
針對這種生產(chǎn)模式,扈少華等[7]、朱強(qiáng)等[8]均設(shè)計(jì)混合啟發(fā)式規(guī)則,依次排布條帶和各條帶長度,但規(guī)則中閾值的引入導(dǎo)致優(yōu)化過早停止,解的質(zhì)量較低;鄧國斌等[9]基于矩形件價(jià)值設(shè)計(jì),嵌套使用動(dòng)態(tài)規(guī)劃和順序啟發(fā)式算法,可以獲得質(zhì)量較優(yōu)的解,但這是以段尾插入異質(zhì)子條帶,增加加工難度為代價(jià)的;黎鳳潔等[10]68面向可加工性,設(shè)計(jì)基于矩形件價(jià)值修正的剪切排樣算法,在滿足限制性加工工藝的同時(shí)優(yōu)化材料利用率,但該算法僅能應(yīng)用于單規(guī)格卷材問題,與實(shí)際生產(chǎn)應(yīng)用仍存在差距。
立足于多品種、大批量訂單的生產(chǎn)模式,課題組在綜合瓦楞紙板行業(yè)下料問題[11-12]的基礎(chǔ)上,提煉出一類帶強(qiáng)順序限制的一般紙板排樣下料問題。受限于高昂的圖案平均準(zhǔn)備成本,紙板生產(chǎn)過程中排樣方式不重復(fù)使用,為了與其他問題區(qū)別,下文中排樣方式均用圖案(pattern)代稱。
該問題為RCC問題的子問題,并具備以下特性:
1) 可選用多規(guī)格卷材;
2) 強(qiáng)制性的二階段切割生產(chǎn)模式;
3) 高昂的圖案平均準(zhǔn)備成本(置換損失);
4) 圖案順序的強(qiáng)約束關(guān)系。
關(guān)于一般紙板排樣下料問題,只有少量文章[13]534與本文選題相符,其采用多目標(biāo)遺傳算法,同時(shí)優(yōu)化原料利用率和圖案數(shù)量。但該方法染色體設(shè)計(jì)較為繁瑣,面對大規(guī)模算例時(shí)優(yōu)化效果不佳。
目前,該類復(fù)雜優(yōu)化問題的求解方法主要可分為3類,即精確求解、構(gòu)造啟發(fā)式和智能優(yōu)化方法。精確求解方法在求解小規(guī)模問題時(shí)可以快速得到最優(yōu)解,對大中規(guī)模問題,因其時(shí)間和空間復(fù)雜度隨問題維度的增加計(jì)算量呈指數(shù)增長,導(dǎo)致“維數(shù)災(zāi)難”;構(gòu)造啟發(fā)式方法基于調(diào)度規(guī)則快速構(gòu)造可行解,很難保證解的質(zhì)量;智能優(yōu)化方法基于特定操作通過迭代搜索不斷改善解的質(zhì)量,具備適用性廣、結(jié)果魯棒及全局優(yōu)化等特點(diǎn),但易陷于局部優(yōu)解。面對較為復(fù)雜的問題,往往會(huì)采用3者嵌套設(shè)計(jì)優(yōu)化方法[14]。
一般紙板生產(chǎn)模式為多規(guī)格卷材高速切割模式下排樣下料模式,如圖1所示。該模式定義為:在多種規(guī)格(寬度)的卷材集上排布出滿足訂單集要求的圖案集,使得原料使用量最小。各訂單所需紙板的基礎(chǔ)參數(shù)為寬度,長度和需求量。圖案的寬度等于選用的卷材寬度,長度為其內(nèi)排布條帶長度的最大值。
圖1 紙板切割一般工藝示意Figure 1 General process illustration of cutting paperboards
圖案在切割時(shí),切裁機(jī)器先用縱切刀將卷材切成條帶,后由橫切刀將條帶加工成相應(yīng)的工件。橫切刀對條帶進(jìn)行周期性裁剪,故任一條帶僅能排布一種訂單。考慮到實(shí)際紙板生產(chǎn)時(shí)的壓楞需求,本文模型中紙板長寬不能互換生產(chǎn)。
縱橫切刀的數(shù)量與圖案排樣的復(fù)雜度有關(guān)聯(lián)。由于紙板在成型過程中幅寬邊緣的定量不穩(wěn)定,因此卷材在縱切時(shí)需要切邊??紤]切邊,故圖案可排條帶數(shù)等于縱切刀數(shù)量減1;橫切刀數(shù)量為任一圖案內(nèi)能夠排布的訂單數(shù)量上限。
基于紙板生產(chǎn)工藝構(gòu)建數(shù)學(xué)模型,其中涉及到的變量或常量符號如下:
K為卷材集合(各卷材標(biāo)記為k);
I為訂單集合(各訂單標(biāo)記為i);
P為有序圖案集合(各圖案標(biāo)記為p);
B和J分別為切裁機(jī)器的縱切刀數(shù)和橫切刀數(shù);
Wk為卷材k的寬度;
li,wi和di分別為訂單i的長度、寬度與需求量;
Lp為圖案p的長度;
nip為決策變量,訂單i在圖案p上排布的紙板數(shù)量;
cip為決策變量,訂單i在圖案p上排布的條帶數(shù);
hpk為決策變量,若圖案p選用卷材k,則取值為1,否則為0;
xip為中間變量,若訂單i在圖案p上排布則取值為1,否則為0;
rip為中間變量,若訂單i在圖案p正在加工時(shí)處于已生產(chǎn)未完成的狀態(tài),則取值為1,否則為0;
C為圖案平均置換損失(表示為原料損失)。
一般紙板排樣下料數(shù)學(xué)模型可以表述為:
(1)
s.t.
(2)
(3)
(4)
(5)
(6)
(7)
nip,cip∈N,hpk∈{0,1}。
(8)
該模型將一般紙板排樣問題轉(zhuǎn)化為關(guān)于(nip,cip,hpk)3類變量的決策問題,綜合優(yōu)化原料使用量和圖案置換次數(shù),如式(1)所示,其中圖案置換損失被轉(zhuǎn)用原料用量表示。式(2)約束所得方案必須滿足訂單足量生產(chǎn)的要求;式(3)限制圖案內(nèi)條帶寬度之和不能大于其選用卷材的寬度;式(4)~(6)為切紙機(jī)橫、縱切刀數(shù)導(dǎo)致的排樣限制。對于有B個(gè)縱切刀的切割機(jī),其可切割條帶數(shù)為B+1;由于外側(cè)2個(gè)條帶被用于修邊,故圖案內(nèi)排布條帶數(shù)不應(yīng)大于B-1;由于一個(gè)橫切刀同時(shí)切割屬于一個(gè)訂單的所有條帶,故其數(shù)量決定圖案內(nèi)的訂單上限;式(7)表明了圖案的長度計(jì)算方法。式(8)為模型決策變量的取值范圍。
紙板生產(chǎn)過程中存在一類限制訂單多圖案排布和圖案順序的約束。每個(gè)橫切刀座附近都存在一個(gè)紙板暫存區(qū),其在同一時(shí)間僅可存放一個(gè)訂單的紙板,每當(dāng)某個(gè)訂單所需紙板全部被滿足,暫存區(qū)清空并可容納下一個(gè)訂單[15]。
增加式(9)~(10),保證在任何階段,當(dāng)前已進(jìn)行但未完成的訂單的數(shù)量不應(yīng)大于暫存區(qū)數(shù)量,即橫切刀數(shù)。δ表示圖案p正在加工的狀態(tài),δ∈(0,1)。
(9)
(10)
針對模型特點(diǎn),算法將暫存區(qū)虛擬為排樣池,設(shè)計(jì)2層嵌套算法(Two-layer nesting algorithm,TNA)。上層為下料方案層,負(fù)責(zé)決策訂單放入排樣池的順序;下層為圖案排樣層,負(fù)責(zé)生成具體的排樣圖案。中間采用排樣池連接。
為了滿足暫存區(qū)存放限制,設(shè)計(jì)排樣池用于放置預(yù)排樣的訂單,其容量等于暫存區(qū)數(shù)量J。在一個(gè)圖案完成排布并結(jié)單一定數(shù)量的訂單后,這些訂單會(huì)被移出排樣池,同時(shí)一些新訂單會(huì)被添加進(jìn)去,始終保持排樣池內(nèi)在制訂單數(shù)等于其容量。
排樣池的設(shè)計(jì),不僅將模型約束轉(zhuǎn)化為算法框架約束,簡化了保證可行解的計(jì)算復(fù)雜度,同時(shí)也作為2層算法數(shù)據(jù)交互的通道,將下料方案優(yōu)化需要的算法能力拆分,有利于提高算法性能,減少運(yùn)算資源需求。
為了便于下料方案層迭代優(yōu)化,該層采用2階段精確算法。
首先求解寬度方向上條帶排布樣式,其為一維下料等同問題。受排樣池的作用,每個(gè)圖案的條帶排布需要決策的變量數(shù)為J+|K|,且無需考慮橫切刀數(shù)的限制。故采用如下線性規(guī)劃方法:
(11)
s.t.
(12)
(13)
在此基礎(chǔ)上決策每個(gè)條帶上排布的紙板數(shù)量,該數(shù)量最終決定各條帶的長度。兩兩條帶的長度差距越大,其造成的材料浪費(fèi)也就越大(稱為段差損失)。在相關(guān)文獻(xiàn)中,該部分往往采用“最小段差損失原則”[16]作為紙板數(shù)量決策依據(jù)。
在本模型中,排樣方式綜合考慮暫存區(qū)存儲規(guī)則和切換圖案的準(zhǔn)備活動(dòng)損耗,需要滿足:每個(gè)圖案至少存在一個(gè)訂單結(jié)單。因而模型內(nèi)存在一類權(quán)衡:
對于訂單集|I|,若每個(gè)圖案內(nèi)結(jié)單一個(gè)訂單,則共有|P|個(gè)圖案需要處理。在此基礎(chǔ)上,1個(gè)圖案中的訂單結(jié)單數(shù)每多1個(gè),下料方案所需的準(zhǔn)備活動(dòng)次數(shù)|P|也就相應(yīng)減1。因此,段差損失和置換損失存在一定程度的資源互斥。為了減少圖案集的規(guī)模,一些“快要生產(chǎn)完”的訂單可能不會(huì)選擇在段差最小的時(shí)候切割訂單,反之亦然。
3) 步驟3。計(jì)算/更新當(dāng)前圖案的長度:
4) 步驟4。計(jì)算對當(dāng)前訂單(r)條帶采用“最小段差損失原則”截?cái)嗪鬁p少的段差損失R:
5) 步驟5。如果R>C×結(jié)單訂單減少數(shù)量,更新截?cái)鄺l帶上排布的紙板數(shù)量:
借助排樣池和排樣方式2階段精確求解算法,在下料方案層僅需決策放入排樣池的順序,其所需決策變量數(shù)為|I|。
該部分采用Wang等[17]提出的單鏈編碼遺傳算法求解。作為一種群體智能算法,其具備并行、高效和全局搜索等優(yōu)點(diǎn)。根據(jù)已有研究,遺傳算法在處理規(guī)模中等、編碼結(jié)構(gòu)簡單的問題時(shí)具備穩(wěn)定且優(yōu)異的表現(xiàn)。受益于嵌套優(yōu)化結(jié)構(gòu),該部分已滿足上述2點(diǎn)特征。
染色體設(shè)計(jì)采用單鏈實(shí)值編碼模式,長度等于|I|,各基因取值為[1,|I|],染色體規(guī)模N=100。
本算法采用Eclipse編程工具,基于JAVA語言實(shí)現(xiàn)。測試計(jì)算機(jī)為intel i7-6700HQ,主頻2.6 GHz,內(nèi)存16 GiB。
對比算法為:①VLGA——Mellouli等[13]539于2019年提出的矩陣結(jié)構(gòu)變長遺傳算法;②VCIA——黎鳳潔等[10]69于2020年提出的價(jià)值修正迭代算法,采用遺傳算法分配圖案寬度以滿足算法要求。
仿真算例中,訂單參數(shù)(wi,li,di)/(mm,mm,片)分別為在區(qū)間[150,800],[500,2 000],[100,8 000]的離散平均隨機(jī)輸入變量,卷材寬度Wk可選值為2 000,2 100,2 200,2 300,2 400和2 500 mm。
算法結(jié)果評價(jià)指標(biāo)為原料利用率:
式中:QTNA為本文算法的原料利用率;QVLGA/VCIA為對比算法的原料利用率。
在J=3,|I|=500,C=500的算例下,各算法隨迭代次數(shù)的變化如圖2所示。
圖2 原料利用率隨迭代次數(shù)變化對比Figure 2 Comparison of change of raw material utilization with iterations
VLGA算法采用矩陣結(jié)構(gòu)變長編碼。將全部決策變量交由算法尋優(yōu)。解空間過于龐大,不僅初始解質(zhì)量難以提高,同時(shí)收斂速度緩慢,最終解質(zhì)量不穩(wěn)定,難以處理大規(guī)模調(diào)度問題。
本文算法與VCIA算法均在遺傳算法的框架下嵌套算法求解最優(yōu)排樣方式,因而可以在初始解中便獲得較優(yōu)的下料方案解。其中,本文算法初始解較優(yōu)的原因在于其采用線性規(guī)劃算法同時(shí)求得最優(yōu)的圖案寬度分配,而VCIA算法需要通過上層迭代算法分配圖案寬度,解空間相對較大。
該算例中本文算法在30代達(dá)到穩(wěn)定,VCIA算法在65代穩(wěn)定。迭代結(jié)束時(shí)本文算法利用率為99.18%,VCIA算法為99.04%,Δ=+0.14%,本文算法結(jié)果較優(yōu)。
在J=3,|I|=500,迭代次數(shù)E=100的算例下,本文算法與VCIA算法在不同平均置換損失C的結(jié)果對比如表1所示。
表1 不同平均置換損失下算法結(jié)果對比Table 1 Comparison of results under different average changeover losses
當(dāng)C=0時(shí),2種算法均采用“最小段差損失原則”生成排樣方式,本文算法受益于解空間規(guī)模的縮小,存在+0.12%的優(yōu)勢。
隨著平均置換損失的增大,2種算法獲得下料方案的原料利用率均在減小,但算法間的優(yōu)化差距逐漸增大。由于VCIA算法不包含考慮置換損失的優(yōu)化模塊,故可以看出,本文算法可以有效權(quán)衡置換損失與段差損失,以獲取更優(yōu)的結(jié)果。
課題組針對一類帶圖案順序強(qiáng)約束的一般紙板排樣下料問題,提出了基于排樣池交互的嵌套優(yōu)化算法。將模型強(qiáng)約束關(guān)系轉(zhuǎn)化為算法特殊結(jié)構(gòu),并利用其特征縮減低質(zhì)量解空間,通過實(shí)例的數(shù)據(jù)對比,證明了課題組所提算法的高尋優(yōu)能力和穩(wěn)定性。另外,條帶截?cái)鄦l(fā)式規(guī)則也被證明能有效綜合置換損失與段差損失,尋求全局優(yōu)解。本研究算法對紙板制造業(yè)流程優(yōu)化具有重要的參考價(jià)值。在未來的工作中,將會(huì)對其它如皮革加工等類似行業(yè)的排樣下料問題開展進(jìn)一步的研究。