改進免疫遺傳算法求解柔性作業(yè)車間調度問題

曹坤煜，陳永當，宋辛辛，強冰冰

(1.西安工程大學 機電工程學院，陜西 西安 710600； 2.西安市現(xiàn)代智能紡織裝備重點實驗室，陜西 西安 710600； 3.昆明理工大學 機電工程學院，云南 昆明 650500)

0 引 言

調度是企業(yè)智能化生產管理提高效率與效益的重要抓手。柔性作業(yè)車間調度(flexible job-shop scheduling problem，F(xiàn)JSP)，因其能夠根據(jù)產品的制造需求快速響應市場變化，合理配置有限的制造資源，更符合實際生產需求而被廣泛應用。但在運用過程中也會出現(xiàn)復雜性、動態(tài)模糊性、多約束性等特點，屬于典型的NP-Hard問題[1]。因此對其研究具有重要的學術意義和應用價值。

近年來，隨著企業(yè)市場化進程的不斷推進，F(xiàn)JSP問題以成為學術界研究的熱門課題。國內外學者已經相繼提出了多種求解FJSP問題的有效算法。如：王春等[2]針對多目標動態(tài)柔性作業(yè)車間調度問題，通過引入虛擬工序和虛擬工時概念，提出了一種改進的遺傳算法。Liu X等[3]通過使用候選操作機制構建了機器的調度方案，提出了一種基于蟻群優(yōu)化(ACO)的集成過程計劃與調度優(yōu)化算法。李浩等[4]為了使算法跳出局部最優(yōu)快速達到全局最優(yōu)，提高算法的收斂性，提出了一種自適應變參粒子群算法。Li X等[5]針對FJSP問題提出了一種遺傳算法與禁忌搜索算法相結合的混合策略，并通過與其他算法橫向測評驗證了混合算法的有效性。劉洪銘等[6]提出了自適應權重混沌的粒子群優(yōu)化算法，通過引入萊維飛行、變鄰域搜索、混沌，增強了算法的搜索能力。Gao等[7]針對具有模糊處理時間的車間調度問題，通過設計啟發(fā)式規(guī)則來初始化種群，提出了一種改進的人工蜂群(IABC)算法。楊振泰等[8]考慮遺傳算法中染色體編碼的特殊性，提出了融合Powell搜索法的遺傳算法。田旻等[9]為彌補遺傳算法局部搜索能力的不足，提出了考慮傳輸時間的粒子群遺傳混合算法。Qin W等[10]通過引入到期日期偏差的概念，設計了滾動視距驅動策略，提出了一種基于蟻群算法的調度方法。Lou G等[11]針對混合車間調度問題，通過添加保優(yōu)記憶庫，使用分組策略的工序調整結構，在引入交叉、變異運算符的基礎上提出了改進的混合免疫遺傳克隆選擇算法。Zhang R[12]設計了一個評估工作瓶頸水平的模糊推理系統(tǒng)，以總加權拖延率為目標，提出了一種基于新型免疫機制的混合模擬退火算法。

以上文獻基于FJSP問題的研究證明了智能算法的實用性，但由于智能算法屬于概率搜索算法，存在收斂速度快、容易陷入局部最優(yōu)解和種群質量低下等問題。基于此，該文提出了一種改進的免疫遺傳算法。該算法采用多種策略的種群初始化方式，提出了抗體濃度的調節(jié)方式以及根據(jù)抗體濃度自適應調節(jié)的交叉算子、變異算子的構造方法，并利用種群分割的思想提高了種群的多樣性和算法的收斂性。

1 FJSP問題描述

FJSP問題可以描述為：有n個工件需要在m臺機器上進行加工，每個工件有Oij(Oij≥1)個工序，每道工序可供選擇的機器數(shù)Oijk(Oijk≥1)，同一工序在不同機器上的加工時間不同。調度的目標就是在一定的約束下，找到最佳的加工順序。

其數(shù)學模型如下：

(1)工件集：J={J1,J2,…,Jn}，Ji表示第i(i=1,2,…,n)個工件。

(2)機器集：M={M1,M2,…,Mm}，Mj表示工件Ji在機器集合M上所有可用機器的集合(j=1,2,…,m)。

(3)工序集合Oij={Oi1,Oi2,…,Oini}，Oij表示工件Ji的第j(j=1,2,…,ni)道工序。

(4)工序加工的時間矩陣T，tijk∈T。

tijk=eijk-bijk

(1)

