求解柔性作業(yè)車間調(diào)度的遺傳算法綜述

黃學文，陳紹芬，周闐玉，孫宇婷

(大連理工大學 經(jīng)濟管理學院，遼寧 大連 116024)

0 引言

調(diào)度通過合理安排生產(chǎn)資源，以縮短生產(chǎn)時間和提高資源利用率為目的，在生產(chǎn)系統(tǒng)中扮演著重要的角色。作業(yè)車間調(diào)度問題(Job-shop Scheduling Problem, JSP)是一類經(jīng)典的調(diào)度問題，其通過安排n個工件在m臺機器上的加工順序來優(yōu)化一個或多個調(diào)度指標。在JSP中，每個工件由一道或多道具有固定加工順序的工序構成，且每道工序的加工機器唯一。柔性作業(yè)車間調(diào)度問題(Flexible Job-shop Scheduling Problem, FJSP)是JSP的擴展，它允許一道工序有多臺可供選擇的加工機器，且在不同機器上的加工時間可能存在差異，即相對于JSP，F(xiàn)JSP具有一般性，更符合柔性制造系統(tǒng)的實際情況。在FJSP中，機器柔性雖然能夠提高制造系統(tǒng)的執(zhí)行效率，但是擴大了可行解的范圍，增加了求解問題的難度和復雜性。

FJSP是一類復雜的NP-hard問題[1]，元啟發(fā)式算法為求解該問題的重要方法，如遺傳算法(Genetic Algorithm, GA)[2-6]、禁忌搜索(Tabu Search, TS)算法[7-9]、蟻群優(yōu)化(Ant Colony Optimization, ACO)算法[10-11]和粒子群優(yōu)化(Particle Swarm Optimization, PSO)算法[12-13]等，其中遺傳算法因操作簡單、通用性強，且具有良好的魯棒性，而成為求解FJSP最受歡迎的算法之一[14-15]。

遺傳算法由Holland于20世紀60年代提出[16]。首先，遺傳算法將待求解問題的解通過染色體編碼方法映射為編碼空間中的染色體(chromosome)，染色體由一定數(shù)量的基因構成，基因及其在染色體上的排列決定了染色體的語義特征；其次，遺傳算法是一種基于群體的方法，染色體代表群體中的個體，通過對群體進行迭代遺傳操作(包括選擇、交叉、變異等)得到問題的最優(yōu)解或近似最優(yōu)解。其中，染色體編碼方法和遺傳算子(特別是交叉算子和變異算子)設計是構造遺傳算法首先需要考慮的兩個重要且互相交織的問題，二者對求解效率和質(zhì)量的影響非常明顯[17-18]，即對于不同優(yōu)化問題，需要設計滿足問題特定約束條件的染色體編碼方法，同時交叉和變異算子的設計或選擇又需要遵守所采用的染色體編碼方法的語義特征。需要說明的是，選擇算子的選擇和設計一般獨立于具體的染色體編碼方法，在求解各類問題中具有高度的通用性，常用的有輪盤賭、錦標賽和精英保留等選擇算子，具體參見文獻[19- 20]。

遺傳算法應用于FJSP時遵循遺傳算法求解一般問題的標準流程，即設計染色體編碼方法來表達FJSP，并形成初始種群，然后對群體進行迭代遺傳操作。具體表現(xiàn)為：利用選擇算子根據(jù)個體的適應度進行選擇操作，利用交叉和變異算子對染色體進行交叉和變異操作，完成種群的不斷繁殖和迭代進化；滿足迭代的終止條件后，輸出搜索到的最優(yōu)解或近似最優(yōu)解。自PAREDIS[21]第一次采用遺傳算法求解FJSP以來，在過去的30年中，學者們設計了許多形式各異的遺傳算法，以及相應的染色體編碼方法和遺傳算子，并取得了良好的結果。本文對求解FJSP的遺傳算法中的兩個關鍵內(nèi)容——染色體編碼方法以及交叉和變異算子進行綜述，以為進一步開展遺傳算法求解FJSP提供系統(tǒng)性的理論支持。

1 FJSP描述

FJSP可描述為：有n個相互獨立的待加工工件(記為工件集J={J1,…,Jn})在m臺加工機器(記為機器集M={M1,…,Mm})上加工，每個工件Ji包含ni道具有固定加工順序的工序，即Ji={Oi1,Oi2,…,Oini}，且工序Oij可在其候選機器集合Mij(Mij?M)中的任意一臺機器上加工。FJSP需要確定每道工序的加工機器(路徑子問題)，并確定所有工序在機器上的加工順序(調(diào)度子問題)，以實現(xiàn)對一個或多個調(diào)度目標的優(yōu)化，如最大完工時間、總機器負荷、總延遲時間、最大松弛時間等。

