混合禁忌搜索的車間調(diào)度遺傳算法研究

管 賽，熊禾根

（武漢科技大學(xué) 機(jī)械自動化學(xué)院，武漢 430081）

0 引言

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

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

1 JSP 問題描述

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

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

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

（3）不考慮工件加工優(yōu)先權(quán)且工序加工過程不能中斷。

建立JSP 數(shù)學(xué)模型如下：

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

2 ITSGA

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

個體適應(yīng)度函數(shù)定義為

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

2.1 隨機(jī)選擇多種交叉方式

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

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

圖1 POX 交叉Fig.1 POX crossover

2.1.1 OX 交叉

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

圖2 OX 交叉Fig.2 OX crossover

2.1.2 PMX 交叉

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

圖3 PMX 交叉Fig.3 PMX crossover

2.2 局部鄰域搜索

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

步驟1確定當(dāng)前解的關(guān)鍵路徑和全部關(guān)鍵塊。

步驟2設(shè)計鄰域構(gòu)造為交換關(guān)鍵塊中的兩個工序。3 種交換方式為：

（1）選擇關(guān)鍵塊中的首工序與塊中任一工序進(jìn)行交換；

（2）選擇關(guān)鍵塊中任意兩個內(nèi)部工序進(jìn)行交換；

（3）選擇關(guān)鍵塊中的尾工序與塊中任一工序進(jìn)行交換。

步驟3通過隨機(jī)選擇來確定關(guān)鍵塊中工序的交換方式。

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

3 算法驗證

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

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

表1 中，C?為已知最優(yōu)解；best 為運(yùn)行10 次得到的最優(yōu)解；avg 為連續(xù)運(yùn)行10 次得到的平均值；加粗?jǐn)?shù)據(jù)表示已經(jīng)達(dá)到最優(yōu)解。選取benchmark 中關(guān)于JSP 的若干算例進(jìn)行驗證。

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

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

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

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

4 結(jié)束語

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