基于免疫遺傳算法求解多目標(biāo)柔性作業(yè)調(diào)度問題

楊立熙，王秀萍

(福州大學(xué) 經(jīng)濟與管理學(xué)院，福建 福州 350108)

調(diào)度是影響制造業(yè)生產(chǎn)效率的重要因素，隨著市場需求的動態(tài)變化，柔性作業(yè)車間調(diào)度問題(flexible job-shop scheduling problem, FJSP)逐漸成為生產(chǎn)管理領(lǐng)域中的研究重點，F(xiàn)JSP需要確定工序加工順序和給每道工序分配機器，因其增加了機器分配部分，增大了問題的復(fù)雜性和難度，被證明是NP-hard問題[1]。

經(jīng)過多年的研究，學(xué)者們求解FJSP常用的方法有遺傳算法、蟻群算法、粒子群算法等[2-4]。其中，遺傳算法因其魯棒性好、通用性強等特點，在生產(chǎn)調(diào)度領(lǐng)域得到廣泛應(yīng)用，如文獻[5]～文獻[9]分別對初始化方法、編碼、流程、變異操作、非支配排序等遺傳算子進行改進。但單一的遺傳算法存在搜索效率低、容易過早收斂等不足，故學(xué)者開始將遺傳算法和其他方法結(jié)合并獲得了成效，如文獻[10]和文獻[11]提出將遺傳算法和移動瓶頸相結(jié)合并求得滿意解，但求解過程和算法實施很復(fù)雜；文獻[12]和文獻[13]分別提出模擬退火遺傳算法和禁忌遺傳算法求得滿意解，但算法對參數(shù)有較強的依賴性；文獻[14]和文獻[15]分別提出BP神經(jīng)算法、蟻群算法和遺傳算法結(jié)合求得FJSP的滿意解，但人工神經(jīng)網(wǎng)絡(luò)和蟻群算法的解依賴于網(wǎng)絡(luò)參數(shù)，且優(yōu)化時間性能較差。

針對以上不足，有學(xué)者采用免疫算法求解FJSP，免疫算法是新興智能算法，借鑒了生物免疫系統(tǒng)的自適應(yīng)識別和排除抗原性異物的功能，是有效的全局尋優(yōu)算法。如文獻[16]提出雙種群的免疫算法求解多目標(biāo)FJSP，但多種群之間的交流會增加運行時間；文獻[17]提出自適應(yīng)免疫遺傳算法求解單目標(biāo)FJSP，但其算子較多導(dǎo)致花費時間長；文獻[18]提出免疫粒子群算法，但粒子群算法的收斂性受初始粒子分布影響。

為避免上述免疫混合算法存在的問題，筆者提出新的免疫遺傳算法(immune genetic algorithm, IGA)，該算法采用新的初始化方法提高種群初始解的質(zhì)量，設(shè)計合理的編碼機制、選擇策略、自適應(yīng)交叉變異操作，結(jié)合免疫接種和免疫記憶等操作，以提高全局收斂性，將該算法應(yīng)用于實例中，結(jié)果表明該算法是有效可行的。

1　柔性作業(yè)車間調(diào)度問題概述

1.1　FJSP描述

FJSP可描述為：有n個加工工件要在m臺機器上加工，每個工件包含一道以上工序，每道工序可以在不同的機器上加工，在機器上的加工時間不一定相同；調(diào)度目標(biāo)是將工件合理地安排到最合適的機器上，且使得整個系統(tǒng)的性能指標(biāo)達(dá)到最佳。此外，還需滿足的條件有：同一工件的各工序的先后順序已知，工序在其上一道工序完成后才可以開始加工；每道工序在加工時只能被一臺機器加工；每臺機器在同一時間不能加工多道工序；每道工序在機器上加工時不允許中途被中斷；不同工件的工序之間是沒有先后順序約束的；所有工件在零時刻都可以被加工；所有機器在零時刻是可以加工工件的。為了更好說明FJSP，以3×5(P-FJSP)柔性作業(yè)車間調(diào)度問題為例，具體如表1所示。

