苗培仁，李曉東，胡 凱，劉 睿，劉 壯

(1.江陰市輝龍電熱電器有限公司，江蘇 江陰 214401；2.江蘇省柔性電加熱器工程技術(shù)研究中心，江蘇 江陰 214401； 3.江蘇省研究生工作站，江蘇 江陰 214401)

0 引言

柔性作業(yè)車(chē)間調(diào)度問(wèn)題(FJSP，flexible Job shop scheduling problem)是柔性制造系統(tǒng)的核心，合理的調(diào)度方案可以有效降低車(chē)間成本，提高車(chē)間效率，使生產(chǎn)線穩(wěn)定運(yùn)轉(zhuǎn)，進(jìn)而提高企業(yè)的效益[1]。自動(dòng)導(dǎo)引車(chē)(AGV，automated guided vehicle)作為一種自動(dòng)物流載具備智能、高效、安全性能好等優(yōu)點(diǎn)，被廣泛應(yīng)用于制造領(lǐng)域[2]，其參與的集成調(diào)度逐漸成為生產(chǎn)調(diào)度優(yōu)化領(lǐng)域的重點(diǎn)研究問(wèn)題之一[3]。

在考慮運(yùn)輸時(shí)間的柔性作業(yè)車(chē)間調(diào)度中，機(jī)器與AGV緊密相連，在調(diào)度過(guò)程中需同時(shí)對(duì)這兩個(gè)元素進(jìn)行決策。群智能優(yōu)化算法[4]具有較強(qiáng)的并行性和穩(wěn)定性，它在解決優(yōu)化問(wèn)題時(shí)具有很好的搜索能力，因此被廣泛應(yīng)用于車(chē)間調(diào)度問(wèn)題求解。文獻(xiàn)[5]以綠色調(diào)度為重點(diǎn)，建立基于能耗閾值的機(jī)器、AGV聯(lián)合調(diào)度模型，使用改進(jìn)帝國(guó)競(jìng)爭(zhēng)算法求解模型獲得較優(yōu)調(diào)度方案。文獻(xiàn)[6]提出一種融合調(diào)度模型，同時(shí)實(shí)現(xiàn)AGV路徑規(guī)劃與車(chē)間生產(chǎn)調(diào)度，使用混合遺傳鯨魚(yú)優(yōu)化算法對(duì)其進(jìn)行求解。文獻(xiàn)[7]以車(chē)輛裝配車(chē)間為研究對(duì)象，引入多AGV搬運(yùn)工件，使用加入工序約束矩陣的改進(jìn)遺傳算法對(duì)其進(jìn)行求解。文獻(xiàn)[8]構(gòu)建AGV和機(jī)器雙約束的多目標(biāo)集成調(diào)度模型，綜合考慮多種時(shí)間因素，設(shè)計(jì)了貪心解碼策略和改進(jìn)NSAG-II (Non-dominated Sorting Genetic Algorithm-II)算法求解模型。文獻(xiàn)[9]提出一種包含AGV調(diào)度和無(wú)沖突路徑規(guī)劃的遺傳算法用以解決 AGV約束下的FJSP。文獻(xiàn)[10]建立基于AGV的柔性作業(yè)車(chē)間自動(dòng)化制造系統(tǒng)，提出多目標(biāo)改進(jìn)遺傳算法優(yōu)化物流需求波動(dòng)和生產(chǎn)周期。文獻(xiàn)[11]采用加入跳躍基因的遺傳算法求解AGV約束的FJSP，優(yōu)化車(chē)間績(jī)效指標(biāo)和AGV使用時(shí)長(zhǎng)。

文獻(xiàn)[12]提出麻雀搜索算法SSA (Sparrow Search Algorithm)。該算法由于具有搜索精度高、收斂速度快等優(yōu)點(diǎn)，一經(jīng)提出便被廣泛應(yīng)用于深度學(xué)習(xí)、路徑規(guī)劃等領(lǐng)域，但在柔性作業(yè)車(chē)間調(diào)度方面應(yīng)用較少，且存在著很大的優(yōu)化空間。在文獻(xiàn)[13-14]中，將麻雀搜索算法應(yīng)用于FJSP，但都未深入討論AGV在FJSP中所起到的約束作用，因此提出一種改進(jìn)麻雀搜索算法求解AGV、機(jī)器雙約束的柔性作業(yè)車(chē)間調(diào)度問(wèn)題。

1 問(wèn)題描述及模型建立

1.1 問(wèn)題描述

