（長安大學 道路施工技術(shù)與裝備教育部重點實驗室，西安 710064）

0 引言

作業(yè)車間調(diào)度問題（Job Shop Scheduling Problem，JSP）是一類典型的組合優(yōu)化問題，科學、合理的調(diào)度方案能夠有效提高生產(chǎn)效率、降低加工成本，而問題的求解方法則是實現(xiàn)這些目標的重要保證。遺傳算法（Genetic Algorithm，GA）作為一種群智能算法，具有隱式并行性和全局搜索特性[1～3]，是求解作業(yè)車間調(diào)度問題的有力工具，但標準遺傳算法存在早熟收斂、解的穩(wěn)定性差、遺傳參數(shù)難以確定等諸多缺點[4,5]。

本文針對標準遺傳算法的不足之處對其作了相應(yīng)的改進，提出了一種新的個體適應(yīng)度值計算方法，采用三種方式對染色體進行配對交叉以增強個體的多樣性，在選擇階段引入了精英保留策略[6]來確保算法的收斂性，在迭代過程中使算法自動對交叉和變異概率進行動態(tài)調(diào)整，并討論了動態(tài)概率調(diào)整函數(shù)中的參數(shù)取不同值時算法性能的變化情況。

1 JSP問題的數(shù)學模型

JSP問題的一般性描述為：n個工件在m臺機器上加工，工件每道工序的加工機器和加工時間確定，同時滿足以下約束條件：1）每個工件的工序按其工藝路線順次加工，中途不得中斷；2）同一時刻，一道工序只能在一臺機器上加工；3）同一時刻，一臺機器只能加工一道工序，4）每個工件在每臺機器上只加工一次。所要解決的問題是對各工件的加工順序進行合理安排以優(yōu)化一個或多個加工性能指標。

本文以最小化最大完工時間為優(yōu)化目標，假設(shè)安裝與調(diào)整時間包含在工序的加工時間內(nèi)，各工件無加工優(yōu)先級之分，相應(yīng)的數(shù)學模型如下：

優(yōu)化目標：

約束條件：

式(1)為優(yōu)化目標函數(shù)；式(2)表示工序約束；式(3)表示機器約束；式(4)表示工件完工時間大于零；式(5)表示各下標變量的取值范圍。

式中，Cmax為最大完工時間；Cip為工件i在機器p上的完工時間；m為機器總數(shù)；n為工件總數(shù)；Sip為工件i在機器p上的開工時間；M是一個極大的正數(shù)；i, j為工件編號；p，q為機器編號。

2 算法設(shè)計

2.1 染色體編碼

本文采用基于工序的實數(shù)編碼來表示個體（染色體）[7]，一組編碼代表一種可行的加工方案，如對于工序碼[3 2 1 1 2 3 2 3 1]，各個數(shù)字代表被加工件的工件號，數(shù)字第幾次出現(xiàn)就代表相應(yīng)工件的第幾道工序，如第一個“3”表示三號工件的第一道工序，第二個“3”表示三號工件的第二道工序。

2.2 種群初始化

初始種群用于生成第一代子代個體，本文采用隨機方式生成初始種群，利用MATLAB軟件自帶的隨機排序函數(shù)“randperm”隨機打亂一組染色體的編碼，通過多次調(diào)用該函數(shù)來獲得所需規(guī)模的初始種群。

2.3 計算個體適應(yīng)度值

在以最小化最大完工時間為優(yōu)化目標時，以往的研究大多以目標函數(shù)值的倒數(shù)作為個體的適應(yīng)度值，這種方式所求得的個體的適應(yīng)度值均較為接近，難以體現(xiàn)出個體差異，從而不利于在選擇階段將具有不同適應(yīng)度值的個體有效區(qū)分開來。因此，對適應(yīng)度函數(shù)進行改進以拉開個體間的差距，并采用精英保留策略使最優(yōu)個體存活下來不受遺傳操作的破壞而直接遺傳到下一代。

設(shè)Ms(i)表示個體i對應(yīng)的最大完工時間，Max和Min分別表示種群中的最大值與最小值，定義個體的適應(yīng)度函數(shù)為：

假設(shè)有5個個體，對應(yīng)的最大完工時間依次為：[10, 11, 12, 13, 14]，按傳統(tǒng)方法算得的個體適應(yīng)度值分別為：[0.1, 0.0909, 0.0833, 0.0769, 0.0714]，個體的選擇概率如圖1(a)所示；按式(6)算得的個體適應(yīng)度值為：[1, 0.6818, 0.4161, 0.1923, 0]，對應(yīng)的個體選擇概率如圖1(b)所示。

