張長(zhǎng)澤， 李引珍， 尹勝男， 裴 驍

(蘭州交通大學(xué)交通運(yùn)輸學(xué)院，蘭州 730070)

柔性作業(yè)車間調(diào)度問題(FJSP)是傳統(tǒng)作業(yè)調(diào)度車間問題(JSP)的延伸和拓展，不僅需要確定加工工序的順序，還要給每道工序分配機(jī)器，是比JSP更為復(fù)雜的NP-hard(non-deterministic polynomial hard)問題[1]。因?yàn)樵趯?shí)際生產(chǎn)過程中，至少存在一道工序的加工機(jī)器是可選機(jī)器中的部分機(jī)器，更符合實(shí)際生產(chǎn)系統(tǒng)中的調(diào)度問題，因此研究FJSP更具實(shí)際意義和理論價(jià)值。

目前，針對(duì)FJSP問題中外學(xué)者已經(jīng)做了深入的研究。李雅瓊等[2]利用時(shí)間Petri網(wǎng)建立區(qū)間柔性作業(yè)車間調(diào)度問題形式化模型，采用區(qū)間表示加工時(shí)間范圍求解線性規(guī)劃問題獲得最小完工時(shí)間下界(上界)的優(yōu)化調(diào)度策略。王雷等[3]以完工時(shí)間、機(jī)器能耗和工人操作機(jī)器的舒適度作為柔性作業(yè)車間調(diào)度問題的多目標(biāo)函數(shù)，提出一種基于權(quán)重的種群初始化方法，提高了初始化種群的質(zhì)量，將不同數(shù)量級(jí)的目標(biāo)轉(zhuǎn)換到相同的數(shù)量級(jí)，將多目標(biāo)轉(zhuǎn)換成單目標(biāo)。王春等[4]采用工件的最大完工時(shí)間和最大拖期時(shí)間最小兩個(gè)優(yōu)化目標(biāo)，引入最小偏差度作為第3個(gè)優(yōu)化目標(biāo)，引入虛擬工序和虛擬工時(shí)概念對(duì)該車間建立調(diào)度數(shù)學(xué)模型；采用MSOS編碼方式進(jìn)行編碼，提出一類基于優(yōu)先級(jí)的操作工序編碼方法。文獻(xiàn)[5-8]采用改進(jìn)的模擬退火算法將粒子群(PSO)中的編碼方式引用到機(jī)器編碼中；提出一種分布式粒子群優(yōu)化算法，采用隨機(jī)黑洞策略改進(jìn)鳥群的覓食方式，以增加種群的多樣性。馬佳等[9]和鄒澤樺等[10]引入免疫算子和種群的自適應(yīng)調(diào)節(jié)策略，提出一種改進(jìn)的自適應(yīng)交叉和變異的混合遺傳箅法。楊立熙等[11]提出一種改進(jìn)的免疫遺傳混合算法，采用基于工序和基于機(jī)器相結(jié)合的雙層編碼方式，即MSOS；設(shè)計(jì)自適應(yīng)交叉變異來控制遺傳操作，自適應(yīng)策略能夠在優(yōu)化過程中依照迭代次數(shù)自適應(yīng)改變交叉變異概率，避免陷入局部最優(yōu)解或收斂過早的情況。文獻(xiàn)[12-17]構(gòu)建了在單目標(biāo)和多目標(biāo)下的柔性作業(yè)車間調(diào)度模型，提出改進(jìn)的遺傳算法來進(jìn)行求解，如改進(jìn)編碼方式和遺傳算子，結(jié)合精英保留策略和小生境技術(shù)；將初始種群劃分為精英層和普通層，對(duì)精英層個(gè)體不斷進(jìn)行鄰域搜索；創(chuàng)建新的染色體表示方法(稱為置換工作)；將遺傳算法和模擬退火算法結(jié)合在一起等，取得了很多研究成果。然而，當(dāng)前對(duì)具有模糊加工時(shí)間的調(diào)度問題的研究較少，同時(shí)將到交貨滿意度一并考慮到柔性作業(yè)車間調(diào)度的研究還鮮見報(bào)道，以及目前大部分利用改進(jìn)的遺傳算法求解FJSP研究的文獻(xiàn)中仍存在局部搜索能力差、容易陷入早熟收斂的缺點(diǎn)。