管道加熱器生產(chǎn)車(chē)間具有多約束性、多目標(biāo)性、加工柔性和運(yùn)輸柔性等特點(diǎn)。其生產(chǎn)過(guò)程主要受到機(jī)器加工時(shí)間和物料運(yùn)輸時(shí)間的約束，且在生產(chǎn)過(guò)程中要兼顧生產(chǎn)效率、生產(chǎn)成本、交貨期等指標(biāo)。此外，管道加熱器的每道工序都可以在不同的機(jī)器上加工，并且具備不同的加工時(shí)間，即加工柔性。工件在機(jī)器之間的運(yùn)輸依靠AGV實(shí)現(xiàn)，每個(gè)運(yùn)輸任務(wù)可以選擇不同的AGV執(zhí)行，因AGV所處位置的差異而具備不同的運(yùn)輸時(shí)間，即運(yùn)輸柔性。綜上所述，生產(chǎn)調(diào)度即在多個(gè)約束條件的限制下尋找可以兼顧多個(gè)生產(chǎn)指標(biāo)的較優(yōu)調(diào)度方案，因其復(fù)雜性被劃分為中的NP-hard (Non-deterministic Polynomial Hard)問(wèn)題[15]。

為便于求解合適的調(diào)度方案，將柔性車(chē)間抽象為數(shù)學(xué)模型，即AGV和機(jī)器雙約束下的多目標(biāo)FJSP，其可以描述為：設(shè)有n個(gè)工件在m個(gè)機(jī)器上加工，有v個(gè)AGV承擔(dān)運(yùn)輸任務(wù)。每個(gè)工件有多道加工工序，加工順序固定，每道工序有多個(gè)可選的加工機(jī)器，且不同機(jī)器上的加工時(shí)間不同。對(duì)車(chē)間模型做出如下假設(shè)：

1)起始時(shí)刻所有工件與AGV均位于倉(cāng)庫(kù)中；

2)AGV執(zhí)行完當(dāng)前任務(wù)后立即執(zhí)行下一任務(wù)；

3)機(jī)器在同一時(shí)刻只能加工一個(gè)工件；

4)工序的加工過(guò)程無(wú)法中斷；

5)機(jī)器的緩沖區(qū)大小不限；

6)同一工件的相鄰工序在同一機(jī)器上加工時(shí)，不需要AGV運(yùn)輸；

7)起始時(shí)刻所有AGV與機(jī)器均可用；

8)機(jī)器緩沖區(qū)中的工件加工順序由解碼方案確定；

1.2 模型建立

數(shù)學(xué)模型可直觀表達(dá)抽象的調(diào)度問(wèn)題，其符號(hào)定義如表1所示。

表1 調(diào)度模型參數(shù)定義

∑Xi，j，k≤1

(1)

∑αv，Wi，j≤1

(2)

Te ，v，pre≤TZb，v，Wi，j

(3)

Pei，j-1≤TZe，v，Wi，j

(4)

TZe，v，Wi，j≤Tb，v，Wi，j

(5)

Ei，j，k

(6)

Te，v，Wi，j-1≤Si，j，k

(7)

Pei，j-1≤Si，j，k

(8)

TZe，v，Wi，j+Te，v，Wi，j-TZs，v，Wi，j-Ts，v，Wi，j=Tv，Wi，j

(9)

Ci=Ei，n，k

(10)

其中：式(1)保證機(jī)器加工工序的時(shí)空唯一性；式(2)表示AGV運(yùn)輸工件的時(shí)空唯一性；式(3)和式(4)確保AGV空載開(kāi)始時(shí)間不早于上一次運(yùn)輸結(jié)束時(shí)間而空載結(jié)束時(shí)間不早于工件的上一道工序的完工時(shí)間；式(5)和式(6)確保AGV負(fù)載開(kāi)始時(shí)間不早于空載結(jié)束時(shí)間和Oi，j加工結(jié)束時(shí)間；式(7)和式(8)表示Oi，j的開(kāi)工時(shí)間不早于負(fù)載結(jié)束時(shí)間和Oi，j-1加工結(jié)束時(shí)間；式(9)表示AGV完成任務(wù)Wi，j所需的時(shí)間等于空載時(shí)間加上負(fù)載時(shí)間；式(10)表示工件的完工時(shí)間等于最后一道工序結(jié)束的時(shí)間。

FJSP一般把某個(gè)調(diào)度指標(biāo)作為評(píng)判調(diào)度方案是否合理的標(biāo)準(zhǔn)，常見(jiàn)的調(diào)度指標(biāo)包括訂單的完成時(shí)間、機(jī)器使用壽命、設(shè)備負(fù)載均衡等，其中最小化最大完工時(shí)間和最小化設(shè)備總負(fù)載是最常用的評(píng)價(jià)指標(biāo)，如式(11)和式(12)所示：

