基于改進(jìn)麻雀算法的銅帶排樣優(yōu)化應(yīng)用

顧雨娟，李學(xué)兵

（湖北汽車工業(yè)學(xué)院電氣與信息工程學(xué)院，湖北十堰 442000）

具有多品種小批量市場供貨特點(diǎn)的銅加工企業(yè)的銅帶產(chǎn)量和銅帶消費(fèi)量巨大，成材率的提高對(duì)此類企業(yè)降低生產(chǎn)成本、提高競爭實(shí)力十分重要。目前在銅合金的成分設(shè)計(jì)和制備加工工藝等方面已經(jīng)取得了一定的研究成果，銅帶的質(zhì)量得到保證，所以影響成材率的關(guān)鍵工序在于剪切工序，選取的排樣方案直接決定產(chǎn)出成品的多少[1]。銅加工企業(yè)大多生產(chǎn)以訂單為導(dǎo)向的定制產(chǎn)品，一卷母帶原料會(huì)根據(jù)不同的訂單需求剪切出十幾種子卷，不合理的排樣方案會(huì)直接導(dǎo)致后續(xù)包裝工序工作量增加，難以及時(shí)交付成品。因此，尋找一個(gè)高效的排樣方案對(duì)剪切工序來說至關(guān)重要，剪切工序排產(chǎn)優(yōu)化實(shí)際成為在最優(yōu)排樣方案下的排產(chǎn)問題。

優(yōu)化剪切工序的排樣模型方案屬于一種具有較高計(jì)算復(fù)雜度的NP-hard帶有工藝約束的矩形件排樣優(yōu)化問題，目前的研究雖然都以提高成材率為目標(biāo)，但未能同時(shí)解決涉及剪切工序的“一刀切”約束和長度浮動(dòng)約束的問題[2-5]。采用勻質(zhì)塊的思想和罰函數(shù)處理這兩種約束，最后采用Singer混沌序列提高初始種群多樣性結(jié)合柯西變異提升后期尋優(yōu)精度，自動(dòng)生成排樣方案，在保證交付期限的情況下提高了成材率。

1 問題描述與數(shù)學(xué)模型

1.1 問題描述

剪切工序可以分為兩個(gè)階段：第1階段使用圓盤剪，根據(jù)排樣方式對(duì)母帶銅卷進(jìn)行排刀橫向剪切；第2 階段使用切頭剪，縱向剪切母帶后分切出若干子卷。其中，第2 階段縱剪母帶至完全切斷即為“一刀切”工藝約束，剪切排樣示例圖如圖1。將n種寬度、長度無限長的卷材，剪切出m種長度為li、寬度為wi、需求量為bi的矩形毛胚，母帶卷料剪切得來的子卷寬度固定，長度在一定范圍內(nèi)浮動(dòng)，要求在約束條件內(nèi)，尋找一個(gè)剪切優(yōu)化排樣模型方案使消耗的卷材面積最小。

圖1 剪切排樣示例圖

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

一個(gè)排樣模型方案由多種排樣方式組合而成，且每種排樣方式均有相應(yīng)的使用次數(shù)，通過限制每種排樣方式的最大使用次數(shù)來處理對(duì)各個(gè)成品需求量的約束，同時(shí)防止因過量生產(chǎn)占用過多倉庫庫存。

設(shè)共有m種待剪矩形毛胚，n種可供排樣選擇的卷材，e種待考察的排樣方式，建立數(shù)學(xué)模型：

式（1）表示目標(biāo)函數(shù)是使所消耗的卷材面積最小；式（2）第一條表示剪切卷材得來的毛胚數(shù)量需滿足訂單需求的數(shù)量，第二條表示每種排樣方式的最大使用次數(shù)約束。