對比圖1(a)和圖1(b)可以看出，傳統(tǒng)的適應(yīng)度值計算法中，每個個體幾乎占據(jù)了相同的扇形面積，即所有個體將以近似相等的概率被選中，而改進的適應(yīng)度值計算方法中，個體之間則具有較高的區(qū)分度，能夠保證適應(yīng)度值最低的個體（如個體5）在選擇階段被淘汰，而適應(yīng)度值高的個體以較大的概率被復(fù)制，從而在真正意義上體現(xiàn)出了遺傳算法“優(yōu)勝劣汰”的特點。

2.4 選擇算子

采用輪盤賭法[8,9]選擇個體，計算公式如下：

圖1 個體的選擇概率

式中，sum(f)表示個體適應(yīng)度值之和，p(i)表示個體i被選擇的概率，q(i)為個體i的累計概率，產(chǎn)生一個取值在區(qū)間[0,1]內(nèi)的隨機數(shù)δ，若δ≤q(1)，則選中第1個個體，否則的話，若q(i-1)＜δ≤q(i)，則選中第i個個體。

2.5 交叉與變異算子

2.5.1 交叉與變異方式

本文采用優(yōu)先工序交叉法（Precedence Operation Crossover，POX）進行交叉操作[10]，并對其進行了擴展。標準POX法中，首先隨機產(chǎn)生兩個基序列J1、J2，將配對的父代個體P1、P2所含的J1中的基因按原位復(fù)制到子代個體C1、C2中，而將所含的J2中的基因按原有順序依次填入到子代個體C2、C1的空位基因處[11]，從而得到交叉后的子代個體C1和C2。

POX法的第一種擴展方式為：將父代個體P1、P2所含的J2中的基因逆序后再填入到子代個體C2、C1中；第二種擴展方式為：將父代個體P1、P2所含的J2中的基因隨機打亂順序后再填入到子代個體C2、C1中。兩種改進的POX法中，父代個體所含的J1中的基因的處理方式與標準POX法相同。迭代時隨機選擇基本POX法與改進的POX其中的一種交叉方式，從而以多種方式使子代繼承父代的優(yōu)良基因，提高了子代個體的多樣性。

變異屬于小概率事件，但有利于擴大種群的多樣性，本文采用互換法（Reciprocal Exchange Mutation，REM）進行變異操作[12]，即隨機選擇兩個含有不同基因的基因位，將對應(yīng)元素調(diào)換位置。

2.5.2 交叉與變異概率

標準遺傳算法以固定的交叉概率和變異概率進行相應(yīng)的操作，當二者取值較小時會使搜索范圍變小，不利于尋找到更優(yōu)解，而取值較大時則可能導(dǎo)致已有的優(yōu)良個體在交叉和變異操作后變得更差。因此，本文設(shè)計了一種動態(tài)自適應(yīng)交叉概率和變異概率，一方面根據(jù)個體在種群中的較高或較低的地位（適應(yīng)度值越大，地位越高，反之則越低）來給予其較小或較大的交叉與變異概率，另一方面通過動態(tài)概率調(diào)整函數(shù)使迭代初期個體以較大的概率進行交叉和變異，以擴大尋優(yōu)范圍，避免算法早熟收斂，而在迭代后期則減小交叉與變異概率，以降低前期所得到的優(yōu)秀個體被交叉和變異操作所破壞的概率，同時保證算法盡快收斂。

改進后的動態(tài)自適應(yīng)交叉概率和變異概率的計算公式如下：

式中，i為當前迭代次數(shù)，N為終止迭代次數(shù)，指數(shù)v是調(diào)整參數(shù)，取值為區(qū)間[1,5]內(nèi)的整數(shù)，Pc為交叉概率，Pm為變異概率，kc, km分別為區(qū)間[0,1]內(nèi)的常數(shù)，fc為兩個交叉?zhèn)€體的較大的適應(yīng)度值，fm為變異個體的適應(yīng)度值，fa和fmax分別為當前種群的平均適應(yīng)度值和最大適應(yīng)度值。

式(9)中，指數(shù)v取不同值時，得到的動態(tài)概率調(diào)整函數(shù)cos(u)的圖形如圖1所示。

圖2 動態(tài)概率調(diào)整函數(shù)圖形