考慮模糊生產(chǎn)環(huán)境下的模糊加工時(shí)間與模糊交貨期綜合問題的研究是目前環(huán)境形勢(shì)所確定的必然要求，具有非常重要的研究意義和實(shí)際應(yīng)用背景?；诖?，采用模糊數(shù)表示加工時(shí)間和交貨期，建立以完工時(shí)間、平均滿意度和最小滿意度為柔性作業(yè)車間調(diào)度問題的多目標(biāo)函數(shù)；將變鄰域搜索嵌入到遺傳算法中，以提高局部搜索能力避免陷入早熟收斂；通過數(shù)值實(shí)來驗(yàn)驗(yàn)證模型和算法的有效性和可行性。

1 問題描述

FJSP問題可描述如下：n個(gè)工件(J1，J2，…，Jn)需要在m臺(tái)機(jī)器(M1，M2，…，Mm)上加工；每個(gè)工件包含一道或多道工序；工序順序是預(yù)先確定的；每道工序可以在多臺(tái)不同加工機(jī)器上進(jìn)行加工，工序的加工時(shí)間隨著加工機(jī)器的不同而有所差異。調(diào)度目標(biāo)是為每道工序選擇最合適的機(jī)器，確定每臺(tái)機(jī)器上各道工序的最佳加工順序及開工時(shí)間，使整個(gè)系統(tǒng)的某些指標(biāo)達(dá)到最優(yōu)。因此，F(xiàn)JSP問題包含兩個(gè)問題：一是為每一道工序選擇可加工的機(jī)器(機(jī)器選擇子問題，MS)；二是在每臺(tái)機(jī)器上安排工序的加工順序，從而確定每道工序的開始時(shí)間和完成時(shí)間(工序排序子問題,OS)。調(diào)度目標(biāo)為同一臺(tái)機(jī)器在同一時(shí)刻只能加工一個(gè)工件；同一工件的同一道工序在同一時(shí)刻只能被一臺(tái)機(jī)器加工；每個(gè)工件的每道工序一旦開始，加工便不能中斷；所有工件的優(yōu)先級(jí)相同；不同工件的工序之間沒有先后約束，同一工件的工序之間有先后約束；所有工件在零時(shí)刻都可以被加工。

為了描述方便，定義以下符號(hào)：n為工件總數(shù)；m為機(jī)器總數(shù)；Ω為總的機(jī)器集；Ωjh為第j個(gè)工件的第h道工序的可選加工機(jī)器集；Ojh為第j個(gè)工件的第h道工序；Mijh為第j個(gè)工件的第h道工序在機(jī)器i上加工；pijh為第j個(gè)工件的第h道工序在機(jī)器i上的模糊加工時(shí)間；sjh為第j個(gè)工件的第h道工序加工開始時(shí)間；cjh為第j個(gè)工件的第h道工序加工完成時(shí)間；Dj為第j個(gè)工件的模糊交貨；Cj為每個(gè)工件的模糊完成時(shí)間；O0為所有工件的工序總數(shù)。

2 模型的建立

2.1 FJSP問題的數(shù)學(xué)模型

在柔性作業(yè)車間調(diào)度問題當(dāng)中，機(jī)器在加工過程中受各種因素的影響及根據(jù)人們的期望不同，機(jī)器的加工時(shí)間和工件的交貨期往往在一個(gè)區(qū)間內(nèi)變化。因此采用三角模糊數(shù)來表示工件的模糊加工時(shí)間和采用梯形模糊數(shù)來表示工件的交貨期。

求解模糊FJSP問題考慮3個(gè)優(yōu)化目標(biāo)，即最小化模糊最大完工時(shí)間、平均滿意度最大、最小滿意度最大，分別定義如下。

(1)模糊最大完工時(shí)間f1最小，即：

(1)

(2)平均滿意度f(wàn)2最大，即：

(2)

式中：AIj表示工件Jj的滿意度[18]，即指完工時(shí)間與交貨期之間的符合程度，滿意度可表示為

(3)

