呂媛媛，樊 坤，瞿 華，周 浪

(北京林業(yè)大學(xué) 經(jīng)濟(jì)管理學(xué)院，北京 100083)

1 引 言

制造業(yè)是國(guó)民經(jīng)濟(jì)的基礎(chǔ)與重要支柱，是我國(guó)市場(chǎng)程度比較高的領(lǐng)域，對(duì)經(jīng)濟(jì)發(fā)展有十分重要的作用.制造車(chē)間調(diào)度問(wèn)題關(guān)系到企業(yè)整個(gè)生產(chǎn)系統(tǒng)的正常運(yùn)轉(zhuǎn)，關(guān)系到制造企業(yè)的生產(chǎn)效率與成本，因此，一直以來(lái)都是眾多學(xué)者關(guān)注的熱點(diǎn)問(wèn)題.目前，針對(duì)多品種、小批量和個(gè)性化的市場(chǎng)需求，越來(lái)越多的離散制造企業(yè)采取面向訂單的生產(chǎn)方式，同時(shí)具有可以并行、機(jī)器功能多、多處理機(jī)任務(wù)等生產(chǎn)特征，即車(chē)間生產(chǎn)往往會(huì)出現(xiàn)工件的一個(gè)或多個(gè)工序需要多臺(tái)處理機(jī)同時(shí)進(jìn)行加工的情況，因此無(wú)法用傳統(tǒng)的具有單處理機(jī)任務(wù)約束的作業(yè)車(chē)間調(diào)度方法解決.基于此，有學(xué)者提出混合多處理機(jī)任務(wù)作業(yè)車(chē)間調(diào)度(Hybrid Job-shop Scheduling with Multiprocessor Task，HJSMT)模型[1].該模型中，多個(gè)工件具有多個(gè)不同加工工序，每個(gè)工序由一到多臺(tái)處理機(jī)同時(shí)進(jìn)行加工，顯然它是作業(yè)車(chē)間調(diào)度(Job-shop Scheduling Problem，JSP)與多處理機(jī)任務(wù)調(diào)度(Multiprocessor Task Scheduling，MTS)相結(jié)合的新型混合車(chē)間調(diào)度問(wèn)題.

目前混合車(chē)間調(diào)度領(lǐng)域研究多集中于柔性作業(yè)車(chē)間調(diào)度[2-4](作業(yè)車(chē)間調(diào)度混合并行機(jī)調(diào)度)和柔性流水車(chē)間調(diào)度[5,6](流水車(chē)間調(diào)度混合并行機(jī)調(diào)度)的研究.而HJSMT問(wèn)題是多處理機(jī)任務(wù)調(diào)度與作業(yè)車(chē)間調(diào)度混合的調(diào)度問(wèn)題，對(duì)于該問(wèn)題研究相對(duì)較少.Brucker&Kramer[1]證明即使只有兩臺(tái)處理機(jī)的HJSMT問(wèn)題已經(jīng)是NP-hard難題.Brucker & Neyer[7]針對(duì)具有柔性特性的最小化總完工時(shí)間的 HJSMT模型提出一種禁忌搜索算法求解該模型，由于缺乏相關(guān)研究，在仿真實(shí)驗(yàn)部分無(wú)對(duì)比算法，只列出了提出的禁忌搜索算法的實(shí)驗(yàn)結(jié)果.Gr?flin等[8]研究具有工件插入的多處理機(jī)任務(wù)作業(yè)車(chē)間調(diào)度的出入策略，目標(biāo)是對(duì)一個(gè)即將插入的工件進(jìn)行排班并使最大完工時(shí)間最小化，但沒(méi)有實(shí)現(xiàn)對(duì)于HJSMT的調(diào)度方案設(shè)計(jì).王蒙等[9]研究網(wǎng)絡(luò)并行計(jì)算，對(duì)具有多步驟的多處理機(jī)任務(wù)調(diào)度問(wèn)題，提出多處理機(jī)任務(wù)作業(yè)車(chē)間調(diào)度問(wèn)題模型，結(jié)合PSO算法與模擬退火算法設(shè)計(jì)混合粒子群優(yōu)化(Hybrid Particle Swarm Optimization，HPSO)算法求解.文獻(xiàn)[10-12]也針對(duì)HJSMT最小化最大完工時(shí)間問(wèn)題作出研究.然而，專(zhuān)門(mén)針對(duì)HJSMT問(wèn)題的研究成果仍非常少，且未見(jiàn)有文獻(xiàn)關(guān)注HJSMT問(wèn)題的多目標(biāo)優(yōu)化研究.

