基于混合遺傳蟻群算法的多目標(biāo)FJSP問題研究*

趙小惠，衛(wèi)艷芳，趙 雯，胡 勝，王凱峰，倪奕棋

(1.西安工程大學(xué)機(jī)電工程學(xué)院，西安 710048；2.西安財(cái)經(jīng)大學(xué)后勤管理處，西安 710100)

0 引言

隨著制造技術(shù)的不斷發(fā)展與完善，傳統(tǒng)車間調(diào)度問題中工序在確定設(shè)備上作業(yè)的生產(chǎn)模式無法滿足目前多品種個(gè)性化的生產(chǎn)需求[1]，而柔性作業(yè)車間調(diào)度問題(flexible job-shop scheduling problem，F(xiàn)JSP)因其具有加工路徑的柔性和機(jī)器設(shè)備柔性，更符合制造業(yè)的需求，從而受到了學(xué)者們的廣泛關(guān)注[2]。實(shí)際生產(chǎn)中調(diào)度往往涉及多個(gè)目標(biāo)的優(yōu)化，各個(gè)目標(biāo)既相互聯(lián)系又相互制約，對某一目標(biāo)的改進(jìn)可能會(huì)致使其他目標(biāo)下降，這使得同時(shí)讓多個(gè)目標(biāo)達(dá)到最優(yōu)化幾乎是不可能的，因此多目標(biāo)柔性作業(yè)車間調(diào)度(MO-FJSP)相對于單目標(biāo)FJSP難度更大，更具實(shí)際研究意義。

近年來，智能優(yōu)化算法由于不受調(diào)度問題規(guī)模的限制成為目前算法研究的主要方向[3]。王玉芳等[4]提出改進(jìn)遺傳算法求解FJSP，從單目標(biāo)和多目標(biāo)兩個(gè)方面驗(yàn)證了算法的有效性。孟冠軍等[5]將禁忌搜索與改進(jìn)人工蜂群算法結(jié)合，有效提升了獲得最優(yōu)解的概率。荊巍巍等[6]提出了自適應(yīng)NSGA-Ⅱ算法，根據(jù)種群的不同狀態(tài)動(dòng)態(tài)改變交叉變異概率，提高了算法的計(jì)算效率和搜索能力。董海等[7]提出了一種多目標(biāo)入侵腫瘤生長優(yōu)化算法求解MO-FJSP問題，最終獲得了處于pareto非支配解集的多種調(diào)度方案。CHIANG等[8]提出一種簡單的進(jìn)化算法，獲得了各基準(zhǔn)算例求解質(zhì)量和多樣性較好的Pareto最優(yōu)解集。ZHANG等[9]提出了一種新的變量鄰域搜索算法與GA相結(jié)合的混合算法，在優(yōu)化過程中采用外部存儲(chǔ)器來保存和更新非支配解，計(jì)算表明該算法能有效解決多目標(biāo)FJSP問題，但獲得的解集的多樣性較少。

上述文獻(xiàn)主要是考慮獲得最優(yōu)解集效率，很少將解集多樣性與求解效率綜合考慮，針對此問題，提出了一種混合遺傳蟻群算法來求解多目標(biāo)FJSP，通過改進(jìn)的NSGA-Ⅱ獲取問題的較優(yōu)解作為蟻群算法的初始信息素分布，之后充分利用蟻群算法的正反饋性使搜索過程不斷收斂并逼近最優(yōu)解，并根據(jù)提出的自適應(yīng)偽隨機(jī)比例規(guī)則和改進(jìn)的信息素更新規(guī)則來優(yōu)化螞蟻的遍歷過程，最后通過鄰域搜索，擴(kuò)大螞蟻的搜索空間，從而提高解集的多樣性。

1 多目標(biāo)柔性作業(yè)車間調(diào)度模型

1.1 問題描述

