混合禁忌搜索的車間調度遺傳算法研究

管 賽，熊禾根

（武漢科技大學 機械自動化學院，武漢 430081）

0 引言

作業車間調度問題（Job Shop Scheduling Problem，JSP）是典型的NP-hard 問題，是目前研究最為廣泛的一類調度問題，其存在于制造、物流、汽車等眾多領域的實際生產中，故研究內容具有重要的理論意義和工程價值。

調度問題的求解方法可分為兩類：精確求解方法和近似求解方法。精確求解方法包括解析法、窮舉法、分支定界法等；近似求解方法包括基于規則的構造性方法、鄰域搜索方法以及人工智能方法等。其中鄰域搜索中的遺傳算法（Genetic Algorithm，GA）結構簡單、易于實現，且能獲得較好的求解結果，所以被作為應用最廣的智能優化算法，廣泛應用于JSP 的求解之中。但標準遺傳算法存在早熟收斂，解的穩定性差等缺點。對此何斌等人［1］提出一種改進遺傳算法來求解作業車間調度問題，通過采取新的個體適應度計算方法，多種交叉操作隨機選擇，自適應交叉變異參數調整策略，來提升遺傳算法的性能。張超勇等人［2］提出一種局部鄰域搜索的遺傳算法求解JSP。該算法采用新的POX 交叉算子，基于鄰域搜索的變異算子，以及基于關鍵路徑鄰域的局部搜索，以改善解的質量。鄭先鵬等人［3］提出的改進遺傳算法采用精英保留策略，并結合改進自適應算子對問題進行求解，提升了求解JSP 的能力。王玉芳等人［4］提出了一種改進混合模擬退火算法，該算法采用自適應策略對概率進行動態調整，選擇一種基于工序編碼新的IPOX 交叉算子，同時加入有記憶功能的模擬退火算法，優化了JSP 的求解結果。禁忌搜索是一種全局尋優算法，搜索過程中能跳出局部最優解，同時具有良好的尋求優良解的能力，能有效提升算法的運算效率，實現高效搜索［5］。標準遺傳算法雖然具有較強的全局搜索能力，但局部搜索能力較弱，在迭代過程中易早熟且陷入局部最優解。因此，本文提出一種混合禁忌搜索的改進遺傳算法（Improved Tabu Search Genetic Algorithm，ITSGA），在原有的標準遺傳算法基礎上加入禁忌搜索算法，并改進算法流程，加入多種交叉方式的隨機選擇來提高種群的多樣性以及產生優質解，同時加入局部鄰域搜索對解進行微調，改善解的質量，達到尋找全局最優解的目的。

1 JSP 問題描述

JSP 可描述為：用m臺機器加工n個工件，每個工件i都包含一系列工序，給定每道工序Oij的加工機器及加工時間pij。約束條件為：

（1）同一時刻一臺機器只能加工一道工序；

（2）工件不能在同一臺機器上多次加工；

（3）不考慮工件加工優先權且工序加工過程不能中斷。

建立JSP 數學模型如下：

其中，目標函數F為最小化最大完工時間；Ci為工件i的最大完工時間；式（1）～式（3）表示工藝約束條件決定的工件上各工序先后操作順序，以及加工各工件的機器先后順序；Cik、pik分別為工件i在機器k上的完工時間和加工時間；M為一足夠大正數；式（4）、式（5）中定義決策變量aihk和xilk，分別確定同一工件在不同機器上的加工先后順序和同一機器上不同工序的加工先后順序，

2 ITSGA

ITSGA 算法采用基于工序編碼的編碼方式來表示個體，具有在進行染色體置換操作后總能得到可行解的優點。種群初始化方式為隨機生成初始種群，以最小化最大完工時間為評價指標，采用輪盤賭選擇算子來進行個體選擇，同時為了保留優秀個體，加快種群收斂速度，加入精英保留策略。在每次選擇時，將最優基因直接復制保留下來，以便個體的優良性狀能遺傳到子代中。

個體適應度函數定義為

其中，MS（g）表示個體g對應的最大完工時間，MSmax為種群中的最大值。

2.1 隨機選擇多種交叉方式

交叉操作是遺傳算法的核心操作，直接決定迭代過程中解的優劣情況和算法的全局搜索能力。本文提出迭代過程中多種交叉方式隨機選擇，以增加求解結果的多樣性。以下列出一些在求解JSP 時用到的交叉操作，隨機選擇的方式為等概率隨機選擇。

POX 交叉［6］示意圖如圖1 所示，隨機劃分工件集｛1，2，3，…，n｝ 為兩個非空子集J1、J2；將父代P1、P2中包含J1的工件復制到子代C1、C2中，保留原位置；復制父代P1中包含J2的工件到子代C2，復制父代P2中包含J2的工件到子代C1，保留其順序。圖1說明了POX 算子交叉過程。