滿意度(AI)是模糊調(diào)度問題當(dāng)中最重要也是應(yīng)用最廣泛的評(píng)價(jià)指標(biāo)之一(圖1)，可以反映工件的加工時(shí)間與交貨期之間的滿意程度，也可直接反映到工件的生產(chǎn)成本、運(yùn)輸成本和儲(chǔ)存成本等多個(gè)經(jīng)濟(jì)指標(biāo)。

(3)最小滿意度f(wàn)3最大，即：

(4)

最小滿意度能夠影響到客戶對(duì)調(diào)度方案的選擇，對(duì)每個(gè)工件都提出了交貨期要求，以便使所有工件的交貨期趨于一致。

2.2 FJSP的模糊析取圖模型

在模糊析取圖模型中用O和*分別表示兩個(gè)虛設(shè)的起始工序和終止工序，每個(gè)節(jié)點(diǎn)v表示一個(gè)加工工序，節(jié)點(diǎn)上面的權(quán)值等于此節(jié)點(diǎn)工序在對(duì)應(yīng)機(jī)器上的模糊加工時(shí)間。在圖2所示的析取圖中，從起點(diǎn)O到終點(diǎn)*的最長(zhǎng)路徑稱為模糊關(guān)鍵路徑[19]，其長(zhǎng)度等于該調(diào)度的模糊最大完工時(shí)間，屬于模糊關(guān)鍵路徑上的每道工序稱為模糊關(guān)鍵工序。圖2中實(shí)線指向表示同一件工序的順序關(guān)系；虛線表示析取弧兩端的工序在同一臺(tái)機(jī)器上加工。圖2所示的一條關(guān)鍵路徑O→O31→O12→O13→O33→*，對(duì)應(yīng)的模糊完工時(shí)間為(27，38，50)，粗線連接的O31、O12、O13、O33為模糊關(guān)鍵工序。假設(shè)析取圖G上的一個(gè)節(jié)點(diǎn)h代表加工工序Oh，sE(h)、cE(h)、sL(h)、cL(h)分別代表工序Oh的模糊最早開工時(shí)間和完工時(shí)間、模糊最晚開工時(shí)間和完工時(shí)間；PM(h)和SM(h)分別表示工序Oh屬于同一機(jī)器的前道工序和后續(xù)工序；PJ(h)和SJ(h)分別表示工序Oh屬于同一工件的前道工序和后續(xù)工序。對(duì)于同一個(gè)調(diào)度方案可能存在多條關(guān)鍵路徑。

圖2 模糊析取圖實(shí)例

3 算法設(shè)計(jì)

3.1 GANS算法步驟

GANS算法采用NSGA-II[20]算法中的快速非支配排序方法。具體步驟如下。

步驟1 確定參數(shù)，設(shè)置包括種群規(guī)模P，最大迭代次數(shù)G，全局選擇(global selection，GS)、局部選擇(local selection，LS)、隨機(jī)選擇(random selection，RS)分別占群比例PGS、PLS、PRS，變異概率Pm等，并初始化種群，令迭代次數(shù)counter=0。

步驟2 采用工序插入式解碼評(píng)價(jià)種群個(gè)體適應(yīng)度，對(duì)種群進(jìn)行非支配解排序，找出當(dāng)前種群的非劣解，將非劣解與非劣解集中的非劣解進(jìn)行比較，并更新非劣解集。

步驟3 判斷算法是否滿足終止準(zhǔn)則(counter>G)，若滿足則停止迭代，返回最優(yōu)解，否則轉(zhuǎn)步驟4。

步驟4 按照交叉概率Pc=1-counter/G，選擇下面兩種方式之一進(jìn)行操作，直到產(chǎn)生的個(gè)體達(dá)到種群數(shù)為止：①?gòu)漠?dāng)前種群中利用輪盤賭法選擇兩個(gè)個(gè)體，分別對(duì)MS和OS部分進(jìn)行交叉，概率為1-Pc；②從記憶庫(kù)中隨機(jī)選擇一個(gè)個(gè)體，利用輪盤賭法選擇一個(gè)個(gè)體，分別對(duì)MS和OS部分進(jìn)行交叉，概率為Pc。

步驟5 根據(jù)變異概率Pm選取進(jìn)行變異的個(gè)體，進(jìn)行變異操作，得到新個(gè)體。

步驟6 對(duì)非劣解集中的非劣解進(jìn)行基于析取圖的鄰域搜索，用更新的個(gè)體取代當(dāng)前的個(gè)體。

