FPD-GA求解多目標柔性作業車間調度問題

王 博，陸寶春

（南京理工大學 機械工程學院，江蘇 南京 210094）

1 引言

長久以來，如何利用生產調度優化技術提高制造系統生產率、縮短產品加工周期一直是生產制造與管理領域的核心問題。作為傳統作業車間調度問題的延伸，柔性作業車間調度問題（Flexible Job Shop Scheduling Problem，FJSP）打破了加工設備唯一性的約束，允許工序在可用設備集中的任一臺上加工，更加符合車間生產實際的同時也增加了該問題的求解難度[1]。近年來，蟻群算法[2]、免疫算法[3]、禁忌搜索算法[4]以及粒子群算法[5]等智能啟發式算法越來越多的被用于求解FJSP，并取得較好的效果。

遺傳算法（Genetic Algorithm）由于其穩定的計算性能和突出的全局搜索能力被廣泛用于求解FJSP。但局部尋優能力差，易過早收斂的缺點使傳統遺傳算法在求解該問題時準確性不高。因此，學者們不斷地致力于改進傳統遺傳算法使其快速準確地獲得最優解。文獻[6]設計了一種非支配排序遺傳算法用于提高求解FSJP的尋優能力；文獻[7]結合遺傳算法與瓶頸移動法解決柔性車間調度問題；文獻[8]在免疫算法的基礎上融入遺傳算子提出了一種遺傳免疫算法。

定點擾動-遺傳算法（FPD-GA）為了避免算法早熟并增強局部搜索能力，一方面用復合選擇策略代替比例選擇算子，保證優良個體遺傳的同時降低劣勢個體淘汰率，維持了種群的多樣性；另一方面定量分析種群收斂程度[9]，并融合模擬退火算法和免疫算法，設計定點擾動機制，避免算法陷入局部最優。最后通過實例驗證改進算法的可行性。

2 FJSP數學模型建立

車間調度問題可描述為：離散制造車間共有m臺機器｛W1，W2，…，WM｝，需完成n個工件｛J1，J2，…，Jn｝的 p 道工序，每道工序Oij的加工設備不唯一，并且相同工序在不同設備上的加工時間不相同。優化調度的目標是為每道工序安排最合適的設備，并在工序不干涉的前提下規定各臺設備的工件加工次序，使整個制造系統達到最佳狀態。同時，加工過程中應滿足以下約束條件：

（1）在某一時刻，工件Ji的某道工序Oij只能在指定的機器Wk上加工，并且加工時間tijk已知。

（2）不同工件的工序相互獨立，同一工件的各道工序按規定的工藝流程依次進行。

（3）在t=0時刻所有設備可以被使用，所有工件可以被加工。

針對實際生產需要，選擇以下目標為制造系統的性能指標，并構建多目標適應度函數：

（1）最小化工件最大完工時間。設Di為工件Ji的完工時間，其目標函數可表示為：f1=Min｛Max｛Di，i=1，2，…，n｝｝

（2）最小化設備最大負荷。設Lk為機器Wk的生產負荷，采用設備的工作時間表述其生產負荷，該目標函數可表示為：

（3）最大化設備使用率。最大化設備使用率在于使設備負荷均衡化，采用所有設備中最大與最小工作時間的差表述機床負荷均衡化：f3=Min（Max（Lk）-Min（Lk））

已有的算法研究中，多目標適應度函數的設計策略主要有加權策略、目標設計策略和非劣解等級優先策略。考慮到兼顧各個性能指標的同時盡可能的減小計算量，采用加權策略在可行域中尋找最優解，并用以上三個目標函數構建多目標適應度函數：

F=ω1f1+ω2f2+ω3f3

3 FPD-GA求解FJSP

3.1 FJSP中遺傳算子設計

3.1.1 編碼與解碼

對于柔性車間調度問題，染色體編碼在反映出工件加工順序的同時，還要體現各道工序所在的加工設備，基于工序或操作的單一編碼形式很難實現該問題的求解。因此采用雙倍染色體編碼形式，即一對相互關聯染色體對應一個調度解，其中第一條染色體采用基于工序的編碼，用于確定所有工件各道工序的加工次序，另一條染色體為基于分配機器的編碼，用于為工序染色體分配加工設備。通過工序和機器染色體共同表達柔性車間的調度解。一個（3×5）調度問題編碼方式，如圖1所示。