符號(hào)定義：Z為下料方案中消耗卷材的總面積；C=[c1,c2,…,ce]T，cj為按照第j種排樣方式剪切矩形毛胚使用卷材的面積，1 ≤j≤e；X=為按照第j種排樣方式剪切矩形毛胚的使用次數(shù)，1 ≤j≤e；Q=[q1,q2,…,qe]T，qj為按照第j種排樣方式剪切矩形毛胚的使用次數(shù)上限，1 ≤j≤e；B=[b1,b2,…,be]T，當(dāng)1 ≤i≤m時(shí)，bi表示第i種毛坯的需求數(shù)量，當(dāng)(m+1)≤i≤(m+n)時(shí)，考慮到不限制每種可供排樣卷材的使用次數(shù)，令bi=0，故=0；A：m行e列矩陣，當(dāng)1 ≤i≤m時(shí)，aij為按照第j種排樣方式剪切卷料時(shí)得到第i種毛坯的數(shù)量；當(dāng)(m+1)≤i≤(m+n)時(shí)，aij為按照第j種排樣方式剪切矩形毛胚使用第（i-m）種卷材，考慮到一種排樣方式只能使用一種卷材

2 剪切排樣方案設(shè)計(jì)

2.1 獲取排樣方式

采用普通兩階段排樣方式（圖2）雖然也可以滿足“一刀切”的工藝約束，但后續(xù)仍需要進(jìn)一步剪切加工為成品矩形毛胚，無疑會(huì)給企業(yè)增加更多的切割成本同時(shí)延長交付時(shí)間。

圖2 普通兩階段排樣方式

實(shí)際剪切生產(chǎn)環(huán)境中，子卷被剪切后需要立即完成包裝操作，不同規(guī)格的成品由不同的箱子進(jìn)行裝箱，這種排樣方式也會(huì)增加包裝工序的復(fù)雜性。求解模型算法需要調(diào)用本節(jié)算法獲取排樣方式，每種排樣方式選取的待排毛胚種類過多會(huì)影響算法的整體性能。采用普通兩階段排樣方式“一刀切”下來會(huì)產(chǎn)生較多的廢料，不利于提高成材率。

為了簡化實(shí)際生產(chǎn)中的切割工藝并減少剪切卷材后續(xù)的包裝工序的操作復(fù)雜度，同時(shí)提升求解算法性能且盡量減少廢料面積，采用勻質(zhì)塊的思想進(jìn)行矩形毛胚的排樣布局（圖3），各個(gè)勻質(zhì)塊中僅含同有一種規(guī)格的矩形毛胚，由切頭剪豎直“一刀切”下來的待剪毛胚最多兩種最少一種，當(dāng)前用來排樣的卷材的剩余的不可使用寬度小于當(dāng)前待排毛胚的最小寬度，并規(guī)定卷材的寬度利用率達(dá)到90%以上。

圖3 勻質(zhì)塊兩階段排樣方式

設(shè)：可供排樣的卷材寬度有n種寬度，N={W1,W2,…Wn} ；待排毛坯寬度有m種寬度，M={w1,w2,…wm} ；當(dāng)前待排毛胚的最小寬度為w'(w'∈M)；當(dāng)前使用排樣的卷材寬度為W'(W'∈N)。當(dāng)排樣方式僅含有一種毛胚，設(shè)第j種排樣方式由第1 種毛坯剪切，則第j種排樣方式使用次數(shù)上限由式（3）求出，其中ceil()函數(shù)為向上取整函數(shù)。

式（4）表示設(shè)第j種排樣方式只剪第1 種毛胚時(shí)的數(shù)量約束。

當(dāng)排樣方式含有兩種毛胚，設(shè)第j種排樣方式由第1、2 種毛坯剪切，則第j種排樣方式使用次數(shù)上限由式（5）求出。

式（6）表示設(shè)第j種排樣方式剪第1、2 種毛胚各自的數(shù)量約束。

在實(shí)際生產(chǎn)環(huán)節(jié)中，包裝工序同時(shí)進(jìn)行單卷卷稱重，工人根據(jù)子卷的卷重是否在訂單要求的最低卷重和最高卷重范圍之間判斷是否可以發(fā)貨，所以在拿到訂單時(shí)需要對(duì)相關(guān)數(shù)據(jù)進(jìn)行預(yù)處理，根據(jù)母帶卷料的銅合金密度、卷料厚度，計(jì)算出每種規(guī)格的成品交付時(shí)的最大長度和最小長度，即實(shí)際長度在最小長度和最大長度范圍內(nèi)即可。為了求取各個(gè)排樣方式的有效長度，首先求出各個(gè)排樣方式的下限長度U={u1,u2,…ue}，上限長度V={v1,v2,…ve}，對(duì)二者取交集得出每種排樣方式的長度范圍。