表1　3×5 FJSP加工時間表　s

1.2　多目標(biāo)FJSP優(yōu)化模型

數(shù)學(xué)模型描述為：工件集合J={J1，J2，…，Jn}(i=1,2,…,n)；工件Ji的工序集合Oi={Oi1,Oi2，…Oini}(j=1,2,…,ni)，Oij是工件Ji的第j道工序；機器集合M={M1，M2，…，Mm}(k=1,2,…,m)；Mj是工件Ji在機器集合M上所有可用機器的集合；Pijk是工件Ji的第j道工序Oij在第Mk臺機器上的加工時間；Ci是工件Ji的完工時間。

調(diào)度目標(biāo)選常見的3個評價指標(biāo)，即最大完工時間最小CM、機器總負(fù)荷最小WT、機器最大負(fù)荷最小WM，指標(biāo)函數(shù)分別如下：

(1)

(2)

(3)

其中，xijk為決策變量，當(dāng)工序Oij在第k臺機器上加工時，xijk=1,否則取0。

2　改進的免疫遺傳混合算法

2.1　編碼和解碼

2.1.1編碼

由于FJSP需要解決兩個子問題：工序排序和機器選擇。因此，筆者采用基于工序和基于機器相結(jié)合的雙層編碼方式。

(1)基于工序的編碼：染色體長度等于所有工序總數(shù)，每個工件的工序都用相應(yīng)的工序號表示，工件號出現(xiàn)的順序表示該工件工序間的先后加工順序。以表1為例，假設(shè)給定染色體(1 2 3 3 1 3 2 1),染色體中第一個“1”表示工序O11,第二個“1”表示工序O12,第三個“1”表示工序O13，即以上染色體表示的加工工序序列為(O11→O21→O31→O32→O12→O33→O22→O13) 。

(2)基于機器的編碼：染色體長度也等于所有工序總數(shù)，每個基因表示當(dāng)前工序選擇的加工機器在可選機器集中的順序編號。假設(shè)給定染色體(2 1 3 4 2 3 1 2),染色體中第一個出現(xiàn)的“2”表示工序O11在其可選機器集中的第2臺機器上進行加工,第二個數(shù)“1”表示工序O21在機器可選集中的第1臺機器上進行加工，以此類推。

2.1.2解碼

采用插入式貪婪解碼算法以提高算法的速度和質(zhì)量。先確定工件和工序，再從機器中搜索機器可利用的空閑時間段并插入余下的工序，減少機器的空閑時間冗余度以提高機器利用率和縮短完工時間。

2.2　抗原識別

在柔性作業(yè)車間調(diào)度問題中，抗原識別是將抗原與實際求解問題的目標(biāo)對應(yīng)，將免疫系統(tǒng)產(chǎn)生的抗體與實際優(yōu)化問題的可行解相對應(yīng)。

2.3　種群初始化

目前，大部分文獻采用的是隨機初始化法，構(gòu)造出的初始種群具有很大的隨機性，使得初始解的質(zhì)量偏低[19]。為了解決初始解的質(zhì)量問題，筆者提出一種多樣化的新型種群初始化方法，一部分種群采用常用的隨機化方法，一部分種群根據(jù)搭積木模型采用工序選擇剩余加工時間最大，機器選擇完工時間最早的啟發(fā)式算法，兩種初始化方法保證初始種群的多樣性且能提高初始解質(zhì)量。

2.4　Pareto最優(yōu)解

筆者采用NSGA-II算法[20]中的Pareto快速非支配方法求解多目標(biāo)優(yōu)化問題，盡可能地找出Pareto可行解，且這些Pareto解集能夠均勻分布在Pareto邊界上。

2.5　抗體評價

2.5.1抗體間的親和度