圖1 雙倍染色體編碼Fig.1 Form of Double Chromosome Encoding

針對上述的編碼方式，在解碼時首先將雙倍染色體解碼為機器矩陣和加工時間矩陣，然后按照工序染色體序列，安排每道工序到對應機器染色體指定機床的最佳加工時刻，最終得到調度解。

3.1.2 交叉算子

交叉操作是通過隨機交換兩個個體的部分基因，從而形成具有更優秀基因組合的新個體的過程。由于編碼的特殊性，為了避免非法解的出現，采用基于染色體對的多父代交叉操作。具體實施步驟：（1）將所有工件劃分為兩個互補的非空子集G1和G2，并在種群中隨機選取三個父代個體 P1、P2、P3；（2）對 P1進行順序操作，去除 P1中所有屬于G1的基因信息并用0代替，得到新染色體對，同理，去除P2中所有屬于G2的基因信息，得到新染色體對；（3） 對 P3進行順序操作，用P3中屬于G1的基因信息按次序替換中的0基因位，得到子代個體C1；同理得到子代個體C2。

3.1.3 變異算子

為了保證變異操作后解的可行性，將該操作分為工序染色體變異和機器染色體變異兩部分。對工序染色體采取插入式變異：隨機生成兩個不同的整數S1和S2，將第S1位的基因插入到第S2位的基因前，得到新的工序染色體；對于機器染色體：遍歷整條染色體，查詢每一個基因位的取值是否包含在對應工序的可用機器集內，如不包含，則在該可用機器集內隨機抽取一臺機器編號替換當前基因，由此得到可行的機器染色體。

3.2 遺傳算法的改進

在求解柔性制造車間調度問題時，采用傳統遺傳算法通常會出現局部搜索效率低，過早陷入局部收斂等問題。分析出現問題的原因有兩個：（1）比例算子使個別優勢個體大量遺傳，導致種群多樣性急劇下降；（2）進化后期的種群個體趨于相似，交叉與變異操作不容易破壞父代個體性狀，算法難以跳出局部最優。

針對上述分析原因，FPD-GA通過改進選擇操作、設計定點擾動策略兩個方面改進傳統遺傳算法。

3.2.1 復合選擇策略

傳統遺傳算法采用的比例選擇操作能夠使種群快速地逼近最優解，但也淘汰掉了可能包含優良基因片段的劣勢個體，使種群過早的陷入收斂狀態。為了避免這一現象的發生，FPD-GA采用精英保留和輪盤賭的復合選擇策略，在保證優良個體遺傳的同時降低劣勢個體淘汰率，維持了種群的多樣性，其步驟：（1）計算個體x的適應度值Fi和種群整體適應度平均值；（2）當 Fi＜時，該個體x被保留；當Fi≥時，以一定概率p接受x，其中p=1/e（Fi-ˉF）；（3）以輪盤賭的方式抽取大于平均適應度的個體，補充種群達到要求的種群規模。

3.2.2 定點擾動策略

算法進化后期，優勢個體大量集中于最優解附近，種群進入收斂狀態，但此時無法判斷種群是否收斂于全局最優解，為了避免種群早熟收斂，提出定點擾動策略。

定點擾動策略的設計以模擬退火算法思想為基礎，借鑒了免疫算法的疫苗接種機制。當種群處于收斂狀態時，強制改變種群中優勢個體的基因片段，不同于模擬退火算法的隨機擾動，該策略通過計算優勢群體等位基因的相似度，改變指定基因位上的基因，并選擇性地保留擾動后的個體，驅使群體向最優解進化。但過于頻繁地定點擾動會干擾正常的進化趨勢，不利于算法快速尋優，因此，在對GA收斂狀態多次分析的基礎上，FPD-GA引入種群收斂度指標（其中為小于群體平均適應度值的個體的適應度平均值，Fmin為當代種群的最小適應度值），用于判斷種群是否進入收斂狀態，并選擇性地觸發定點擾動機制。