在企業(yè)實(shí)際生產(chǎn)中，工件最大完工時(shí)間、總拖期時(shí)間、機(jī)器總能耗、生產(chǎn)或庫(kù)存成本等指標(biāo)都是車(chē)間中經(jīng)?？紤]的因素，調(diào)度問(wèn)題的各個(gè)優(yōu)化目標(biāo)之間可能存在不一致甚至沖突的情況，單一指標(biāo)很難滿(mǎn)足車(chē)間生產(chǎn)要求.處理多目標(biāo)優(yōu)化問(wèn)題通常采用兩種方法，一種是簡(jiǎn)化為單目標(biāo)優(yōu)化問(wèn)題，然后再借助工具來(lái)求解；另一種方法是Pareto最優(yōu)解方法，也是目前比較常用的多目標(biāo)優(yōu)化方法[13].對(duì)于多目標(biāo)問(wèn)題，國(guó)內(nèi)外學(xué)者提出多種經(jīng)典求解算法，例如Deb等[14]提出的非支配排序遺傳算法NSGA-II，Coello等[15]提出的MOPSO，Zitzler等[16]提出的SPEA2等.許多學(xué)者用改進(jìn)的經(jīng)典算法解決車(chē)間調(diào)度問(wèn)題：Aghajani & Fouladi[17]提出一種考慮機(jī)器可靠性指標(biāo)這一重要因素的柔性作業(yè)車(chē)間調(diào)度問(wèn)題的雙目標(biāo)數(shù)學(xué)模型，設(shè)計(jì)了一種改進(jìn)非支配排序遺傳算法來(lái)尋找該問(wèn)題的帕累托最優(yōu)解.雷德明等[18]以最小化總拖后時(shí)間和最大完成時(shí)間為優(yōu)化目標(biāo)建立多目標(biāo)作業(yè)車(chē)間調(diào)度模型，將檔案維護(hù)和全局最好位置選取結(jié)合在一起，設(shè)計(jì)了Pareto檔案粒子群算法(PAPSO)并通過(guò)實(shí)驗(yàn)對(duì)比驗(yàn)證其有效性.鞠錄巖等[19]設(shè)計(jì)了相應(yīng)的矩陣編碼、交叉算子、改進(jìn)的非劣前沿分級(jí)方法，提出基于Pareto等級(jí)的自適應(yīng)變異算子以及精英保留策略，形成改進(jìn)遺傳算法.綜上，雖然已有研究通過(guò)改進(jìn)了多目標(biāo)求解算法來(lái)解決常見(jiàn)的車(chē)間調(diào)度問(wèn)題，但是這些算法都不能直接求解HJSMT多目標(biāo)優(yōu)化問(wèn)題.

由此可見(jiàn)，已有的HJSMT問(wèn)題研究不僅較少，而且且目標(biāo)函數(shù)也主要是單目標(biāo)最小化最大完工時(shí)間，即單目標(biāo)優(yōu)化.而實(shí)際生產(chǎn)中通常需要實(shí)現(xiàn)多個(gè)優(yōu)化目標(biāo)，且不同情況下，決策者可能對(duì)于各個(gè)目標(biāo)的期望值會(huì)有所不同，因此，利用結(jié)合Pareto最優(yōu)解理論的算法進(jìn)行求解，能夠獲取多種調(diào)度方案供決策者選擇.本文研究多目標(biāo)HJSMT問(wèn)題，目標(biāo)函數(shù)除了最常用的最小化總完工時(shí)間以外，加入最小化總拖延時(shí)間.拖延時(shí)間是指完工時(shí)間超過(guò)規(guī)定交貨期的時(shí)間.該優(yōu)化目標(biāo)的增加是因?yàn)槠髽I(yè)不僅需要按時(shí)交貨，提高企業(yè)信用，而且能夠減少庫(kù)存積壓，降低成本.本文首先構(gòu)建HJSMT問(wèn)題多目標(biāo)優(yōu)化模型，然后設(shè)計(jì)改進(jìn)多目標(biāo)粒子群算法(Improved Multi-Objective Particle Swarm Optimization，IMOPSO)進(jìn)行求解并驗(yàn)證其有效性.

2 多目標(biāo)HJSMT調(diào)度優(yōu)化模型

2.1 多目標(biāo)HJSMT問(wèn)題描述