求解FJSP通常需要滿足如下假設條件：

(1)0時刻，所有工件均處于待加工狀態(tài)，所有機器均處于空閑狀態(tài)。

(2)同一時刻，同一臺機器只能加工一個工件的某道工序。

(3)同一時刻，同一工件只能被一臺機器加工，且不允許中斷正在加工的工序。

(4)同一工件的工序加工順序固定且不可更改，不同工件的工序間沒有順序約束關系。

基于上述FJSP的描述，很多學者提出求解FJSP的0-1整數(shù)規(guī)劃模型[22-25]，另外析取圖模型也常用于描述FJSP[26-28]，本文不再給出這些模型的數(shù)學定義。

根據(jù)生產(chǎn)系統(tǒng)的柔性程度，F(xiàn)JSP可分為完全柔性作業(yè)車間調(diào)度問題(Total FJSP, T-FJSP)和部分柔性作業(yè)車間調(diào)度問題(Partial FJSP, P-FJSP)兩類。在T-FJSP中，對于任意工序Oij，可選擇機器集合M中的任意一臺機器加工，即Mij=M；在P-FJSP中，至少存在一道工序Oij，有Mij?M且Mij≠M。表1所示為3個工件在3臺機器上加工的P-FJSP實例，其中“-”表示該工序無法在對應機器上加工。

表1 3×3的P-FJSP實例

2 染色體編碼方法

染色體編碼方法是遺傳算法首要解決的問題[18]，原因是：①它定義了染色體上的基因排列形式及其語義特征，從而決定了編碼空間基因型與解空間表現(xiàn)型之間的映射關系和遺傳搜索空間的大??；②它嚴重影響交叉和變異算子的設計、選擇和執(zhí)行[17-18]。一個不完善的染色體編碼方法甚至會在交叉或變異操作之后產(chǎn)生不可行解，此時需要設計額外的染色體修復機制來保證解的可行性，不僅降低了遺傳算法的計算效率，還增加了設計的復雜性。

本文將求解FJSP的染色體編碼方法分為5大類，即MSOS(machine selection and operation sequence)編碼、三元組編碼、表格編碼、矩陣編碼和A/B串編碼。除此之外，還有一些不常使用的染色體編碼方法，如TAY等[29]提出的三段編碼。

設表1所示FJSP的一種工序加工順序為(O21,M2)?(O11,M1)?(O31,M3)?(O12,M2)?(O32,M1)?(O22,M1)?(O23,M3)，其中：二元組(Oij,Mk)表示Oij在機器Mk上加工；符號“?”表示工序之間的加工順序性；工序O21在該加工順序中為第一個被調(diào)度的工序。圖1所示為該工序的加工順序在半主動調(diào)度(1)調(diào)度分為4種類型，即半主動調(diào)度、主動調(diào)度、非延遲調(diào)度和混合調(diào)度，其中半主動調(diào)度是在不改變?nèi)我鈾C器上工序加工順序的前提下，沒有任何工序可以減小加工開始時間的調(diào)度。其他幾種調(diào)度類型可參見文獻[30]。下的甘特圖。為了便于說明問題，以下分別用這5類編碼方法表示圖1對應的調(diào)度方案。

2.1 MSOS編碼

在求解FJSP的各類遺傳算法中，MSOS編碼方法應用得最廣泛，其最初由HO等[31]提出。MSOS編碼將染色體分為機器選擇串(machine selection)和工序順序串(operation sequence)兩條子串(或子染色體)，分別用于解決路徑子問題和調(diào)度子問題。

i=k，j=x-lk-1，lk-1

機器選擇串中的基因編碼又分為兩種方法：①將機器選擇串上的基因用該位置對應工序的加工機器的機器號或機器索引號(所選加工機器在候選機器集合中的索引)編碼[2, 8, 32-40]；②將機器選擇串上的基因用一個0-1數(shù)組編碼[31, 41-42]，其中0-1數(shù)組的長度等于該基因?qū)ば虻暮蜻x機器集合的模，且每個0-1數(shù)組中有且只有一個元素的值為1，其他值均為0，機器選擇串中每個位置上的0-1數(shù)組表示對應工序由1所對應的機器加工。

