徐 雨，黃海松，胡 淶

（貴州大學(xué)現(xiàn)代制造技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，貴州 貴陽(yáng) 550025）

1 引言

車間作業(yè)調(diào)度問(wèn)題（job shop scheduling problem，JSP）是企業(yè)制造系統(tǒng)中的一個(gè)關(guān)鍵環(huán)節(jié)，其通過(guò)合理的安排零件加工時(shí)間和次序、合理的分配現(xiàn)有資源來(lái)制定在生產(chǎn)過(guò)程中的生產(chǎn)計(jì)劃。JSP問(wèn)題直接關(guān)系著企業(yè)管理及其生產(chǎn)效率。有效的優(yōu)化JSP問(wèn)題，能夠降低企業(yè)生產(chǎn)成本、提高生產(chǎn)資源的利用率、快速響應(yīng)市場(chǎng)的需求，從而提高企業(yè)競(jìng)爭(zhēng)力。JSP屬于NP（nondeterministic polynomial）問(wèn)題[1]。目前應(yīng)用在車間作業(yè)調(diào)度問(wèn)題的優(yōu)化算法主要有免疫算法[2]、遺傳算法[3-4]、粒子群算法[5]、蟻群算法[6]和模擬退火算法[7]等，而且這些算法在JSP方面都擁有杰出的成果。免疫遺傳算法（Immune genetic algorithm，IGA）是一種免疫算法與遺傳算法相結(jié)合的混合算法，其相比較于一般的遺傳算法，在種群進(jìn)化過(guò)程中，免疫遺傳算法通過(guò)免疫操作能有效的提高算法的搜索能力和加快算法的收斂速度。免疫遺傳算法已經(jīng)被應(yīng)用到多個(gè)研究領(lǐng)域，車間調(diào)度問(wèn)題[2]也包括在其中。文獻(xiàn)[8]對(duì)免疫算法的產(chǎn)生和發(fā)展進(jìn)行了概述，且對(duì)免疫算法的發(fā)展前景進(jìn)行了展望。文獻(xiàn)[9]中設(shè)計(jì)了抽取和接種疫苗的免疫操作，即將加工機(jī)器的基因片段作為疫苗，并以加工機(jī)器為基準(zhǔn)接種疫苗，此算法有效的提高了算法的準(zhǔn)確性與收斂效率，但算法在求解較大規(guī)模的車間問(wèn)題時(shí)偏差較大。文獻(xiàn)[10]中設(shè)計(jì)一種改進(jìn)的優(yōu)先操作交叉算子，同時(shí)重新設(shè)計(jì)了免疫算子，該算法能對(duì)較大規(guī)模的車間調(diào)度問(wèn)題得到很好地解決，但隨機(jī)運(yùn)算次數(shù)過(guò)多，運(yùn)算時(shí)間較長(zhǎng)。文獻(xiàn)[11]中將免疫遺傳算法和模擬退火算法結(jié)合使用，利用分解策略對(duì)車間調(diào)度進(jìn)行求解，該算法在抑制種群退化，防止算法陷入局部最優(yōu)和加快算法的收斂速度方面做出了貢獻(xiàn)，但就精英個(gè)體選擇方面考慮欠佳。為此，將模擬退火算法的局部搜索理論與免疫遺傳算法的全局性、多樣性和自適應(yīng)性結(jié)合起來(lái)，互相取長(zhǎng)補(bǔ)短，形成性能優(yōu)良的全局尋優(yōu)的混合免疫遺傳算法，并設(shè)置了自適應(yīng)精英選擇操作，最后將其應(yīng)用在作業(yè)車間調(diào)度問(wèn)題的求解中。

2 車間作業(yè)調(diào)度問(wèn)題描述