HJSMT問(wèn)題具有JSP的多工序特點(diǎn)和MTS的多臺(tái)處理機(jī)同時(shí)加工的特點(diǎn)，描述如下：n個(gè)工件在m臺(tái)機(jī)器上加工，每個(gè)工件的工序間具有一定的加工次序(工藝路線(xiàn)約束)，每道工序需要由一到多臺(tái)指定的處理機(jī)進(jìn)行加工且其相應(yīng)的加工時(shí)間固定(資源有限約束).需要確定各工序的加工順序及加工開(kāi)始時(shí)間，使各個(gè)工序能夠在對(duì)應(yīng)的處理機(jī)上加工，并要求在滿(mǎn)足約束的條件下進(jìn)行，同時(shí)優(yōu)化一些性能指標(biāo).HJSMT問(wèn)題需要滿(mǎn)足以下幾個(gè)條件：

1)工件的各工序之間具有一定的加工次序；

2)每道工序在一到多臺(tái)指定的處理機(jī)上同時(shí)加工且具有固定加工時(shí)間；

3)同一時(shí)刻一臺(tái)處理機(jī)只能加工一道工序；

4)每臺(tái)處理機(jī)互不相同，且不能相互替代；

5)不同工件的工序之間不存在先后約束；

6)工序一旦開(kāi)始加工，中途不能停止直到加工結(jié)束；

7)不存在突發(fā)情況，如處理機(jī)損壞、原料缺失、工件插入等.

除了要滿(mǎn)足以上條件外，HJSMT問(wèn)題還包括不同的優(yōu)化目標(biāo).以往研究都是以最小化總完工時(shí)間為目標(biāo)，而在定制化趨勢(shì)下，以訂單生產(chǎn)的模式中，越來(lái)越多的企業(yè)傾向于面向訂單的生產(chǎn)方式，在這種情況下，若是工件交貨期延誤將會(huì)損害訂貨方的經(jīng)濟(jì)利益，也不利于生產(chǎn)企業(yè)樹(shù)立良好的企業(yè)信譽(yù).因此，為了滿(mǎn)足按時(shí)交貨的需求，在采用最小化最大完工時(shí)間這一最常用優(yōu)化目標(biāo)外，還加入最小化總的交貨拖延時(shí)間.后續(xù)在企業(yè)實(shí)際運(yùn)作中，可以依據(jù)訂單重要性建立拖延懲罰函數(shù)，用總拖延懲罰替代這一目標(biāo).

2.2 多目標(biāo)HJSMT數(shù)學(xué)模型

2.2.1 符號(hào)定義

參照文獻(xiàn)[10]，符號(hào)定義如下：

S：所有工件的集合，S={Ji|i=1,2,…,n}；

I：所有工序的集合，I={Oij|i=1,2,…,n;j=1,2,…,li}，li：完成任務(wù)Ji的所需的步驟總數(shù)；

Ci：工件Ji的完工時(shí)間；

Di：工件Ji的交貨期；

σ：“開(kāi)始虛工序”，此工序在所有工序開(kāi)始之前開(kāi)始，將其加工時(shí)間設(shè)為0；

μ：“結(jié)束虛工序”，此工序在所有工序結(jié)束之后開(kāi)始，將其加工時(shí)間設(shè)為0；

xq：工序q的開(kāi)始加工時(shí)間；

mq：工序q所需處理機(jī)集合；

tq：工序q加工用時(shí).

