基于改進麻雀算法的銅帶排樣優化應用

顧雨娟，李學兵

（湖北汽車工業學院電氣與信息工程學院，湖北十堰 442000）

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

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

1 問題描述與數學模型

1.1 問題描述

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

圖1 剪切排樣示例圖

1.2 數學模型

一個排樣模型方案由多種排樣方式組合而成，且每種排樣方式均有相應的使用次數，通過限制每種排樣方式的最大使用次數來處理對各個成品需求量的約束，同時防止因過量生產占用過多倉庫庫存。

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

式（1）表示目標函數是使所消耗的卷材面積最?。皇剑?）第一條表示剪切卷材得來的毛胚數量需滿足訂單需求的數量，第二條表示每種排樣方式的最大使用次數約束。

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

2 剪切排樣方案設計

2.1 獲取排樣方式

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

圖2 普通兩階段排樣方式

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

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

圖3 勻質塊兩階段排樣方式

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

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

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

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

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

3 求解算法

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

3.1 問題編碼與解碼

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

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

3.2 適應度函數設計

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

3.3 改進麻雀搜索算法

標準麻雀搜索算法(SSA)是受麻雀群體覓食行為啟發而來[6]，模擬其在自然環境中尋找食物和避開天敵的行為以尋找最優解，可簡單抽象為尋找者－跟隨者模型。尋找者在種群中引領搜尋食物的方向，跟隨者時刻監視尋找者的方向并跟隨移動，二者身份動態變化，在麻雀群體中隨機選取10%～ 20%為預警者，一旦發現有天敵靠近，則向安全區域移動。SSA算法原理為：

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

3.3.1 Singer混沌

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

3.3.2 柯西變異機制

麻雀群體在尋找食物的過程中，跟隨者往往在具有較高適應度值的發現者附近食，進而轉換身份成為發現者，這就會導致算法陷入局部最優，降低算法尋找最優解的精度。為了避免這種情況，在標準麻雀搜索算法中引入柯西變異機制跳出局部最優解，跟隨者位置更新變異公式為：

3.4 算法步驟

步驟1：初始化各個生產參數、麻雀算法參數，調用2.1 節算法獲取排樣方式組合A，單卷使用卷材長度下限U、上限V，排樣方式使用次數上限Q。

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

步驟3：計算每個麻雀位置對應的適應度函數值，并記錄全局最優解和全局最差解。

步驟4：對麻雀種群依據適應度函數值進行排序，選取排序值前30%的麻雀為發現者，其余為跟隨者，用式（10）和式（11）更新發現者和跟隨者位置。

步驟5：在麻雀種群中隨機選取15%個體為預警者，用式（12）對預警者進行位置更新，并更新全局最優解和全局最差解。

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

步驟7：達到最大迭代次數，結束算法，否則繼續迭代步驟3。

4 實驗結果與分析

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

表1 生產實例中的訂單需求數據

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

表2 排樣求解結果

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

圖4 迭代曲線收斂圖

5 結語

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