湯洪濤，鄭之恒，李英德，陳青豐，江偉光

(浙江工業(yè)大學 機械工程學院，浙江 杭州 310023)

0 引言

型材下料車間(Profile Blanking Workshop, PBW)是指對鋼制原材料進行切、沖、鉆等基礎加工處理的車間，通常由多條輥道流水線組成。一臺套整機產(chǎn)品所需的不同型號的型材通常需要在多條線分頭下料，一根型材在產(chǎn)線上通常切割成不同規(guī)格的零件以供不同臺套整機產(chǎn)品使用。型材經(jīng)切割后通常需根據(jù)后道工序生產(chǎn)要求按整機產(chǎn)品成套分揀，并送往后續(xù)車間生產(chǎn)。為了提高分揀效率和智能化水平，一種新的使用自動導引小車(Automated Guided Vehicle, AGV)進行成套分揀的新模式在下料車間出現(xiàn)。車間由數(shù)條切割下料生產(chǎn)線組成，需切割的型材通過輥道上料，經(jīng)過切割加工后，從輥道下線至特定的料框中。AGV搬運各個料框分別在各條下料線的下線點之間移動，確保同一臺套物料放入同一個料框，并最終將完成分揀的料框搬運至成品庫。

考慮到型材重量和尺寸導致的搬運不便，下料時通常需要將一根型材全部切割完畢，不留余料，在生產(chǎn)排程時需以一根原材料為一組進行調(diào)度，因此可以歸為成組調(diào)度(Group Scheduling, GS)。在傳統(tǒng)GS研究方面，LOGENDRAN等[1]首次對具有序列不相關準備時間和一致并行機類型的混合流水車間成組調(diào)度問題進行了研究，分析了在單準備時間和多準備時間兩種情況下GS問題的性質(zhì)特征，并基于此對3種不同的組合啟發(fā)式算法的性能進行了對比分析；隨后，LOGENDRAN等[2-5]對無關并行機、序列相關等各種情況下的組調(diào)度都進行了研究；袁帥鵬等[6-7]對兩階段流水車間成組調(diào)度問題進行了研究；隨后又針對無關并行機類型的混合流水車間成組調(diào)度問題，在考慮序列相關準備時間的情況下，以最小化最大完工時間[8]為目標設計了一種改進的候鳥優(yōu)化算法。傳統(tǒng)成組調(diào)度的研究針對各種不同加工環(huán)境下的流水車間，而型材下料車間成組調(diào)度(Profile Blanking Workshop GS，PBWGS)與一般采用成組調(diào)度的作業(yè)車間相比，其工序相對較少，加工工藝簡潔，無需考慮工藝間的調(diào)度，且節(jié)拍相對穩(wěn)定，完工時間趨向于固定，若使用AGV進行成套分揀則需要型材生產(chǎn)排程與AGV調(diào)度密切配合，且成套分揀的需求將導致更復雜的AGV路線、更靈活的AGV調(diào)度方案、以及更高的AGV使用成本。

在AGV調(diào)度研究方面，研究倉庫環(huán)境中的路徑以及搬運時間優(yōu)化的多AGV調(diào)度問題較多[9-10]；ZHANG等[11]研究了矩陣式制造車間多臺AGV的調(diào)度問題，設計了改進的迭代貪婪算法以優(yōu)化運輸成本；為了解決考慮運輸時間和多機器人的作業(yè)車間調(diào)度問題(Job Shop Scheduling Problem, JSSP)，NUORI等[12-13]開發(fā)了兩種新的元啟發(fā)式雜交算法；AFSAR[14]等提出一種主/從方法來解決具有運輸限制的JSSP；AGV的應用及其成本的控制已經(jīng)進入了研究的視野，但成組調(diào)度與AGV分揀的結(jié)合還仍有必要進行深入研究，面向PBW綜合考慮生產(chǎn)排程與AGV調(diào)度，研究其調(diào)度方法有重要的理論意義和實用價值。