車間作業(yè)調(diào)度問(wèn)題（JSP）主要研究：n個(gè)工件，在m臺(tái)機(jī)器上加工完成，每個(gè)工件i的工序數(shù)為oi，每個(gè)工件的不同工序在不同的機(jī)器上加工完成，其相應(yīng)的加工時(shí)間也各不相同。假設(shè)：（A）同一機(jī)器，可以加工多道工序，但是同一時(shí)刻最多只有一個(gè)工件在上面加工。（B）每個(gè)工件的每道工序加工機(jī)器和時(shí)間已知。（C）工序開始加工后，不能中斷加工。（D）不同工件的工序加工沒有先后順序的要求。（E）同一工件在加工過(guò)程中，有預(yù)設(shè)的加工順序。數(shù)學(xué)符號(hào)定義，如表1所示。

表1 數(shù)學(xué)符號(hào)定義Tab.1 Mathematical Symbol Definition

3 求解JSP問(wèn)題的改進(jìn)IGA算法

3.1 編碼與解碼

遺傳算法在車間作業(yè)調(diào)度問(wèn)題（JSP）方面的編碼方式主要有兩種，即間接編碼與直接編碼。其中，間接編碼的染色體是由一組工件的分配規(guī)則編碼而成，其調(diào)度方案則是由分配規(guī)則序列得到的。而直接編碼的染色體直接由一個(gè)調(diào)度方案編碼而成。

考慮到直接編碼方式編碼和解碼方式簡(jiǎn)單、柔性高和防死鎖等優(yōu)點(diǎn)，采用一種基于工序的直接編碼方式[12]。直接編碼過(guò)程就是：在求解有m臺(tái)機(jī)器加工n個(gè)工件的JSP問(wèn)題時(shí)，假設(shè)每個(gè)工件有m道工序，這些工序分別在m臺(tái)機(jī)器上加工，所以編碼的染色體組成的基因個(gè)數(shù)為n*m，每條染色體都可視為一個(gè)調(diào)度方案，染色體中同一工件的加工工序序號(hào)相同。在一條染色體中，若同一工件的加工工序序號(hào)第k次出現(xiàn)，則這個(gè)第k次出現(xiàn)的基因表示這一工件的第k道工序。例如：一個(gè)3×3的JSP問(wèn)題，如表2所示?？蓪⑺囊粋€(gè)工序序列設(shè)為［3 1 1 2 3 2 2 3 1］。其中，1，2，3分別表示工件wp1，wp2和wp3，工序序列中從左到右三個(gè)1分別表示工件wp1的第一道工序，第二道工序和第三道工序，2和3同1類似。

表2 一個(gè)3＊3的JSP問(wèn)題Tab.2 A 3＊3 JSP Problem

解碼就是將計(jì)算機(jī)語(yǔ)言轉(zhuǎn)化到實(shí)際問(wèn)題的一種映射過(guò)程，在車間作業(yè)調(diào)度問(wèn)題中，解碼就是將染色體轉(zhuǎn)化成一個(gè)調(diào)度方案。采用的解碼方法是一種插入式貪婪解碼算法[13]。貪婪解碼過(guò)程為：首先按照染色體上加工工序的從左到右依次降低工序的優(yōu)先權(quán)重，然后安排染色體上的工序序列的第1道工序進(jìn)行加工，再然后依次安排各工件剩余工序，并將其插入到對(duì)應(yīng)機(jī)器上可行的最佳加工時(shí)刻加工，最終達(dá)到所有的加工工序都安排在對(duì)應(yīng)機(jī)器上最佳可行的時(shí)刻加工。例如：上述的3×3的調(diào)度問(wèn)題，其中一條染色體為［3 1 1 2 3 2 2 3 1］，對(duì)應(yīng)加工時(shí)間序列為［1 3 2 2 3 2 3 3 4］，機(jī)器序列表述為［2 1 3 2 3 1 3 1 2］，該染色體通過(guò)貪婪式解碼后可得到：機(jī)器1上的工件加工順序?yàn)?-3-2，機(jī)器2上的工件加工順序?yàn)?-1-3，機(jī)器3上的工件加工順序?yàn)?-3-1。使用貪婪解碼方法與半主動(dòng)解碼方法，如圖1、圖2所示。由圖可知使用一般解碼方法的時(shí)間為11，而使用貪婪解碼的時(shí)間為10。

