多AGV和機器集成的多目標(biāo)柔性作業(yè)車間調(diào)度研究

馬千慧，梁曉磊，劉星雨，張孟鏑，黃 凱

武漢科技大學(xué) 汽車與交通工程學(xué)院，武漢 430065

柔性作業(yè)車間調(diào)度問題（flexible job-shop scheduling problem，F(xiàn)JSP）包含工序排序和機器選擇兩個子問題，是典型的NP-hard問題，也一直是國內(nèi)外學(xué)者研究的熱點。目前對FJSP的研究主要集中在考慮加工時間且以最小化最大完工時間為目標(biāo)[1-3]，求解方法也多以智能優(yōu)化算法為主，如遺傳算法[4]、狼群算法[5]、混合遺傳雜草算法[6]等。大多數(shù)研究中考慮了工件在機器上的加工過程，卻忽略了工件的搬運過程。而現(xiàn)代制造業(yè)正向智能化方向升級，工件在機器之間的裝卸件大多通過自動導(dǎo)引小車（automatic guided vehicle，AGV）進(jìn)行搬運，AGV在加工設(shè)備和運輸資源的集成調(diào)度及協(xié)同優(yōu)化中發(fā)揮的作用成為智能制造系統(tǒng)高效運作的重要支撐，因此考慮AGV調(diào)度與FJSP問題的結(jié)合有重要的實用價值。

目前對于AGV參與下的FJSP的研究主要集中在機器分配、工序調(diào)度、AGV調(diào)度分配、AGV路徑選擇等四個方面，如楊立熙等[7]、張國輝等[8]考慮了工序間的運輸時間，但沒有考慮運輸設(shè)備的調(diào)度；賀長征等[9]、Zheng等[10]考慮了機器和AGV的集成調(diào)度，但都以單目標(biāo)優(yōu)化為主，對AGV數(shù)量和調(diào)度目標(biāo)兩者之間的關(guān)系分析不足；在多目標(biāo)優(yōu)化問題上，有學(xué)者考慮以車間總能量消耗最小和最大完工時間最小為目標(biāo)[11]、以最小化綜合能耗成本和完工時間為目標(biāo)[12]、以最大完工時間最小和AGV利用率最大為目標(biāo)[13]構(gòu)建模型，但較少考慮AGV因素下的優(yōu)化指標(biāo)。AGV作為運輸設(shè)備和約束條件，在加工過程中將其作為調(diào)度目標(biāo)的考慮因素是必要的。在求解算法中，近年研究多采用多目標(biāo)優(yōu)化算法進(jìn)行求解，如鞠錄巖等[14]提出改進(jìn)NSGA算法求解多目標(biāo)柔性作業(yè)車間調(diào)度問題，景志強等[15]提出NSGA-Ⅱ和模擬退火算法的混合算法，董海等[16]將入侵腫瘤生長優(yōu)化算法和NSGA-Ⅲ算法進(jìn)行混合，但算法對問題的求解效率還需進(jìn)一步提升。

在實際制造過程中，由于加工任務(wù)的到達(dá)是隨機的，每個工件設(shè)置不同的到達(dá)時間，有些工件的完工限制在一定時間范圍內(nèi)，需滿足客戶要求在交貨期前完工，因此本文在考慮加工時間的同時，結(jié)合考慮工件的到達(dá)時間、交貨期等多時間因素，集成AGV調(diào)度和機器調(diào)度，建立多目標(biāo)柔性作業(yè)車間調(diào)度模型，研究AGV數(shù)量變化與調(diào)度目標(biāo)的關(guān)系。在求解方面，針對NSGA-Ⅱ算法運算復(fù)雜和精英策略不足的缺點，提出一種改進(jìn)的NSGA-Ⅱ優(yōu)化算法對本文模型進(jìn)行有效求解。

1 機器/AGV雙約束的FJSP調(diào)度問題描述與建模

1.1 問題描述