其中，bijk、tijk、eijk分別表示工序Oij在機器Mk上的加工開始時間、加工時間和加工完成時間。

(5)約束條件。

①工序約束。

eij≤bi(j+1)

(2)

其中，bi(j+1)表示工件Ji的第j+1道工序的加工開始時間。

②機器約束。

各工序使用機器的總數(shù)為1次。

(3)

其中，Mij表示工序Oij可供選擇的機器總數(shù)，且在時刻t(t>0)，如果?Wijk=1，則對?p或q，不存在工序Opq，使得Wpqk=1，

③時間約束。

所有工件在零時刻都可以被加工。

bij≥0

(4)

所有機器在零時刻都可以加工工件，且各機器之間相互獨立，即某一機器出現(xiàn)故障并不會對剩余機器造成影響。

④工序的加工過程不會被中斷。

(5)

(6)目標函數(shù)。

調度目標是使最大完工時間TM最小。

(6)

其中，Ti表示工件Ji的完工時間。

2 改進免疫遺傳算法設計

2.1 算法流程

算法流程如圖1所示。

賈寶柱(1974—)，男，遼寧阜新人，副教授，博士，研究方向為輪機工程。E-mail:jiabzh@gmail.com

圖1 改進免疫遺傳算法流程

算法的具體實現(xiàn)步驟如下：

(1)分析問題。將目標函數(shù)和約束條件作為抗原，可行解作為抗體。

(2)產生初始抗體群。采用混合策略生成70%初始種群，剩余30%，采用多次迭代隨機生成保留部分抗體的方法組成。

(3)抗體的多樣性評價。以抗體的期望繁殖概率Pv為標準對抗體進行評價。

(4)終止條件判斷。若滿足算法的終止條件則輸出結果，否則繼續(xù)執(zhí)行下步操作。

(5)抗體的促進和抑制。促進親和力高濃度低的抗體，抑制親和力低濃度高的抗體。

(6)抗體的產生。按照精英保留與輪盤賭相結合的策略進行克隆選擇操作，并依據(jù)種群中抗體濃度的高低進行自適應的交叉和變異操作，產生新一代的抗體群。

(7)判斷是否分割。根據(jù)預先設定的閾值，在新一代的抗體群中提取出親和力較弱的抗體并再次進行交叉、變異操作。

2.2 改進免疫遺傳算法求解FJSP過程

(1)個體編碼與解碼。

[1 3 2 1 2 3 2 1 3 1 3 2 3 4 5 1 2 4]

其中，前8位為工序的加工序列，即：O11→O31→O21→O12→O22→O32→O23→O13→O33，后8位為加工機器的序列，即：M1→M3→M2→M3→M4→M5→M1→M2→M4。

解碼時采用文獻[13]給出的前沿貪心方式解碼成活動調度。首先根據(jù)基因串確定各工序的加工機器，然后根據(jù)各機器的可利用時間隨機插入剩余工序。以此確定每臺機器上各工件的加工序列。

(2)抗原識別。

抗原對應問題的目標函數(shù)與約束條件。抗體對應解決問題過程中產生的所有可行解。

(3)種群初始化。

根據(jù)上述編碼原則利用最大工作剩余和最多工序剩余的思想在工序排序及加工機器分配的基礎上采用混合方法產生70%初始種群。剩余30%，采用多次迭代隨機生成的方法，在每次生成的抗體群中只保留部分親和力較高的抗體。并將抗體群中親和力較弱的抗體，在下次迭代過程中進行替代。以此為循環(huán)，直至達到隨機生成的種群規(guī)模。

(4)抗體的多樣性評價。

①抗體與抗體之間的親和力。

借鑒Forrest等提出的R位連續(xù)方法計算[14]，即：

(7)

其中，kv,s表示抗體v與抗體s相同的位數(shù)，L為抗體長度。

②抗體與抗原間親和力。

采用歐幾里得距離作為衡量抗體與抗原親和力的重要指標。針對整數(shù)編碼，抗體v={v1,v2,…,vn}與抗原r={r1,r2,…,rn}之間的歐氏距離為：

(8)

親和力為：

(9)

其中，Av,r反映了抗體v與抗原r之間的差異度，當dv=0，Av,r=1時抗體與抗原匹配度最高。

③抗體濃度。

抗體濃度Cv反映種群中相似抗體所占的比例，即:

(10)

④期望繁殖概率。

在種群中，抗體的期望繁殖概率Pv由抗體與抗原的親和力Av和抗體濃度Cv共同決定，即：