對(duì)于S中的任意一個(gè)任務(wù)Ji∈S，都有Ji={Oij|j=1,2,…,li}.同樣有Ji?I.為了建立數(shù)學(xué)模型，定義代表整個(gè)過(guò)程的開(kāi)始時(shí)刻和結(jié)束時(shí)刻的“開(kāi)始虛工序”σ和“結(jié)束虛工序”μ，有mσ=mμ=?,tσ=tμ=0.由結(jié)束虛工序含義可知：xμ是最大完工時(shí)間.A={{a,b}:a,b∈J, anda

2.2.2 模型建立

針對(duì)雙目標(biāo)HJSMT問(wèn)題建立數(shù)學(xué)模型如下，

目標(biāo)函數(shù)：

(1)

約束條件：

xb-xa≥ta，for all {a，b} ∈A

(2)

xb-xa≥ta∪xa-xb≥tb，for all {a，b} ∈ B

(3)

xa-xσ≥0∪xμ-xa≥ta，for alla∈ I

(4)

其中，式(1)中f1代表最小化最大完工時(shí)間，f2代表最小化總拖延時(shí)間.式(2)是工藝路線(xiàn)約束;式(3)是資源有限約束;式(4)是針對(duì)“開(kāi)始虛工序”和“結(jié)束虛工序”的約束.

3 粒子群算法介紹

3.1 經(jīng)典粒子群算法

粒子群算法(Particle Swarm Optimization，PSO)是一種模擬自然界中鳥(niǎo)類(lèi)覓食行為的進(jìn)化算法[20].算法生成一組初始解，然后種群中的粒子將按照一定的規(guī)則，在每次迭代中更改速度位置搜索最優(yōu)解.PSO算法通過(guò)公式(5)、公式(6)進(jìn)行粒子位置與速度的更新.

(5)

(6)

3.2 多目標(biāo)粒子群算法

粒子群算法具有精度高、收斂速度快等優(yōu)點(diǎn)，也有很多學(xué)者改進(jìn)粒子群算法形成多目標(biāo)粒子群算法(MOPSO).文獻(xiàn)[21]中總結(jié)了在MOPSO基礎(chǔ)上形成的6類(lèi)常見(jiàn)MOPSO，其中基于Pareto方法的MOPSO結(jié)合了目前多目標(biāo)求解領(lǐng)域最常見(jiàn)的Pareto理論，為后續(xù)研究提供了重要參考.這種方法通常建立一個(gè)外部種群用來(lái)存儲(chǔ)每一次迭代過(guò)程中尋找到的非支配解，并在外部種群中按照一定規(guī)則選擇全局最優(yōu)粒子gbest.在迭代過(guò)程中，外部種群不斷更新，最后輸出外部種群中的粒子作為最優(yōu)解集.MOPSO算法迭代更新類(lèi)似單目標(biāo)粒子群算法[22].一般流程如圖1所示.

4 改進(jìn)多目標(biāo)粒子群求解算法(IMOPSO)

4.1 編碼解碼機(jī)制

圖1 MOPSO一般流程圖Fig.1 MOPSO general flow chart

4.2 粒子更新方式

原始的粒子群算法在粒子迭代更新時(shí)采用公式更新法，這里受遺傳算法的啟發(fā)，采用交叉和變異操作來(lái)實(shí)現(xiàn)粒子每一代的更新.

4.2.1 改進(jìn)優(yōu)先操作交叉(IPOX)策略

遺傳算法染色體交叉操作具有單點(diǎn)交叉、多點(diǎn)交叉、均勻交叉、算術(shù)交叉等多種方式.本文選用改進(jìn)優(yōu)先操作交叉(IPOX)[23].A1、A2代表兩條父代染色體.

步驟1.將任務(wù)集合S={Ji|i=1,2,…,n}隨機(jī)分成S1和S2兩個(gè)子集合；

步驟2.A1中屬于S1的元素和A2屬于S2的元素不改變相對(duì)位置放入B1；

步驟3.A1中屬于S2的元素和A2屬于S1的元素不改變相對(duì)位置放入B2；

步驟4.比較子代粒子B1和B2的適應(yīng)值，選擇Pareto占優(yōu)的粒子，若互不支配則隨機(jī)選擇.

圖2 IPOX示例Fig.2 Example of IPOX

圖2顯示了交叉操作的示例，當(dāng)S1={J2，J3}，S2={J1}時(shí)，新粒子B1保留了A1中元素2、3和A2中的元素 1，B2保留了A1中元素1和A2中元素2、3.

4.2.2 多輪變異(MM)操作

本文對(duì)粒子的工序采用互換變異操作.變異操作可以提高粒子跳出局部最優(yōu)的能力，從而提高粒子的全局搜索能力.對(duì)于當(dāng)前交叉操作粒子，隨機(jī)產(chǎn)生兩個(gè)不同的整數(shù)a和b，然后將a、b位置的元素進(jìn)行交換.例，有一枚粒子p=(1，3，1，3，2，1，2，2，3)，在[1,9]范圍內(nèi)隨機(jī)生成兩個(gè)整數(shù)3和7,把位置3與位置7的元素互相交換之后得到新粒子(1，3，2，3，2，1，1，2，3).通常在遺傳算法中變異操作會(huì)選擇一個(gè)較小的變異概率，低于這個(gè)概率則粒子進(jìn)行變異操作.在IMOPSO的粒子更新中，每代粒子不再是根據(jù)變異概率選擇是否進(jìn)行變異，而是進(jìn)行20次變異操作，在此稱(chēng)為多輪變異(Multiple Mutations，MM).若每次變異操作后的粒子Pareto占優(yōu)則保留變異操作后的粒子，若被原始粒子支配則不更換，若二者互不支配則隨機(jī)選擇.

4.3 Pareto外部種群及其尋優(yōu)機(jī)制

4.3.1 Pareto外部種群

外部種群的更新和維護(hù)是多目標(biāo)粒子群算法中用來(lái)保存運(yùn)算過(guò)程中優(yōu)良粒子的的重要部分.通常外部種群用來(lái)保存Pareto解，全局最優(yōu)解從外部種群中獲取.

Pareto解又稱(chēng)非支配解或不受支配解：當(dāng)有多個(gè)目標(biāo)時(shí)，目標(biāo)之間可能會(huì)出現(xiàn)沖突和無(wú)法比較的現(xiàn)象.一個(gè)解決方案在一個(gè)目標(biāo)上是最好的，但在其他目標(biāo)上可能更差.在改進(jìn)任何一個(gè)目標(biāo)函數(shù)時(shí)，都需要至少一個(gè)其他目標(biāo)函數(shù)被削弱，則這個(gè)解叫做非支配解或帕累托最優(yōu)解，這樣一組非支配解叫做帕累托最優(yōu)集.

帕累托支配關(guān)系一般可以描述為：對(duì)于最小化多目標(biāo)問(wèn)題，對(duì)于n個(gè)目標(biāo)分量fi(x),i=1，…，n，任意給定兩個(gè)決策變量Xa，Xb，如果有以下兩個(gè)條件成立，則稱(chēng)Xa支配Xb.

對(duì)于?i∈1,2,…,n，使得fi(Xa)≤fi(Xb)成立.

?i∈1,2,…,n，使得fi(Xa)

4.3.2 外部種群尋優(yōu)機(jī)制(EPOM)

在求解雙目標(biāo)問(wèn)題時(shí)，最小化問(wèn)題的Pareto邊界在坐標(biāo)系的左下方.對(duì)于優(yōu)秀個(gè)體的選取，本文借鑒文獻(xiàn)[24]中的Pareto前沿搜尋方式，設(shè)計(jì)外部種群尋優(yōu)機(jī)制(External Population Optimization Mechanism，EPOM).設(shè)有popsize個(gè)迭代粒子，每次迭代對(duì)每個(gè)粒子進(jìn)行如下步驟：

步驟1.根據(jù)適應(yīng)值f1計(jì)算當(dāng)前粒子與其他粒子之間的距離，找到鄰近的L個(gè)粒子作為它的鄰域粒子；

步驟2.根據(jù)適應(yīng)值f2計(jì)算當(dāng)前粒子和L個(gè)鄰域粒子中f2適應(yīng)值最小的，記錄在當(dāng)前代粒子最優(yōu)解集Temp中.

經(jīng)過(guò)對(duì)每個(gè)粒子進(jìn)行如上步驟后，Temp解集中存放了popsize個(gè)粒子(存在重復(fù))，這些粒子靠近Pareto前沿邊界處，經(jīng)過(guò)不斷迭代最終解不斷靠近并落在Pareto前沿上.

將此步驟應(yīng)用于多目標(biāo)粒子群算法中，設(shè)內(nèi)部種群粒子集合為P，外部種群中粒子集合為A.在粒子每次更新后，在內(nèi)部種群中用EPOM選出當(dāng)前代優(yōu)秀個(gè)體集合，并將其放入外部種群A中.對(duì)外部種群進(jìn)行維護(hù)，在外部種群A中用EPOM再次選擇優(yōu)秀個(gè)體并且刪除重復(fù)個(gè)體；如果外部種群數(shù)量超出原定數(shù)量M，參考NSGA-II[14]算法中根據(jù)擁擠距離刪減種群的方式，按照A中個(gè)體擁擠距離降序排序，保留擁擠距離較大的個(gè)體，刪除超出原定數(shù)量的個(gè)體.這樣能夠保留每代運(yùn)行產(chǎn)生的優(yōu)良粒子，并且能夠控制外部種群的數(shù)量，以免迭代次數(shù)增加外部種群粒子不斷增多.同時(shí)，由于根據(jù)個(gè)體擁擠距離刪減，能夠保留較分散個(gè)體粒子.由此，外部種群中保留了當(dāng)前較優(yōu)的粒子集合，在每次更新時(shí)，全局最優(yōu)粒子在外部種群中隨機(jī)選取.

4.4 IMOPSO算法步驟

改進(jìn)的鄰域多目標(biāo)粒子群算法主要步驟如下：

步驟1.參數(shù)設(shè)定，包括內(nèi)部種群大小popsize，最大迭代次數(shù)N，外部種群存放個(gè)數(shù)Na；

步驟2.采用基于工序的編碼方式初始化種群P，并初始化外部種群A；

步驟3.更新粒子.在外部種群中隨機(jī)選取一個(gè)粒子作為全局最優(yōu)粒子；通過(guò)IPOX交叉和多輪變異更新得到新一代粒子，并計(jì)算適應(yīng)值；

步驟4.更新個(gè)體最優(yōu)粒子.若當(dāng)前粒子Pareto占優(yōu)則更換位當(dāng)前粒子，若當(dāng)前粒子被歷史最優(yōu)粒子支配則不更換，若二者互不支配則隨機(jī)選擇；

步驟5.在新一代粒子中采用外部種群尋優(yōu)機(jī)制(EPOM)尋找占優(yōu)的粒子，加入外部種群A；

步驟6.對(duì)外部種群A進(jìn)行維護(hù)，刪除重復(fù)粒子，并在A(yíng)中用EPOM留取粒子；若A中粒子個(gè)數(shù)超過(guò)Na，則根據(jù)擁擠距離對(duì)A進(jìn)行刪減；

步驟7.是否滿(mǎn)足終止條件，若滿(mǎn)足，則輸出外部種群A；否則返回步驟3.

5 算例仿真

本文的仿真實(shí)驗(yàn)環(huán)境為:Windows10操作系統(tǒng)，CPU為i7-8550U，處理器主頻為1.80GHz和內(nèi)存8G，采用Java語(yǔ)言實(shí)現(xiàn)算法編程.

在以往車(chē)間調(diào)度研究中，作業(yè)車(chē)間調(diào)度的標(biāo)準(zhǔn)算例沒(méi)有給出交貨期的數(shù)據(jù)，但有學(xué)者[25-27]設(shè)置作業(yè)車(chē)間調(diào)度的標(biāo)準(zhǔn)問(wèn)題的貨期.對(duì)于10個(gè)工件的問(wèn)題，第2、3個(gè)工件交貨期設(shè)置為1.5倍加工時(shí)間總和，第10個(gè)工件交貨期設(shè)置為與加工時(shí)間總和相同，剩余工件交貨期設(shè)置成的2倍的加工時(shí)間總和.HJSMT目前沒(méi)有標(biāo)準(zhǔn)算例，在本文中，將采用文獻(xiàn)[9]中的HJSMT算例生成方式.形成工件數(shù)量10，工序數(shù)量5的算例(10-Job問(wèn)題)，參考上述內(nèi)容設(shè)置交貨期.對(duì)于5個(gè)工件的問(wèn)題，形成工序數(shù)量5的算例(5-Job問(wèn)題)，對(duì)于交貨期，第2個(gè)工件設(shè)置為1.5倍的加工時(shí)總和，第5個(gè)工件設(shè)置為與加工時(shí)間總和相同，其他工件交貨期設(shè)置成2倍的加工時(shí)間的總和.

對(duì)于單目標(biāo)問(wèn)題的車(chē)間調(diào)度求解算法的性能對(duì)比，由于最終解只有一個(gè)，往往對(duì)比不同算法的求解速度和最優(yōu)解質(zhì)量.在多目標(biāo)問(wèn)題上，由于解通常是一個(gè)最優(yōu)解集，所以不能用以上方法對(duì)比算法優(yōu)劣程度.本文采用指標(biāo)C[27]比較算法性能.X,Y為2種算法產(chǎn)生的非劣解集，C(X,Y)代表Y中至少被集合X中的一個(gè)解支配的粒子數(shù)與Y中粒子總數(shù)之比，即：

(7)

C(X，Y)=1說(shuō)明對(duì)于集合Y中的任何一個(gè)粒子，集合X總存在比它優(yōu)的粒子；C(X，Y)=C(Y，X)=0，則X、Y互不支配.

5.1 IMOPSO不同鄰域粒子個(gè)數(shù)選取實(shí)驗(yàn)

本文通過(guò)實(shí)驗(yàn)選擇較優(yōu)的參數(shù)值.首先，對(duì)于本文提出的鄰域MOPSO算法，設(shè)置內(nèi)部種群數(shù)100，外部種群數(shù)Na=20，迭代次數(shù)200，對(duì)左右鄰域L=1，L=2，L=3，分別隨機(jī)運(yùn)行20次記錄每次求解所得外部種群粒子，將20次運(yùn)行結(jié)果中所有外部種群粒子合并，并剔除重復(fù)解與被支配解，得到最終非支配解集，對(duì)比選擇不同鄰域數(shù)的算法表現(xiàn)優(yōu)劣性.IMOPSO1、IMOPSO2、IMOPSO3分別代表L=1，L=2，L=3時(shí)的IMOPSO算法.以表2中第4條記錄為例，當(dāng)L設(shè)置為2時(shí)，有一組可行解的適應(yīng)值f1=595，f2=483,這組可行解的 數(shù)量為9.由表1所示，當(dāng)處理5-Job問(wèn)題時(shí)，IMOPSO1、

表1 IMOPSO不同鄰域粒子個(gè)數(shù)選取的適應(yīng)值對(duì)比結(jié)果(5-Job問(wèn)題)
Table 1 Comparison results of adaptive values selected by Different MOPSO Neighborhood particle Numbers(5-Job problem)

鄰域粒子個(gè)數(shù)設(shè)置適應(yīng)值f 1f 2不同調(diào)度方案?jìng)€(gè)數(shù)IMOPSO1584251IMOPSO25842513IMOPSO35842515