f1=Cmax=min(maxCi)

(11)

(12)

2 改進(jìn)麻雀搜索算法求解柔性作業(yè)車(chē)間調(diào)度問(wèn)題

半導(dǎo)體管道加熱器柔性作業(yè)車(chē)間的生產(chǎn)調(diào)度方案決定車(chē)間的生產(chǎn)效率及生產(chǎn)成本。不同于傳統(tǒng)的FJSP，還需考慮工件的運(yùn)輸時(shí)間。隨著產(chǎn)業(yè)的智能化升級(jí)，AGV被應(yīng)用到車(chē)間的配送環(huán)節(jié)中，承擔(dān)工件的運(yùn)輸任務(wù)，AGV成為求解車(chē)間生產(chǎn)調(diào)度方案的重要約束。

將管道加熱器生產(chǎn)車(chē)間抽象為1.2所述數(shù)學(xué)模型，以最大完工時(shí)間代表生產(chǎn)效率，以設(shè)備總負(fù)載代表生產(chǎn)成本，并考慮實(shí)際生產(chǎn)過(guò)程中可能出現(xiàn)的撤單、設(shè)備故障、新訂單等動(dòng)態(tài)擾動(dòng)。為求解車(chē)間的生產(chǎn)調(diào)度方案，可以采取啟發(fā)式群智能優(yōu)化算法[16]。其中麻雀搜索算法于2020 年提出，由于具有搜索穩(wěn)定、精度高、收斂快等一系列優(yōu)點(diǎn)，一經(jīng)提出便被廣泛應(yīng)用于深度學(xué)習(xí)、路徑規(guī)劃等領(lǐng)域，但在柔性作業(yè)車(chē)間調(diào)度方面應(yīng)用較少，且存在著很大的優(yōu)化空間。麻雀搜索算法被廣泛應(yīng)用于FJSP，但都未能深入討論AGV在FJSP中所起到的約束作用，因此提出一種改進(jìn)麻雀搜索算法求解AGV、機(jī)器雙約束的柔性作業(yè)車(chē)間調(diào)度問(wèn)題，并使用開(kāi)源數(shù)據(jù)集進(jìn)行驗(yàn)證。

2.1 麻雀搜索算法

作為一種群智能優(yōu)化算法，麻雀搜索算法受自然界動(dòng)物種群?jiǎn)l(fā)，主要模擬麻雀種群的覓食及反捕食行為。麻雀種群在尋找食物的過(guò)程中具備明確的內(nèi)部分工，覓食能力強(qiáng)的個(gè)體被稱為發(fā)現(xiàn)者，其余麻雀作為跟隨者共享發(fā)現(xiàn)者提供的食物信息。同時(shí)，種群中具有警戒者，它們?cè)诟兄轿ｋU(xiǎn)后會(huì)發(fā)出警報(bào)信號(hào)，種群會(huì)飛行至其他安全區(qū)域覓食。在迭代中，發(fā)現(xiàn)者的位置更新公式為：

(13)

其中：t為迭代次數(shù)，Xi，j為麻雀i在j維的解，itermax為最大迭代次數(shù)，α為(0，1]內(nèi)的一個(gè)隨機(jī)數(shù)，ST為安全值，R2是預(yù)警值，L是元素為1的d維矩陣，Q是服從正態(tài)分布的隨機(jī)數(shù)。對(duì)于跟隨者，其位置更新公式如下：

(14)

其中：XP為最優(yōu)發(fā)現(xiàn)者，Xworst則表示全局最差解，A為一個(gè)d維矩陣。當(dāng)i>n/2 時(shí)，表明跟隨者i沒(méi)有食物，需要飛往其它地方覓食。對(duì)于警戒者，其位置更新公式為：

(15)

其中：Xbest則表示全局最優(yōu)解，β為步長(zhǎng)控制參數(shù)，K為一個(gè)隨機(jī)數(shù)，fi則是當(dāng)前個(gè)體的適應(yīng)度值，fg和fw分別為當(dāng)前全局最佳和最差的適應(yīng)度值，ε為最小的常數(shù)。

2.2 編碼與解碼

