多目標模糊柔性作業車間調度問題優化

張長澤， 李引珍， 尹勝男， 裴 驍

(蘭州交通大學交通運輸學院，蘭州 730070)

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

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

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

1 問題描述

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

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

2 模型的建立

2.1 FJSP問題的數學模型

在柔性作業車間調度問題當中，機器在加工過程中受各種因素的影響及根據人們的期望不同，機器的加工時間和工件的交貨期往往在一個區間內變化。因此采用三角模糊數來表示工件的模糊加工時間和采用梯形模糊數來表示工件的交貨期。

求解模糊FJSP問題考慮3個優化目標，即最小化模糊最大完工時間、平均滿意度最大、最小滿意度最大，分別定義如下。

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

(1)

(2)平均滿意度f2最大，即：

(2)

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

(3)

滿意度(AI)是模糊調度問題當中最重要也是應用最廣泛的評價指標之一(圖1)，可以反映工件的加工時間與交貨期之間的滿意程度，也可直接反映到工件的生產成本、運輸成本和儲存成本等多個經濟指標。

(3)最小滿意度f3最大，即：

(4)

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

2.2 FJSP的模糊析取圖模型

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

圖2 模糊析取圖實例

3 算法設計

3.1 GANS算法步驟

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

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

步驟2 采用工序插入式解碼評價種群個體適應度，對種群進行非支配解排序，找出當前種群的非劣解，將非劣解與非劣解集中的非劣解進行比較，并更新非劣解集。

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

步驟4 按照交叉概率Pc=1-counter/G，選擇下面兩種方式之一進行操作，直到產生的個體達到種群數為止：①從當前種群中利用輪盤賭法選擇兩個個體，分別對MS和OS部分進行交叉，概率為1-Pc；②從記憶庫中隨機選擇一個個體，利用輪盤賭法選擇一個個體，分別對MS和OS部分進行交叉，概率為Pc。

步驟5 根據變異概率Pm選取進行變異的個體，進行變異操作，得到新個體。

步驟6 對非劣解集中的非劣解進行基于析取圖的鄰域搜索，用更新的個體取代當前的個體。

步驟7 轉到步驟2。

3.2 種群的初始化

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

3.3 Pareto排序

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

3.4 染色體的編碼和解碼

3.4.1 編碼

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

表1 2×6的FJSP數據

圖3 FJSP染色體編碼

3.4.2 解碼

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

3.5 進化算子

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

3.5.1 交叉算子

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

圖4 基于工件優先順序的交叉操作

3.5.2 變異算子

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

(1)對于機器選擇部分，因為每道工序都可以由多臺機器完成，因此可在該工序的加工機器集中選擇一個加工時間最短的機器。

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

3.6 鄰域搜索

鄰域搜索作為一種高效的局部搜索方法，在流水線調度問題中能夠較大改善算法的搜索性，因此，被應用到許多組合優化的問題求解當中。鄰域搜索算法主要利用鄰域結構的系統化變換思想，提高算法的局部搜索能力，并避免陷入局部最優。因此，結合變鄰域搜索算法的特點，采取移動模糊關鍵工序鄰域結構。

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

步驟1 刪除節點k與同一臺機器上其他節點的弧連接，設置節點k的權值為0。

步驟2 從k的可選加工機器集中選擇一臺機器i(i∈Ωk)，將k分配給機器i并且選擇合適的插入位置，設置節點k的權值即在機器i上的加工時間pik。

假設插入位置在機器Mi上的工序r前且加工時間為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插入位置中不然包括一個使總完工時間最小的插入，通過上面的操作可以得到工序k的所有鄰域集為

Nk=∪i∈ΩkNik

(6)

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

(7)

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

綜上所述，當工序k換到機器i上時，如果在圖G-中r到k的路徑存在，只有當工序r必須在工序k之前調度時才會產生可行解；反之，如果工序k到工序r的路徑存在，只有當工序r必須在工序k之后調度時才會產生可行解；如果工序r和工序k之間不存在路徑，無論工序r放在工序k前或后都會產生可行解。

3.7 改進精英保留策略

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

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

4 數值試驗

4.1 試驗設計

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

表2 8×8 的P-FJSP數據

4.2 模型的計算結果及分析

4.2.1 結果分析

為驗證GANS算法對具有模糊加工時間和模糊交貨期的柔性作業車間調度問題的有效性，與NSGA-II算法對解的結果進行比較。兩種算法的Pareto最優解如表3所示。由表3可知，GANS求解得到的Pareto最優解比NSGA-II求解所得到的Pareto最優解要多，且GANS中的最好解比NSGA-II的優或相當，解的結果良好。

4.2.2 測試算列

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

(8)

利用GANS算法對WangData測試數據[24]進行優化求解，其中WangData測試數據包括4×6、6×10、8×8、10×10，并且與傳統GA的求解結果進行比。分布度越小表示所求非支配解集中解的分布性越好；分布率的值越小表示算法運行時的穩定性越好。試驗結果如表4所示。

表3 8×8FJSP的Pareto最優解

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

5 結論

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

(1)在建立模型時，考慮了工件加工時間和交貨期這兩個不確定因素同時存在的情況，并引入滿意度這一概念，使得客戶能夠對調度方案進行很好的選擇并對其整體滿意度進行衡量。

(2)針對遺傳算法多樣性容易丟失的特點，在選擇個體進行交叉時，采用動態交叉概率，即不需要用戶輸入交叉概率，比較符合工程需要。

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

(4)為提高算法的局部搜索能力，采用移動模糊關鍵工序鄰域結構。

今后研究中應考慮工件具有動態性，即柔性作業車間的動態調度問題。由于在動態調度中，工件的技術路徑、到達時間、交貨期、各工序加工時間及可選的加工機器集合等并非事先知道，只能隨著時間的推移而逐漸獲得，因此更加符合實際的生產調度過程。

表4 各算法求解WangData測試數據的試驗結果