IMOPSO2、IMOPSO3獲得相同的適應(yīng)值(f1，f2)組合，不同調(diào)度方案?jìng)€(gè)數(shù)逐漸增加.由表2與表3可見(jiàn)，當(dāng)處理10-Job問(wèn)題

表2 IMOPSO不同鄰域粒子個(gè)數(shù)選取的適應(yīng)值對(duì)比結(jié)果(10-Job問(wèn)題)
Table 2 Comparison results of fitness values selected by Different IMOPSO Neighborhood particle Numbers(10-Job problem)

鄰域粒子個(gè)數(shù)設(shè)置適應(yīng)值f 1f 2不同調(diào)度方案?jìng)€(gè)數(shù)IMOPSO161453816005831IMOPSO2615405159548396585081IMOPSO360059416065271

表3 IMOPSO不同鄰域粒子個(gè)數(shù)選取C值對(duì)比結(jié)果(10-Job問(wèn)題)
Table 3 Comparison results of C values selected by different number of IMOPSO neighborhood particles(10-Job problem)

C(IM1,IM2)C(IM2, IM1)C(IM2,IM3)C(IM3,IM2)C(IM1,IM3)C(IM3,IM1)01100.30.5

注：IM1：IMOPSO1，IM2：IMOPSO2，IM3：IMOPSO3