3 求解算法

首先根據(jù)2.1 節(jié)排樣算法獲取每種排樣方式的待剪毛胚種數(shù)、待剪毛胚數(shù)量以及排樣方式長度范圍，然后以改進(jìn)麻雀搜索算法作為求解算法。

3.1 問題編碼與解碼

將每種排樣方式使用對(duì)應(yīng)卷材的總面積(每種排樣方式使用卷材的面積C×每種排樣方式的使用次數(shù)X)作為決策變量，其中一個(gè)解可以表示為P={p1,p2,…pe}，pj表示第j種排樣方式剪切卷材的總面積，則pj需要同時(shí)滿足式（7）和式（8），其中1 ≤j≤e,1 ≤t≤n,k∈N+，Wt為第j種排樣方式使用的卷材寬度。

式（7）為P的可行解范圍，式（8）為矩形毛胚的長度浮動(dòng)約束，以及限制排樣方式的使用次數(shù)必須為整數(shù)。

3.2 適應(yīng)度函數(shù)設(shè)計(jì)

f為適應(yīng)度函數(shù)值，f越小，下料方案使用卷材的總面積越少，卷料利用率越高，適應(yīng)度越好。對(duì)于不滿足式（7）和式（8）約束的解，將會(huì)生成一個(gè)罰函數(shù)，將第j種排樣方式生成的罰函數(shù)值設(shè)為為yj，令yj?pj，罰函數(shù)加到原適應(yīng)度函數(shù)值上，通過比較原適應(yīng)度函數(shù)的值，不符合約束的將會(huì)成為劣解并被淘汰。

3.3 改進(jìn)麻雀搜索算法

標(biāo)準(zhǔn)麻雀搜索算法(SSA)是受麻雀群體覓食行為啟發(fā)而來[6]，模擬其在自然環(huán)境中尋找食物和避開天敵的行為以尋找最優(yōu)解，可簡單抽象為尋找者－跟隨者模型。尋找者在種群中引領(lǐng)搜尋食物的方向，跟隨者時(shí)刻監(jiān)視尋找者的方向并跟隨移動(dòng)，二者身份動(dòng)態(tài)變化，在麻雀群體中隨機(jī)選取10%～ 20%為預(yù)警者，一旦發(fā)現(xiàn)有天敵靠近，則向安全區(qū)域移動(dòng)。SSA算法原理為：

式（10）為發(fā)現(xiàn)者位置更新方式。t和T分別為當(dāng)前迭代次數(shù)和最大迭代次數(shù)，α為0 到1 之間的隨機(jī)數(shù)，Q為服從正態(tài)分布的隨機(jī)數(shù)，R和ST分別為捕食過程中的預(yù)警值和安全值，R∈[0,1]和ST∈[0.5,1]。當(dāng)R

3.3.1 Singer混沌

Singer映射是一種典型的混沌映射，相比于其他混沌映射，其數(shù)學(xué)表達(dá)式簡單，參數(shù)較少，可使初始解更加均勻地分布，在一定程度上提升種群多樣性，并且在迭代初期加快搜索速度，其表示形式為：

3.3.2 柯西變異機(jī)制

麻雀群體在尋找食物的過程中，跟隨者往往在具有較高適應(yīng)度值的發(fā)現(xiàn)者附近食，進(jìn)而轉(zhuǎn)換身份成為發(fā)現(xiàn)者，這就會(huì)導(dǎo)致算法陷入局部最優(yōu)，降低算法尋找最優(yōu)解的精度。為了避免這種情況，在標(biāo)準(zhǔn)麻雀搜索算法中引入柯西變異機(jī)制跳出局部最優(yōu)解，跟隨者位置更新變異公式為：

3.4 算法步驟

步驟1：初始化各個(gè)生產(chǎn)參數(shù)、麻雀算法參數(shù)，調(diào)用2.1 節(jié)算法獲取排樣方式組合A，單卷使用卷材長度下限U、上限V，排樣方式使用次數(shù)上限Q。

步驟2：用公式（13）對(duì)麻雀種群進(jìn)行初始化，使之生成均勻分布的混沌序列。

