基于改進遺傳算法的柔性作業(yè)車間調(diào)度研究*

金 秋 王清巖 原博文

（天津科技大學經(jīng)濟與管理學院，天津 300457）

柔性作業(yè)車間調(diào)度問題（FJSP）是柔性制造系統(tǒng)中的一項關鍵調(diào)度問題，有效的生產(chǎn)調(diào)度對于提高工業(yè)生產(chǎn)效率和資源利用率具有重要意義。在FJSP 中，每個作業(yè)都可以在不同的機器上完成，并且每個作業(yè)在每臺機器上的加工時間可能存在差異。此外，每個作業(yè)的工序順序也可能不同，使得FJSP 成為一個復雜的NP-Hard 問題[1]。

在解決FJSP 問題時，Brucker P 和Schlie R 提出了一種多項式圖算法[2]，然而該算法在處理多工件、多機床、大規(guī)模和多約束調(diào)度問題時效果不佳。因此，研究人員開始嘗試采用啟發(fā)式優(yōu)化算法來解決這些問題。

粒子群算法[3]、遺傳算法[4]、貪婪算法[5]和蟻群算法[6]等是常見的啟發(fā)式算法，在學術研究中被廣泛應用。相較于其他算法，遺傳算法具有過程簡單、搜索能力快和魯棒性好等優(yōu)點。因此，在解決柔性作業(yè)車間調(diào)度問題時，遺傳算法被廣泛采用[7-10]。然而，傳統(tǒng)的遺傳算法存在收斂速度慢和容易陷入局部最優(yōu)等問題。因此，近年來國內(nèi)外研究人員對傳統(tǒng)的遺傳算法進行了改進，以克服其不足之處。王佳怡等[11]構建了一個多目標混合整數(shù)線性規(guī)劃模型，設計了一種改進的遺傳算法，引入了基于多父代的交叉算子和多種變異算子，并結合了精英保留和輪盤賭選擇策略。姜一嘯等[12]提出了一種低碳調(diào)度模型，采用改進的帶精英策略的非支配遺傳算法（NSGA-II）來優(yōu)化該模型。唐藝軍等[13]提出了一種改進的混合遺傳算法，結合了模擬退火算法和萊維飛行擾動策略，以提高算法性能。趙慧娟等[14]提出了一種方法，考慮不同情境下目標權重系數(shù)的變化，并采用改進的遺傳算法來優(yōu)化完工時間、能耗和質(zhì)量的權衡模型。Chen R 等[15]提出了一種自學習遺傳算法（SLGA），其中采用遺傳算法（GA）作為基本優(yōu)化方法，并基于強化學習（RL）對其關鍵參數(shù)進行智能調(diào)整。

根據(jù)國內(nèi)外學者們對FJSP 的相關研究現(xiàn)狀，存在以下幾個問題：（1）使用的優(yōu)化算法的尋優(yōu)能力一般，主要是算法的反應時間太長，容易進入局部最優(yōu)解，并且關鍵參數(shù)無法進行有效的動態(tài)調(diào)整，導致求解效率和質(zhì)量無法滿足生產(chǎn)要求；（2）優(yōu)化的目標過于單一，優(yōu)化目標往往只考慮了最大完工時間，沒有反映車間的實際生產(chǎn)情況。

為此，本文建立以最大完工時間和能耗為目標的數(shù)學模型，提出了一種改進算法。該算法針對無法動態(tài)調(diào)整參數(shù)的問題，對交叉變異算子進行了非均勻改進，并引入了基于鄰域的變異算子，以提高算法的搜索能力和穩(wěn)定性。

1 問題描述及數(shù)學模型

1.1 問題描述

FJSP 是對經(jīng)典JSP 的擴展，用于描述N個待加工工件在M臺機器上進行加工。每個工件由S道工序組成，F(xiàn)JSP 問題的主要參數(shù)見表1。

1.2 柔性作業(yè)車間調(diào)度模型