時(shí)，IMOPSO1、IMOPSO2、IMOPSO3獲得的適應(yīng)值組數(shù)分別為2、2、3，在數(shù)量上相近，其中IMOPSO2在獲得適應(yīng)值組合(595,483)時(shí)具有9個(gè)不同調(diào)度方案.但是在占優(yōu)性對(duì)比上，C(IM1, IM2)小于C(IM2, IM1)，算法性能在L=2時(shí)優(yōu)于L=1時(shí)；C(IM3, IM2)小于C(IM2, IM3)，算法性能在L=2時(shí)優(yōu)于L=1時(shí)，當(dāng)L=2時(shí)算法結(jié)果占優(yōu).在圖3中可以看出IMOPSO2獲得的適應(yīng)值組合的點(diǎn)更靠近坐標(biāo)系左下方，也可以看出當(dāng)L=2時(shí)算法具有較好性能.

5.2 算法性能對(duì)比

NSGA-II是目前處理多目標(biāo)問(wèn)題常見(jiàn)經(jīng)典優(yōu)化算法，已有很多學(xué)者用其求解車(chē)間調(diào)度問(wèn)題并取得較好結(jié)果，因此本 文將以此作為對(duì)比.本文將改進(jìn)MOPSO算法和NSGA-II算法分別應(yīng)用于5-Job與10-Job算例，記錄每次求解所得外部種群中的非支配解.同5.1每個(gè)算法隨機(jī)運(yùn)行20次，將20次