多目標(biāo)柔性作業(yè)車間調(diào)度問題是指n個(gè)工件J={J1,J2,…,Jn}需在m臺加工性能不同的設(shè)備M={M1,M2,…,Mm}上進(jìn)行加工，每個(gè)工件Ji有ni道工序，并且工件的各道工序加工順序都是事先確定的，需嚴(yán)格按照工序順序進(jìn)行加工。Oij表示工件Ji的第j道加工工序，工序Oij在不同的機(jī)器Mk上的加工時(shí)間Pijk不同。MO-FJSP需要對現(xiàn)有的資源實(shí)現(xiàn)較優(yōu)的實(shí)時(shí)分配，即為工序合理安排加工設(shè)備和為設(shè)備上的工序任務(wù)合理排序。

1.2 模型構(gòu)建

根據(jù)實(shí)際生產(chǎn)的需求，本文選用以下3個(gè)優(yōu)化指標(biāo)，即最小化最大完工時(shí)間、最小化瓶頸機(jī)器負(fù)荷、最小化機(jī)器總負(fù)荷。MO-FJSP問題的數(shù)學(xué)模型如下：

(1)最小化最大完工時(shí)間：

f1=min[max(Ci)]

(1)

(2)最小化最大瓶頸機(jī)器負(fù)荷：

(2)

(3)最小化機(jī)器總負(fù)荷：

(3)

式中，Ci為完工時(shí)間；k為機(jī)器號，k=1,2,…,m；tijk為Oij在機(jī)器Mk上加工所需的時(shí)間；xijk判斷Oij是否在機(jī)器Mk上進(jìn)行加工，若是，xijk=1；否則xijk=0。

1.3 約束條件

一般的，在加工過程中MO-FJSP需滿足以下約束：

(1)在零時(shí)刻任何設(shè)備可用，任何工件可被加工；

Sijk≥0

(4)

(2)同工件加工需按照工藝順序進(jìn)行；

Sij+tijkxijk≤Si(j+1)

(5)

(3)同一時(shí)刻，一個(gè)工序只能被一臺設(shè)備所加工；

(6)

(4)工序一旦開始加工不能被中斷。

Sij+tijkxijk=Eij

(7)

式中，Sijk為工序Oij在機(jī)器Mk上開始加工時(shí)間；Sij和Eij分別為工序Oij開始加工和結(jié)束時(shí)間；Si(j+1)為工序Oi(j+1)開始加工時(shí)間。

2 混合遺傳蟻群算法設(shè)計(jì)

2.1 NSGA-Ⅱ算法設(shè)計(jì)

(1)編碼與解碼。本文采用雙層編碼方式編碼。第1層為基于工序的編碼層，第2層為基于機(jī)器的編碼層，工序?qū)佑脕泶_定各工序的加工順序，其長度等于該批工件的所有工序數(shù)之和，其數(shù)字代表工件號，數(shù)字出現(xiàn)的次數(shù)表示工件的工序。機(jī)器層用來確定工序的加工機(jī)器，其長度與工序編碼的長度一致，其數(shù)字表示從第1個(gè)工件的第1道工序到最后1個(gè)工件的最后1道工序的加工機(jī)器在該工序的可選加工機(jī)器集合中的序號(不同于機(jī)器編號)。雙層編碼如圖1所示。

圖1 雙層編碼示意圖

解碼采用插入式貪婪解碼方式，即找到所有機(jī)器上的空閑時(shí)間段，并判斷工序Oij是否可在該機(jī)器的空閑時(shí)間段內(nèi)進(jìn)行加工，若可以，則將工序Oij放置該機(jī)器的空閑時(shí)間段加工，否則將其放置于機(jī)器加工完最后一道工序之后加工。

(2)交叉操作。本文工序編碼部分與機(jī)器編碼部分分別采用不同的交叉與變異方式。工序部分采用張超勇等[10]提出的IPOX方式，此處不再進(jìn)行復(fù)述。機(jī)器編碼部分采用多點(diǎn)交叉操作，該方式能夠較好的保留父代機(jī)器選擇的特性。其具體操作步驟為：隨機(jī)產(chǎn)生一組0、1組成的基因序列R，其長度等于工序編碼的長度；將父代1(P1)中與R中“1”所在的對應(yīng)位置復(fù)制到子代2(C2)相同的位置，“0”所在的對應(yīng)位置復(fù)制到子代1(C1)相同的位置；父代2(P2)中與R中“1”所在的對應(yīng)位置復(fù)制到C1相同的位置，“0”所在的對應(yīng)位置復(fù)制到C2相同的位置。具體操作如圖2所示。