對于FJSP，每個作業(yè)由一系列優(yōu)先級受限的操作組成，這些操作的加工時間在不同分配的機器之間是不同的。本文旨在建立一個多目標柔性作業(yè)車間調(diào)度模型，目標函數(shù)是將歸一化的最大完工時間和能耗加權最小化，見式（7），并給出一些約束條件。

約束條件：

對目標函數(shù)的處理、加權：

最小化最大完工時間用式（1）表示；通過式（2）可以實現(xiàn)最小化加工能耗；式（3）描述了同一工件工序的先后約束關系；任一工序的完工時間均需滿足式（4）的約束；式（5）表示工序的加工時間大于零；式（6）表示所有工件在0 時刻開始加工。式（7）為目標函數(shù)，其中 φ為權重系數(shù)，0＜ φ＜1。

2 改進遺傳算法

2.1 改進遺傳算法流程

改進后算法流程圖如圖1 所示，具體步驟如下。

圖1 改進后的遺傳算法流程圖

步驟一：設置相關參數(shù)，隨機生成一組初始種群。

步驟二：編碼與解碼。

步驟三：采用輪盤賭策略，選擇優(yōu)秀個體。

步驟四：計算種群個體適應度值。

步驟五：對選中父代進行均勻交叉操作，改變個體的編碼，再經(jīng)過非均勻交叉率篩選。

步驟六：對工件編碼進行鄰域搜索變異操作，對機器編碼采用單點變異，再經(jīng)過非均勻變異率，以此提高算法的搜索能力和穩(wěn)定性。

步驟七：判斷是否滿足終止條件，如果達到最大迭代次數(shù)或達到停止條件時，終止迭代過程，否則返回步驟四。

步驟八：輸出結果。

2.2 編碼與解碼

FJSP 的染色體由操作順序部分和機器分配部分組成，這種編碼方式可簡化解碼過程，降低成本。圖2 展示表2 中的一個FJSP 實例的編碼示例，它表示優(yōu)化問題的解決方案，其中操作的機器分配用粗體表示。染色體的長度是操作次數(shù)的兩倍，在該實例中共有8 個操作，因此染色體的長度為16。掃描操作順序時，工件層按照從左到右的順序，第一個“l(fā)”是指在機器M3上處理的作業(yè)J1的第一個操作，對應機器分配部分的“3”；第二個“1”表示將在機器M2上處理的工件1 的第二個操作，對應機器分配部分中的“2”。根據(jù)上述說明，機器M1的操作順序為O41→O21→O32，機器M2為O31→O42→O12，機器M3為O11→O22。求解的操作順序和機器分配可以解釋為：{(O11,M3),(O41,M1),(O31,M2),(O21,M1),(O42,M2),(O32,M1),(O12,M2),(O22,M3)}。

圖2 表1 染色體的編碼圖

表2 一個4×3 的部分FJSP 實例

2.3 適應度函數(shù)

適應度函數(shù)是評估個體質(zhì)量、篩選方案和確定群體中優(yōu)秀個體的方法。通常，適應度函數(shù)通過計算個體的適應度來實現(xiàn)，該適應度基于目標函數(shù)值的倒數(shù)。在遺傳算法中，適應度函數(shù)起著重要作用，能夠量化個體的適應程度，并作為選擇和進化的依據(jù)。通過適應度函數(shù)的評估，遺傳算法能夠優(yōu)化搜索過程，保留和發(fā)展群體中更優(yōu)秀的個體。適應度函數(shù)為

式中：fit(f(x)) 為適應度值；Cmax為最大完工時間；E為機器加工的總負荷；φ為權重系數(shù)。

2.4 選擇操作

為了使遺傳算法在迭代早期朝著更好、更有優(yōu)勢的方向發(fā)展，選擇操作用于從群體中選出優(yōu)秀的個體。常用的基于適應度值進行選擇的方法是輪盤賭選擇法。該方法根據(jù)個體的適應度值來確定選擇概率，適應度值越高的個體被選中的概率也越高，這樣可以確保優(yōu)秀的個體在群體中得到更多被選擇的機會，記為Pa。