圖1 貪婪解碼方法Fig.1 Greedy Decoding Method

圖2 半自動(dòng)解碼方法Fig.2 Semi-Automatic Decoding Method

3.2 精英保留策略

在抗體評(píng)價(jià)過(guò)程中，一方面提高了適應(yīng)度高的個(gè)體的選擇概率，而另一方面又降低了濃度高的個(gè)體的選擇概率。而在抑制高濃度的個(gè)體過(guò)程中，很容易丟失最優(yōu)解。所以利用精英保留策略來(lái)保留已獲得的優(yōu)質(zhì)的進(jìn)化成果。傳統(tǒng)的精英保留策略只保留某一固定數(shù)量適應(yīng)度最高的個(gè)體，這種保留策略不利于算法的收斂，且容易導(dǎo)致算法陷入局部最優(yōu)?；诖藛?wèn)題提出了一種自適應(yīng)精英保留策略。

為了確定種群進(jìn)化程度，引入了成熟度的概念。若單個(gè)抗體v的適應(yīng)度和濃度分別為Agv，Cv，則成熟度為：

式中：M—種群進(jìn)化的成熟度；α—常數(shù)，為了加權(quán)適應(yīng)度與濃度的響。

精英保留在種群的成熟度較低的時(shí)候應(yīng)該保留較多的精英個(gè)體，加快收斂速度，成熟度較高時(shí)，選擇較少精英個(gè)體，提高種群的多樣性。所以，其保留精英個(gè)體數(shù)的公式為：

式中：Ne—精英保留個(gè)體數(shù)；N—抗體總數(shù)；b—預(yù)設(shè)正整數(shù)，防止初期保留太多精英個(gè)體，導(dǎo)致算法陷入局部最優(yōu)；ceil—向上取整。

3.3 變異算子

為了有效的提高算法的收斂速度和避免算法陷入局部最優(yōu)，該算法將變尺度變異與自適應(yīng)概率變異進(jìn)行了融合，提出了混合變異算子。其中，自適應(yīng)變異概率為：

式中：pm—變異概率；farg—群體的平均適應(yīng)度值；fmax—群體最大適應(yīng)度值；f—變異個(gè)體適應(yīng)度值；取pc1=0.1，pc2=0.001。

在算法早期，種群大多數(shù)是由隨機(jī)產(chǎn)生的，離最優(yōu)解相差甚遠(yuǎn)，種群中的大多數(shù)抗體的適應(yīng)度低，大概率的采用反轉(zhuǎn)變異可以提高算法在早期的查找效率。在算法后期，種群抗體的適應(yīng)度高，如果也采用反轉(zhuǎn)法變異將會(huì)產(chǎn)生過(guò)多的冗余信息。為了避免盲目搜索，提高算法執(zhí)行效率，又不至于陷入局部最優(yōu)，該算法采用基于自適應(yīng)變異概率的小步成熟機(jī)制的換位變異法進(jìn)行變異操作。

混合變異算子的流程為：

（1）計(jì)算當(dāng)代種群平均適應(yīng)度與需要變異抗體的適應(yīng)度。

（2）比較（1）中兩適應(yīng)度的大小，若變異抗體適應(yīng)度大于平均適應(yīng)度，選擇小步成熟機(jī)制的換位法變異；若變異抗體適應(yīng)度小于等于平均適應(yīng)度，則采用反轉(zhuǎn)變異法

（3）根據(jù)自適應(yīng)變異公式計(jì)算變異概率，開始變異操作。

3.4 免疫算子

3.4.1 疫苗的提取與接種