步驟7 轉(zhuǎn)到步驟2。

3.2 種群的初始化

在進(jìn)化算法中種群的初始化是一個(gè)關(guān)鍵問題，初始解的質(zhì)量對(duì)遺傳算法求解的速度和質(zhì)量有非常大的影響。對(duì)于FJSP問題，機(jī)器選擇比工序排序更為重要，如何能夠較好地考慮機(jī)器負(fù)荷平衡，是非常有意義的。針對(duì)FJSP的特點(diǎn)，采用文獻(xiàn)[10]提出的GLR機(jī)器選擇方法，包括全局選擇GS、LS和RS。GS和LS主要是為了考慮機(jī)器選擇的負(fù)荷問題，使各臺(tái)被選擇的機(jī)器的工資負(fù)荷盡量平衡，提高機(jī)器的利用率；RS主要考慮使初始化種群盡量分散地分布于整個(gè)解空間，保持多樣性。

3.3 Pareto排序

由于FJSP屬于離散的組合優(yōu)化問題，因此適用于NSGA-Ⅱ算法中的快速非支配排序方法。假設(shè)種群為P，計(jì)算P中每個(gè)個(gè)體p的兩個(gè)參數(shù)np和sp，其中：np為種群中支配個(gè)體p的個(gè)體數(shù)；sp為種群中被個(gè)體p支配的個(gè)體的集合。具體的執(zhí)行步驟為①找到種群中np=0的個(gè)體，并保存在當(dāng)前集合Fl中；②對(duì)于當(dāng)前集合Fl中的每個(gè)個(gè)體i，其所支配的個(gè)體集合為si，遍歷si中的每個(gè)個(gè)體l，執(zhí)行nl=nl-1，如果nl=0則將個(gè)體l保存到集合H中；③記Fl中的得到的個(gè)體為第一非支配層的個(gè)體，所以H作為當(dāng)前集合，重復(fù)上述操作，直到整個(gè)種群被分級(jí)。

3.4 染色體的編碼和解碼

3.4.1 編碼

染色體編碼采用MSOS整數(shù)編碼方式，由兩部分組成，這兩部分的染色體長(zhǎng)度都等于所有工件工序總數(shù)Oo。以表1為例，對(duì)染色體編碼進(jìn)行闡述，如圖3所示，工序O11有4臺(tái)機(jī)器可以選擇，對(duì)應(yīng)的3表示可選機(jī)器集中第3臺(tái)機(jī)器，即在機(jī)器M3上加工。同理，工序O12有5臺(tái)機(jī)器可以選擇，對(duì)應(yīng)的4表示可選機(jī)器集中第4臺(tái)機(jī)器，即在機(jī)器M5上加工；OS(工序排序部分)的每基因用工件號(hào)編碼，工件號(hào)出現(xiàn)的順序表示該工件工序間的先后順序，即對(duì)染色體從左到右進(jìn)行編譯，對(duì)于第h次出現(xiàn)的工件號(hào)代表該工件j的第h道工序。如圖3所示，各個(gè)工件工序的加工順序?yàn)镺21→O11→O12→O22→O23→O13。

表1 2×6的FJSP數(shù)據(jù)

圖3 FJSP染色體編碼

3.4.2 解碼

FJSP染色體由機(jī)器選擇部分MS和工序排序部分OS組成，分別對(duì)其進(jìn)行解碼，關(guān)鍵是需要將工序排序部分解碼成對(duì)應(yīng)于機(jī)器選擇部分的活動(dòng)調(diào)度。采用工序插入式貪婪解碼算法，該算法描述如下：將染色體看作工序的有序序列，根據(jù)工序在該序列上的順序進(jìn)行解碼，每道工序插入到該工序可選加工機(jī)器上最佳可行的加工時(shí)刻安排加工，直到序列上的所有工序都安排完為止。

3.5 進(jìn)化算子

GAVNS算法的進(jìn)化算子包括交叉算子和變異算子，由于染色體編碼由MS和OS兩部分組成，所以交叉算子和變異算子都分別包括兩部分的交叉和變異。

3.5.1 交叉算子