具體步驟：（1）計算種群收斂度指標Δ，當Δ小于收斂系數ε時，觸發定點擾動機制；（2）對所有個體的適應度值從小到大排序，抽取適應度值前20%的個體組成精英群體Q；（3）計算Q中工序染色體第i個基因位上等位基因的相似度ηi，即ηi=nmax/nQ（i=1，2，…，np）。其中nmax—染色體第i位上出現頻率最高基因的頻數；nQ—Q中工序染色體總數；np—工序染色體基因數；（4）對ηi從小到大排序，設定前r個基因位為擾動基因位，對工序染色體擾動基因位上的基因進行位置互換，對機器染色體擾動基因位上的基因進行單點變異；（5）對擾動后的個體，計算適應度值，若≤Fi，則用擾動后的個體代替原個體，若＞Fi，以概率 Pt接受擾動后的個體。其中

圖2 FPD-GA流程圖Fig．2 Flow Diagram of FPD-GA

FPD-GA流程圖，如圖2所示。FPD-GA的主要實現步驟如下：

（1）設定參數。設定種群規模N，迭代最大次數T，交叉概率Pc，變異概率 Pm，擾動系數 r，收斂系數 ε，適應度函數權重 ω1、ω2、ω3；

（2）初始化種群。隨機產生由工序染色體和機器染色體組成的種群個體，并設迭代次數t=0；

（3）適應度值評價。計算每個個體的適應度值Fi，并獲得最小適應度值Fmin和適應度平均值Fˉ；

（4）檢查算法終止條件。如果t≥T，輸出最優解Fmin，否則執行步驟（5）；

（5）選擇操作。執行復合選擇操作，得到新的種群；

（6）交叉操作。對滿足交叉概率的種群個體進行多父代交叉操作；

（7）評價種群收斂程度。計算當前種群收斂度Δ，當Δ＜ε時，轉入步驟（9），否則執行步驟（8）；

（8）變異操作。以設定的變異概率對選中個體進行變異，返回步驟（3）；

（9）定點擾動操作。按照定點擾動策略對精英群體執行定點擾動。

（10）令 t=t+1，返回步驟（3）；

4 實例驗證與結果分析

為了驗證改進算法的有效性，以某液壓油缸零部件生產車間A小組生產計劃為實例，測試改進算法。該實例中共有9個工件，每個工件有4道工序（車、銑、鉆、鏜），共有12臺設備，其中M1、M2、M3、M4、M5、M6 可用于車，M4、M5、M6、M7、M8 可用于銑，M4、M5、M9、M10 可用于鉆，M5、M6、M11，M12 可用于鏜。工序加工時間表，如表1所示。

表1 工序加工時間表Tab.1 Schedule of Procedure

設種群規模N=60，迭代次數t=1000，交叉概率Pc=0．8，變異概率Pm=0．05，擾動系數r=8，收斂系數ε=0．9，適應度函數權重ω1=0．4，ω2=0．3，ω3=0．3。利用 MATLAB 對實例進行仿真計算，并得到最佳調度方案。傳統遺傳算法（SGA）和FPD-GA收斂曲線，如圖3、圖4所示。SGA、自適應遺傳算法（AGA）和FPD-GA的實例計算結果比較，如表2所示。采用FPD-GA計算實例的最佳調度優解，如圖5所示。

圖3 傳統GA收斂曲線Fig．3 Convergence Curve of Traditional GA

圖4 FPD-GA收斂曲線Fig．4 Convergence Curve of FPD-GA

通過對比圖3圖4可以看出：傳統遺傳算法在進化初期迅速進入收斂狀態，優勢個體大量遺傳，平均適應度值變化平緩且不斷趨近最小適應值，種群一直保持收斂狀態；而FPD-GA在復合選擇策略的影響下平均適應度值波動式減小，當進入收斂狀態后觸發定點擾動機制，使種群跳出局部最優值，不斷朝全局最優值進化。通過表2數值對比，采用FPD-GA對實例求解，與其他算法相比，適應度函數分別減小了7.4%、3.7%，各項指標也明顯優于SGA和AGA的計算結果，驗證了FPD-GA的有效性。

表2 算法仿真計算結果對比Tab.2 Comparison of Simulation Results

圖5 最佳調度方案Fig.5 Optimal Scheduling Scheme

5 結論

在應用遺傳算法的基礎上引入復合選擇操作，并設計定點擾動策略，提出了一種融合遺傳算法—FPD-GA。FPD-GA繼承了遺傳算法全局搜索能力突出的優勢，同時克服了局部尋優能力差的缺陷，能快速地擺脫局部收斂的狀態，向全局最優解的方向進化。通過生產實例驗證，該方法在解的質量上有較大提升和改善，是一種高效求解FJSP的方法。