抗體間的親和度反映了抗體間的相似度，用來評價抗體的優(yōu)劣，從而保證抗體群的多樣性。假設(shè)有N個抗體，每個抗體有L個基因位即抗體長度為L，每個基因位有S個符號可供選擇，即S1,S2,…，SS，則這N個抗體的信息熵為：

(4)

第w號和第v號抗體之間的抗體親和度AYwv為：

(5)

式中：Hwv(2)為第w號抗體和第v位號抗體的信息熵，Hwv(2)=0表明兩抗體所有基因相同，AYwv∈[0,1]。

2.5.2抗體濃度

濃度Cv表示種群中相似抗體所占的比例，表征抗體種群多樣性的好壞，濃度計算采用基于信息熵的方法，第v號抗體的濃度為：

(6)

2.5.3抗體與抗原間的親和度

抗體與抗原間的親和度AXvz表示抗體v對抗原z的識別度，反映解和目標(biāo)的匹配度。

(7)

(8)

式中：dvz為抗體v與抗原z之間的差異度；rvz為抗體v和抗原z不相同的位數(shù)；L為抗體長度。

2.5.4期望繁殖概率

抗體的期望繁殖概率Pv由抗體v與抗原間z的親和度AXvz和抗體濃度Cv共同決定。

(9)

其中，?為常數(shù)。

2.6　免疫記憶

為了避免有效基因的損失，在每次更新記憶庫時，先將抗原親和度最高的個體存入記憶庫中，再按照期望繁殖概率將剩余群體中的優(yōu)秀個體存入記憶庫中。記憶細(xì)胞庫的更新、免疫記憶的引入能夠有效抑制算法優(yōu)化過程中出現(xiàn)的退化現(xiàn)象。

2.7　抗體產(chǎn)生

2.7.1克隆選擇操作

對種群個體進行克隆選擇時采用的方法是輪盤賭選擇，根據(jù)期望繁殖概率將輪盤分成N個扇區(qū)，每份扇區(qū)的面積為種群抗體的期望繁殖概率，由于抗體濃度越大，選擇的概率越小，反之，選擇概率越大，這樣能夠保留高適應(yīng)度的個體，也能夠保證抗體的多樣性，提高全局收斂性。

2.7.2自適應(yīng)交叉操作

(1)交叉操作:為使得產(chǎn)生的新個體能更多地繼承父代優(yōu)良的遺傳基因，提高尋優(yōu)能力，筆者對雙層編碼分別采取不同的交叉操作，基于工序部分采用新型的基于工件順序的交叉方式(IPOX)[21]和基于機器部分采用新型的多點交叉方式(MPX)。IPOX隨機選擇一個工件并保持工件在兩父代編碼中的位置不變，其余工件的工序按照在父代中出現(xiàn)的順序互換兩父代個體。MPX即隨機產(chǎn)生由0,1數(shù)值構(gòu)成且長度為機器基因總數(shù)的序列，將兩父代中與序列中數(shù)字為1的位置所對應(yīng)的基因相互交換，其余位置保持不變，形成子代。

(2)自適應(yīng)交叉概率:在種群進化過程中，當(dāng)抗體之間的適應(yīng)度非常接近時，不容易跳出局部最優(yōu)解，交叉概率Pc和變異概率Pm是算法的重要參數(shù)，如果Pc和Pm保持不變會導(dǎo)致過于隨機或影響算法的收斂速度，因此筆者設(shè)計自適應(yīng)交叉變異來控制遺傳操作。自適應(yīng)策略能夠使得Pc和Pm隨著種群多樣性自動改變[22]，能夠在優(yōu)化過程中依照迭代次數(shù)自適應(yīng)改變交叉變異概率，避免陷入局部最優(yōu)解或收斂過早的情況。