交叉的目的是利用父代個(gè)體經(jīng)過一定操作之后產(chǎn)生新個(gè)體，在盡量降低有效模式被破壞的概率基礎(chǔ)上對(duì)解空間進(jìn)行高效搜索。機(jī)器選擇部分必須保證每位基因的先后順序保持不變，采用多點(diǎn)交叉(MPX)方式，具體操作如下：①選擇MS(機(jī)器選擇部分)的兩個(gè)父代P1和P2，并隨機(jī)生成一個(gè)長(zhǎng)度為Oo的0、1串；②遍歷該串，對(duì)第一個(gè)子代C1，為1的地方來自于父代P1的基因，為0的地方來自于父代P2的基因；③對(duì)第二個(gè)子代C2，為1的地方來自于父代P2的基因，為0的地方來自于父代P1的基因。工序部分應(yīng)保證交叉之后產(chǎn)生的解為可行解，采用基于工件優(yōu)先順序的多父代交叉(POX)，多父代交叉算子操作有可能在產(chǎn)生子代個(gè)體的過程中綜合更多(相對(duì)于兩父代而言)父代個(gè)體的信息，因而可能獲得更好的解空間搜索效率和尋優(yōu)質(zhì)量[21]，多父代交叉算子首先要求選擇3個(gè)及其以上的父代染色體，具體方法如下：①選擇OS部分的3個(gè)父代染色體P1、P2和P3，并把所有工件隨機(jī)劃分為兩個(gè)工件集，第一個(gè)子代C1的第一部分基因來自于第一個(gè)工件集里對(duì)應(yīng)的父代P1基因的原位置填充，第二個(gè)子代C2的第一部分基因來自于第二個(gè)工件集里對(duì)應(yīng)的父代P2基因的原位置填充；②遍歷父代P3的基因串，將基因按順序依次放入C1的空余位置和C2的空余位置，如圖4所示。

圖4 基于工件優(yōu)先順序的交叉操作

3.5.2 變異算子

變異算子的作用是為了改善算法的局部搜索能力，增加種群多樣性。

(1)對(duì)于機(jī)器選擇部分，因?yàn)槊康拦ば蚨伎梢杂啥嗯_(tái)機(jī)器完成，因此可在該工序的加工機(jī)器集中選擇一個(gè)加工時(shí)間最短的機(jī)器。

(2)對(duì)于工序排序部分，選定一個(gè)個(gè)體作為父代，然后隨機(jī)選擇一道工序，由于對(duì)同一工件來說各工序間有順序限制，要求在保證加工順序不變的前提下選擇一個(gè)工件各工序加工次序的某個(gè)基因插入到另外一個(gè)工件各工序加工次序基因串的對(duì)應(yīng)位置上。

3.6 鄰域搜索

鄰域搜索作為一種高效的局部搜索方法，在流水線調(diào)度問題中能夠較大改善算法的搜索性，因此，被應(yīng)用到許多組合優(yōu)化的問題求解當(dāng)中。鄰域搜索算法主要利用鄰域結(jié)構(gòu)的系統(tǒng)化變換思想，提高算法的局部搜索能力，并避免陷入局部最優(yōu)。因此，結(jié)合變鄰域搜索算法的特點(diǎn)，采取移動(dòng)模糊關(guān)鍵工序鄰域結(jié)構(gòu)。

通過對(duì)關(guān)鍵路徑上的一道工序在機(jī)器鏈表中位置進(jìn)行移動(dòng)或插入操作來得到新解。設(shè)析取圖G上移除一個(gè)關(guān)鍵工序k(k∈O，O表示所有工序的集合)后得到的析取圖G-。移動(dòng)關(guān)鍵工序的目的是在G-上將工序k插入新的機(jī)器得到G*，且滿足Cmax(G*)≤Cmax(G)。工序k的可選加工機(jī)器集為Ωk，具體操作如下。

步驟1 刪除節(jié)點(diǎn)k與同一臺(tái)機(jī)器上其他節(jié)點(diǎn)的弧連接，設(shè)置節(jié)點(diǎn)k的權(quán)值為0。

步驟2 從k的可選加工機(jī)器集中選擇一臺(tái)機(jī)器i(i∈Ωk)，將k分配給機(jī)器i并且選擇合適的插入位置，設(shè)置節(jié)點(diǎn)k的權(quán)值即在機(jī)器i上的加工時(shí)間pik。