假設(shè)包含多道工序的n個工件可以在不同的m臺機器上進(jìn)行加工，且有V臺相同的AGV在車間運送工件，所有工序按照規(guī)定的加工工藝路線在可加工機器集中的機器上加工，一道工序操作完成后，其下一道工序加工前要考慮AGV的運輸情況。本文提出在柔性作業(yè)車間調(diào)度問題中同時調(diào)度機器和AGV，充分考慮到達(dá)時間、加工時間、運輸時間、交貨期等多時間因素，建立機器/AGV雙約束的FJSP模型，調(diào)度以最小化最大完工時間、最小化總延期、最小化設(shè)備總負(fù)荷為目標(biāo)。模型假設(shè)：零時刻AGV在入庫區(qū)準(zhǔn)備就緒；AGV一次只能運載一個工件，且沿著預(yù)定的雙向單通道最短路徑行駛，且規(guī)定某一時刻一條路徑上只允許行駛一臺AGV；AGV執(zhí)行完當(dāng)前運輸任務(wù)后直接前往下一運輸任務(wù)加工機器旁，不返回入庫區(qū)；考慮工件從入庫區(qū)到各機器和最后一道工序加工完后到出庫區(qū)的運輸時間；任意時刻每臺機器只能加工一個工件；不同工件間沒有優(yōu)先級，同一工件各工序存在先后順序；假定全部工件由AGV運送至出庫區(qū)即為加工完成；不考慮機器故障、AGV路徑?jīng)_突和碰撞等因素。

1.2 參數(shù)定義

模型參數(shù)定義如表1所示。

表1 參數(shù)定義Table 1 Parameters definition

其中：

1.3 模型建立

模型約束構(gòu)建如下：

式（7）表示某時刻某工件只能被一臺機器加工；式（8）表示每臺AGV每次只接受一個運送任務(wù)；式（9）表示AGV需在工件工序加工完成后接受運送任務(wù)；式（10）表示AGV零時刻在入庫區(qū)等待；式（11）表示工件Ji加工完后被送至出庫區(qū)；式（12）表示同一工件兩個相鄰工序的加工約束；式（13）表示同一機器上緊前工序的加工約束；式（14）表示工件的第一道工序開始加工前需由AGV從入庫區(qū)搬運至第一臺機器；式（15）表示工件最后一道工序加工完后需由AGV搬運至出庫區(qū)；式（16）表示AGV完成運送任務(wù)Wi,j的結(jié)束運輸時間為開始運輸時間加上運輸時間；式（17）表示機器的加工能力限制；式（18）表示AGV的能力限制；式（19）表示交貨期限制；式（20）表示當(dāng)前機器空閑時才能加工工件。

由于考慮了工件的到達(dá)時間，且假設(shè)AGV運送任務(wù)狀態(tài)分為裝卸件兩種，則需要探究是否為第一道工序、AGV搬運運送任務(wù)到達(dá)某一機器時該機器的工作情況：

（1）當(dāng)AGV執(zhí)行裝件運送任務(wù)時，若為第一道工序，AGV工作時間即運輸時間；若非第一道工序，AGV工作時間為AGV所在機器、裝件點和加工機器三點間的運輸時間之和，計算如式（21）所示：

（2）當(dāng)AGV執(zhí)行卸件運送任務(wù)時，若待接受運送工序已加工完，AGV工作時間為AGV所在機器、待接受運送工序加工完成機器與卸件點三點間的運輸時間之和；若未加工完，需判斷該工序完工時間與AGV運輸時間的大小，AGV工作時間取最大值與該機器到卸件點的運輸時間之和。計算公式為：

相應(yīng)地，考慮AGV運輸時間約束和機器可用時間段時，需要探究是否為第一道工序以及機器是否空閑的工作情況：

（1）當(dāng)機器空閑時，若為第一道工序，工件開始加工時間為到達(dá)時間與Tv,Wi,j之和；若非第一道工序，工件開始加工時間為該工序上一道工序的完工時間與Tv,Wi,j之和。計算公式為：

（2）當(dāng)機器不可用時，若為第一道工序，工件開始加工時間由到達(dá)時間與Tv,Wi,j兩者之和、機器開始空閑時間中的最大值決定；若非第一道工序，工件開始加工時間由該工序上一道工序的完工時間與Tv,Wi,j之和、機器開始空閑時間中的最大值決定。計算公式為：