機(jī)器和AGV雙約束的FJSP包含3個(gè)子問(wèn)題：工序分配子問(wèn)題、機(jī)器分配子問(wèn)題以及AGV調(diào)度子問(wèn)題。其中機(jī)器分配子問(wèn)題是為工序選擇合適的加工機(jī)器；工序分配子問(wèn)題是指確定機(jī)器上的工序加工順序，以此確定工序加工起止時(shí)間；而AGV分配子問(wèn)題是為各工序安排適合的AGV，進(jìn)而確定運(yùn)輸任務(wù)的起點(diǎn)、終點(diǎn)以及運(yùn)輸時(shí)間。通過(guò)麻雀?jìng)€(gè)體的編碼去解決機(jī)器分配問(wèn)題和工序排序問(wèn)題，在解碼過(guò)程中通過(guò)一種自適應(yīng)貪心算法求解AGV調(diào)度子問(wèn)題。

合理的編碼規(guī)則和解碼方式是求解FJSP的關(guān)鍵，模型采取基于工序的二維編碼方式，包括工序向量OS(Operation Sequencing)和機(jī)器向量MS(Machine Sequencing)。OS由工件號(hào)組成，順序讀取OS，工件的工序數(shù)即工件號(hào)當(dāng)前的出現(xiàn)次數(shù)，MS從左向右與OS逐一對(duì)應(yīng)，如圖1所示。

圖1 編碼方式

AGV在解碼過(guò)程中進(jìn)行調(diào)度，構(gòu)建一種基于自適應(yīng)貪心算法的AGV分配策略。解碼過(guò)程是順序解碼，當(dāng)編碼靠后的工件先抵達(dá)指定機(jī)器時(shí)，其需要等待編碼靠前的工件抵達(dá)并加工后才能進(jìn)行加工，這種情況可能造成最大完工時(shí)間的整體后移，因此，需要在解碼過(guò)程中加入前插判定，對(duì)于工序Oi，j和機(jī)器M，若滿足以下條件則進(jìn)行前插。

1)當(dāng)Oi，j-1同樣是在機(jī)器M上加工時(shí)，遍歷機(jī)器M上已解碼工件集OM，設(shè)Om.n和Ox，y是機(jī)器M上相鄰的兩道工序，且Ox，y先于Om，n加工，當(dāng)滿足式(16)時(shí)工序Oi，j可以前插置Ox，y和Om，n之間進(jìn)行加工。

Si，j，M≥Ei，j-1，M&&Sm，n，M-Ex，y，M≥Pi，j，M

(16)

2)當(dāng)Oi，j-1在其他機(jī)器上加工時(shí)，遍歷機(jī)器M上已解碼工件集OM，當(dāng)滿足式(17)時(shí)工序Oi，j可以前插置Ox，y和Om，n之間進(jìn)行加工。

(Te，v，Wi，j≥Ex，y，M&&Sm，n，M-Te，v，Wi，j≥

Pi，j，M)||(Ex，y，M≥Te，v，Wi，j&&Sm，n，M-Ex，y，M≥Pi，j，M)

(17)

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

2.3.1 初始化種群

種群的初始解質(zhì)量會(huì)直接影響算法的收斂速度和最終解的質(zhì)量。綜合考慮初始解的多樣性和收斂性，選擇隨機(jī)生成和局部貪心選擇兩種方法相結(jié)合生成初始麻雀種群，兩種初始化方式各占50%。

兩種方法的工序碼隨機(jī)由隨機(jī)數(shù)排序產(chǎn)生。對(duì)于機(jī)器碼，隨機(jī)初始化可以選擇可用機(jī)器集中的任意機(jī)器，而局部貪心初始化左至右遍歷工序碼，選擇加工耗時(shí)最短的機(jī)器，獲得的解具有較小的初始設(shè)備總負(fù)載。

2.3.2 改進(jìn)位置更新公式

由于SSA主要用來(lái)解決連續(xù)優(yōu)化問(wèn)題，而FJSP是典型的離散優(yōu)化問(wèn)題，直接將式(13)～(15)用于解的更新會(huì)產(chǎn)生大量非法解，極大地降低搜索效率，且麻雀搜索算法具有收斂過(guò)早、易陷入局部最優(yōu)等缺陷。因此在SSA的位置更新公式中結(jié)合NSGA-II算法，將交叉變異算子和變鄰域搜索應(yīng)用于麻雀位置更新，提高算法尋優(yōu)能力。