假設(shè)插入位置在機(jī)器Mi上的工序r前且加工時(shí)間為pik，則工序r滿足：

max{CE[G-,PM(G-,r)],CE[G-,PJ(k)]}+pik≤min{sL[G-,r,Cmax(G)],sL[G-,SJ(k),Cmax(G)]}

(5)

所有的k插入位置中不然包括一個(gè)使總完工時(shí)間最小的插入，通過上面的操作可以得到工序k的所有鄰域集為

Nk=∪i∈ΩkNik

(6)

式(6)中：Nik表示機(jī)器i上的所有可行鄰域解集。但是節(jié)點(diǎn)插入必須滿足一定條件才可以是可行解，假設(shè)Qi是圖G-中在機(jī)器i上加工的工序集，其中k=Qi，且按在機(jī)器Mi上的最早模糊開工時(shí)間升序排列。定義以下兩個(gè)工序子集集合見式(7)，文獻(xiàn)[22]已經(jīng)證明節(jié)點(diǎn)k的最優(yōu)插入位置在所有節(jié)點(diǎn)Ri〗Li之前和在所有節(jié)點(diǎn)Li〗Ri之后。

(7)

則將工序k插入到Li(或Ri)所有工序之后，并且在Ri(或Li)所有工序之前的鄰域解集合為Nik。

綜上所述，當(dāng)工序k換到機(jī)器i上時(shí)，如果在圖G-中r到k的路徑存在，只有當(dāng)工序r必須在工序k之前調(diào)度時(shí)才會(huì)產(chǎn)生可行解；反之，如果工序k到工序r的路徑存在，只有當(dāng)工序r必須在工序k之后調(diào)度時(shí)才會(huì)產(chǎn)生可行解；如果工序r和工序k之間不存在路徑，無(wú)論工序r放在工序k前或后都會(huì)產(chǎn)生可行解。

3.7 改進(jìn)精英保留策略

為避免算法早熟或陷入局部最優(yōu)，確保算法朝著正確的Pareto曲面進(jìn)行搜索，提出一種改進(jìn)的精英策略，以保證種群的多樣性，即限制精英解的數(shù)量而選擇一些非精英解。該策略描述如下：①將父代Pt和子代Ct的全部個(gè)體合成為一個(gè)種群Qt(t為迭代次數(shù))，數(shù)量為2N；②將種群Qt中的每個(gè)個(gè)體按照Pareto等級(jí)進(jìn)行排序，然后選擇每個(gè)非劣前沿等級(jí)中等級(jí)個(gè)體數(shù)減1的個(gè)體值直接復(fù)制到下一代種群，若某些個(gè)體具有相同序值，則計(jì)算非劣解等級(jí)中的個(gè)體擁擠度，然后按照由小到大的原則逐個(gè)將個(gè)體復(fù)制到下一代種群；③重復(fù)該過程，直到種群規(guī)模達(dá)到進(jìn)化群體規(guī)模為止。

同時(shí)，為更好地利用非劣解的優(yōu)良信息，以加快算法的收斂速度，每一次對(duì)新種群評(píng)價(jià)排序之后，都需要對(duì)非劣解集進(jìn)行更新，由于FJSP是離散問題，非劣解集記錄進(jìn)化過程中產(chǎn)生的所有非劣解，在每次更新時(shí)，新解與非劣解集的所有解進(jìn)行比較：如果新解被非劣解集中某個(gè)解所支配，則丟棄新解；如果新解支配非劣解集中的某個(gè)解，則用新解替換非劣解集中的當(dāng)前解；如果沒有支配關(guān)系存在，則將新解加入非劣解集。

4 數(shù)值試驗(yàn)

4.1 試驗(yàn)設(shè)計(jì)

算法在操作系統(tǒng)為Windows 7，Intel(R) Core(TM) i5-2450M CPU @2.50 GHz 4.0 GB，MATLAB R2018a平臺(tái)上進(jìn)行測(cè)試。參數(shù)設(shè)置如下：種群規(guī)模P=200，GS、LS、RS比列分別為0.6、0.3、0.1，種群最大迭代次數(shù)G=200，變異概率Pm=0.1。為驗(yàn)證GAVNS算法的優(yōu)劣性，選取某加工產(chǎn)8個(gè)工件在8臺(tái)機(jī)器上加工的P-FJSP，其中每個(gè)工件的加工時(shí)間不確定，且交貨期也有不同的要求，如表2所示。