綜上，工件的結(jié)束加工時間的計算方式為：

根據(jù)以上約束模型，考慮到車間效率、客戶滿意度和設(shè)備使用情況，設(shè)置最大完工時間、總延期和設(shè)備總負(fù)荷最小三個目標(biāo)，目標(biāo)函數(shù)構(gòu)建如下：

（1）最小化最大完工時間：

工件從入庫到出庫整個流程結(jié)束表示其加工完成，則工件最大完工時間為結(jié)束加工時間與加工完后從最后一臺機器到出庫區(qū)的運輸時間之和。

（2）最小化總延期：

為滿足交貨期限制，減少總延期時間以提高客戶滿意度。

（3）最小化設(shè)備總負(fù)荷：

將AGV作為考慮因素加入設(shè)備總負(fù)荷優(yōu)化指標(biāo)中，其中包含機器負(fù)荷和AGV負(fù)荷（負(fù)載和空載），以提高設(shè)備利用率。

2 求解算法設(shè)計

2.1 AGV調(diào)度規(guī)則

為了合理分配車間調(diào)度資源和提高系統(tǒng)效率，提出新的AGV調(diào)度規(guī)則以確定加工工件和AGV的分配關(guān)系。針對本文FJSP模型特點，AGV調(diào)度規(guī)則分為單AGV和多AGV兩種情況，如圖1所示：（1）單AGV時，AGV完成上一運送任務(wù)后立即進(jìn)行下一運送任務(wù)運輸；（2）多AGV時，如果每臺AGV在完成下一工序運輸任務(wù)的時間節(jié)點都大于下一工序能開始加工的時間，則選擇最早能完成運輸任務(wù)的AGV；如果僅有一臺AGV在完成下一工序運輸任務(wù)的時間節(jié)點在該工序能開始加工的時間之前，則選擇此AGV；如果有多臺AGV在完成下一工序運輸任務(wù)的時間節(jié)點在該工序能開始加工的時間之前，則選擇其中完成運輸任務(wù)時AGV運行距離最短的AGV。新的AGV調(diào)度規(guī)則在工件加工過程中根據(jù)不同情況考慮AGV最早到達(dá)和距離最短，使得工件在加工時獲得一個最早的開始加工時間。

圖1 AGV調(diào)度規(guī)則Fig.1 AGV scheduling rules

2.2 算法編碼及解碼策略設(shè)計

為提高NSGA-Ⅱ算法求解效率，本文設(shè)計了基于工序和啟發(fā)策略的編碼和解碼策略。以一個3×5（3個工件、5臺機器）FJSP問題為例，工件加工及AGV信息如表2所示。

表2 3×5 FJSP問題實例Table 2 Example of 3×5 FJSP problem

針對本文構(gòu)建模型，采用基于工序的擴展染色體編碼，染色體結(jié)構(gòu)如圖2所示。該染色體由兩部分組成，第一部分采用基于工序的編碼，基因位上工件號出現(xiàn)的次數(shù)代表該工件的第幾道工序，如第一個基因位上的數(shù)值2表示工件2的第一道工序，第二個基因位上的數(shù)值1表示工件1的第一道工序，以此類推；第二部分采用基于機器的編碼，基因位上的數(shù)值代表相應(yīng)工序的可選機器號，如第一個基因位上的數(shù)值2代表工件2的第一道工序選擇機器2加工，第二個基因位上的數(shù)值3代表工件1的第一道工序選擇機器3加工，以此類推。

圖2 FJSP染色體編碼Fig.2 FJSP chromosome coding

上述編碼操作可以解決工序順序和機器分配問題，而AGV的調(diào)度體現(xiàn)在解碼中。本文構(gòu)建了一種基于AGV分配的貪婪式解碼策略。以圖1染色體為例，具體步驟如下：

（1）根據(jù)染色體編碼可以獲得相應(yīng)基因位的信息，包括工序基因P，加工機器Mk，進(jìn)行運送任務(wù)的AGV號Pv以及AGV接受運送任務(wù)時所在的機器M′v,Wi,j，將獲取的信息作為解碼的輸入條件。