根據(jù)前文機器選擇串的編碼方法，將MSOS編碼分為MSOS-I編碼和MSOS-II編碼，分別對應機器選擇串中編碼的方法①和方法②。圖2所示為MSOS-I和MSOS-II編碼方法對圖1調(diào)度方案的編碼示例，兩種編碼方法中的工序順序串完全一致，例如該串中的兩個“1”從左到右依次表示工件J1的第1道和第2道工序，即工序O11和O12，第1個基因值“1”(位于串中第2位)表示工序O11，為全部工序中第2個被調(diào)度的工序。另一方面，兩種編碼方法中的機器選擇串各不相同，其中圖2a的機器選擇串是MSOS-I(采用機器索引號編碼)的編碼結果，圖2b的機器選擇串是MSOS-II的編碼結果。例如，圖1中工序O11選用機器M1加工，MSOS-I編碼通過設置機器選擇串中第1個基因座的基因為“1”來表示工序O11選用了其候選機器集合{M1,M3}中的第1臺機器M1加工；MSOS-II編碼通過將0-1數(shù)組中的機器M1對應位置的值設為“1”來表示O11選用機器M1加工。

顯然，任意一個由MSOS編碼生成的染色體總可以解碼成一個可行的調(diào)度方案，這是因為機器選擇串總為每道工序指派一臺可行的加工機器，且工序順序串總可以解碼為一個可行的調(diào)度方案(基于工序的編碼總對應JSP的一個可行調(diào)度[18]，當每道工序指派了一臺加工機器后，F(xiàn)JSP變成一個標準的FJSP)。另外，MSOS編碼中的兩條子串分別有不同的語義特征，且在編碼階段采用相互獨立的編碼方法，因此可以使用符合各自語義特征的交叉算子和變異算子分別對兩條子串進行遺傳操作。

2.2 三元組編碼

三元組編碼方法生成的任意一條染色體總可以解碼成一個可行的調(diào)度方案。三元組(i,j,k)中的3個變量有不同的語義特征，其中前兩個變量(即i,j)及其從左到右的排列順序表示調(diào)度子問題，第3個變量(即k)表示路徑子問題，因此可以結合FJSP中的兩個子問題的定義以及這些變量的具體語義特征進行單獨的交叉和變異操作。

2.3 表格編碼

表格編碼最初由MESGHOUNI[49]提出，其首先通過隨機算法或啟發(fā)式算法等分配算法為每道工序指派一臺加工機器，得到一個機器分配表，再運用調(diào)度規(guī)則將機器分配表轉(zhuǎn)換為確定了工序的加工開始時間、加工完成時間或加工機器的譯碼分配表，得到一個完整的調(diào)度方案。在譯碼分配表時，調(diào)度規(guī)則用于解決調(diào)度過程中出現(xiàn)多道工序，需要在同一時間段使用同一臺機器的沖突，即保證每次只有一個工序被調(diào)度。常用的調(diào)度規(guī)則有最短加工時間優(yōu)先(Shortest Processing Time first，SPT)、最長加工時間優(yōu)先(Largest Processing Time first，LPT)和后進先出(Last In First Out，LIFO)等。

表格編碼共有3種形式，分別是工序機器編碼(Operations Machines Coding, OMC)、平行工件編碼(Parallel Jobs Representation,PJsR)和平行機器編碼(Parallel Machine Representation, PMR)。下面以OMC為例對表格編碼法進行說明。

首先，通過一種分配算法，如theapproach by localization[50]，為每道工序確定一臺加工機器，得到一個機器分配表，如圖4a所示。機器分配表中的行表示工序，列表示機器；單元格中的值為1表示該工序選擇了對應列上的機器，值為0表示未選擇對應列上的機器。顯然，機器分配表中任意一行有且只有一個單元格的值為1(因為每道工序只能選擇一臺機器)。然后，通過調(diào)度規(guī)則將機器分配表中的數(shù)值1轉(zhuǎn)換為該工序的加工開始時間和加工完成時間，從而得到譯碼分配表，即一個可行的調(diào)度方案，如圖4b所示。譯碼分配表中第1行第1列的二元組為(0,1)，表示工序O11在機器M1上的加工開始時間為0，加工完成時間為1。

這種編碼方法生成的任意一條染色體總表示一個可行調(diào)度方案，然而因為基于調(diào)度規(guī)則生成的調(diào)度方案不能保證是全局最優(yōu)解或近似最優(yōu)解，所以采用表格編碼的遺傳算法不能保證生成高質(zhì)量的調(diào)度方案。

2.4 矩陣編碼

這種編碼方法可看作為三元組編碼的變型，只是將三元組編碼中選擇的機器從機器號表示換成0-1數(shù)組表示，因此矩陣編碼繼承了三元組編碼的特點。

2.5 A/B串編碼

