吳青松， 楊宏兵， 陳睿卿

(蘇州大學(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]。

1 問題描述

一般紙板生產(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ù)量上限。

2 模型

基于紙板生產(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為圖案平均置換損失(表示為原料損失)。

2.1 基礎(chǔ)模型

一般紙板排樣下料數(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)為模型決策變量的取值范圍。

2.2 暫存區(qū)約束(圖案順序強(qiáng)約束)

紙板生產(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)

3 算法設(shè)計(jì)

3.1 算法總框架

針對模型特點(diǎn)，算法將暫存區(qū)虛擬為排樣池，設(shè)計(jì)2層嵌套算法(Two-layer nesting algorithm，TNA)。上層為下料方案層，負(fù)責(zé)決策訂單放入排樣池的順序；下層為圖案排樣層，負(fù)責(zé)生成具體的排樣圖案。中間采用排樣池連接。

3.2 排樣池

為了滿足暫存區(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)算資源需求。

3.3 排樣方式生成方法(圖案排樣層)

為了便于下料方案層迭代優(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ù)量：

3.4 訂單下料順序優(yōu)化算法(下料方案層)

借助排樣池和排樣方式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。

4 實(shí)驗(yàn)分析

4.1 仿真環(huán)境、基礎(chǔ)數(shù)據(jù)及分析指標(biāo)

本算法采用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為對比算法的原料利用率。

4.2 仿真結(jié)果對比

在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é)果。

5 結(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)一步的研究。