（2）從左到右讀取染色體基因，轉(zhuǎn)換成相應(yīng)工序Oi,j和機器Mk，通過選擇的加工機器確定加工時間Pi,j,k，得到前置工序Oi,(j－1)的結(jié)束加工時間Ei,(j－1),k，前置工序所在機器位置Mv,Wi,j。

（3）確定工序開始加工時間Si,j,k。解碼計算時需考慮工件和加工機器的約束，見公式（23）、（24）。

（4）確定AGV運輸時間Tv,Wi,j。解碼計算時需考慮機器和AGV的雙約束，見公式（21）、（22）。

（5）確定AGV號Pv。通過AGV調(diào)度規(guī)則根據(jù)不同情況判斷選擇最早到達(dá)還是距離最短，即判斷AGV完成下一工序運輸任務(wù)的時間節(jié)點Te,v,Wi,j與該工序能開始加工的時間節(jié)點Si,(j+1),k的大小關(guān)系。

（6）確定工序結(jié)束加工時間Ei,j,k和完工時間。見公式（23）、（24）、（25）。

（7）重復(fù)步驟（2）～（6），直到所有的工件加工完成為止，得到每個工件每道工序的開始加工時間、加工機器、AGV和完工時間，即生成調(diào)度方案。

2.3 算法操作算子設(shè)計

（1）選擇算子

首先對初始種群進(jìn)行排序并分級，找到種群中所有不被其他個體支配的個體作為第一級非支配個體集合，不斷分級操作，直到所有的個體分級完成，再進(jìn)行擁擠度估計。經(jīng)過非支配排序和擁擠度計算，本文采用二元錦標(biāo)賽選擇方法，每次隨機選擇兩個個體，優(yōu)先選擇排序等級高的個體，如果排序等級一樣，優(yōu)先選擇擁擠度大的個體，如果擁擠度相同則選擇序號小的個體。

（2）交叉變異算子

針對染色體編碼以及機器可選的特點，在保證可行解的前提下，設(shè)計分段交叉和變異操作。

工序交叉：將所有工件隨機分成兩組J1、J2，隨機選擇兩個不同的父代工序染色體，將F1中屬于J1的工序位置保留到Z1，將F2中屬于J2的工序位置保留到Z2；將F2中屬于J2的工序復(fù)制到Z1的剩余位置，將F1中屬于J1的工序復(fù)制到Z2的剩余位置。其交叉過程見圖3（a）所示。

圖3 染色體交叉操作過程Fig.3 Chromosome crossover procedure

機器交叉：選擇兩個不同的父代染色體，隨機生成進(jìn)行機器交叉的工序位置做為父代1交叉的位置，然后與父代2對應(yīng)的位置進(jìn)行機器交叉。例如，選擇F1中工件2的第一道工序作為交叉位置點，找出F2中此工序的位置，將此位置作為機器基因交叉點。其交叉過程見圖3（b）所示。

工序變異：選擇一個父代染色體，隨機生成兩個需要進(jìn)行工序變異的工序位置，將兩個位置的工序進(jìn)行交換，為滿足對應(yīng)加工工序的機器不變，對機器序列進(jìn)行重新排序。例如：把工件1的第一道工序與工件3的第二道工序進(jìn)行交換，交換后此時工件3的第二道工序變?yōu)榈谝坏拦ば颍淖兞斯ば蝽樞颍瑱C器選擇發(fā)生了變化，需對機器進(jìn)行重新選擇，修正之后加工機器可能從機器3變?yōu)闄C器1，機器5變?yōu)闄C器2。其變異過程如圖4（a）所示。

圖4 染色體變異操作過程Fig.4 Procedure of chromosome mutation

機器變異：選擇一個父代染色體，隨機生成多個需要進(jìn)行機器變異的工序位置，在各工序?qū)?yīng)加工的機器集里重新選擇機器。例如：選擇工件1的第二道工序的位置進(jìn)行變異，其可選機器集合為{2，5}，生成該集合長度內(nèi)的隨機數(shù)r，若r=1，則選擇機器2；若r=2，則選擇機器5，其變異過程如圖4（b）所示。