CHEN等[53]提出A/B串編碼，其將一條染色體分成A，B兩條子串，其中：A串與MSOS-I編碼中的機器選擇串相同(此處采用機器號編碼)，用于確定每道工序的加工機器；在A串已經(jīng)確定每臺機器加工工序的基礎上，B串用于記錄每臺機器上的工序加工順序，因此B串共有m個基因。圖1中的調(diào)度方案采用該編碼方法的結果如圖6所示，由A串可得，機器M1需要加工工序O11，O22，O32，M2需要加工工序O12，O21，M3需要加工工序O23，O31。B串基于A串給出了各臺機器上的工序加工順序，即O11?O32?O22，O21?O12和O31?O23。

A/B串編碼無法保證任意一條染色體均可解碼為一個可行的調(diào)度方案，因此需要額外的染色體修復機制。這是因為：①B串中各機器上的加工工序不一定與A串確定的在同一臺機器上的加工工序一致，特別是在交叉和變異操作之后；②B串只確定了每臺機器上的工序加工順序，全部工序的加工順序可能產(chǎn)生循環(huán)調(diào)度現(xiàn)象，即死鎖狀態(tài)。例如，若將圖6中B串機器M3上工序的加工順序改為O23?O31，則會出現(xiàn)循環(huán)調(diào)度O32?O22?O23?O31?O32。以上情況表明，B串依賴A串，且B串的遺傳操作要遵循多重約束(即解決上述兩個問題)，從而極大增加了B串交叉和變異的復雜性。

3 遺傳算子

遺傳算法主要有選擇、交叉和變異3類遺傳算子，其中交叉和變異算子直接以染色體為操作對象，與染色體的編碼方法及其所表示的語義特征密切相關。

3.1 交叉算子

交叉算子是遺傳算法產(chǎn)生新個體的主要操作，其在很大程度上決定算法性能的高低[54]。交叉操作前先需要選擇性地對群體中的個體進行兩兩配對，然后再以某種方式交換配對染色體的部分基因，形成兩條新染色體(即子代染色體)。目前，在求解FJSP的遺傳算法中使用的交叉算子主要有以下8種形式。

3.1.1 單點交叉

單點交叉為經(jīng)典的交叉算子[53, 55]，即在染色體中隨機選擇一個交叉點，并互換兩條染色體交叉點之后的所有基因，產(chǎn)生兩條新的染色體，具體操作過程如下：

步驟1隨機選擇兩條染色體P1和P2，并隨機設置某個基因座為交叉點。

步驟2相互交換交叉點之后的所有基因，產(chǎn)生兩條新的染色體O1和O2。

單點交叉適用于MSOS中的機器選擇串和A/B串編碼中的A串，圖7所示為MSOS-I編碼中的機器選擇串應用單點交叉的一個實例，圖中縱向虛線表示交叉點。然而，單點交叉不適用于其他子串或編碼方法。以MSOS的工序順序串為例，若采用單點交叉算子，則子代染色體不能保證工件號i有且僅出現(xiàn)ni次，即不能保證解的可行性。

3.1.2 兩點交叉

兩點交叉為經(jīng)典的交叉算子[56-57]，即在染色體中隨機選擇兩個交叉點，并互換兩個交叉點之間的所有基因，產(chǎn)生兩條新的染色體，具體操作過程如下：

步驟1隨機選擇兩條染色體P1和P2，并隨機設置兩個基因座為交叉點。

步驟2相互交換兩個交叉點之間的所有基因，產(chǎn)生兩條新的染色體O1和O2。

顯然，兩點交叉適用于MSOS的機器選擇串和A/B串編碼的A串，但不適用于其他子串或編碼方法，原因與單點交叉算子相同。圖8所示為MSOS-II編碼中的機器選擇串(用0-1數(shù)組表示基因)應用兩點交叉的一個實例。

3.1.3 均勻交叉

均勻交叉為經(jīng)典的交叉算子[58-61]，屬于多點交叉，其通過隨機產(chǎn)生的一條與染色體長度相同的二進制串，來決定子代染色體上基因與父代染色體上基因之間的繼承關系，具體操作過程如下：

步驟1隨機選擇兩條染色體P1和P2，并初始化兩條空的子代染色體O1和O2。

步驟2隨機產(chǎn)生一條與染色體長度相同的二進制串w1,w2,…,wi,…,wl,其中l(wèi)表示染色體的長度。

步驟3若wi=0，則O1第i個基因座上的基因繼承P1相同基因座上的基因，O2第i個基因座上的基因繼承P2相同基因座上的基因；若wi=1，則O1第i個基因座上的基因繼承P2相同基因座上的基因，O2第i個基因座上的基因繼承P1相同基因座上的基因。

均勻交叉適用于MSOS的機器選擇串和A/B串編碼的A串，但不適用于其他子串或編碼方法，原因與單點交叉算子相同。圖9所示為MSOS-I編碼中的機器選擇串應用均勻交叉的一個實例。