針對該問題，本文以最小化AGV使用成本為目標建立數(shù)學模型，在考慮型材下料車間實際加工生產(chǎn)特點的情況下提出一種采用多層編碼方式的改進遺傳算法，該算法采用帶加工屬性的多層編碼方式區(qū)分加工要求，用不同層的屬性來區(qū)分原料、臺套和零件并分層交叉變異，設計了不同的鄰域搜索機制來構(gòu)造不同層的鄰域結(jié)構(gòu)，并提出了基于禁忌表的雙層協(xié)同優(yōu)化策略。最后分別與基礎遺傳算法、基礎蟻群算法、變鄰域改進遺傳算法和改進蜂群算法進行綜合對比，驗證了本文算法的有效性與魯棒性。

1 問題描述和數(shù)學模型

1.1 問題描述

型材下料車間加工工藝如圖1所示，型材從原材料庫到達各條平行的下料流水生產(chǎn)線，經(jīng)過切割下料后，由機械手抓取切割后的零件放入AGV搬運的料框，將車間不同產(chǎn)線切割的屬于同一臺套的零件放入同一個料框中，最后以框為單位齊套入庫。假設一個由3條產(chǎn)線構(gòu)成的下料車間同時生產(chǎn)多個臺套產(chǎn)品，如圖2所示為一臺AGV依次經(jīng)過2—3—2—1—3號產(chǎn)線的5個下線點裝載1號臺套零件的過程，其中：連續(xù)的方框表示同一根型材，數(shù)字表示零件所屬的臺套編號，虛線框表示下線緩存區(qū)位置，帶箭頭連線表示AGV依次在各個產(chǎn)線的下線點裝載下線的零件。

成材率是型材下料最重要的考慮因素，車間企業(yè)資源計劃(Enterprise Resource Planning, ERP)系統(tǒng)安排每日加工任務時，首先根據(jù)最省型材原材料的原則進行初步排樣。型材的生產(chǎn)排樣涉及到每一根型材的先后切割順序和每一根型材內(nèi)部各段零件的先后切割順序。本文研究AGV分揀的PBWGS問題是在車間ERP系統(tǒng)經(jīng)過初步排樣后對型材切割順序及一根型材內(nèi)部各段的切割順序的二次調(diào)度，可描述如下：

(1)下料車間抽象為多臺并行排列的性能不同的切割機；(2)訂單在上級ERP系統(tǒng)按最省原材料原則初步排樣；(3)同一根型材的各段零件只能在同一臺機器上切割；(4)零件切割完成后在緩存區(qū)等待機械手抓取下線進入料框；(5)同臺套的零件放入同一料框，料框由AGV背負在產(chǎn)線間移動，接收下線的零件；(6)同一臺套的料框的每次移動可以由任意一臺AGV完成。

本文優(yōu)化的目標是最小化AGV的使用成本。AGV的使用成本可以簡化為由電池折舊成本和用電成本兩部分組成。電池折舊成本可以視作與充放電[15-17]次數(shù)正相關，充放電次數(shù)與AGV的有效工作時間正相關；用電成本也與AGV的有效工作時間正相關。因此，最終將AGV使用成本轉(zhuǎn)換為AGV的有效工作時間(即搬運行走時間和舉升/放下料框時間)。針對該問題，建立數(shù)學模型并設計合適的求解算法。

1.2 數(shù)學模型

根據(jù)以上對下料車間的描述，建立以下假設和約束：

(1)任一時刻一臺機器只能切割一段零件，且每段零件只能被約定的機器所切割；(2)切割過程不可中斷，不考慮設備故障；(3)零時刻，所有型材均可切割；(4)假設所有設備切割一段零件用時相同；(5)料框中的零件需齊套存儲；(6)一個料框可以容納一臺套零件，并且可以由一臺AGV移動；(7)忽略AGV行走過程中的擁堵等待；(8)假設各條產(chǎn)線平行布置，依次順序編號。

為描述該車間作業(yè)問題，對數(shù)學模型中的主要參數(shù)作如下定義：

表1 參數(shù)定義匯總表

優(yōu)化的目標函數(shù)為：

(1)

(2)

s.t.

(3)

i,j,q∈N*；

(4)

xij+M(1-Api)+M(1-Zih)+

M(1-Zph)≥Cp+tijh,i,j,p∈N*；

(5)

xpj+M(Api)+M(1-Zih)+M(1-Zph)≥

Ci+tpjh，i,j,p∈N*；

(6)

(7)

m∈[1,Ik],i,j∈N*,k∈[1,K],h∈[1,H]；

(8)

i,j∈N*,k∈[1,K],h∈[1,H]。