2.4 改進(jìn)NSGA-Ⅱ算法

（1）多種群參數(shù)控制

多種群中的各種群采用不同的以某類指標(biāo)為主的搜索方式，給不同的種群賦予不同的控制參數(shù)，突破NSGA-Ⅱ僅靠單個群體進(jìn)行遺傳進(jìn)化的框架。本文目的側(cè)重種群進(jìn)化完成后使得三個目標(biāo)相對較優(yōu)以及處于第一層級非支配序的解分布均勻，具體操作為，對種群進(jìn)行二元錦標(biāo)賽選擇，對第一個種群選擇以非支配排序為主的適合繁殖的父代種群，對第二個種群選擇以完工時間最小為主的適合繁殖的父代種群，對第三個種群選擇以設(shè)備總負(fù)荷最小為主的適合繁殖的父代種群，對三個種群分別進(jìn)行交叉變異操作，引入三個種群同時進(jìn)行優(yōu)化搜索，實現(xiàn)多種群的協(xié)同進(jìn)化。

（2）基于Pareto級的去重精英保留策略

首先將第t代產(chǎn)生的新種群Qt放入新的父代種群Pt+1中，然后對上一代父代種群Pt進(jìn)行非支配排序，產(chǎn)生一系列非支配集Zi并計算擁擠度，將經(jīng)過非支配排序以后的最優(yōu)的非支配解存入新的第一層級非支配集Z′1中，再將Z′1中不同的個體放入新的父代種群Pt+1中，即Pt+1=Qt+Z′1。

本文采用的精英保留策略中種群數(shù)量不確定，每次迭代只保留第一層級中去掉重復(fù)解的個體到下一代中，這樣操作保證最優(yōu)解遺傳到下一代，且能避免傳統(tǒng)隱形精英保留策略在進(jìn)化過程中大部分非支配解處于第一層級的非支配曲面造成局部收斂的情況。種群進(jìn)化過程如圖5所示。

圖5 種群進(jìn)化過程Fig.5 Procedure of population evolution

2.5 算法流程

AGV/機器雙約束下的改進(jìn)NSGA-Ⅱ算法求解柔性作業(yè)車間調(diào)度問題的具體流程如圖6所示。

圖6 算法流程圖Fig.6 Algorithm flowchart

2.6 INSGA-Ⅱ算法時間復(fù)雜度分析

假設(shè)目標(biāo)函數(shù)個數(shù)為M，種群規(guī)模為N，從2.5節(jié)算法流程可以看出，INSGA-Ⅱ算法尋優(yōu)主要由六部分組成：第一部分初始化種群，由單次種群搜索行為分析可知，其時間復(fù)雜度約為O(MN)；第二部分計算適應(yīng)度值，其時間復(fù)雜度約為O(N1+N2+N3)=O(N′)，Nk為子群k的規(guī)模；第三部分快速非支配排序，首先二層循環(huán)生成非支配解，該步時間復(fù)雜度為O(MN2)，其次訪問集合中每一個非支配解得到非支配面，由于每個解最多由N－1個解支配，所以每個解被訪問的次數(shù)最多為N－1次，該步時間復(fù)雜度為O(N2)，綜上，快速非支配排序的時間復(fù)雜度約為O(MN2)；第四部分擁擠度計算，對每一個體求目標(biāo)值并找其最大值，其時間復(fù)雜度約為O(MNlogN)；第五部分多種群進(jìn)化，加入三個種群，其時間復(fù)雜度約為O(N·3)=O(N)；第六部分精英保留，其時間復(fù)雜度約為O(MN)。因此，INSGA-Ⅱ算法的總時間復(fù)雜度為：

3 車間調(diào)度仿真實例

3.1 案例求解