Pa的計算公式為

式中：fa為群體中每個個體的適應度值；F為種群的總適應度。

2.5 交叉操作

本文采用了均勻交叉方式來生成新個體。具體實現(xiàn)是隨機選擇兩個個體的基因位，并以相等的概率交換這些基因位，從而產(chǎn)生兩個新的個體。這種交叉方式的目的是增加遺傳算法的多樣性，提高全局搜索的效果。為解決這個問題，引入了非均勻交叉概率Pc：

式中：Pc0表示初始交叉率；gen表示當前迭代次數(shù)；MAXGEN表示總的迭代次數(shù)；γ為(0,1)的常數(shù)。

在遺傳算法中，交叉操作采用了多種不同的方式，包括均勻交叉、多點交叉、局部均勻交叉、順序交叉和周期交叉等方法。這些方法提供了多樣的策略，用于在遺傳算法的進化過程中實現(xiàn)基因的交換和組合。本文采用了均勻交叉方式，其具體實現(xiàn)是隨機選擇兩個個體的基因位，并以相等的概率交換這些基因位，從而生成兩個新的個體。均勻交叉是一種常見的遺傳算法交叉操作方式，能夠幫助算法更好地搜索解空間，增強全局搜索能力。均勻交叉的示例圖如圖3 所示。

圖3 染色體工序編碼交叉示例圖

被選擇進行交叉操作的基因位在圖3 和圖4 中為陰影部分，而每一個基因位被選擇的概率都是隨機的，不是確定的。

圖4 染色體機器編碼交叉示例圖

2.6 變異操作

傳統(tǒng)遺傳算法領域，常見的做法是使用固定的變異概率進行操作。然而，這種方式可能使算法陷入局部最優(yōu)解，從而無法找到更優(yōu)的解決方案。為了解決這個問題，可以引入非均勻變異率Pm，使得遺傳算法在搜索空間中進行更全面的探索。

通常情況下，初始階段的變異率較高，以便快速地探索解空間。隨著迭代次數(shù)的增加，變異率逐漸降低，以便更精確地搜索最優(yōu)解。具體的非均勻變異率可以根據(jù)式（11）來計算。

式中：Pm0為初始變異率。這個函數(shù)的意義是，隨著迭代次數(shù)的增加，變異率會隨之緩慢降低，ρ的范圍在(0,1)，作用是控制變異率的下降速度，ρ的值接近1 時，變異率的下降速度會比較緩慢；ρ的值接近0 時，變異率的下降速度會比較快。運用非均勻變異使得變異率隨著迭代次數(shù)的增加逐漸降低，以達到更好的優(yōu)化效果。本文提出了一種改進的工件編碼變異方法，旨在提高子代適應度并朝著更優(yōu)的方向進化，同時保持種群多樣性。該方法利用基于鄰域搜索的變異算子來進行工件編碼的變異。在機器編碼中，采用了單點變異法來替換機器的選擇操作。具體的操作示意如圖5 和圖6 所示。

圖5 工序?qū)踊卩徲虿僮鞯淖儺惒僮?/p>

圖6 機器編碼單點變異操作

變鄰域變異操作具體步驟如下：

（1）選出一定數(shù)量的不同位置，代表不同工件的基因。這些位置可以是隨機選擇或者使用其他策略進行選擇。

（2）對于這些位置進行全排列，生成當前鄰域中的所有解。對這些位置進行全排列，可以得到鄰域解的不同組合。

（3）計算每個鄰域解的適應度，根據(jù)具體問題使用適應度函數(shù)進行評估。

（4）具有最佳適應度的鄰域解被選擇為當前解。根據(jù)適應度的評估結果，選擇適應度最高的鄰域解作為當前解。