從圖中可以看出，隨著迭代次數(shù)增加，函數(shù)cos(u)的值從1變?yōu)?，斜率逐漸增大，從而在迭代初期保持較大的Pc和Pm進行尋優(yōu)，在迭代后期則以較小Pc和Pm來加速收斂，而指數(shù)v取值越大時，曲線凸起程度越大，從而在越多的迭代次數(shù)范圍內(nèi)以大概率進行交叉與變異，以擴大種群多樣性來搜索更優(yōu)解，但同時也會使收斂速度降低。因此，當要求算法具有更強的尋優(yōu)能力時，應(yīng)取較大的v值，當要求算法具有更快的收斂速度時，應(yīng)取較小的v值。

改進遺傳算法的流程圖如圖3所示。

圖3 改進遺傳算法計算過程

3 實例驗證

以Ft06基準算例[13]來驗證改進后的遺傳算法的性能，試驗數(shù)據(jù)如表1所示，程序運行平臺為Windows7操作系統(tǒng)下的MATLAB軟件，取種群規(guī)模為PS=40，迭代次數(shù)為FC=200，標準遺傳算法采用基本POX法進行交叉操作，采用互換法進行變異操作，交叉和變異概率分別為Pc=0.7，Pm=0.1，改進遺傳算法由式(6)計算個體適應(yīng)度值，隨機選擇三種交叉方式中的一種進行交叉操作，變異操作仍采用互換變異法，交叉概率Pc和變異概率Pm分別由式(10)和式(11)確定，式中，取kc=0.9，km=0.12，指數(shù)v分別取1、2、3、4、5，將標準遺傳算法和指數(shù)v的不同取值下的改進遺傳算法各運行20次，所得結(jié)果如表2所示。

表1 各工序加工機器（加工時間）

由表2可知，標準遺傳算法求得的最優(yōu)解為56，而改進遺傳算法求得的最優(yōu)解為55，且后者最優(yōu)解的個數(shù)遠大于前者，雖然在v=4，5時，改進算法的平均迭代次數(shù)大于標準遺傳算法，但無論指數(shù)v取何值，改進遺傳算法所求目標函數(shù)的平均值均小于標準遺傳算法對應(yīng)的值?？梢姡谧顑?yōu)解的質(zhì)量和數(shù)量上，改進遺傳算法均優(yōu)于標準遺傳算法，表明了改進后的遺傳算法的有效性與可行性，標準遺傳算法與改進遺傳算法所求最優(yōu)解的調(diào)度甘特圖如圖4、圖5所示。

表2 改進前/后算法試驗結(jié)果對比

根據(jù)表2數(shù)據(jù)，得到改進遺傳算法中指數(shù)v分別取1，2，3，4，5時的目標函數(shù)均值與平均迭代次數(shù)的變化趨勢如圖6所示。

由圖6可以看出，在改進遺傳算法中，參數(shù)v的取值與問題解的優(yōu)度呈正相關(guān)關(guān)系，而與收斂速度呈負相關(guān)關(guān)系，與理論分析結(jié)果是吻合的，因此，本文所提出的改進遺傳算法中，較大的v值有利于提高解的優(yōu)度，較小的v值有利于提高算法的收斂速度，在實際應(yīng)用時可根據(jù)具體要求來合理選取參數(shù)v的值。

圖4 標準遺傳算法最優(yōu)解調(diào)度甘特圖

圖5 改進遺傳算法最優(yōu)解調(diào)度甘特圖

圖6 不同v值下的改進遺傳算法所求目標函數(shù)均值與平均迭代次數(shù)變化趨勢

4 結(jié)束語

本文針對以最小化最大完工時間為優(yōu)化目標的作業(yè)車間調(diào)度問題，從個體適應(yīng)度函數(shù)、染色體交叉方式以及交叉與變異概率三方面對標準遺傳算法進行了相應(yīng)的改進，所設(shè)計的動態(tài)交叉概率與變異概率能夠根據(jù)個體的適應(yīng)度值與算法迭代次數(shù)而自動調(diào)整，從而擴大迭代初期的搜索范圍，使算法在前期具有較強的尋優(yōu)能力，而在后期以較小的交叉與變異概率使算法盡快收斂，同時，對動態(tài)概率調(diào)整函數(shù)的參數(shù)v取不同值時算法的性能進行了分析，為實際應(yīng)用中v值的選取提供了參考。今后的研究可以從種群的初始化方式、個體的選擇規(guī)則以及遺傳算法與其他智能算法的融合等方面入手，從而使求解作業(yè)車間調(diào)度問題的算法變得更加高效和完善。