本文以表3所示的8×8問題實例和表4所示的AGV搬運時間為例，對以最大完工時間、總延期、設(shè)備總負(fù)荷為優(yōu)化目標(biāo)的FJSP問題進(jìn)行驗證。問題規(guī)模設(shè)置為工件數(shù)n=8，機器數(shù)m=8，AGV數(shù)V=3。采用Matlab 2018b進(jìn)行編程實現(xiàn)，實驗在平臺（Intel?Core?i5-6500 CPU@3.20 GHz 3.19 GHz，內(nèi)存8.00 GB）上進(jìn)行。算法參數(shù)設(shè)置為：種群規(guī)模P=200，最大迭代次數(shù)M=100，交叉概率Pc=0.8，變異概率Pm=0.1。

表3 具有工件到達(dá)時間和交貨期的8×8 FJSP問題實例Table 3 Example of 8×8 FJSP problem with workpiece arrival time and delivery date單位：min

表4 AGV搬運時間Table 4 AGV handling time 單位：min

實驗結(jié)果如圖7（a）所示，其中機器加工時間段用工件號、工序號、加工時間構(gòu)成的字符串進(jìn)行標(biāo)記，即p（工件，工序）=加工時間；AGV運輸時間段分為空載和負(fù)載兩個階段，分別用虛線框和實線框標(biāo)記，圖中數(shù)字代表各個位置節(jié)點。方案中調(diào)度的3個目標(biāo)最佳值分別為最大完工時間121、總延期13、設(shè)備總負(fù)荷568。從圖7（a）中可以看出，AGV存在無效運輸時間段，如空載段10-6-6。分析可知此時待運送工件的下一道工序仍在同一機器上加工，不需搬運。因此，增加如下約束：相同工件的不同操作工序在同一臺機器上加工不需要AGV運輸。校正后調(diào)度解甘特圖如圖7（b）所示，此時3個目標(biāo)最佳值分別為最大完工時間112、總延期12、設(shè)備總負(fù)荷561，獲得了更優(yōu)秀的解。

圖7 8×8案例調(diào)度甘特圖Fig.7 8×8 case scheduling Gantt chart

校正后該方案得到AGV的運輸時間矩陣為：

其中，每個矩陣第一列數(shù)值表示AGV號，第二列表示AGV位置節(jié)點，第三列表示工件位置節(jié)點，第四列表示工件加工機器位置節(jié)點，第五列表示AGV空載開始時間，第六列表示AGV負(fù)載開始時間，第七列表示AGV負(fù)載結(jié)束時間。含義如下：第八個工件的第一道工序O81開始加工時間為其到達(dá)時間0、小車1從入庫區(qū)搬運O81到機器1的運輸時間4之和即4，對應(yīng)AGV時間矩陣為[1 9 9 1 0 0 4]；小車1負(fù)載結(jié)束時間為4，由位置1行駛至入庫區(qū)搬運工序O21到機器3上加工，其開始加工時間計算判斷小車到達(dá)時間和工件到達(dá)時間的大小取最大值，即max（4+4，17）+6=23，對應(yīng)AGV時間矩陣[1 1 9 3 13 17 23]，以此類推，最終確定調(diào)度方案。

針對最大完工時間、總延期以及設(shè)備總負(fù)荷的3個目標(biāo)的柔性作業(yè)車間調(diào)度問題，用本文改進(jìn)NSGA-Ⅱ算法求解得到的Pareto前沿如圖8所示，各解相互之間重疊小，解集覆蓋性較好。

3.2 AGV數(shù)量與調(diào)度目標(biāo)關(guān)系分析

為研究AGV數(shù)量變化對調(diào)度目標(biāo)的影響，本文基于8×8算例，取不同數(shù)量的AGV，進(jìn)行獨立測試，分別計算20次取平均值，得到結(jié)果如圖9所示。從圖9中可以看出，當(dāng)AGV數(shù)量超過3時，最大完工時間和總延期變化趨于平緩，而由于AGV增加造成AGV空載減少，設(shè)備總負(fù)荷會相應(yīng)減少。總的來說，隨著AGV數(shù)量的增加，三個目標(biāo)函數(shù)值會逐漸減小，且減小的幅度會越來越小，即對提高相同任務(wù)調(diào)度效率的影響隨AGV數(shù)量的增加而減小。實際生產(chǎn)過程中，在考慮AGV成本的情況下，選擇相同調(diào)度效率下AGV數(shù)量少的方案。

