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

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

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

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

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

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

1.1 問(wèn)題描述

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

1.2 參數(shù)定義

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

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

其中：

1.3 模型建立

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

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

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

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

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

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

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

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

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

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

（1）最小化最大完工時(shí)間：

工件從入庫(kù)到出庫(kù)整個(gè)流程結(jié)束表示其加工完成，則工件最大完工時(shí)間為結(jié)束加工時(shí)間與加工完后從最后一臺(tái)機(jī)器到出庫(kù)區(qū)的運(yùn)輸時(shí)間之和。

（2）最小化總延期：

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

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

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

2 求解算法設(shè)計(jì)

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

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

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

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

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

表2 3×5 FJSP問(wèn)題實(shí)例Table 2 Example of 3×5 FJSP problem

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

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

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

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

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

（3）確定工序開(kāi)始加工時(shí)間Si,j,k。解碼計(jì)算時(shí)需考慮工件和加工機(jī)器的約束，見(jiàn)公式（23）、（24）。

（4）確定AGV運(yùn)輸時(shí)間Tv,Wi,j。解碼計(jì)算時(shí)需考慮機(jī)器和AGV的雙約束，見(jiàn)公式（21）、（22）。

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

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

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

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

（1）選擇算子

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

（2）交叉變異算子

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.5 算法流程

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

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

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

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

3 車(chē)間調(diào)度仿真實(shí)例

3.1 案例求解

本文以表3所示的8×8問(wèn)題實(shí)例和表4所示的AGV搬運(yùn)時(shí)間為例，對(duì)以最大完工時(shí)間、總延期、設(shè)備總負(fù)荷為優(yōu)化目標(biāo)的FJSP問(wèn)題進(jìn)行驗(yàn)證。問(wèn)題規(guī)模設(shè)置為工件數(shù)n=8，機(jī)器數(shù)m=8，AGV數(shù)V=3。采用Matlab 2018b進(jìn)行編程實(shí)現(xiàn)，實(shí)驗(yàn)在平臺(tái)（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á)時(shí)間和交貨期的8×8 FJSP問(wèn)題實(shí)例Table 3 Example of 8×8 FJSP problem with workpiece arrival time and delivery date單位：min

表4 AGV搬運(yùn)時(shí)間Table 4 AGV handling time 單位：min

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

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

校正后該方案得到AGV的運(yùn)輸時(shí)間矩陣為：

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

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

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

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

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

3.3 算法性能測(cè)試

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

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

圖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)行性能對(duì)比。AGV=7時(shí)以上3種算法下的目標(biāo)函數(shù)平均收斂曲線如圖11所示。結(jié)果可以看出，INSGA-Ⅱ算法克服了MOPSO和HDE求解AGV機(jī)器調(diào)度問(wèn)題的過(guò)早收斂現(xiàn)象，且較NSGA-Ⅱ有更好的優(yōu)化效果。體現(xiàn)了本文改進(jìn)算法的可擴(kuò)展性。

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

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

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

4 結(jié)論

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