(9)

其中：式(1)表示優(yōu)化目標1為AGV所有轉(zhuǎn)運任務完成所經(jīng)過的路程之和最短。其中，加工完成順序相鄰的兩段零件所處的加工產(chǎn)線間的距離為需要AGV接運的距離。式(2)表示優(yōu)化目標2為加工完成時間順序相鄰的同臺套的兩個零件所屬的加工產(chǎn)線不同，這種情況出現(xiàn)的次數(shù)最少，即物料下線時需要AGV搬運料框前往另一條產(chǎn)線承接物料的次數(shù)最少。式(3)和式(4)表示同一根型材的兩段零件切割完工時間之差大于等于后一段的切割加工時間。式(3)和式(4)共同確定了同一根型材的各段零件切割的先后順序。式(5)和式(6)表示同一條產(chǎn)線上后一根型材的任意一段的切割完工時間大于等于前一根型材的完工時間與該段型材的加工時間之和。式(5)和式(6)共同確定同一條產(chǎn)線各根型材之間的加工順序。式(7)表示一根型材只能由一條產(chǎn)線加工；式(8)將屬于同臺套的零件按加工完成的先后順序排序，完工時間相同的按所在產(chǎn)線編號從小到大排序。式(9)確定了同臺套的零件的加工產(chǎn)線。

2 改進遺傳算法的設計

由于采用AGV分揀的PBWGS問題具有強NP難的特點[18]，常采用遺傳算法求解該類問題[19-21]，但也存在過早收斂和后期搜索效率低的問題，因此，結(jié)合研究問題的特點，本文提出了改進的遺傳算法，采用三層編碼，第一層表示型材型號，第二層表示零件所屬的臺套，第三層表示加工屬性，同時在交叉變異時，將第一層與第二層分開處理，防止兩者的同時變化丟失部分優(yōu)秀基因，以增強全局搜索能力，并提出了不同的鄰域搜索方式以構(gòu)造兩層不同的鄰域，最后以雙層禁忌表的方式將兩層鄰域協(xié)同優(yōu)化，提高算法的效率和適用性。算法流程圖如圖3所示。

2.1 染色體的編碼與解碼

本文采用如圖4所示的帶加工屬性的多層矩陣式編碼，廠區(qū)有3條生產(chǎn)線，各自的任務互不相同。每層產(chǎn)線編碼有三層，從上至下，第一層為原材料型號層，表示先下料的是外徑50 mm，壁厚4 mm的圓鋼，后續(xù)為外徑50 mm，壁厚3 mm的圓鋼；第二層為臺套屬性層，表示第一根圓鋼被切為4段，分別用于臺套編號為第3、1、3、4的整機；第三層為加工屬性層，表示切割的4段零件長度分別是2 000 mm，1 800 mm，2 600 mm，3 300 mm。

2.2 適應度計算

如前文所述，本文優(yōu)化的目標是最小化AGV的使用成本，最終可以轉(zhuǎn)換為AGV的有效工作時間。相鄰產(chǎn)線間轉(zhuǎn)運一次需要完成兩次轉(zhuǎn)彎進接運區(qū)舉升料框的動作，完成一次動作耗時為t，在產(chǎn)線間移動速度為v，產(chǎn)線間距為b。因此總時間為：

(10)

適應度函數(shù)值與染色體被選擇概率成正比，AGV成本越低，表示優(yōu)化效果越好，染色體越應該在進化過程中被保留，因此將適應度函數(shù)設置為：

(11)

2.3 初始種群生成

為了增加種群的豐富度，將第一層型材的下料順序隨機打亂并同時隨機打亂第二層型材內(nèi)部零件的排列順序，以生成初始種群。

2.4 迭代過程

2.4.1 選擇

采用輪盤賭規(guī)則對各個染色體進行選擇，染色體的適應度值與被選擇概率成正比。其選擇概率為：

(12)

式中aj表示種群中的染色體。

為防止最優(yōu)個體沒有被選擇到的特殊情況，本文采用精英選擇模式，直接將最優(yōu)個體放在新種群的第一位。

2.4.2 交叉

交叉算子：

(13)

其中：Pc為個體的交叉概率，Pc1和Pc2為最大、最小交叉概率，f′為個體適應度值，fmax為種群中的最大適應度值，favg為種群的平均適應度值。