通過以上步驟，可以實現(xiàn)變鄰域操作，增加搜索空間和多樣性，從而提高算法的收斂性和搜索能力。

3 仿真結果與分析

為了評估本文提出的改進非均勻交叉和非均勻變異的遺傳算法的性能，選取基準算例kacem01 和kacem03 進行測試[16]。其中，kacem01 算例表示4個工件對應5 臺加工機器，而kacem03 算例表示10 個工件對應10 臺加工設備。使用Matlab R2023a作為具體的數(shù)據(jù)仿真軟件，并將仿真結果同傳統(tǒng)遺傳算法進行比較。本文相關參數(shù)設置為：最大迭代次數(shù)MAXGEN=300，選擇率Ps=0.8，初始交叉率Pc=0.8，初始變異率Pm=0.03。

4×5 和10×10 算例的迭代過程如圖7 和圖8 所示，可以看出，本文提出的改進遺傳算法所得到的最優(yōu)解均低于平均值，證明該改進算法在尋找最優(yōu)解方面具有更強的能力。

圖7 4×5 迭代過程圖

圖8 10×10 迭代過程圖

對比圖9 和圖10 可以看出改進后遺傳算法與傳統(tǒng)遺傳算法之間的差異。目標函數(shù)用于衡量解的優(yōu)劣，如果目標函數(shù)是最小化的，適應度越低表示解越好。這是因為適應度是根據(jù)目標函數(shù)的值來計算的，而目標函數(shù)越小越好。因此，適應度越低表示解越接近最優(yōu)解。通過觀察圖9 和圖10 可以發(fā)現(xiàn)，改進后的遺傳算法在最優(yōu)適應度方面表現(xiàn)更低。

圖9 4×5 改進后的遺傳算法與改進前遺傳算法的對比圖

圖10 10×10 改進后遺傳算法與改進前遺傳算法的對比圖

本文基于改進的遺傳算法所求得的調(diào)度結果如圖11 和圖12 所示。在遺傳算法等優(yōu)化算法中，通常會使用適應度來評估個體的優(yōu)劣，并根據(jù)適應度來進行選擇、交叉和變異等操作，以搜索最優(yōu)解。由圖11 和圖12 可以看出，改進后的遺傳算法在獲取解的質(zhì)量上有明顯的提升，在4×5 的經(jīng)典算例中最優(yōu)適應度從6.5 優(yōu)化到4，10×10 的算例中則從6優(yōu)化到3，證明了改進后算法的優(yōu)越性。

圖11 4×5 改進后遺傳算法調(diào)度結果甘特圖

圖12 10×10 改進后遺傳算法調(diào)度結果甘特圖

4 結語

本文提出了一個柔性作業(yè)車間調(diào)度問題模型，目標函數(shù)為最小化最大完工時間和最小化總能耗。為了有效解決該問題，引入了改進的遺傳算法方法。

通過引入非均勻改進，能夠根據(jù)問題的特點和種群的演化階段動態(tài)調(diào)整交叉率和變異率，改進的遺傳算法可以提高算法的全局搜索的能力。并且在變異操作中，對工件編碼使用鄰域變異，對機器編碼使用單點變異，以增加解空間的探索能力和多樣性。

通過這種改進的遺傳算法，期望能夠找到更好的解決方案，并優(yōu)化算法的性能。該算法能夠在較短的時間內(nèi)收斂到較優(yōu)的解，從而提高問題的求解效率。

為了驗證改進遺傳算法的效果，進行了改進遺傳算法和傳統(tǒng)遺傳算法的對比實驗，選取經(jīng)典算例kacem。實驗結果表明，改進后的算法的最優(yōu)適應度明顯低于傳統(tǒng)遺傳算法。

然而，本研究還存在一些局限性，只考慮了完工時間和能耗這兩個目標，而實際生產(chǎn)中可能還存在其他重要目標。此外，本研究僅針對靜態(tài)調(diào)度問題，對于動態(tài)調(diào)度問題仍需進一步研究。