SSA的尋優(yōu)能力主要取決于發(fā)現(xiàn)者，若發(fā)現(xiàn)者陷入局部最優(yōu)，則算法性能也隨之下降，因此發(fā)現(xiàn)者應(yīng)當(dāng)具備尋優(yōu)方式多樣和尋優(yōu)能力強(qiáng)等特點(diǎn)。為擴(kuò)大搜索域，將POX (Precedence Operation Crossover)算子和RPX (Random Precedence Crossover)算子[17]引入發(fā)現(xiàn)者位置更新，在使用式(13)對(duì)工序碼進(jìn)行更新后，使用式(18)對(duì)發(fā)現(xiàn)者的位置進(jìn)行再次更新：

(18)

圖2 POX交叉算子

對(duì)機(jī)器段使用RPX交叉算子，即遍歷父代的機(jī)器段，以一定概率交換兩個(gè)體中相同工序所選擇的不同機(jī)器。Mut()是變異操作，以一定概率采用兩點(diǎn)變異。為了防止出現(xiàn)無(wú)效解，在變異后需要對(duì)機(jī)器碼做修復(fù)，若工序Oi，j無(wú)法在機(jī)器k上加工，則從工序Oi，j的機(jī)器集中隨機(jī)選一個(gè)可用機(jī)器。

從式(14)和(15)可以看出警戒者和跟隨者的位置更新均受最差個(gè)體的影響，這限制了種群多樣性和種群的搜索范圍，為加強(qiáng)發(fā)現(xiàn)者的引導(dǎo)作用，使用交叉變異算子使跟隨者獲取發(fā)現(xiàn)者的位置信息，跟隨者的位置更新公式為：

(19)

同理，在警戒者進(jìn)行位置更新后使用變鄰域下降搜索算法對(duì)其進(jìn)行再次更新，公式為：

(20)

警戒者可用來(lái)突破局部最優(yōu)，鄰域結(jié)構(gòu)包括：兩點(diǎn)交換鄰域、單點(diǎn)插入鄰域、變異鄰域結(jié)構(gòu)。前兩者可能產(chǎn)生無(wú)效解，需要在變鄰域搜索后遍歷并做修復(fù)。

2.3.3 基于Patero等級(jí)排序

由于算法具備多個(gè)優(yōu)化目標(biāo)，適應(yīng)度值是向量而非標(biāo)量，單一指標(biāo)無(wú)法判斷解的優(yōu)劣，因此引入Patero支配策略[18]來(lái)劃分解的質(zhì)量?jī)?yōu)劣。解之間的支配關(guān)系反映了兩個(gè)解質(zhì)量的好壞，假設(shè)x1，x2是解空間的兩個(gè)可行解，解x1生成的方案要優(yōu)于x2，則稱解x1支配解x2，而x1支配x2的充要條件是任意x1的目標(biāo)函數(shù)小于等于x2的目標(biāo)函數(shù)且存在x1的目標(biāo)函 數(shù)小于x2的目標(biāo)函數(shù)。若x1，x2互不支配，則稱x1與x2無(wú)差別。

結(jié)合NSGA-II算法的快速非支配排序，根據(jù)解的Patero等級(jí)和擁擠度進(jìn)行排序，并依次劃分發(fā)現(xiàn)者和跟隨者。在快速非支配排序中，設(shè)每個(gè)解都有參數(shù)S(j)和N(j)，其中S(j)是麻雀j支配的解的集合，N(j)是種群中可以支配麻雀j的解的數(shù)量。N(j)越小解越優(yōu)秀，若N(j)等于0，則解j的Patero等級(jí)是0，稱解j是最優(yōu)解。對(duì)于同一Patero等級(jí)的解，通過(guò)擁擠度進(jìn)行排序，擁擠度的計(jì)算采用的Harmonic平均距離[19]，某個(gè)體的Harmonic平均距離Hdsi定義如式(21)，排序步驟如下：

1)計(jì)算所有麻雀的N(j)和S(j)，k= 1；

2)將所有N(j) = 0的個(gè)體存入集合F(k)；

3)遍歷F(k)中個(gè)體的S(i)，將集合S(i)中每個(gè)個(gè)體的N(j)減1；

4)將F(k)中個(gè)體按照擁擠度進(jìn)行排序，k=k+1；

5)重復(fù)步驟2)～4)直到所有麻雀都被排序。

(21)

其中：di，Nm表示與其他個(gè)體的幾何距離，Nm表示優(yōu)化目標(biāo)數(shù)目，在式(19)中表示參與計(jì)算的與該個(gè)體集合距離最小的個(gè)體數(shù)量。

2.3.4 精英麻雀策略