由于染色體第一層的順序變化和第二層的順序變化都會對適應度值產(chǎn)生影響，兩者同時交叉容易丟失最優(yōu)解，本文采用第一層和第二層分開交叉的模式，50%的個體進行第一層的交叉，50%的個體進行第二層的交叉，兩層交叉均采用兩點交叉，如圖5所示以一條產(chǎn)線的染色體為例說明第一層交叉的步驟。其中P1和P2代表兩個父代個體，C1和C2分別代表其對應的交叉后的子代個體，具體步驟如下：

步驟1在種群中隨機找到兩個個體P1和P2，并在第一層隨機找到兩個交叉位置點a和b；

步驟2將父代個體P2的a和b之間的第一層基因O50×4和O102×6賦值給P1的子代個體C1相應的位置，同時將P1的a和b間的第一層基因O60×3.5和O50×3賦值給P2的子代個體C2相應的位置。而C1的O50×4和O102×6的第二、三層屬性繼承P1中的O50×4和O102×6的第二、三層屬性。同理，C2的O60×3.5和O50×3的第二、三層屬性繼承P2中的O60×3.5和O50×3的第二、三層屬性。

步驟3子代個體C1其他空缺基因位全部從P1中繼承，按其在P1中的位置左右順序在C1中從左到右填補。以圖5所示為例，子代個體C1已經(jīng)通過交叉確定了a、b之間O50×4和O102×6兩段基因，然后將P1中剩余的O60×3.5、O50×3和O89×4三段基因依次填補在C1的3段空缺基因位上。同理，子代個體C2也從P2中繼承并填補。

步驟4同理，對于種群中的其他個體也進行交叉操作，得到新的種群。

這樣的方式避免了某些可能的優(yōu)秀基因在交叉過程中丟失，如圖5中，若C1直接繼承了P2的a與b間的三層基因位，C2繼承了P1的a與b間的三層基因位，則兩個子代中的O50×4都將從P2繼承，此時P1的O50×4的后兩層屬性就會在該過程中丟失。

第二層交叉的步驟與第一層類似：

步驟1如圖6所示，在種群中隨機找到P1和P2兩個個體，并在P1中隨機選擇一段基因，如第一層編號為O50×4的基因。

步驟2在P2中找到第一層編號同樣為O50×4的基因(若有多個第一層編號為O50×4的基因，則應該選擇第二層同樣具有4,2,2,1,3,5,5,1這8個片段的基因)。

步驟3在基因O50×4的后兩層染色體中隨機確定兩個交叉位置a和b。

步驟4將P1的O50×4基因第二、三層的a和b之間的片段交叉給C2的O50×4基因第二、三層的a和b之間，同理可將P2的基因片段對應交叉給C1。

步驟5將C1的O50×4基因其他缺失位按照P1的O50×4基因中的剩余基因片段依次補齊。同理補齊C2的基因，完成第二層的交叉。

步驟6同理，對于種群中的其他個體進行交叉操作，得到新的種群。

2.4.3 變異

變異算子：

Pm=

(14)

其中：Pm1、Pm2為最大、最小變異概率。

變異操作是為了保持種群的多樣性，防止算法早熟。變異操作同樣分兩階段進行。首先，將每段基因的3層視為一個整體，隨機選擇兩個基因位互換位置，完成第一階段變異；其次，隨機選擇某一段基因的第二和第三層，將其排列順序做倒序互換，完成第二階段變異。通過變異，在較強的局部搜索能力下，兼顧了全局搜索的能力[22]。

2.4.4 鄰域解的生成

為了提高算法的局部搜索能力和效率，根據(jù)PBWGS問題的特點，設計了插入、反轉(zhuǎn)、打亂等3種鄰域構(gòu)造方式。同時引入禁忌搜索算法中的禁忌概念，以雙層禁忌表的形式將兩層鄰域協(xié)同優(yōu)化為完整的鄰域解。鄰域解的生產(chǎn)流程如圖7所示，在第一層鄰域結(jié)構(gòu)設計和第二層鄰域結(jié)構(gòu)設計的基礎上，構(gòu)建協(xié)同優(yōu)化策略生成最終鄰域解。

(1)第一層鄰域結(jié)構(gòu)設計