表2 8×8 的P-FJSP數(shù)據(jù)

4.2 模型的計(jì)算結(jié)果及分析

4.2.1 結(jié)果分析

為驗(yàn)證GANS算法對(duì)具有模糊加工時(shí)間和模糊交貨期的柔性作業(yè)車間調(diào)度問題的有效性，與NSGA-II算法對(duì)解的結(jié)果進(jìn)行比較。兩種算法的Pareto最優(yōu)解如表3所示。由表3可知，GANS求解得到的Pareto最優(yōu)解比NSGA-II求解所得到的Pareto最優(yōu)解要多，且GANS中的最好解比NSGA-II的優(yōu)或相當(dāng)，解的結(jié)果良好。

4.2.2 測(cè)試算列

為進(jìn)一步驗(yàn)證GANS算法的穩(wěn)定性和求得的解集的分布性，用文獻(xiàn)[23]中分布度Δ與分布率Δv來表示解集的分布性，如式(8)所示：

(8)

利用GANS算法對(duì)WangData測(cè)試數(shù)據(jù)[24]進(jìn)行優(yōu)化求解，其中WangData測(cè)試數(shù)據(jù)包括4×6、6×10、8×8、10×10，并且與傳統(tǒng)GA的求解結(jié)果進(jìn)行比。分布度越小表示所求非支配解集中解的分布性越好；分布率的值越小表示算法運(yùn)行時(shí)的穩(wěn)定性越好。試驗(yàn)結(jié)果如表4所示。

表3 8×8FJSP的Pareto最優(yōu)解

由表4可知，GANS算法較NSGA-II算法具有更好的分布性和穩(wěn)定性，說明混合GANS算法在求解模糊FJSP問題時(shí)的有效性。

5 結(jié)論

考慮了模糊操作時(shí)間和模糊交貨期同時(shí)存在的情況，建立了以工件最終完成時(shí)間和交貨期相交所得到的平均滿意度最大、最小滿意度最大以及最大完工時(shí)間最小為目標(biāo)的模糊FJSP的調(diào)度模型，然后設(shè)計(jì)了改進(jìn)的遺傳算法。數(shù)值試驗(yàn)驗(yàn)證了模型和算法對(duì)于模糊柔性作業(yè)車間調(diào)取問題的可行性和有效性，并使用MATLAB工具將算法對(duì)WangData測(cè)試數(shù)據(jù)進(jìn)行測(cè)試，與NSGA-II算法進(jìn)行對(duì)比。結(jié)果表明提出算法具有較好的可行性、高效性、精確性和魯棒性。得出以下結(jié)論。

(1)在建立模型時(shí)，考慮了工件加工時(shí)間和交貨期這兩個(gè)不確定因素同時(shí)存在的情況，并引入滿意度這一概念，使得客戶能夠?qū)φ{(diào)度方案進(jìn)行很好的選擇并對(duì)其整體滿意度進(jìn)行衡量。

(2)針對(duì)遺傳算法多樣性容易丟失的特點(diǎn)，在選擇個(gè)體進(jìn)行交叉時(shí)，采用動(dòng)態(tài)交叉概率，即不需要用戶輸入交叉概率，比較符合工程需要。

(3)提出改進(jìn)精英保留策略來提高算法的收斂性。

(4)為提高算法的局部搜索能力，采用移動(dòng)模糊關(guān)鍵工序鄰域結(jié)構(gòu)。

今后研究中應(yīng)考慮工件具有動(dòng)態(tài)性，即柔性作業(yè)車間的動(dòng)態(tài)調(diào)度問題。由于在動(dòng)態(tài)調(diào)度中，工件的技術(shù)路徑、到達(dá)時(shí)間、交貨期、各工序加工時(shí)間及可選的加工機(jī)器集合等并非事先知道，只能隨著時(shí)間的推移而逐漸獲得，因此更加符合實(shí)際的生產(chǎn)調(diào)度過程。

表4 各算法求解WangData測(cè)試數(shù)據(jù)的試驗(yàn)結(jié)果