步驟3：計(jì)算每個(gè)麻雀位置對(duì)應(yīng)的適應(yīng)度函數(shù)值，并記錄全局最優(yōu)解和全局最差解。

步驟4：對(duì)麻雀種群依據(jù)適應(yīng)度函數(shù)值進(jìn)行排序，選取排序值前30%的麻雀為發(fā)現(xiàn)者，其余為跟隨者，用式（10）和式（11）更新發(fā)現(xiàn)者和跟隨者位置。

步驟5：在麻雀種群中隨機(jī)選取15%個(gè)體為預(yù)警者，用式（12）對(duì)預(yù)警者進(jìn)行位置更新，并更新全局最優(yōu)解和全局最差解。

步驟6：對(duì)跟隨者按一定概率用式（14）進(jìn)行柯西變異，若變異后適應(yīng)度更高則替代原來位置，否則不變。

步驟7：達(dá)到最大迭代次數(shù)，結(jié)束算法，否則繼續(xù)迭代步驟3。

4 實(shí)驗(yàn)結(jié)果與分析

為了檢驗(yàn)求解算法的合理性，測試了來源于湖北精益高精銅板帶有限公司的實(shí)際生產(chǎn)數(shù)據(jù)，通過對(duì)客戶訂單數(shù)據(jù)進(jìn)行預(yù)處理后得到單卷最小長度、最大長度、成品寬度和需求量見表1，可供排樣的卷材為厚度0.1 mm，寬度分別為420 mm 和350 mm，銅含量99.95%以上，含氧量0.01‰以下，導(dǎo)電量大于98%IACS的TP2紫銅帶。

表1 生產(chǎn)實(shí)例中的訂單需求數(shù)據(jù)

仿真實(shí)驗(yàn)運(yùn)行在MatlabR2022a 上，設(shè)定種群大小為20，最大迭代次數(shù)500，分別獨(dú)立運(yùn)行5 次，將遺傳模擬退火算法(GASA)、基于排擠的小生境遺傳算法(DC)[8]、改進(jìn)麻雀搜索算法(SCSSA)三種算法在相同環(huán)境中進(jìn)行對(duì)比運(yùn)算，結(jié)果見表2。

表2 排樣求解結(jié)果

為了分析對(duì)比結(jié)果，卷料利用率迭代收斂曲線圖如圖4。經(jīng)過Singer 混沌結(jié)合柯西變異的改進(jìn)麻雀算法SCSSA 算法在卷材利用率、尋找最優(yōu)解能力等方面明顯高于另外兩者算法，這是因?yàn)镚ASA 算法在尋找最優(yōu)解后期有易陷入局部最優(yōu)解的缺陷，DC 算法在處理相似解的判斷和替換能力上表現(xiàn)欠佳，而SCSSA 引入的柯西變異機(jī)制能夠限制陷入局部最優(yōu)解，提高尋優(yōu)能力。

圖4 迭代曲線收斂圖

5 結(jié)語

針對(duì)基于剪切優(yōu)化排樣模型方案的滾動(dòng)排產(chǎn)問題，以消耗最少母帶卷料面積為目標(biāo)建立了排樣優(yōu)化模型，依據(jù)排樣結(jié)果來進(jìn)行滾動(dòng)排產(chǎn)。從排樣方式上講，基于一種勻質(zhì)塊的思想設(shè)計(jì)矩形毛胚的排入順序，不僅有利于指導(dǎo)工人在實(shí)際生產(chǎn)中簡化卷材剪切工藝，也減少了后續(xù)成品包裝工序的操作復(fù)雜度，加快了交付進(jìn)程；從求解算法上講，使用改進(jìn)的麻雀搜索算法進(jìn)行求解，相比其他算法在卷料利用率方面有更優(yōu)秀的表現(xiàn)，全局尋優(yōu)和局部尋優(yōu)能力更強(qiáng)。由于實(shí)際剪切工序在分剪時(shí)不可避免地出現(xiàn)帶頭帶尾損耗，在今后的研究中將進(jìn)一步通過數(shù)據(jù)分析，并在客戶接受的一定程度內(nèi)考慮成品卷重、數(shù)量超發(fā)減發(fā)的情況，建立相應(yīng)的優(yōu)化模型使成材率更加精確。