免疫操作分兩步進(jìn)行，即提取疫苗和接種疫苗。適當(dāng)?shù)倪M(jìn)行疫苗注射可以有效的避免種群退化和提高種群的適應(yīng)度，從而大大加快了算法的收斂速度和提高算法的尋優(yōu)能力。

這里算法所采用的疫苗提取方法為基于加工機(jī)器的基因片段提取疫苗[8]。

提取疫苗的流程為：

①將上代抗體中親和力最大的若干個(gè)體抽取出來(lái)。

②將抽取出來(lái)的抗體按加工機(jī)器打碎成基因片段，將所得到的基因片段保存在疫苗庫(kù)中。

接種疫苗是利用前面提取的疫苗來(lái)修改所選的部分個(gè)體染色體的某些位置的某些基因，從而有效的避免種群退化和提高種群的適應(yīng)能力。

疫苗接種操作如下：

（1）將父代種群的部分個(gè)體選取出來(lái)。

（2）隨機(jī)選取疫苗庫(kù)中的疫苗作為注射疫苗。

（3）取第（1）步操作中的未注射疫苗的一個(gè)個(gè)體作為疫苗注射對(duì)象。

（4）將疫苗的基因順序代替注射對(duì)象同一機(jī)器所對(duì)應(yīng)位置基因的順序。

（5）重復(fù)（2）到（4）步操作，直到第（1）步操作所選取出來(lái)的個(gè)體全部注射疫苗。

3.4.2 抗體評(píng)價(jià)及退火免疫選擇

以抗體v的繁殖概率ev即免疫選擇率作為個(gè)體的評(píng)價(jià)標(biāo)準(zhǔn)。繁殖概率是由抗體的親和度與該抗體的濃度共同決定的。利用繁殖概率這種選擇機(jī)制選擇抗體既有效的鼓勵(lì)了適應(yīng)度高的個(gè)體，又適當(dāng)?shù)囊种屏藵舛雀叩目贵w，其計(jì)算公式為：

為了更好地接受適應(yīng)度高的抗體，并且適當(dāng)?shù)囊种茲舛雀叩目贵w，提出了基于抗體評(píng)價(jià)的模擬退火選擇。

模擬退火選擇可以分為檢測(cè)抗體和選擇抗體兩步來(lái)進(jìn)行。第一步，檢測(cè)抗體，檢測(cè)注射疫苗的抗體的適應(yīng)度并將其適應(yīng)度值與舊抗體的適應(yīng)度值進(jìn)行比較，若新抗體適應(yīng)度更高，則以抗體的繁殖概率選取新抗體進(jìn)入下一代；若舊抗體適應(yīng)度更高，則說(shuō)明出現(xiàn)了種群退化現(xiàn)象，需要進(jìn)入第二步操作。第二步是利用模擬退火的Metropolis接受準(zhǔn)則來(lái)決定接受新抗體的概率。即①若Δfv=

式中：T0—退火初始溫度；γ∈（0，1）—降溫系數(shù)；Tk—當(dāng)前退火溫度；p—Tk溫度下的接受概率；Δfv—新個(gè)體適應(yīng)度與舊體適應(yīng)度之差；fvs—新個(gè)體適應(yīng)度值；fv（s-1）—上一次迭代中舊個(gè)體適應(yīng)度值。

3.5 算法流程

算法流程圖，如圖3所示。

圖3 算法流程圖Fig.3 Algorithm Flow Chart

（1）設(shè)置算法參數(shù)并隨機(jī)初始化種群。

（2）設(shè)置迭代次數(shù)為0，計(jì)算種群的適應(yīng)度、濃度以及期望繁殖概率。

（3）自適應(yīng)精英選擇精英個(gè)體，更新記憶庫(kù)，對(duì)種群進(jìn)行免疫遺傳操作。

（4）進(jìn)行選擇操作，自適應(yīng)交叉。