3.1.4 POX

POX(precedence preserving order-based crossover)是典型適用于基于工序編碼的交叉算子[62-63]，該算子可以保證所有工件在父代和子代中出現(xiàn)的次數(shù)相同，并保持任意工件工序之間的順序約束關系，具體操作過程如下：

步驟1隨機選擇兩條染色體P1和P2，并初始化兩條空的子代染色體O1和O2。

步驟2將工件集隨機分為兩個非空的集合S1和S2，且S1∪S2=J，S1∩S2=?。

步驟3將P1中屬于集合S1的工件所對應的基因復制到O1相同的基因座上，再將P2中刪除了O1中已確定的基因后剩余的基因從左到右依次填充到O1的空位上。

步驟4互換P1和P2的角色，生成O2。

圖10a所示為MSOS中的工序順序串應用POX的示例；另外，POX也可用于三元組編碼和矩陣編碼，對于這兩種編碼，POX算子僅作用于工序加工順序的相關變量上，不改變工序的加工機器。圖10b所示為三元組編碼應用POX的示例，其中所有工序的加工機器不發(fā)生改變。

需要說明的是，與POX相似的交叉算子還包括基于工件的交叉(Job-Based Crossover, JBX)算子、部分映射交叉(Partial-Mapped Crossover，PMX)算子、順序交叉(Order Crossover,OX)算子和線性順序交叉(Linear Order Crossover, LOX)算子等，具體參見文獻[2, 17, 64]。

3.1.5 指派交叉

指派交叉專用于三元組編碼方法[65]，屬于均勻交叉的變型。該交叉算子僅對三元組(i,j,k)中的變量k進行操作，以改變部分工序的加工機器，具體操作過程如下:

步驟1隨機選擇兩條染色體P1和P2，并初始化兩條空的子代染色體O1和O2。

步驟2將P1中所有三元組(i,j,k)中的變量i和j復制到O1相應的位置。

步驟4互換P1和P2的角色，生成O2。

圖11所示為三元組編碼應用指派交叉的一個實例。

3.1.6 行(列)交叉

行(列)交叉專用于表格編碼方法，是兩點交叉的變型[66]。因為行(列)交叉只涉及染色體上相同基因座上的基因交換，所以產(chǎn)生的子代染色體均可解碼成可行的調(diào)度方案。行(列)交叉的具體操作過程如下：

步驟1隨機選擇兩條染色體P1和P2，并初始化兩條空的子代染色體O1和O2。

步驟2隨機選擇一個工件Ji(1≤i≤n)，O1中所有屬于工件Ji的工序都選擇與P1相同的機器，剩余工序都選擇與P2相同的機器(隨機選擇每個工件中的第j道工序，O1中所有工件的第j道工序都選擇與P1相同的機器，剩余的工序都選擇與P2相同的機器)。

步驟3根據(jù)得到的O1的機器分配表，計算每道工序的加工開始和加工結束時間，得到O1的譯碼分配表。

步驟4互換P1和P2的角色，生成O2。

圖12所示為OMC應用行交叉的一個實例，本例中隨機選擇工件J2作為被選中的工件，交叉操作后形成兩個新的機器分配表，又利用調(diào)度規(guī)則重新得到每道工序的加工開始和加工完成時間。需要說明的是，行(列)交叉算子的設計與具體的表格編碼方法密切相關，關于PJsR和PMR的行(列)交叉算子，請參見文獻[49]。

3.1.7 矩陣交叉

矩陣交叉是為矩陣編碼專門設計的交叉算子，屬于兩點交叉的變型[51]，具體操作過程如下：

步驟1隨機選擇兩條染色體P1和P2，并初始化兩條空的子代染色體O1和O2。

步驟4互換P1和P2的角色，生成O2。

圖13所示為矩陣交叉操作的一個實例，本例中h1=3，h2=5。顯然，這種交叉操作后的子代染色體很可能不能遵守同一工件中工序之間的順序約束關系，從而生成不可行的調(diào)度方案，例如圖13中的子代染色體O1中的工序O22排在工序O21之前。

3.1.8 保留順序交叉

保留順序交叉是為A/B串編碼中的B串專門設計的交叉算子[53]，該算子只對某臺機器上的工序加工順序進行操作，具體操作過程如下：

步驟1隨機選擇兩條染色體P1和P2，并初始化兩條空的子代染色體O1和O2。