改進(jìn)麻雀搜索算法融合了傳統(tǒng)麻雀算法和NSGA-II搜索算法的特征。在子代更新階段，傳統(tǒng)麻雀算法可能導(dǎo)致父代的優(yōu)秀個(gè)體丟失。而NSGA-II算法在子代更新階段使用二元錦標(biāo)賽法篩選子代種群，隨著迭代的進(jìn)行，子代中存在大量近似解，算法陷入局部最優(yōu)。為使算法在保持種群多樣性的情況下保留父代的優(yōu)秀個(gè)體，引入一個(gè)獨(dú)立于迭代種群外的精英種群，初始精英種群由初始麻雀種群的最優(yōu)解集組成，并隨著迭代的不斷更新種群成員。同時(shí)，為提高子代種群的搜索質(zhì)量，選擇精英解加入到發(fā)現(xiàn)者中參與迭代。精英種群的更新方法如下：

1)遍歷子代種群，若精英種群中存在一個(gè)解支配子代個(gè)體，則跳過(guò)該個(gè)體；

2)若子代個(gè)體與精英種群中所有個(gè)體均互不支配，將其加入精英種群；

3)若子代個(gè)體支配精英種群中一個(gè)或多個(gè)個(gè)體，則子代個(gè)體替換精英種群中被其支配的個(gè)體；

4)在更新過(guò)程中，為防止精英種群中個(gè)體越來(lái)越多，需設(shè)置種群數(shù)目上限，并使用擁擠度排序去除所有順序超出上限的解。

2.3.5 自適應(yīng)種群比例因子

搜索廣度與深度之間的協(xié)調(diào)對(duì)于SSA的性能至關(guān)重要。為此，提出自適應(yīng)種群比例策略。在迭代的早期階段，發(fā)現(xiàn)者占大多數(shù)，其數(shù)目隨著迭代次數(shù)的增加而自適應(yīng)減少，跟隨者的數(shù)量自適應(yīng)增加，從而提高方案的質(zhì)量。具體公式表示為：

(22)

pNum=r*N

(23)

sNum=(1-r)*N

(24)

其中：pNum定義為發(fā)現(xiàn)者的數(shù)量，sNum表示跟隨者的數(shù)量，b定義為一個(gè)比例因子，σ是一個(gè)[0，1]之間的偏差因子，N是總迭代次數(shù)，T是當(dāng)前迭代次數(shù)。

3 算法流程

使用ISSA (improved sparrow search algorithm)求解柔性作業(yè)車(chē)間調(diào)度方案的流程如圖3所示，具體步驟如下：

圖3 改進(jìn)麻雀搜索算法流程圖

1)初始化麻雀種群數(shù)量、初始發(fā)現(xiàn)者、跟隨者、警戒者比例、ST等，按照2.3.1節(jié)方法獲取初始解。

2)按照2.3.3節(jié)方法劃分種群的Patero等級(jí)，將最優(yōu)解集加入到精英種群。

3)按照式(13)和(16)更新發(fā)現(xiàn)者位置。

4)按照式(14)和(17)更新跟隨者位置。

5)按照式(15)和(18)更新警戒者位置。

6)劃分子種群的Patero等級(jí)，按2.3.4節(jié)方法更新精英種群。

7)若滿足終止條件，輸出精英種群作為最終調(diào)度方案集合，否則返回步驟3)。

4 實(shí)驗(yàn)驗(yàn)證

4.1 仿真實(shí)驗(yàn)