(11)

(5)免疫操作。

①克隆選擇。

按照精英保留與輪盤賭相結合的策略進行克隆選擇操作。這樣在每次更新記憶庫時，先將親和力較高的抗體進行保存，再按照期望繁殖概率大小將種群中優(yōu)秀的抗體存入記憶庫。抗體被選擇的概率即為式(11)計算出的期望繁殖概率。

②自適應交叉、變異。

(12)

(13)

其中，C'為待交叉抗體的最大濃度，Cmax為種群的最大濃度，Cavg為種群的平均濃度，Cmin為種群的最小濃度，C為待變異抗體的濃度，Pc、Pm為交叉、變異概率的初始值。

(6)種群分割。

為了提高種群的多樣性，以抗體的平均親和力為標準，把未滿足要求的抗體分割出來，進行再次交叉、變異操作，待提高抗體的親和力后并入原種群中，進行下次迭代。

(14)

α2(i)=cross & mutation(α1(i))

(15)

α=combine(α(N-i),α2(i))

(16)

其中，α(i)為分割前的種群，α1(i)為分割后的新種群，α2(i)為經過再次交叉、變異后的種群，α為合并后的種群，Ai為抗體i的親和力，Aavg為種群的平均親和力，Pt為種群的分割概率。

(7)克隆記憶。

在經過以上操作后會產生大量的可行解，將效果最好的可行解即最小的目標函數(shù)值，與記憶庫中的抗體進行比較，如果大于記憶庫中抗體的親和力則替換相應的記憶細胞，然后對其進行克隆操作。

克隆操作就是把最接近最優(yōu)解的抗體根據(jù)親和度的不同按照不同的尺寸復制成多個抗體的過程，抗體的克隆規(guī)模qi為：

(17)

其中，Nc為種群總的克隆數(shù)目，int為向下取整，qi為第i個抗體的克隆數(shù)目。

3 仿真實驗與算法比較

為了全面驗證算法性能，選取文獻[15-19]中的基準算例作為測試對象。算法程序是在MATLAB 2018a的基礎上實現(xiàn)，在處理器為Intel(R)Core(TM)i5-5200U CPU、RAM為4 GB、運行環(huán)境為Windows10(64 位)的個人計算機上進行仿真測試。實驗參數(shù)設置如表1所示。

表1 實驗參數(shù)

首先選取4×6FJSP算例，具體信息見表2。其中-表示該工序不能在此臺機器上加工。根據(jù)表2進行仿真實驗20次，得到如圖2、圖3的仿真結果。

表2 4×6FJSP加工時間

續(xù)表2

圖2 4×6算例仿真甘特圖

圖3 4×6算例仿真收斂圖

由表3可知，文中算法的最優(yōu)完工時間為17 s，與文獻[16]相比算法搜索能力較優(yōu)。文中算法的平均收斂代數(shù)為7.8，與文獻[15,17]相比算法的收斂速度快，效率高。在20次的仿真實驗中，文中算法17次得到最優(yōu)解，與文獻[15,17]相比算法的求解穩(wěn)定性較好。

表3 4×6算例不同算法仿真結果對比

為進一步驗證算法的可行性，選取6×10FJSP算例對算法性能進行再次驗證，同樣選取以上參數(shù)并獨立運行20次。其仿真結果如圖4和圖5所示。

圖4 6×10算例仿真甘特圖

圖5 6×10算例仿真收斂圖

由表4可知，文中算法的最優(yōu)完工時間為44 s，與文獻[17-19]相比算法用時最少，算法最優(yōu)解的搜索質量較高。文中算法的平均收斂代數(shù)為19，與文獻[17-19]相比算法收斂速度快，效率高。在獨立運行20次中，文中算法平均進化率為80%，高于文獻[17,19]的進化率，算法的求解穩(wěn)定性較好。

表4 6×10算例不同算法仿真結果對比

4 結束語

針對智能算法在解決柔性作業(yè)車間調度問題中的不足，在對免疫遺傳算法的種群初始化方式、抗體的濃度及期望繁殖概率調節(jié)的基礎上，提出了新的種群初始化方式、抗體濃度的調節(jié)方式及依據(jù)抗體濃度自適應調節(jié)的交叉算子與變異算子的設計方法，并以種群的平均親和力為標準對種群進行分割操作設計，保證了種群多樣性，提高了算法的收斂能力。最后通過與其他算法進行橫向測評，驗證了該算法的有效性。