圖2 基于機(jī)器編碼的多點(diǎn)交叉

(3)交叉操作。變異操作與交叉操作大致相同，均將工序與機(jī)器作為兩個(gè)獨(dú)立的個(gè)體分別對其進(jìn)行變異操作，工序部分采用隨機(jī)交換變異方式，具體操作如圖3所示。機(jī)器部分的變異時(shí)隨機(jī)選擇兩個(gè)基因，并從所選中的基因?qū)?yīng)工序的可選機(jī)器集中隨機(jī)選擇一臺機(jī)器替換原有的機(jī)器基因，具體操作如圖4所示。

圖3 基于工序編碼的隨機(jī)交換變異 圖4 基于機(jī)器編碼的變異

2.2 種群初始化

進(jìn)行選擇、交叉、變異操作之后，將父代與子代基因合并，并對其進(jìn)行非支配排序和擁擠度排序，將非支配等級低且擁擠距離大較優(yōu)的個(gè)體獲取的較優(yōu)解作為蟻群算法的信息素的初始分布。如圖5所示，NSGA-Ⅱ算法初期搜索效率較高，后期效率較低，相反，蟻群算法初期由于缺乏信息素從而搜索效率較低，后期充分利用自身的正反饋特性使搜索過程不斷收斂從而使搜索效率不斷提高。因此選用NSGA-Ⅱ算法所獲得的較優(yōu)解作為蟻群算法的信息素初始分布，充分利用兩個(gè)算法尋求最優(yōu)解的優(yōu)勢，有效避免了在蟻群算法初期缺乏有用的信息素而致使搜索效率較慢的情況。

圖5 兩種算法進(jìn)化率-時(shí)間曲線圖

2.3 自適應(yīng)偽隨機(jī)比例規(guī)則

蟻群系統(tǒng)(ACS)采用狀態(tài)轉(zhuǎn)移規(guī)則來構(gòu)建候選的解，第k只螞蟻從節(jié)點(diǎn)i轉(zhuǎn)移到節(jié)點(diǎn)j的選擇方式為：

(8)

(9)

式中，allowedk為下一步可達(dá)工序節(jié)點(diǎn)的集合；τij(t)為t時(shí)刻路徑(i,j)的信息素濃度；ηij(t)為啟發(fā)函數(shù)；α為信息啟發(fā)因子；β為期望啟發(fā)因子；式(8)和式(9)聯(lián)合稱為偽隨機(jī)比例規(guī)則。參數(shù)q是來決定ACS是采用最優(yōu)選擇還是隨機(jī)選擇的方式構(gòu)建候選解的概率，q越大時(shí)，越側(cè)重于利用先驗(yàn)知識來求解，此時(shí)容易使候選解較為集中，從而致使算法過早的收斂；q越小時(shí)，越側(cè)重于對搜索空間的不斷探索，此時(shí)容易使候選解的分布相對較分散，從而致使收斂過慢。蟻群算法運(yùn)行過程中存在著收斂性和解多樣性的矛盾，為解決這一問題，提出一種自適應(yīng)調(diào)整參數(shù)q的偽隨機(jī)比例規(guī)則，即在算法每次迭代完成之后，根據(jù)擁擠度來自適應(yīng)的調(diào)整參數(shù)q的取值，同時(shí)為避免參數(shù)q的取值過大或過小，嚴(yán)格將其限定在[0,1]之間。

(10)

式中，idmax和idmin分別為擁擠度最大值和最小值。

2.4 鄰域搜索

本文的鄰域搜索按照以下方法進(jìn)行：

(1)將工序調(diào)整到有最小操作時(shí)間的機(jī)器上；

(2)將工序調(diào)整到加工該工序最少加工負(fù)荷的機(jī)器上；

(3)將工序調(diào)整到總加工機(jī)器負(fù)荷最少的機(jī)器上。