在種群進化開始階段，交叉概率越大越能擴大種群的區(qū)間范圍，在進化后期，由于種群已具有較大的適應(yīng)度，為避免一定的破壞性，進化后期交叉率越小越好，因此提出自適應(yīng)交叉概率的計算公式，如式(10)所示。當(dāng)?shù)螖?shù)小于迭代總數(shù)的一半時(t≤T/2)，以固定初設(shè)的交叉概率交叉，在進化后期(t>T/2)使用式(10)的交叉概率進行交叉。

Pc(i)=Pc(1-i/N)1/2

(10)

式中：Pc(i)表示第i個抗體的交叉概率；Pc表示初始的交叉概率。

2.7.3自適應(yīng)變異操作

(1)變異操作：其目的是改善算法的局部搜索能力，維持群體的多樣性，防止早熟現(xiàn)象[23]。筆者采用不同的變異操作，基于工序部分采用插入式變異方式，基于機器部分采用分配機器的變異方式。插入式變異方式，即隨機選擇一個基因位，將其隨機插入到另一個基因位之前，該基因位及其后面的基因位因而順延一位。機器部分采用分配機器的變異操作，即隨機選擇一個機器編碼染色體基因，在該基因?qū)?yīng)工序的可選加工機器集中隨機選取一臺可用的機器替換該基因。

(2)自適應(yīng)變異概率：在進化初期，種群具有較小的適應(yīng)度，如果以較小的概率變異，難以變異出較大適應(yīng)度的抗體，為了利于種群的進化，抗體在進化初期的變異概率越大越好。在進化后期，種群具有較高的適應(yīng)度，為了保留最佳抗體，適應(yīng)度高的抗體變異概率越小越好。因此，筆者提出自適應(yīng)變異概率的計算公式,如式(11)所示。

(11)

2.8　免疫接種

2.8.1抽取疫苗

地下水為第四系松散層孔隙潛水，含水層為第四系全新統(tǒng)人工填土、沖積粉土及砂、礫石層，水位埋深3.1 m～4.5 m，高程790.024 m～793.415 m，主要靠大氣降水及側(cè)向徑流和城市供水、排水滲漏補給，排泄方式以蒸發(fā)、人工抽取地下水及側(cè)向徑流補給為主。

由于求解問題難以形成較成熟的先驗知識，不能保證得到有效的疫苗，因此筆者在群體進化過程中從每代最優(yōu)基因中抽取有效信息制作疫苗，將群體進化過程中免疫記憶細(xì)胞庫的優(yōu)良解的基因片段當(dāng)作疫苗，將每個抗體的等位基因上出現(xiàn)的最大概率大于設(shè)定閾值的基因作為疫苗片段。

2.8.2接種疫苗

從父代群體中選擇適應(yīng)度最差的個體作為接種對象，按照接種概率將疫苗的基因片段插入到選中的個體，產(chǎn)生更優(yōu)的免疫種群。

3　實例仿真與實驗

3.1　基準(zhǔn)實例

為了評估和比較算法的性能，筆者選取文獻[24]和文獻[25]中的8×8，10×10基準(zhǔn)問題實例。實驗參數(shù)：兩種群規(guī)模均為P=100，最大迭代次數(shù)為T=100次，交叉概率Pc=0.7，變異概率Pm=0.1，免疫接種率Pv=0.75，記憶庫容量Pr=20，所有實例均充分實驗100次。將筆者算法和傳統(tǒng)遺傳算法SGA[26]、PSO+SA[27]、SM[28]、MOGA[29]進行比較，優(yōu)化結(jié)果如表2所示。由表2可知，該實例中筆者算法比SGA、PSO+SA、MOGA和SM得到更多的Pareto解集，且迭代次數(shù)更少。以8×8實例的結(jié)果為例，繪制出其甘特圖結(jié)果，如圖1所示。

表2　仿真實驗對比結(jié)果

圖1　8×8實例的甘特圖結(jié)果

3.2　應(yīng)用驗證