根據(jù)本文的染色體設計，染色體中各基因的第一層確定了各并行生產(chǎn)線上各型材的順序，選用插入操作來構(gòu)造鄰域結(jié)構(gòu)，步驟如下：

1)隨機選擇一個染色體，假設含有m+1個基因。在第一層中隨機選擇一個基因位。

2)將選擇的基因位插回該染色體中，共有m+1種插法，可以構(gòu)造m+1個鄰域結(jié)構(gòu)。其中基因的第二和第三層屬性跟隨第一層的移動而移動，但內(nèi)部不發(fā)生變化。

3)計算m+1種鄰域結(jié)構(gòu)的適應度值，選擇其中最優(yōu)者作為第一層的鄰域結(jié)構(gòu)。

(2)第二層鄰域結(jié)構(gòu)設計

第二層確定了型材內(nèi)各段零件的加工順序，采用反轉(zhuǎn)和打亂的方式構(gòu)造鄰域結(jié)構(gòu)。

1)隨機選擇一個染色體，在第一層中隨機選擇一個基因位，提取該基因位的第二層基因。

2)在第二層基因中隨機選擇兩個位置，將兩個位置間的基因采用反轉(zhuǎn)和打亂的方式構(gòu)造鄰域結(jié)構(gòu)。第三層屬性跟隨第二層移動。

3)計算各鄰域結(jié)構(gòu)的適應度值，選擇最優(yōu)者作為第二層的鄰域結(jié)構(gòu)。

(3)組合生成鄰域解

以上將染色體的第一、二兩層分開構(gòu)建鄰域結(jié)構(gòu)，但兩層屬性有很強的關聯(lián)性[8]，對適應度值都有決定性作用，因此兩層鄰域結(jié)構(gòu)的有效組合對算法的性能至關重要。為此，本文設計了基于禁忌表的協(xié)同優(yōu)化策略來生成最終鄰域解，思路如下：

1)隨機選擇染色體，隨機選擇第一層一個基因位，判斷該基因是否已經(jīng)在禁忌表1中，若是，則更換基因位;否則將其放入禁忌表1，然后構(gòu)造第一層鄰域結(jié)構(gòu)；

2)選擇第一層隨機基因位，判斷該基因是否已經(jīng)在禁忌表2中，若是，則更換基因位;否則將其放入禁忌表2；

3)將選擇的第一層基因位下的第二層基因構(gòu)造鄰域結(jié)構(gòu)；

4)混合兩層鄰域結(jié)構(gòu)，生成鄰域解，其中第二層屬性跟隨第一層移動，第三層跟隨第二層；

5)重復上述步驟，生成足夠數(shù)量的鄰域解。

以圖6所示的P1染色體為例，鄰域解的生成過程如圖8所示。

3 實驗驗證

以某塔吊型材下料車間為案例，驗證算法的可行性。以該車間使用的某型號叉車AGV為例，該AGV使用鋰電池，容量為24 V 210 Ah，負載情況下可運行時間約為6 h，直線速度v=1 m/s，產(chǎn)線間距3.2 m，轉(zhuǎn)彎進接運區(qū)舉升料框耗時30 s。則

(15)

鑒于企業(yè)實際數(shù)據(jù)保密的要求，如表2所示的算例數(shù)據(jù)基于實際數(shù)據(jù)進行適當?shù)靥幚怼Ｆ渲校核憷?為某日的實際生產(chǎn)數(shù)據(jù)，算例1和算例2為處理后的數(shù)據(jù)。

表2 算例參數(shù)表

3.1 參數(shù)設置

參數(shù)設置與問題規(guī)模有關，且對實驗結(jié)果有顯著影響，本文選用經(jīng)典的遺傳算法參數(shù)[23]，并結(jié)合大量實驗結(jié)論[24]，確定了自適應變異參數(shù)。本文最終的參數(shù)設置如表3所示。

表3 算法運行參數(shù)表

3.2 仿真實驗結(jié)果分析