（5）判斷抗體適應(yīng)度是否大于平均適應(yīng)度，若是，則計(jì)算變異概率pm2執(zhí)行換位變異；若不是，則計(jì)算變異概率pm1執(zhí)反轉(zhuǎn)變異。

（6）退火選擇，更新退火溫度，更新種群。

（7）判斷是否達(dá)到最大迭代次數(shù)，如果未到達(dá)進(jìn)入下一次迭代，如果達(dá)到進(jìn)入（8）。

（8）判斷退火溫度是否達(dá)到結(jié)束溫度，若未達(dá)到返回（2），若達(dá)到輸出最優(yōu)解，結(jié)束算法。

4 計(jì)算結(jié)果和比較分析

為驗(yàn)證算法的有效性與高效性，下面用Muth和Thompson提出的著名的MT06作為該算法的測(cè)試基準(zhǔn)。利用該算法不同參數(shù)對(duì)MT06問(wèn)題仿真試驗(yàn)20次，取最優(yōu)的算法參數(shù)，參數(shù)設(shè)置如下：種群規(guī)模為 47；交叉概率（0.6～0.9），初始值為 0.9；變異概率為0.01；闕值T為0.95；初始溫度為10000；衰減系數(shù)為0.90；迭代次數(shù)為110。使用MATLAB2010b在Windows環(huán)境下運(yùn)行。算法收斂曲線，如圖3所示。由圖4可知，混合免疫遺傳算法在第四十次迭代就完成了收斂，找到最優(yōu)值，說(shuō)明了算法的高效性；最佳工件加工順序圖，如圖5所示。得到最短生產(chǎn)時(shí)間為55s，達(dá)到最優(yōu)，說(shuō)明了算法的有效性。

圖4 收斂曲線圖Fig.4 Convergence Curve

圖5 工件加工甘特圖Fig.5 Workpiece Processing Gantt Chart

基于MT06問(wèn)題的不同算法的比較，如表3所示。就MT06問(wèn)題而言本算法比一般的IGA，SA算法得到最優(yōu)解的概率要高很多，而且平均偏差僅為2.03%；不同算法性能比較，如表4所示。對(duì)于MT20問(wèn)題，這里算法比其他算法得到的結(jié)果更優(yōu)，對(duì)MT06和MT10問(wèn)題，雖然各個(gè)算法都能得到最優(yōu)值，但這里算法的出錯(cuò)率更低。綜上所述，這里算法前期能夠快速收斂，后期能夠跳出局部收斂，防止“早熟”，顯示了其良好的全局尋優(yōu)能力。

表3 基于MT06問(wèn)題的不同算法的比較Tab.3 Comparison of Different Algorithms Based on MT06 Problem

表4 不同算法性能比較Tab.4 Comparison of Performance of Different Algorithms

5 結(jié)論

通過(guò)對(duì)免疫遺傳算法及模擬退火算法的了解，結(jié)合了兩者的優(yōu)點(diǎn)，提出了一種混合免疫遺傳算法并用其求解了著名的JSP問(wèn)題。通過(guò)仿真試驗(yàn)結(jié)果證明了算法的可行性和高效性。具體表現(xiàn)為：（1）算法通過(guò)對(duì)MT06問(wèn)題的仿真，生成了最優(yōu)的調(diào)度方案。其中，最大完成時(shí)間達(dá)到了最優(yōu)的55s，說(shuō)明了算法的可行性；算法在第四十次就達(dá)到了收斂，說(shuō)明了算法的高效性。（2）就MT06問(wèn)題而言，混合IGA算法比普通的SA算法和IGA算法擊中最優(yōu)解的概率更高，而且偏差更小。（3）在求解相對(duì)復(fù)雜的MT10問(wèn)題時(shí)，混合IGA算法比普通的SA算法和IGA算法離最優(yōu)解更近，離最優(yōu)解相差只有1s。