為驗證算法的實用性，筆者將其應(yīng)用于解決屬FJSP的實例上，選取文獻[30]提供的某汽車公司加工車間的生產(chǎn)數(shù)據(jù)，該車間有6個工件在6臺機器上加工，該實例的數(shù)據(jù)如表3所示。

應(yīng)用筆者算法得到的結(jié)果如表4所示，比文獻[30]的結(jié)果更優(yōu)且能獲得更多數(shù)目的Pareto解，可知工件被合理地安排在各機器上進行加工，通過該實例也驗證了筆者算法的實用性。筆者算法求解該實例的甘特圖如圖2所示。

表36×6FJSP加工時間表

s

表4　Pareto解集

圖2　6×6(P-FJSP)甘特圖

4　結(jié)論

車間調(diào)度是實現(xiàn)先進制造技術(shù)的核心，F(xiàn)JSP是當(dāng)前生產(chǎn)實踐中研究的重大課題，針對FJSP的特點，筆者提出改進的自適應(yīng)免疫遺傳混合算法，利用免疫機制和遺傳算法的特性，可提高算法的全局搜索能力使其不易陷入局部最優(yōu)，最后仿真結(jié)果證明了該算法的有效性和實用性。由于實際生產(chǎn)調(diào)度中往往會發(fā)生訂單加急、機器故障等動態(tài)因素，在下一步的工作中將考慮建立含有不確定因素的FJSP模型，為更接近實際生產(chǎn)調(diào)度提供優(yōu)良調(diào)度方案。

參考文獻：

[1]GAREY M R, JOHNSON D S, SETHI R. The complexity of flow shop and job shop scheduling[J]. Mathematics of Operations Research, 1976,1(2):117-129.

[2]GEN M,JIE G,LIN L. Multistage based genetic algorithm for flexible job-shop scheduling problem[J]. Studies in Computational Intelligence, 2009(187):183-196.

[3]劉志勇,呂文閣,謝慶華,等.應(yīng)用改進蟻群算法求解柔性作業(yè)車間調(diào)度問題[J].工業(yè)工程與管理,2010,15(3):115-119.

[4]賈兆紅,朱建建,陳華平.柔性作業(yè)車間調(diào)度的動態(tài)禁忌粒子群優(yōu)化算法[J].華南理工大學(xué)學(xué)報(自然科學(xué)版),2012,40(1):69-76.

[5]谷峰,陳華平,盧冰原.基于均勻設(shè)計的多目標(biāo)遺傳算法在柔性作業(yè)車間調(diào)度問題中的應(yīng)用[J].系統(tǒng)管理學(xué)報，2006,15(6):71-74.

[6]張國輝,高亮,李培根,等.改進遺傳算法求解柔性作業(yè)車間調(diào)度問題[J].機械工程學(xué)報,2009,45(7):145-151.

[7]楊曉梅，曾建潮.遺傳算法求解柔性job shop調(diào)度問題[J].控制與決策，2004，19(10):1197-1200.

[8]席衛(wèi)東，喬兵，朱劍英.基于改進遺傳算法的柔性作業(yè)車間調(diào)度[J].哈爾濱工業(yè)大學(xué)學(xué)報，2007,39(7)：1151-1153.

[9]尹作海,邱洪澤,周萬里.基于改進變異算子的遺傳算法求解柔性作業(yè)車間調(diào)度[J].計算機系統(tǒng)應(yīng)用,2009, 18(10):156-159.

[10]陳鋼,高杰,孫林巖.帶瓶頸移動法的混合遺傳算法求解頭型作業(yè)車間調(diào)度[J].系統(tǒng)工程，2007,25(9):91-97.

[11]趙詩奎.求解柔性作業(yè)車間調(diào)度問題的兩級鄰域搜索混合算法[J].機械工程學(xué)報,2015,51(14):175-184.

[12]莫建麟,吳喆.基于混合遺傳禁忌的多目標(biāo)柔性作業(yè)車間調(diào)度[J].重慶師范大學(xué)學(xué)報(自然科學(xué)版),2013,30(2):92-96.