圖3 IMOPSO不同鄰域粒子數(shù)量適應(yīng)值散點(diǎn)圖(10-Job問(wèn)題)Fig.3 Scatter diagram of the adaptive values of different IMOPSO neighborhood particle numbers(10-Job problem)

記錄最終非支配解集，比較各算法最終非支配解集優(yōu)劣情況.對(duì)于NSGA-II，設(shè)置種群數(shù)100，迭代次數(shù)200，交叉概率0.9.遺傳算法往往設(shè)置一個(gè)較低的變異概率，本文中展示Pm分別為0.2和0.4的結(jié)果.IMOPSO2代表設(shè)置L=2時(shí)的IMOPSO算法，NSGA-II1、NSGA-II2分別代表Pm=0.2、Pm=0.4時(shí)的NSGA-II算法.

表4 IMOPSO與NSGA-II適應(yīng)值對(duì)比結(jié)果(5-Job問(wèn)題)
Table 4 Comparison results of IMOPSO and NSGA-II fitness(5-Job problem)

鄰域粒子個(gè)數(shù)設(shè)置適應(yīng)值f 1f 2不同調(diào)度方案?jìng)€(gè)數(shù)IMOPSO258425158433120+58823820+NSGA-II159721320+61617420+6352520+58433120+58823820+NSGA-II259721320+61617420+6352520+