圖9 AGV數(shù)量對目標(biāo)函數(shù)值的影響Fig.9 Influence of AGV numbers on objective functions values

3.3 算法性能測試

為測試算法求解能力，設(shè)置不同AGV數(shù)量，在相同規(guī)模問題（8×8算例）下，實驗中AGV數(shù)V＜n，種群規(guī)模P=200，最大迭代次數(shù)M=100，交叉概率Pc=0.8，變異概率Pm=0.1。

不同AGV規(guī)模案例中，INSGA-Ⅱ算法求解8×8算例的3個目標(biāo)函數(shù)平均收斂曲線分別如圖10所示。由圖10可以看出，隨著AGV數(shù)量的增加，算法收斂速度先加快，后不變，3個目標(biāo)迭代到一定程度時均收斂到最優(yōu)值，可以證明改進(jìn)的NSGA-Ⅱ算法在求解此類調(diào)度問題上具有較強的搜索能力。

圖10 不同AGV數(shù)量下目標(biāo)函數(shù)平均收斂曲線圖Fig.10 Average convergence curves of objective functions under different AGV quantities

此外，構(gòu)建AGV=7案例，選擇多目標(biāo)粒子群優(yōu)化（multi-objective particle swarm optimization，MOPSO）算法[17]、混合差分進(jìn)化（hybrid differential evolution，HDE）算法[18]、非支配排序遺傳（non-dominated sorting genetic algorithm-Ⅱ，NSGA-Ⅱ）算法與本文算法進(jìn)行性能對比。AGV=7時以上3種算法下的目標(biāo)函數(shù)平均收斂曲線如圖11所示。結(jié)果可以看出，INSGA-Ⅱ算法克服了MOPSO和HDE求解AGV機器調(diào)度問題的過早收斂現(xiàn)象，且較NSGA-Ⅱ有更好的優(yōu)化效果。體現(xiàn)了本文改進(jìn)算法的可擴展性。

圖11 AGV=7時對比算法下的目標(biāo)函數(shù)平均收斂曲線圖Fig.11 Average convergence curves of objective functions under comparative algorithm at AGV=7

為進(jìn)一步驗證模型和INSGA-Ⅱ算法及優(yōu)化策略的有效性，分別使用文獻(xiàn)中3×5算例[19]、10×8算例[20]、12×10算例[21]和本文8×8算例數(shù)據(jù)進(jìn)行模型和算法測試。文獻(xiàn)算例中未指明的AGV運輸時間采用表4中數(shù)據(jù)。4種多目標(biāo)優(yōu)化算法在每組測試數(shù)據(jù)下分別運行20次取平均值，得到對比結(jié)果如表5所示。結(jié)果顯示，改進(jìn)算法均獲得更高質(zhì)量的解，證明本文INSGA-Ⅱ算法能夠有效求解帶有AGV約束的多目標(biāo)柔性作業(yè)車間調(diào)度問題，且對大規(guī)模問題也更好地優(yōu)化效果。

表5 不同案例算法對比結(jié)果Table 5 Comparison results of different case algorithms單位：min

4 結(jié)論

針對FJSP中較少考慮運輸過程的不足，本文在加工過程的基礎(chǔ)上增加了運輸資源AGV的調(diào)度，考慮多時間因素和一個或多個AGV組成的柔性作業(yè)車間系統(tǒng)，用于解決機器和多個相同AGV的同時調(diào)度問題。針對任務(wù)分配和AGV調(diào)度對模型進(jìn)行多目標(biāo)優(yōu)化，設(shè)計了改進(jìn)NSGA-Ⅱ算法，提出了基于AGV分配的貪婪式解碼策略，同時結(jié)合多種群和精英保留策略提高算法的搜索能力。通過與其他算法對比實驗，結(jié)果證明了本文提出模型的有效性，且改進(jìn)算法能夠獲得優(yōu)秀的調(diào)度結(jié)果。在下一步研究工作中，將重點研究模型中隨機因素對FJSP問題的影響以及進(jìn)一步改善算法求解效率。