步驟2隨機選擇染色體的某個基因座(設為第k個基因座，即第k臺機器)，l=min {l1,l2},其中l(wèi)1和l2分別為P1和P2染色體在第k臺機器上加工的工序數(shù)量；當l≥2時，從[1,l]之間產(chǎn)生兩個隨機數(shù)x1和x2(1≤x1

步驟3將P1的第k個基因座之外的所有基因復制到O1的相應位置。

步驟4互換P1和P2的角色，生成O2。

圖14所示為A/B串編碼中的B串應用保留順序交叉的一個實例，本例隨機選擇染色體第1個基因M1上第1個位置到第2個位置上的工序進行工序加工順序重排，因為P1中只有工序O32出現(xiàn)在P2的M1上，所以O1第1個基因的工序加工順序不變；而P2中M1上的工序加工順序為O22?O32，根據(jù)P1中M1上的工序順序，M1上的工序加工順序在O2中發(fā)生逆轉(zhuǎn)，即O32?O22。

3.2 變異算子

變異算子是遺傳算法產(chǎn)生新個體的另一種重要操作，其通過將染色體中某些位置上的基因用其他等位基因替換來產(chǎn)生新個體。變異操作可顯著改善算法的局部搜索能力，并通過防止有效基因遺失來維持群體的多樣性，有助于避免遺傳算法早熟。目前，在求解FJSP的遺傳算法中使用的變異算子主要有6種形式。

3.2.1 交換變異

交換變異通過交換染色體兩個不同基因座上的基因來產(chǎn)生新的染色體[17, 59]，具體操作過程如下：

步驟1隨機選擇一條染色體P。

步驟2隨機選擇染色體P上的兩個基因座，交換兩個基因座上的基因，生成子代染色體O。

圖15所示為MSOS-I編碼中的工序順序串應用交換變異的一個實例。需要說明的是，交換變異只適用于MSOS的工序順序串，不適用于其他子串或編碼方法。因為其他子串或編碼方法的染色體上各個基因座的等位基因不同，交換不同基因座上的基因可能使子代染色體無法解碼成可行的調(diào)度方案。

3.2.2 插入變異

插入變異通過將某基因座上的基因插入染色體的其他基因座上來產(chǎn)生新的染色體[28, 61, 67]，具體操作過程如下：

步驟1隨機選擇一條染色體P。

步驟2隨機選擇染色體P上的一個基因，將該基因隨機移動到染色體的其他基因座上，生成子代染色體O。

插入變異只適用于MSOS的工序順序串，原因與交換變異相同。圖16所示為MSOS-I編碼中的工序順序串應用插入變異的一個實例。

3.2.3 倒序變異

倒序變異通過逆轉(zhuǎn)染色體中任意兩個基因座之間的基因排列順序來產(chǎn)生新的染色體[17]，具體操作過程如下：

步驟1隨機選擇一條染色體P。

步驟2隨機選擇染色體P上的兩個基因座，逆轉(zhuǎn)兩個基因座之間基因的排列順序，生成子代染色體O。

倒序變異只適用于MSOS的工序順序串，原因與交換變異相同。圖17所示為MSOS-I編碼中的工序順序串應用倒序變異的一個實例。需要說明的是，相比交換變異和插入變異，倒序變異對染色體產(chǎn)生的改變更大。

3.2.4 智能變異

智能變異主要用于路徑子問題的變異操作[45, 60]，一般基于減少某道工序的加工時間或平衡不同機器間的機器負荷(即機器全部加工工序的加工時間之和)進行操作。以下以減少某道工序的加工時間為例，說明其具體操作過程：

步驟1隨機選擇一條染色體P，然后從在機器負荷最大的機器上加工的工序中隨機選擇一道工序Oij。

步驟2從工序Oij的候選機器集合中選擇加工時間最少的機器Mk，將機器Mk分配給工序Oij。

圖18所示為三元組編碼應用智能變異的一個實例，本例中機器M3的負荷最大(M1的負荷為3，M2的負荷為4，M3的負荷為5，如圖1)，若隨機選擇的工序是O31，則變異操作之前，該工序的加工機器和加工時間分別為機器M3和3；變異操作之后，將工序O31重新分配給加工時間最少的機器，即機器M2，則相應的加工時間減少到2。顯然，智能變異適用于FJSP的所有染色體編碼方法。

3.2.5 PPS變異

PPS(precedence preserving shift mutation)變異是插入變異的變型[46, 65]，其通過隨機選擇一個工序，在保持任意工件的工序之間順序約束關系的前提下，改變?nèi)抗ば虻募庸ろ樞?，具體操作過程如下：

步驟2將工序Oij隨機移動到任意一個x1到x2之間的位置上，形成子代染色體O。