如表4、表5顯示，在求解5-Job算例時(shí)，NSGA-II1與NSGA-II2獲得了5組相同的適應(yīng)值組合，并且都具有很多個(gè)不同的調(diào)度方案，IMOPSO2得到的適應(yīng)值組合種類(lèi)較少.但是 從C指標(biāo)來(lái)看,C(N1, IM2)小于C(IM2, N1)，C(N2, IM2)小于C(IM2, N2)，IMOPSO算法對(duì)于Pm=0.2和Pm=0.4 時(shí)的NSGA-II算法都有優(yōu)勢(shì).如表6顯示，在求解10-Job算例時(shí)，Pm=0.2、Pm=0.4時(shí)的NSGA-II算法獲得了較多數(shù)量的適應(yīng)值組合，IMOPSO2僅獲得2組適應(yīng)值，且NSGA-II算法的不同調(diào)度方案?jìng)€(gè)數(shù)要比IMOPSO2多.但是由表7可見(jiàn)，C(N1, N2)小于C(N2, N1)，說(shuō)明Pm=0.4時(shí)的NSGA-II算法較優(yōu).C(N1, IM2)小于C(IM2, N1)，C(N2, IM2)小于C(IM2, N2)，依然是IMOPSO算法效果較好.且圖4顯示， IMOPSO2獲得的適應(yīng)值組合相對(duì)于NSGA-II1和NSGA-II2更靠近坐標(biāo)系左下方.因此，雖然本文提出的IMOPSO算法得到的適應(yīng)值組合種類(lèi)相對(duì)較少，但是在占優(yōu)性上取得較好結(jié)果.

表5 IMOPSO與NSGA-II的C值對(duì)比結(jié)果(5-Job問(wèn)題)
Table 5 Comparison between the C values of IMOPSO and NSGA-II(5-Job problem)

C(IM2,N1)C(N1,IM2)C(IM2,N2)C(N2,IM2)C(N1,N2)C(N2,N1)101000

注：IM2：IMOPSO2，N1：NSGA-II1，N2：NSGA-II2

表6 IMOPSO與NSGA-II適應(yīng)值對(duì)比結(jié)果(10-Job問(wèn)題)
Table 6 Comparison results of IMOPSO and NSGA-II fitness(10-Job problem)

鄰域粒子個(gè)數(shù)設(shè)置適應(yīng)值f 1f 2不同調(diào)度方案?jìng)€(gè)數(shù)IMOPSO26154051595483959762820+60053820+NSGA-II1612522262951526465042761481158749720+NSGA-II268845727114382

表7 IMOPSO與NSGA-II的C值對(duì)比結(jié)果(10-Job問(wèn)題)
Table 7 Comparison between the C values of IMOPSO and NSGA-II(10-Job problem)

C(IM2,N1)C(N1,IM2)C(IM2,N2)C(N2,IM2)C(N1,N2)C(N2,N1)100.67001

注：IM2：IMOPSO2，N1：NSGA-II1，N2：NSGA-II2

6 結(jié) 論

本文在單目標(biāo)混合多處理任務(wù)作業(yè)車(chē)間調(diào)度(Hybrid Job-shop Scheduling with Multiprocessor Task，HJSMT)基礎(chǔ)上，以制造工期、總拖延懲罰最小化為目標(biāo)函數(shù)，構(gòu)建了雙目標(biāo)混合多處理任務(wù)作業(yè)車(chē)間調(diào)度模型.以多目標(biāo)粒子群算法為基礎(chǔ)，結(jié)合遺傳算法，以IPOX與多輪變異策略更新新一代種群粒子，用搜索動(dòng)態(tài)鄰域的方式設(shè)計(jì)外部種群尋優(yōu)機(jī)制 (EPOM)尋找每一代占優(yōu)粒子，并結(jié)合NSGA-II的擁擠距離計(jì)算縮減外部種群，形成了IMOPSO算法.在仿真實(shí)驗(yàn)中，以5-Job問(wèn)題和10-Job問(wèn)題算例測(cè)試其性能.首先，鄰域粒子數(shù)量L分別設(shè)置1、2、3，對(duì)比尋找較優(yōu)的鄰域數(shù)量，L=2時(shí)算法獲得較好性能.進(jìn)而以L(fǎng)=2時(shí)的IMOPSO算法與NSGA-II算法進(jìn)行比較，結(jié)果表明提出的IMOPSO算法能有效地解決HJSMT雙目標(biāo)優(yōu)化問(wèn)題.下一步將考慮加入新的優(yōu)化目標(biāo)，進(jìn)一步研究多目標(biāo)(3個(gè)以上目標(biāo))混合多處理任務(wù)作業(yè)車(chē)間調(diào)度問(wèn)題.

圖4 IMOPSO與NSGA-II粒子適應(yīng)值散點(diǎn)圖(10-Job問(wèn)題)Fig.4 Scatter plots of particle fitness values for IMOPSO and NSGA-II(10-Job problem)