圖1 POX 交叉Fig.1 POX crossover

2.1.1 OX 交叉

OX 交叉操作的示意如圖2 所示。父代中隨機生成兩個基因座（假設4 和6），以生成子代C1為例，將父代P1基因片段323 繼承給子代C1，以父代P2第7 個基因座作為第一個基因，從右往左生成臨時基因編碼｛232321311｝，再根據對應位置將基因片段在臨時基因編碼中一一剔除｛232321311｝ →｛221311｝，最后再將剔除后剩余的基因片段放入子代C1中。同理，子代C2的生成過程與上述類似。

圖2 OX 交叉Fig.2 OX crossover

2.1.2 PMX 交叉

PMX 交叉操作的示意如圖3 所示。隨機選擇兩個基因座（假設4 和7），得到映射關系3（工件3第一道工序）←→1（工件1 第三道工序）、1（工件1第三道工序）←→1（工件1 第二道工序），將父代P1的基因片段3231 繼承給子代C1并保留原位置，再根據映射關系替換父代P2中非選中基因片段｛321xxxx32｝→｛121xxxx32｝，將替換后的片段放入子代C1中，生成子代C1。同理子代C2的生成過程與上述類似。

圖3 PMX 交叉Fig.3 PMX crossover

2.2 局部鄰域搜索

關鍵路徑的變化是改變最大完工時間的關鍵，本文采取基于關鍵塊的快速鄰域搜索方式［7-9］，其流程如下：

步驟1確定當前解的關鍵路徑和全部關鍵塊。

步驟2設計鄰域構造為交換關鍵塊中的兩個工序。3 種交換方式為：

（1）選擇關鍵塊中的首工序與塊中任一工序進行交換；

（2）選擇關鍵塊中任意兩個內部工序進行交換；

（3）選擇關鍵塊中的尾工序與塊中任一工序進行交換。

步驟3通過隨機選擇來確定關鍵塊中工序的交換方式。

步驟4將經過局部鄰域搜索操作后的解添加到種群中。

3 算法驗證

為了驗證ITSGA 算法在求解作業車間調度問題的有效性，將本文算法與改進粒子群（Improved Particle Swarm Optimization，IPSO）算法［10］、量子鯨魚優化（Quantum Whale Optimization Algorithm，QWOA）算法［11］、改進混合遺傳模擬退火（Improved Genetic Simulated Annealing Algorithm，IGSAA）算法［4］進行對比。算法采用python 編程，在2.40 GHz處理器的Windows10 系統下運行。參數設置如下：

種群規模P ＝100，最大迭代次數200，交叉概率pc ＝0.9，變異概率pm ＝0.1，禁忌表長度為最大迭代次數。

表1 中，C?為已知最優解；best 為運行10 次得到的最優解；avg 為連續運行10 次得到的平均值；加粗數據表示已經達到最優解。選取benchmark 中關于JSP 的若干算例進行驗證。

表1 各算法對benchmark 問題求解結果比較Tab.1 Comparison of the results of benchmark problem by different algorithms

從表1 中所列數據可以看出，ITSGA 算法對于表格算例中求解的最優值和平均值均優于其它算法。對于除FT20 外的其他算例均已達到最優解，這是其他算法所未能達到的，且本文算法求解FT10、FT20 得到的平均值都要明顯優與其他算法。

以求解機器數量較多的FT10 為例，進一步說明ITSGA 的有效性。ITSGA 算法在求解FT10 得到的最優值和平均值都大大優于算法GA，更易跳出局部最優解，且在迭代初期就能快速收斂，說明加入的禁忌搜索算法和多種交叉方式隨機選擇起到了很好的作用。同時，精英保留策略也能夠使子代更好地繼承父代的優良性狀；局部鄰域搜索則提高了算法達到最優解的可能性。圖4 為運用ITSGA 求解算例FT10 得到的甘特圖，圖中O1，2中1 表示工件號，2 表示工序號。

圖4 ITSGA 求解FT10 得到的甘特圖Fig.4 Gantt chart obtained by ITSGA solving benchmark FT10

4 結束語

本文提出的ITSGA 算法通過融合禁忌搜索和局部鄰域搜索的改進，增強了求解JSP 的尋優能力，既有一定的全局尋優能力，能很好地避免陷入局部最優解，提高了算法的求解效率。將本文算法應用于求解若干基準問題時得到了較好結果，與傳統遺傳算法的求解結果相比均有較大的提升，經過與其它改進算法的比較結果，驗證了ITSGA 算法的有效性。