仿真調(diào)度案例使用文獻(xiàn)[20]和文獻(xiàn)[21]中提出的考慮工件運(yùn)輸時(shí)間的FJSP基準(zhǔn)實(shí)例(數(shù)據(jù)集下載地址：https：//fastmanufacturingproject.wordpress.com)。改進(jìn)麻雀算法的主要參數(shù)包括迭代次數(shù)M=100，種群數(shù)量N=50，精英種群數(shù)量SN= 10，安全閾值ST=0.8，發(fā)現(xiàn)者、跟隨者的比例按2.3.5節(jié)劃分，警戒者占20%，設(shè)存在兩個(gè)AGV進(jìn)行物料運(yùn)輸。

為驗(yàn)證改進(jìn)措施的有效性，分別對(duì)比ISSA、離散化SSA、SSA+初始化、SSA+精英策略、SSA+自適應(yīng)因子5種算法，將5種算法分別命名為ISSA、ISSA-1、ISSA-2、ISSA-3，ISSA-4，其中離散化SSA由2.3.2和2.3.3節(jié)組成。為避免偶然性對(duì)實(shí)驗(yàn)結(jié)果的影響，分別進(jìn)行20次仿真實(shí)驗(yàn)，對(duì)實(shí)驗(yàn)數(shù)據(jù)取平均值，對(duì)比5種算法取得的Cmax和L。

由表2可以看出，ISSA算法所求得的Cmax和L都是最優(yōu)的，驗(yàn)證了所提出的4種改進(jìn)策略的有效性。從ISSA-1、ISSA-2、ISSA-3、ISSA-4的對(duì)比數(shù)據(jù)中可以看出混合初始化機(jī)制、精英種群機(jī)制和自適應(yīng)比例因子都對(duì)算法尋優(yōu)有一定效果。其中ISSA-3的尋優(yōu)效果提升更大，說(shuō)明精英種群機(jī)制對(duì)算法的求解質(zhì)量有較大的提升效果。這是由于SSA在迭代過(guò)程中會(huì)丟失父代的較優(yōu)解，導(dǎo)致每輪迭代的最優(yōu)解集互相之間沒(méi)有聯(lián)系，局部搜索能力下降。而在設(shè)置精英種群且精英種群加入子代選擇后，精英解為種群提供導(dǎo)向，且隨著精英種群動(dòng)態(tài)更新，可有效防止算法陷入局部最優(yōu)。

表2 案例結(jié)果對(duì)比表

為探究各優(yōu)化策略對(duì)算法性能的影響，以算例JS1L1為例，5種算法求解算例JS1L1的收斂曲線如圖4所示。采取了混合初始化方法的ISSA-2擁有質(zhì)量較高的初始解。擁有自適應(yīng)種群因子的ISSA-4在算法早期獲得較大的發(fā)現(xiàn)者比例，提高全局搜索能力，隨著迭代的進(jìn)行擴(kuò)大跟隨者的比例，提升算法局部尋優(yōu)能力，使得種群迅速收斂。而ISSA-3則通過(guò)精英種群策略保留并更新每代的最優(yōu)解集，獲取較強(qiáng)的突破局部最優(yōu)的能力，其收斂曲線呈階梯型下降。而ISSA算法綜合以上特點(diǎn)，具備最佳的尋優(yōu)能力。

圖4 算例JS1L1的迭代曲線圖

為進(jìn)一步驗(yàn)證ISSA算法的有效性，分別與INSGA-II算法、SSA算法、MICA算法及IGA算法進(jìn)行對(duì)比，結(jié)果如表3所示。

表3 管道加熱器的工藝信息表

表3 最大完工時(shí)間對(duì)比結(jié)果

由表3可知，ISSA算法求解出的最優(yōu)值均達(dá)到當(dāng)前最佳。對(duì)于案例JS7L4，其最優(yōu)值和平均值均遠(yuǎn)強(qiáng)于其它算法，表明了ISSA算法在求解較復(fù)雜案例時(shí)也有著較為突出的搜索性能。同時(shí)，ISSA算法的平均解值與最優(yōu)解值的差距很小，可見(jiàn)算法搜索性能的穩(wěn)定。圖5為ISSA求解JS7L3算例所獲得的甘特圖。

圖5 JS7L3調(diào)度甘特圖

4.2 工廠實(shí)例

以某公司半導(dǎo)體管道加熱器柔性作業(yè)車(chē)間為例，研究ISSA在實(shí)際生產(chǎn)中的應(yīng)用。該車(chē)間是管道加熱器組裝及后處理車(chē)間，主要包括管道外觀修飾、焊接控制器和封頭等工序。車(chē)間布局如圖6所示。

圖6 改進(jìn)后的車(chē)間布局圖

對(duì)半導(dǎo)體管道加熱器生產(chǎn)車(chē)間進(jìn)行改造，按照功能將原車(chē)間劃分為14個(gè)加工區(qū)域。引入AGV進(jìn)行區(qū)域間的物料運(yùn)輸，使用改進(jìn)蟻群算法求解 AGV 在不同區(qū)域間的物流時(shí)間。以一批包含4種8個(gè)工件的訂單加工任務(wù)為研究對(duì)象，安排其在改造后的車(chē)間進(jìn)行加工。組裝車(chē)間主要的加工目標(biāo)是多品種的半導(dǎo)體管道加熱器，以小管加工為例，其工序以及可選擇的加工區(qū)域如表3所示。每個(gè)工序可以選擇多個(gè)不同機(jī)器進(jìn)行加工，雖然工序相同，但 由于不同品種的加熱器具有不同的尺寸、形狀以及控制器數(shù)量，且在加工過(guò)程中受工人操作熟練度約束，同一工序在不同工位上加工時(shí)有不同的加工時(shí)間。

在車(chē)間的生產(chǎn)調(diào)度中，AGV數(shù)量會(huì)對(duì)調(diào)度結(jié)果產(chǎn)生較大影響。當(dāng)AGV數(shù)量較少時(shí)，無(wú)法高效地完成物料運(yùn)輸，機(jī)器大多處在等待工件的狀態(tài)，設(shè)備利用率較低。當(dāng)AGV過(guò)多時(shí)，其相互之間的路徑?jīng)_突增多，運(yùn)輸效率下降，造成生產(chǎn)效率下降，且過(guò)多的AGV會(huì)增加企業(yè)的運(yùn)營(yíng)成本，降低企業(yè)利潤(rùn)。