圖19所示為三元組編碼應用PPS變異的一個實例，本例被選中的工序O31是工件J3中的第1道工序，其可以移動到工序O32之前的任意一個基因座上，即有4個可以移動的位置。最終將工序O31移動到第1個基因座上，產(chǎn)生子代染色體O。顯然，PPS變異適用于三元組編碼、矩陣編碼和MSOS中的工序順序串。

3.2.6 鄰域變異

鄰域變異專用于MSOS的工序順序串[2, 17, 68]，通過對一條被選定的染色體進行鄰域變換(即對染色體產(chǎn)生小的擾動或變化)生成該染色體的多個鄰域染色體，從中隨機選擇一條作為子代染色體(也可以從鄰域染色體中選擇最好的一個作為子代染色體，但該方法計算成本過高)，具體操作過程如下：

步驟1隨機選擇一條染色體P，再隨機在染色體P上選擇x個基因座(一般1

步驟2通過改變x個基因座上的基因排列順序，生成染色體P所有的鄰域染色體。

步驟3從生成的鄰域染色體中隨機選擇一條作為子代O。

圖20所示為MSOS中的工序順序串應用鄰域變異的一個實例，本例選擇3個基因座的基因，通過改變3個基因值的排列順序可以得到5個鄰域染色體。

4 討論

基于前文可以看出，染色體編碼方法設計是應用遺傳算法求解FJSP的關鍵，同時染色體編碼方法又對交叉、變異算子的選擇或設計有重要影響，并最終對遺傳算法求解FJSP的效率和質(zhì)量產(chǎn)生根本影響，即染色體編碼方法與交叉、變異算子之間相互交織、互相影響。為此，本文首先評價前文所述的交叉和變異算子，然后對各類染色體編碼方法進行整體評價。

4.1 交叉算子的評價

交叉算子的設計決定了子代與父代之間的繼承關系和交叉算子操作(或計算)的復雜性。就子代與父代之間的繼承關系而言，文獻[17，69]指出，交叉算子設計需要考慮子代繼承父代特性的能力和子代引入新模式的能力，其中子代繼承父代特性的能力表示交叉操作應盡可能減小對父代的改變，即盡可能地繼承父代的特性，這有利于遺傳算法快速收斂，單點交叉、兩點交叉及兩者的變型交叉算子均具有較強的子代繼承父代特性的能力；子代引入新模式的能力表示交叉操作應盡可能增大對父代的改變，從而擴大遺傳算法的搜索能力，均勻交叉及其變型交叉算子均具有較強的引入新模式的能力。就交叉算子的操作復雜性而言，交叉算子設計越簡單，交叉操作的復雜性越低，算法的整體計算效率越高。一般經(jīng)典交叉算子的操作復雜性較低，而針對某種特定編碼方法設計的交叉算子的操作復雜性較高。在前文所述的8類交叉算子中，除單點交叉、兩點交叉和均勻交叉為經(jīng)典交叉算子外，其他都是為適應FJSP及其特殊編碼方法設計的，例如A/B串編碼方法中，B串需同時遵循A串的約束條件和問題本身的約束條件，為此專門為B串的交叉操作設計了交叉算子，即保留順序交叉，該交叉算子不僅具有很高的操作復雜性，還可能產(chǎn)生不可行解。

表2采用交叉算子的3個評價指標對前文所述的交叉算子進行了綜合評價。表3所示為這些交叉算子對FJSP的5類染色體編碼方法的適用性，其中符號“√”表示該算子適用于對應的染色體編碼方法或子染色體。

表2 8類交叉算子對比

表3 5類染色體編碼方法的交叉算子適用表

4.2 變異算子的評價

變異算子設計決定變異算子的操作(或計算)復雜性，并嚴重影響遺傳算法的搜索性能。為增加遺傳算法的搜索性能，變異算子設計同樣需考慮局部搜索能力和全局搜索能力。其中，局部搜索能力指變異操作對父代染色體的擾動應盡可能地小，從而提高局部搜索能力，有利于遺傳算法快速收斂，例如智能變異就具有很強的局部搜索能力；全局搜索能力指變異操作對父代染色體產(chǎn)生的變動應盡可能地大，從而提高群體的多樣性，有利于擴大遺傳算法的搜索能力，例如倒序變異就具有較強的全局搜索能力。就變異算子的操作復雜性而言，變異算子設計越簡單，變異操作的復雜性越低，算法的整體計算效率越高。一般經(jīng)典變異算子的執(zhí)行過程相對簡單，而針對特定編碼方法設計的變異算子的執(zhí)行過程相對復雜。在6類變異算子中，除交換變異、插入變異和倒序變異是經(jīng)典變異算子外，其他均為適應FJSP及其特殊編碼方法設計，其操作過程更加復雜。

表4 6類變異算子對比

表4采用變異算子的3個評價指標對前文所述的變異算子進行了綜合評價。表5所示為這些變異算子對FJSP的5類染色體編碼方法的適用性。

表5 5類染色體編碼方法的變異算子適用表

4.3 染色體編碼方法的評價

表6 5類編碼方法對比

(1)編碼可行性 編碼可行性指基于某種染色體編碼方法生成的染色體總能解碼成一個可行的調(diào)度方案。顯然，在上述5類編碼方法中，僅A/B串編碼不能保證所生成的任意染色體能夠解碼成一個可行的調(diào)度方案。

(2)編碼空間與解空間的映射關系 映射關系通常有1-to-1，1-to-n，n-to-1映射3種。對于染色體編碼方法而言，編碼空間與解空間的映射關系必須保證唯一性，即一條染色體只能解碼成一個特定的可行調(diào)度方案，雖然1-to-1映射和n-to-1映射都滿足唯一性，但是n-to-1映射存在多條染色體可解碼成同一種調(diào)度方案的情況，這會降低搜索性能[70]，因此1-to-1映射被認為是編碼空間與解空間最期望的映射關系。顯然，在半主動調(diào)度下(對于其他調(diào)度類型，映射關系可能發(fā)生變化)，除A/B串編碼是1-to-1映射外，其余編碼方法均屬于n-to-1映射。

(3)染色體存儲空間 染色體存儲空間指存儲一條染色體所需的空間，其與染色體的數(shù)據(jù)結構密切相關。在以上5類編碼方法中，MSOS-I和A/B串編碼的染色體存儲空間最小，一條染色體需要2T個“整數(shù)”存儲空間(0，1，以及工序號和機器號均看作為一個整數(shù))。

(4)解碼復雜性 解碼指將編碼空間中的一條染色體轉(zhuǎn)換為解空間中一個調(diào)度方案的過程。在5類編碼方法中，表格編碼生成的染色體不需要解碼，因為表格編碼已經(jīng)運用相關的調(diào)度規(guī)則對給定的機器分配進行了調(diào)度計算，即表格編碼中的譯碼分配表本身就是一個調(diào)度方案，而其他4類編碼方法均需解碼才可以得到調(diào)度方案。

(5)編碼完備性 編碼完備性指任意調(diào)度方案均能在編碼空間中找到與之對應的染色體，這是保障遺傳算法求解質(zhì)量的關鍵。顯然，在5類編碼方法中，表格編碼方法因為采用調(diào)度規(guī)則解決FJSP的調(diào)度子問題無法保證找到所有可行調(diào)度方案(包括最優(yōu)解)，所以不具備編碼完備性。

(6)遺傳操作復雜性 遺傳操作越簡單，執(zhí)行效率越高，算法的整體計算效率相對越高。由表2～表5的分析結果可知，MSOS的遺傳操作最簡單。

(7)遺傳操作多樣性 染色體編碼方法可應用的交叉和變異算子越多，特別是經(jīng)典的交叉和變異算子越多，越具有遺傳操作多樣性，可借此提高遺傳算法的性能。由表3和表4可知，MSOS可使用的交叉和變異算子的種類最多，因此具有較好的遺傳操作多樣性。

綜上可知，MSOS是5類染色體編碼方法中綜合性能最好的一類編碼方法，特別是MSOS-I編碼可以保證編碼可行性，且存儲空間小，相應的遺傳操作簡單多樣，運用這種染色體編碼方法的遺傳算法通常表現(xiàn)出較高的性能，目前MSOS-I編碼方法已經(jīng)成為求解FJSP遺傳算法中使用最多的編碼方法。

5 結束語

遺傳算法是求解FJSP使用最廣泛的方法，在過去30年，研究者通過改進遺傳算法的各個要素提升了其求解FJSP的性能。本文聚焦遺傳算法的染色體編碼方法，詳細介紹和分析了求解FJSP的5類主要染色體編碼方法，并結合這些編碼方法適用的交叉和變異算子，從7個維度對這些編碼方法進行了評價。綜述結果表明，MSOS-I編碼是遺傳算法求解FJSP較好的染色體編碼方法，其染色體結構簡單，并可選用較多類型的交叉和變異算子。

基于在染色體編碼方法和遺傳算子方面對遺傳算法求解FJSP的討論，未來研究可側重于改進現(xiàn)有染色體編碼方法或設計新的染色體編碼方法，在保證其結構簡單、編碼具有可行性和完備性的前提下，盡量使其適用于經(jīng)典的交叉和變異算子，以降低遺傳操作的復雜性，提高遺傳操作的多樣性。