根據(jù)以上3種鄰域搜索方法所構(gòu)造的新的調(diào)度結(jié)果與原調(diào)度結(jié)果進(jìn)行比較，選擇較優(yōu)的結(jié)果作為該螞蟻的調(diào)度結(jié)果，并對其進(jìn)行局部更新。

2.5 信息素更新規(guī)則

為提高算法搜索效率以及確保最終得到的結(jié)果是全局最優(yōu)解，本文選擇最優(yōu)螞蟻對其進(jìn)行全局信息素更新，其更新公式為：

τij(t+1)=(1-ρ)τij(t)+ρΔτij(t)

(11)

(12)

式中，ρ為信息素?fù)]發(fā)系數(shù)；Q為信息素強(qiáng)度；Δτij(t)為路徑(i,j)上信息素增量的總和；Lgb為全局最優(yōu)目標(biāo)函數(shù)值。

2.6 混合遺傳蟻群算法流程

采用混合遺傳蟻群算法求解多目標(biāo)FJSP問題，混合算法將遺傳與蟻群算法的特性優(yōu)勢互補(bǔ)，通過改進(jìn)的NSGA-Ⅱ獲取問題較優(yōu)解，以此來確定蟻群算法的初始信息素分布，從而改進(jìn)了蟻群算法。具體的混合遺傳蟻群算法流程如圖6所示。

圖6 混合遺傳蟻群算法流程圖

3 算例分析

為驗(yàn)證本文提出的混合遺傳蟻群算法在求解多目標(biāo)FJSP的有效性，選用Kacem算例(4×5、10×7、15×10)和BRdata算例(MK01、MK05)進(jìn)行驗(yàn)證。設(shè)置NSGA-Ⅱ算法參數(shù)種群規(guī)模200，最大迭代次數(shù)200，交叉概率Pm為0.7，變異概率Pc為0.2；ACO算法參數(shù)信息素因子α=1，啟發(fā)函數(shù)因子β=2，信息素?fù)]發(fā)因子ρ=0.3，信息素常量Q=100。依次對不同規(guī)模大小的算例分別進(jìn)行20次實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如下。

3.1 Kacem算例分析

在Kacem標(biāo)準(zhǔn)算例下，將本文提出的混合遺傳蟻群算法與IGA算法[11]、EDA算法[12]、HTABC[5]的運(yùn)行結(jié)果對比，不同算法在不同規(guī)模算例的運(yùn)行結(jié)果如表1所示。表2為不同算法在不同規(guī)模算例的非支配解個(gè)數(shù)。

表1 不同算法在Kacem不同規(guī)模算例的運(yùn)行結(jié)果對比

表2 不同算法在Kacem不同規(guī)模算例的非支配解個(gè)數(shù)

從表1和表2中看出，在4×5規(guī)模算例上，本文混合遺傳蟻群算法得到的非支配解與HTABC得到的非支配解數(shù)量一致，且比EDA算法求得的非支配解更多，同時(shí)，本文算法得到了新的支配解(f1=12，f2=8，f3=32)；在10×7和15×10規(guī)模的算例中，本文算法的非支配解數(shù)量最多，并且均得到了與其它算法一致的非支配解，與此同時(shí)出現(xiàn)了新的非支配解(10×7規(guī)模：f1=12，f2=11，f3=60；15×10規(guī)模：f1=12，f2=10，f3=91)，因此證明混合遺傳蟻群算法的可行性和有效性。15×10算例是Kacem算例中復(fù)雜程度最高的算例，本文算法在此算例下的其中一個(gè)解集(最大完工時(shí)間為11，最大瓶頸機(jī)器負(fù)荷為11，總機(jī)器負(fù)荷為91)輸出的甘特圖如圖7所示。15×10算例中不同算法各個(gè)調(diào)度目標(biāo)下的迭代過程如圖8所示。

圖7 15×10調(diào)度甘特圖

(a) 完工時(shí)間迭代圖 (b) 瓶頸機(jī)器負(fù)荷迭代圖

(c) 總機(jī)器負(fù)荷迭代圖圖8 15×10算例不同算法的各個(gè)目標(biāo)迭代過程圖