作業(yè)車(chē)間的現(xiàn)行調(diào)度方案為人工實(shí)時(shí)調(diào)度，其調(diào)度規(guī)則如下：1)在選擇加工順序時(shí)，按照工件的工序順序和訂單序號(hào)進(jìn)行調(diào)度；2)在選擇機(jī)器時(shí)，按照訂單序號(hào)和機(jī)器序號(hào)依次安排可用機(jī)器；3)若存在多道相鄰工序可在同一機(jī)器上加工，則由同一機(jī)器完成相鄰工序的加工。調(diào)度方案如圖7所示，其最大完工時(shí)間是289.9 min，設(shè)備總負(fù)荷是1 124.3 min。同時(shí)，使用改進(jìn)麻雀搜索算法對(duì)同一調(diào)度問(wèn)題進(jìn)行求解，調(diào)度甘特圖如圖8所示，其最大完工時(shí)間是242.3 min，設(shè)備總負(fù)載是1 093.9 min。

圖7 改進(jìn)麻雀搜索算法調(diào)度甘特圖

圖8 人工調(diào)度甘特圖

根據(jù)圖8可知人工調(diào)度方案加工順序并不合理，且各設(shè)備負(fù)載差距較大，總加工時(shí)間較長(zhǎng)。雖然簡(jiǎn)單明了，但忽略了每個(gè)工件之間的加工時(shí)長(zhǎng)差異。而在小批量、多品種柔性作業(yè)車(chē)間中，個(gè)體之間的加工順序可能相同，但單步工序的加工時(shí)間差距較大，人工調(diào)度無(wú)法獲得高效、低成本的加工方案。使用改進(jìn)麻雀搜索算法求解的調(diào)度方案可先于人工方案47.6 min完成生產(chǎn)任務(wù)，效率提升了19.6%，同時(shí)其比人工方案減少了30.4 min的設(shè)備使用時(shí)長(zhǎng)。

5 結(jié)束語(yǔ)

探究實(shí)際的柔性作業(yè)車(chē)間生產(chǎn)過(guò)程，將運(yùn)輸時(shí)間引入傳統(tǒng)FJSP，將AGV作為物流系統(tǒng)的載體，同時(shí)提出多種柔性作業(yè)車(chē)間優(yōu)化目標(biāo)，建立更貼合實(shí)際的FJSP模型。設(shè)計(jì)一種二維編碼方法表示調(diào)度方案。在解碼過(guò)程中使用自適應(yīng)貪心算法解決AGV分配問(wèn)題，并提出一種改進(jìn)麻雀搜索算法獲取較優(yōu)解。將ISSA算法與NSGA-II算法進(jìn)行結(jié)合，使用交叉變異算子以及變鄰域搜索算法突破局部最優(yōu)，使用精英種群保存迭代過(guò)程中的較優(yōu)解集。通過(guò)多個(gè)經(jīng)典案例測(cè)試，結(jié)果表明算法在求解靜態(tài)及動(dòng)態(tài)調(diào)度問(wèn)題上有很好的效果。

本文提出改進(jìn)麻雀搜索算法和改進(jìn)蟻群算法分別求解AGV約束下的多目標(biāo)FJSP和AGV的路徑規(guī)劃問(wèn)題，此外還對(duì)車(chē)間的動(dòng)態(tài)擾動(dòng)做了深入探討，取得了一定成果。

結(jié)合某公司柔性生產(chǎn)車(chē)間，研究了上述算法的實(shí)際生產(chǎn)意義，對(duì)原生產(chǎn)車(chē)間進(jìn)行改進(jìn)以便引入AGV執(zhí)行運(yùn)輸任務(wù)，使用上述算法生成調(diào)度方案，并與車(chē)間原生產(chǎn)方案進(jìn)行對(duì)比，驗(yàn)證了算法的優(yōu)越性。結(jié)合車(chē)間的實(shí)際擾動(dòng)事件，驗(yàn)證了所提方法的可行性。