為了驗證算法有效性，將本文算法與基礎遺傳算法、基礎蟻群算法、變領域改進遺傳算法[25]，以及改進蜂群算法[26]在3種批量數(shù)據(jù)下進行對比?；A遺傳算法采用種群規(guī)模50，迭代次數(shù)200，交叉概率0.9，變異概率0.1?；A蟻群算法采用啟發(fā)式因子α=1，β=5，信息揮發(fā)系數(shù)ρ=0.6，信息素強度因子Q=1 000進行計算。由于作為對比的各種算法編碼方式與本文模型不匹配，本文多層編碼第一層和第三層屬性只在于區(qū)分型材原料和零件參數(shù)，不會對迭代結(jié)果產(chǎn)生影響，因此將各算法原來的實數(shù)編碼統(tǒng)一改為本文的多層編碼，在此基礎上對5種算法進行綜合比對，每個算法進行10次運算，取最優(yōu)值，仿真實驗環(huán)境采用MATLABR2018a仿真軟件，Intel(R)Core(TM)i5-9400F,2.90GHz處理器，內(nèi)存為16.00GB，結(jié)果如表4所示。不同規(guī)模數(shù)據(jù)在5種算法下迭代效果對比如圖9所示。

表4 5種算法在不同大小規(guī)模下的實驗結(jié)果對比

由表4和圖9可以看出，相對于隨機生成的調(diào)度方案，幾種算法均有顯著改善，但改善效果仍有差異。本文采用多層編碼的改進遺傳算法在優(yōu)化效果和效率上都優(yōu)于其他算法。變鄰域改進遺傳算法在前期效果顯著，但隨著問題規(guī)模的加大，鄰域結(jié)構(gòu)越來越復雜，迭代出更優(yōu)解的時間大幅增加，收斂速度較慢；改進蜂群算法在全局搜索能力上有一定優(yōu)勢，但同樣存在隨著問題規(guī)模的加大導致收斂速度慢的不足。本文的改進遺傳算法在求解采用AGV分揀的PBWGS問題上，首先采用多層編碼的方式，相較其他算法，能更好地區(qū)分型材、臺套和零件的關系。其次，在交叉變異過程中采用分層式處理的方式，避免優(yōu)秀基因的丟失，增強了全局搜索能力。最后采用鄰域搜索機制來構(gòu)造不同層的鄰域結(jié)構(gòu)，并提出了基于禁忌表的雙層協(xié)同優(yōu)化策略，能有效構(gòu)造出高質(zhì)量的鄰域結(jié)構(gòu)，禁忌表的采用也減少了無效鄰域的生成，大大增強了局部搜索能力。與其他算法相比，既有更好的收斂效果，也能很好地表達復雜的加工信息， 在該類問題的求解上具有顯著優(yōu)勢。

實際生產(chǎn)應用中，算法的魯棒性至關重要。相較于算法的優(yōu)越性，每一次的求解高效且穩(wěn)定對生產(chǎn)更為重要。本文對算法10次重復運行的結(jié)果進行統(tǒng)計分析，繪制箱線圖如圖10所示。

從圖10可以看出，改進遺傳算法在求解采用AGV分揀的型材下料車間成組調(diào)度問題上，在不同的批量數(shù)據(jù)下，都能保持較高的魯棒性，更適合企業(yè)實際需求[27]。

4 結(jié)束語

本文針對型材下料車間智能化程度低、效率低、成本高的問題，采用了AGV分揀的新方式，并在此基礎上優(yōu)化AGV分揀的成本，對采用AGV分揀的型材下料車間成組調(diào)度問題建立混合整數(shù)規(guī)劃模型，并針對該問題開發(fā)了改進的遺傳算法。采用第一層表示型材型號、第二層表示零件所屬臺套號、第三層表示零件加工屬性的多層編碼方式，提出將第一層和第二層分層交叉變異的方法，同時采用插入、反轉(zhuǎn)、倒序的方式構(gòu)造不同層的鄰域結(jié)構(gòu)，并使用含有雙層禁忌表的協(xié)同優(yōu)化策略生成鄰域解。通過算例將本文算法與其他算法進行對比，表明所設計算法在解決該問題上具有顯著優(yōu)勢和較好的魯棒性。

采用AGV分揀的型材下料車間調(diào)度問題涉及較多要素，如AGV數(shù)量約束等，實際生產(chǎn)中存在多條線可加工相同型材的情況等，以及本文將型材排樣結(jié)果作為調(diào)度的輸入條件，而型材排樣方案與型材切割調(diào)度兩者可以結(jié)合做聯(lián)合優(yōu)化等，這些都可以作為進一步研究的方向。