[13]陸漢東,何衛(wèi)平,周旭,等.基于禁忌搜索的柔性作業(yè)車間分批調(diào)度[J].上海交通大學(xué)學(xué)報,2012,46(12):2003-2008.

[14]ZHOU D,JIANG J, LUO C L, et al. Multi-objective flexible job-shop scheduling method study based on the integration algorithm of GA-BP[J]. International Journal of Digital Content Technology and Its Applications, 2013,7(2):109-116.

[15]王小蓉,李蓓智,周亞勤,等.基于混合遺傳算法的柔性作業(yè)車間調(diào)度研究[J].現(xiàn)代制造工程,2015(5):39-42.

[16]余建軍,孫樹棟,郝京輝.免疫算法求解多目標(biāo)柔性作業(yè)車間調(diào)度研究[J].計算機集成制造系統(tǒng),2006,12(10):1643-1650.

[17]馬佳,高立群,石剛,等.求解柔性作業(yè)車間調(diào)度問題的免疫遺傳算法[J].東北大學(xué)學(xué)報(自然科學(xué)版),2008,29 (7):936-939.

[18]張永強,高銳敏.改進人工免疫算法求解柔性作業(yè)車間調(diào)度問題[J].鄭州大學(xué)學(xué)報(理學(xué)版),2016,48(2):53-57.

[19]趙詩奎,方水良,顧新建.柔性車間調(diào)度的新型初始機制遺傳算法[J].浙江大學(xué)學(xué)報(工學(xué)版),2013,47(6):103-111.

[20]DEB K, AGRAWAL S, PRATAP A, et al. A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II[M].Berlin:Springer Berlin Heidelberg,2000:849-858.

[21]張鐵男,韓兵,于渤.生產(chǎn)能力約束條件下的柔性作業(yè)車間調(diào)度優(yōu)化[J].系統(tǒng)工程理論與實踐,2011,31(3):505-511.

[22]馬佳,石剛,高立群,等.求解FJSP的自適應(yīng)免疫遺傳算法[J].系統(tǒng)仿真學(xué)報, 2009,21(12):3609-3613.

[23]劉勝,于海強.基于改進遺傳算法的多目標(biāo)FJSP問題研究[J].控制工程,2016,23(6):816-822.

[24]KACEM I,HAMMADI S,BORNE P. Approach by localization and multi-objective evolutionary optimization for flexible job-shop scheduling problems[J].IEEE Transactions on Systems Man & Cybernetics Part C,2002,32(1):1-13.

[25]ZHANG H P, GEN M. Multistage-based genetic algorithm for flexible job-shop scheduling problem[J]. Journal of Complexity, 2005(11):223-232.

[26]KACEM I, HAMMADI S, BORNE P. Pareto-optimality approach based on uniform design and fuzzy evolutionary algorithms for flexible job-shop scheduling problems (FJSPs)[C]∥ IEEE International Conference on Systems, Man and Cybernetics. [S.l.]：IEEE, 2002:7-8.

[27]XING L N, CHEN Y W, YANG K W. An efficient search method for multi-objective flexible job shop scheduling problems[J]. Journal of Intelligent Manufacturing, 2009,20(3):283-293.

[28]SAKAWA M, KUBOTA R. Fuzzy programming for multi-objective job shop scheduling with fuzzy processing time and fuzzy due date through genetic algorithm[J]. European Journal of Operational Research, 2000,120(2):393-407.

[29]WANG X, GAO L, ZHANG C, et al. A multi-objective genetic algorithm based on immune and entropy principle for flexible job-shop scheduling problem[J]. The International Journal of Advanced Manufacturing Technology, 2010,51(5):757-767.

[30]彭建剛,劉明周,張銘鑫,等.基于改進非支配排序的云模型進化多目標(biāo)柔性作業(yè)車間調(diào)度[J].機械工程學(xué)報,2014,50(12):198-205.