可以看出，隨著迭代次數(shù)的不斷增加，最大完工時(shí)間、最大瓶頸機(jī)器負(fù)荷、最大總機(jī)器負(fù)荷的最優(yōu)值不斷優(yōu)化減小，雖然幾種算法均在150代左右達(dá)到收斂，但本文算法的各目標(biāo)在進(jìn)化代數(shù)為90代左右就趨于收斂，進(jìn)一步證明了本文算法具有更高的求解效率。

3.2 BRdata算例分析

針對BRdata算例中的MK01(10×6)、MK05(15×4)規(guī)模算例，運(yùn)用本文混合遺傳蟻群算法對其進(jìn)行調(diào)度求解，將其調(diào)度結(jié)果與其他算法(MOGA[13]、EA[8]、BEG-NSGA-Ⅱ[14])求得的非劣解進(jìn)行對比分析，測試結(jié)果如表3所示，表4為不同算法在BRdata算例的非支配解個(gè)數(shù)。

表3 BRdata算例測試結(jié)果對比

表4 不同算法在BRdata算例的非支配解個(gè)數(shù)

從表3、表4可見，不同算法在BRdata算例的非支配解數(shù)量及質(zhì)量都不同，本文混合遺傳蟻群算法求解BRdata算例結(jié)果與其它算法對比結(jié)果具體如下：

(1)在MK01算例中，本文算法求解得到的非支配解數(shù)量遠(yuǎn)多于MOGA算法和BEG-NSGA-Ⅱ算法，且比EA算法得到的非支配解數(shù)量多1，本文算法求得的11個(gè)非支配解中，包含了其它3種算法所有非支配解，與此同時(shí)，混合遺傳蟻群算法中得出了其他3個(gè)算法均未得到的新的非支配解，并且這4個(gè)新的非支配解均支配了其他3個(gè)算法的部分解。

(2)在MK05算例中，本文算法的非支配解數(shù)量遠(yuǎn)多于其他3個(gè)算法得到的非支配解數(shù)量，并且均得到了與其它3個(gè)算法一樣的非支配解，且求出了3個(gè)新的非支配解，其中新的非支配解8、解9分別支配了BEG-NSGA-Ⅱ算法的解6、解5，證明了本文算法求解的廣泛性和優(yōu)越性。分別對MOGA算法、EA算法、BEG-NSGA-Ⅱ算法以及本文算法求解MK05算例的非支配解進(jìn)行對比，其結(jié)果如圖9所示。

圖9 不同算法在MK05算例中的非支配解對比三維圖

可以看出，本文算法求解的非支配解均包含了其余3個(gè)算法的非支配解，同時(shí)有新的非支配解出現(xiàn)，且本文算法部分新解也有支配其他算法的部分解情況，因此無論是非支配解的數(shù)量還是質(zhì)量，本文混合遺傳蟻群算法都有較好效果。

故在BRdata兩個(gè)算例的對比分析下，進(jìn)一步驗(yàn)證了混合遺傳蟻群算法求解MO-FJSP的有效性和可行性。

4 結(jié)論

根據(jù)實(shí)際生產(chǎn)車間情況，建立了最大完工時(shí)間、瓶頸機(jī)器負(fù)荷和機(jī)器總負(fù)荷最小的多目標(biāo)FJSP數(shù)學(xué)模型。針對解集多樣性與求解效率的問題，設(shè)計(jì)了一種基于混合遺傳蟻群算法，利用NSGA-Ⅱ獲得的較優(yōu)解作為蟻群算法的初始信息素，從而提高了求解效率。同時(shí)，提出了自適應(yīng)偽隨機(jī)比例規(guī)則和鄰域搜索的方法來擴(kuò)大搜索的范圍，提高了解集的多樣性。通過Kacem算例和BRdata算例進(jìn)行實(shí)驗(yàn)驗(yàn)證，結(jié)果表明混合遺傳蟻群算法進(jìn)行多目標(biāo)求解時(shí)，能夠在較短迭代次數(shù)內(nèi)獲得更多新的非支配解，具備更高的求解效率和更好解集多樣性。