基于正向投影灰靶模型的多目標(biāo)流水車(chē)間調(diào)度優(yōu)化

朱光宇，張 崢

(1.福州大學(xué) 先進(jìn)制造學(xué)院，福建 泉州 362200;2.福州大學(xué) 機(jī)械工程及自動(dòng)化學(xué)院，福建 福州 350108)

0 引言

置換流水車(chē)間調(diào)度問(wèn)題(Permutation Flow-shop Scheduling Problem, PFSP)作為經(jīng)典N(xiāo)P-hard問(wèn)題，在現(xiàn)實(shí)生產(chǎn)模式中應(yīng)用廣泛[1]，針對(duì)此問(wèn)題，近些年來(lái)研究者提出了不同的智能方法進(jìn)行求解，如基于直覺(jué)模糊集相似度[2]、帶高斯變異的和聲搜索[3]、基于模糊關(guān)聯(lián)熵[4]、混合自適應(yīng)差分算法[5]、混合NSGA-Ⅱ[6]等。可以看出，在求解流水車(chē)間調(diào)度問(wèn)題時(shí)，主要求解含兩個(gè)或三個(gè)目標(biāo)的問(wèn)題，個(gè)別研究者考慮3個(gè)以上目標(biāo)的高維流水車(chē)間調(diào)度問(wèn)題。隨著企業(yè)間競(jìng)爭(zhēng)的加大，生產(chǎn)者在選取調(diào)度方案時(shí)，需考慮多種因素，如完工時(shí)間、機(jī)器利用率、生產(chǎn)成本、庫(kù)存成本等，因此對(duì)于高維多目標(biāo)(目標(biāo)數(shù)量>3)調(diào)度問(wèn)題的研究顯得尤為重要。

求解多目標(biāo)問(wèn)題的智能算法大致可分為4類(lèi)[7-9]：①基于支配關(guān)系的，利用Pareto適應(yīng)度分配策略找出所有非支配個(gè)體。但隨著目標(biāo)維數(shù)的增大，非支配解數(shù)量急劇上升，難以區(qū)分最優(yōu)解。②基于指標(biāo)的，使用性能評(píng)價(jià)指標(biāo)選擇最優(yōu)解引導(dǎo)算法進(jìn)化，不能較好維持前沿的覆蓋率，或計(jì)算效率低下。③基于分解的，通過(guò)聚集函數(shù)將多目標(biāo)的子目標(biāo)加權(quán)求和組合為單個(gè)目標(biāo)求解，這類(lèi)算法需對(duì)領(lǐng)域數(shù)進(jìn)行設(shè)置以及對(duì)權(quán)重向量進(jìn)行調(diào)整，參數(shù)的設(shè)置影響最終解的質(zhì)量;④基于標(biāo)量化的，將多目標(biāo)優(yōu)化問(wèn)題轉(zhuǎn)化為數(shù)值優(yōu)化問(wèn)題，通過(guò)求解數(shù)值優(yōu)化問(wèn)題得到多目標(biāo)問(wèn)題的解，其中基于標(biāo)量化的方法具有計(jì)算簡(jiǎn)單、設(shè)置參數(shù)少，能以較快速度收斂等優(yōu)點(diǎn)，是多目標(biāo)優(yōu)化的研究熱點(diǎn)之一。

因此本文提出一種基于正向投影灰靶模型的多目標(biāo)進(jìn)化算法，將投影靶心距作為標(biāo)量值引導(dǎo)算法進(jìn)化?；野欣碚撌翘幚矶鄬傩詻Q策問(wèn)題的常用方法[10-11]，對(duì)于小樣本、多目標(biāo)的不確定性問(wèn)題具有良好的適用性。隨著研究的深入，一些新的灰靶決策模型被提出，如灰熵加權(quán)的正負(fù)靶心灰靶決策模型[12]、變權(quán)—投影灰靶模型[10]、改進(jìn)調(diào)節(jié)變量主成分權(quán)重的廣義灰靶決策模型[11]。它們被廣泛應(yīng)用于各種決策之中，如磨損狀態(tài)評(píng)估[13]、機(jī)構(gòu)績(jī)效評(píng)價(jià)[14]、風(fēng)險(xiǎn)投資項(xiàng)目選擇[15]等方向領(lǐng)域。分析現(xiàn)有文獻(xiàn)，只有較少的文獻(xiàn)[16-17]將灰靶理論應(yīng)用到多目標(biāo)優(yōu)化、車(chē)間調(diào)度領(lǐng)域，但僅用于最終方案的選擇決策，沒(méi)有用于優(yōu)化迭代過(guò)程中。

就以上已有灰靶決策模型及權(quán)重研究應(yīng)用到多目標(biāo)優(yōu)化、車(chē)間調(diào)度優(yōu)化而言，存在以下局限性：

(1)決策模型中，度量各方案優(yōu)劣性排序的模型公式得到的度量值為相對(duì)量，其理論意義在多目標(biāo)優(yōu)化中無(wú)法解釋。

(2)多目標(biāo)優(yōu)化過(guò)程中，不同智能方法需充分利用解或解集內(nèi)的個(gè)體信息，存在信息缺失的問(wèn)題。

(3)權(quán)重分配機(jī)制包含信息不足，所運(yùn)用的權(quán)重分配方法多數(shù)考慮的是指標(biāo)(對(duì)應(yīng)本問(wèn)題為目標(biāo)函數(shù))的重要性程度，而沒(méi)有深入探討數(shù)據(jù)波動(dòng)性及指標(biāo)與指標(biāo)間是否存在相關(guān)性的情況，與實(shí)際情況可能脫節(jié)。

本文針對(duì)以上局限性，提出正向投影灰靶模型，并將該模型與進(jìn)化算法結(jié)合，實(shí)現(xiàn)車(chē)間調(diào)度問(wèn)題的高維多目標(biāo)優(yōu)化。在定義包含四目標(biāo)的置換流水車(chē)間調(diào)度模型基礎(chǔ)上，在多目標(biāo)優(yōu)化領(lǐng)域給出灰靶模型定義。在多目標(biāo)優(yōu)化領(lǐng)域，為克服同一剖切面上不同Pareto前端的靶心距不同的問(wèn)題，建立正向投影灰靶模型。進(jìn)一步，在此模型中引入由CRITIC法和熵權(quán)法組合的綜合客觀權(quán)重，提取目標(biāo)函數(shù)值間的波動(dòng)性和相關(guān)性信息，建立綜合客觀權(quán)重法改進(jìn)正向投影灰靶模型。將遺傳算法作為進(jìn)化算法的代表與改進(jìn)模型結(jié)合，提出基于正向投影灰靶模型的多目標(biāo)進(jìn)化算法求解高維多目標(biāo)置換流水車(chē)間調(diào)度問(wèn)題。采用多組實(shí)驗(yàn)及算法驗(yàn)證本文方法的有效性。

1 PFSP問(wèn)題描述及模型建立

1.1 問(wèn)題及模型符號(hào)說(shuō)明

PFSP問(wèn)題及模型出現(xiàn)的符號(hào)定義如表1所示。

表1 PFSP問(wèn)題及模型符號(hào)定義

續(xù)表1

1.2 PFSP問(wèn)題及模型

置換流水車(chē)間調(diào)度描述為：n個(gè)工件按相同加工順序依次在m臺(tái)機(jī)器上加工，不同工件在不同機(jī)器上的加工時(shí)間已知，多個(gè)工件不能同時(shí)在一臺(tái)機(jī)器上加工，不同機(jī)器不能同時(shí)加工同一個(gè)工件，期望獲得工件的最優(yōu)加工順序，使得設(shè)定的目標(biāo)達(dá)到最優(yōu)。設(shè)工件集Job={1,2,…,l,…,n}，機(jī)器集Machine={1,2,…,k,…,m}。在收到客戶n個(gè)工件的訂單后，制造商需要在約定的交貨期將生產(chǎn)完成的工件交付給客戶。工件在交貨期前完成會(huì)產(chǎn)生庫(kù)存成本，在交貨期后完成會(huì)產(chǎn)生拖期成本，同時(shí)影響企業(yè)信譽(yù)。每當(dāng)工件完成一定數(shù)量時(shí)開(kāi)始運(yùn)輸，裝運(yùn)時(shí)間設(shè)為單批次最后一個(gè)工件的完成時(shí)間。制造商生產(chǎn)車(chē)間從企業(yè)效益出發(fā)，需要合理安排生產(chǎn)調(diào)度，從而達(dá)到降低生產(chǎn)成本，保證生產(chǎn)和服務(wù)質(zhì)量，提高生產(chǎn)效率的目的。

本文針對(duì)該問(wèn)題，設(shè)置最大完工時(shí)間、最大延遲時(shí)間、庫(kù)存成本以及拖期成本為目標(biāo)函數(shù)，以最小化這4個(gè)目標(biāo)函數(shù)為目標(biāo)，利用作者研究成果建立以下數(shù)學(xué)模型[4,18]。設(shè)xi={xi1,xi2,…,xil,…,xin}(i=1,2,…,N)為n個(gè)決策變量組成的向量，即工件加工順序。F(xi)=(f1(xi),f2(xi),…,fj(xi),…,fM(xi))為xi的目標(biāo)向量，則

F(xi)=(f1(xi),f2(xi),f3(xi),f4(xi)),

(1)

minf1(xi)=max{Clm(xi)|l∈1,2,…,n},

minf2(xi)=max{(0,(Clm(xi)-Dl))|

l∈1,2,…,n},

(2)

s.t.

C11(xi)=T11;

(3)

C1k(xi)=C1(k-1)(xi)+T1k,k=2,3,…,m;

(4)

Cl1(xi)=C(l-1)1(xi)+Tl1,l=2,3,…,n;

(5)

Clk(xi)=max{Cl(k-1)(xi),C(l-1)k(xi)}+Tlk,

l=2,3,…,n,k=2,3,…,m;

(6)

Bt≤h,t=1,2,…,b。

(7)

其中：式(1)表示由決策向量xi求得的4個(gè)目標(biāo)函數(shù);式(2)表示最小化4個(gè)目標(biāo)函數(shù)為本文目標(biāo)，其中，f1(x)為最大完工時(shí)間，f2(x)為最大延遲時(shí)間，f3(x)為庫(kù)存成本，f4(x)為拖期成本;式(3)和式(4)描述了第一個(gè)工件在所有機(jī)器上的完工時(shí)間，且約束同一工件某一時(shí)刻只能在一臺(tái)機(jī)器上加工;式(5)描述了所有工件在第一臺(tái)機(jī)器上的完工時(shí)間，且約束一臺(tái)機(jī)器在某一時(shí)刻只能加工一個(gè)工件;式(6)描述了任一工件l在任一機(jī)器k上完工時(shí)間，約束在機(jī)器k上加工完工件不允許占有機(jī)器;式(7)約束任一批次運(yùn)輸量不大于其單次最大運(yùn)輸量。

2 灰靶理論在多目標(biāo)優(yōu)化問(wèn)題中的描述

將灰靶理論引入優(yōu)化領(lǐng)域時(shí)，其實(shí)現(xiàn)原理可解釋為：在未知全局最優(yōu)解的情況下，通過(guò)實(shí)驗(yàn)構(gòu)建理想最優(yōu)解，這里稱為參考解，并將待評(píng)估的Pareto前端與參考解函數(shù)值進(jìn)行關(guān)聯(lián)分析，計(jì)算靶心距，根據(jù)靶心距的大小對(duì)Pareto解進(jìn)行判斷。

(8)

Ui稱為M維決策灰靶。U={U1,U2,…,Ui,…,UN}為Pareto前端集合S的映射效果集合。

(9)

定義3利用靶心計(jì)算靶心距，多目標(biāo)優(yōu)化問(wèn)題的第i個(gè)Pareto前端的灰靶靶心距計(jì)算公式如下：

(10)

靶心距的大小反映的是Pareto前端的效果向量的優(yōu)劣。靶心距最小對(duì)應(yīng)的Pareto前端即為最優(yōu)Pareto前端，相應(yīng)的解即為最優(yōu)解。

3 正向投影灰靶模型及綜合客觀權(quán)重正向投影灰靶模型

3.1 灰靶變換及綜合客觀權(quán)重正向投影灰靶模型

首先通過(guò)確定正負(fù)參考解及標(biāo)準(zhǔn)化處理實(shí)現(xiàn)Pareto前端的灰靶變換，建立灰靶理論與多目?jī)?yōu)化的聯(lián)系。

3.1.1 構(gòu)建正負(fù)參考解

定義4為了使灰靶空間中各Pareto解的目標(biāo)函數(shù)值能投影到正負(fù)參考解連線上，設(shè)置參考解

(11)

(12)

3.1.2 標(biāo)準(zhǔn)化處理

為有效消除各目標(biāo)數(shù)量級(jí)及量綱的影響，效果映射采用標(biāo)準(zhǔn)化處理，公式如下：

(13)

種群所有個(gè)體經(jīng)過(guò)標(biāo)準(zhǔn)化處理后構(gòu)成標(biāo)準(zhǔn)化灰靶矩陣U，

(14)

式中：i=1,2,…,N;j=1,2,…,M;Ui表示第i個(gè)Pareto前端標(biāo)準(zhǔn)處理后的向量;uij為第i個(gè)Pareto前端第j個(gè)目標(biāo)標(biāo)準(zhǔn)化后數(shù)據(jù)。

3.1.3 正向投影灰靶模型

(15)

(16)

(17)

(18)

3.2 綜合客觀權(quán)重法

在定義6中，引入指標(biāo)權(quán)重向量ωi，其反映了各目標(biāo)函數(shù)在優(yōu)化過(guò)程中的相對(duì)重要程度。在灰靶模型的研究中，指標(biāo)權(quán)重對(duì)決策評(píng)價(jià)問(wèn)題尤為重要，可分為主觀權(quán)重、客觀權(quán)重、集成主客觀權(quán)重3類(lèi)[11]?，F(xiàn)有灰靶模型的指標(biāo)權(quán)重研究成果應(yīng)用到多目標(biāo)流水車(chē)間調(diào)度優(yōu)化時(shí)，存在以下局限性：①由于各個(gè)目標(biāo)的重要程度難以準(zhǔn)確界定，因此包含主觀權(quán)重的方法難以滿足實(shí)際生產(chǎn)需求;②客觀權(quán)重法中大多采用變異系數(shù)法或熵權(quán)法[11,19]。這兩種方法主要是衡量單個(gè)指標(biāo)的不確定信息，很少考慮目標(biāo)之間的聯(lián)系以及目標(biāo)數(shù)據(jù)的波動(dòng)性。

為了克服灰靶理論權(quán)重分配機(jī)制應(yīng)用到多目標(biāo)流水車(chē)間優(yōu)化時(shí)存在的不足，本文基于CRITIC法和熵權(quán)法提出一種新的綜合客觀權(quán)重法，以此改進(jìn)正向投影灰靶模型。

3.2.1 CRITIC法計(jì)算權(quán)重

CRITIC法[18]綜合考慮了目標(biāo)的對(duì)比強(qiáng)度和目標(biāo)間的沖突性，對(duì)比強(qiáng)度反映同一目標(biāo)在不同個(gè)體間取值的差異性大小，用標(biāo)準(zhǔn)差σj來(lái)衡量，標(biāo)準(zhǔn)差越大，表明該目標(biāo)數(shù)據(jù)的波動(dòng)越大，而分配的權(quán)重應(yīng)該越高。沖突性體現(xiàn)各目標(biāo)間的相關(guān)性，相關(guān)性用相關(guān)系數(shù)rj1j2來(lái)表示，1-|rj1j2|則表示沖突性，相關(guān)系數(shù)rj1j2越小，沖突性越大，分配的權(quán)重就越高。CRITIC法計(jì)算權(quán)重公式如下：

(19)

式中：j,j1,j2=1,2,…,M;rj1j2為目標(biāo)j1和目標(biāo)j2的相關(guān)系數(shù);σj為種群中第j個(gè)目標(biāo)的數(shù)據(jù)標(biāo)準(zhǔn)差。

3.2.2 熵權(quán)法計(jì)算權(quán)重

熵權(quán)法能夠體現(xiàn)不確定信息的客觀權(quán)重，用來(lái)表征目標(biāo)信息的離散程度，熵值越小，則目標(biāo)信息的不確定性越小，所攜帶的信息量越大，則權(quán)重分配應(yīng)該越高。熵權(quán)法產(chǎn)生權(quán)重公式如下：

(20)

(21)

3.2.3 綜合客觀權(quán)重

本文將上述兩種賦權(quán)法的優(yōu)點(diǎn)結(jié)合，提出一種新的綜合客觀權(quán)重法，充分反映目標(biāo)數(shù)據(jù)的波動(dòng)性、相關(guān)性和不確定性。因?yàn)闃?biāo)準(zhǔn)差和熵都可以表示數(shù)據(jù)的離散程度，所以本文將它們放于同等地位考慮，建立的CRITIC法結(jié)合熵權(quán)法產(chǎn)生權(quán)重的公式如下：

(22)

式中：σj為種群中第j個(gè)目標(biāo)的數(shù)據(jù)標(biāo)準(zhǔn)差;eij為第i個(gè)個(gè)體第j個(gè)目標(biāo)的信息熵;rj1j2為目標(biāo)j1和目標(biāo)j2的相關(guān)系數(shù)。由此得到種群個(gè)體的權(quán)重矩陣

(23)

式中：i=1,2,…,N;j=1,2,…,M;ωij為第i個(gè)Pareto前端第j個(gè)目標(biāo)的權(quán)重。

將式(22)～式(23)應(yīng)用到式(15)～式(17)，提出一種基于CRITIC法和熵權(quán)法的綜合客觀權(quán)重正向投影灰靶模型。

4 基于正向投影灰靶模型的多目標(biāo)進(jìn)化算法

4.1 算法流程

將綜合客觀權(quán)重正向投影灰靶模型與進(jìn)化算法結(jié)合，構(gòu)建多目標(biāo)進(jìn)化算法，可使得算法更偏重選擇包含數(shù)據(jù)信息量大、波動(dòng)大、沖突性大的個(gè)體參加迭代進(jìn)化，以加快算法收斂。

為便于與經(jīng)典的、新穎的多目標(biāo)進(jìn)化算法比較，本文選擇遺傳算法(Genetic Algorithm, GA)作為基礎(chǔ)算法，使其與改進(jìn)正向投影灰靶模型組合，構(gòu)建基于正向投影灰靶模型的多目標(biāo)GA算法(Positive Projection Grey Target-Genetic Algorithm, PPGT_GA)，所提算法流程如圖2所示,具體步驟如下：

步驟1產(chǎn)生初始種群。隨機(jī)生成N個(gè)個(gè)體的初始種群作為當(dāng)前種群并存入外部檔案，當(dāng)前迭代次數(shù)Iter=1，maxIter為最大迭代次數(shù)。

步驟3生成權(quán)重矩陣。根據(jù)式(23)生成N×M的權(quán)重矩陣。

步驟4計(jì)算投影靶心距。用式(18)計(jì)算正投影靶心距，并將其作為PPGT_GA的適應(yīng)度值來(lái)引導(dǎo)算法進(jìn)化。

步驟5選擇、交叉和變異操作。根據(jù)適應(yīng)度值升序排序，選擇前N個(gè)個(gè)體作為新一代種群，利用精英保留策略，從外部檔案隨機(jī)選擇一個(gè)個(gè)體和當(dāng)前種群的個(gè)體進(jìn)行交叉操作，交叉操作采用部分映射交叉(Partial Mapped Crossover, PMX)[21]，變異操作采用互換(Swap)變異[22]，形成新的子代種群。其中Pc為交叉概率，Pm為變異概率。利用步驟3和步驟4計(jì)算正投影靶心距。

步驟6外部檔案更新。合并子代種群和父代種群，將正投影靶心距按大小順序排序，選擇前N個(gè)個(gè)體作為新的種群，將新種群與外部檔案合并，判斷種群中個(gè)體是否被支配，得到非支配解集，將其作為更新后的外部檔案。

步驟7判斷是否滿足終止條件。滿足最大迭代數(shù)maxIter,則結(jié)束迭代，并輸出結(jié)果，否則Iter=Iter+1,轉(zhuǎn)步驟3。

4.2 個(gè)體編碼及約束處理

在上述算法實(shí)現(xiàn)過(guò)程中，個(gè)體編碼采用整數(shù)編碼，即個(gè)體i表示為xi={xi1,xi2,…，xil,…,xin}(i=1,2,…,N)代表工件組成的序列。計(jì)算個(gè)體目標(biāo)函數(shù)值時(shí)，在解碼過(guò)程中處理約束。首先取個(gè)體(工件)序列xi，由式(3)和式(4)求得個(gè)體第一個(gè)工件在所有機(jī)器的完工時(shí)間C1k(xi)，由式(5)求得所有工件在第一臺(tái)機(jī)器的完工時(shí)間Cl1(xi)，則第2個(gè)工件完工時(shí)間C2k(xi)為C2(k-1)(xi),C1k(xi)更大值加上T2k，依次可得第l個(gè)工件完工時(shí)間Clk(xi)為max{Cl(k-1)(xi),C(l-1)k(xi)}+Tlk，再根據(jù)式(2)計(jì)算該個(gè)體目標(biāo)函數(shù)值。

5 實(shí)驗(yàn)設(shè)置

為驗(yàn)證PPGT_GA算法在求解多目標(biāo)流水車(chē)間調(diào)度問(wèn)題的求解性能和效果，本文選取CEC(congress on evolutionary computation)測(cè)試集中6個(gè)MaF函數(shù)[21]、10個(gè)不同規(guī)模的置換流水車(chē)間測(cè)試實(shí)例[23]及1個(gè)工程應(yīng)用開(kāi)展實(shí)驗(yàn)測(cè)試，選取4個(gè)經(jīng)典或新穎的多目標(biāo)進(jìn)化算法作為比較算法，分別為：基于直覺(jué)模糊集相似度的多目標(biāo)遺傳算法(Similarity of Intuitionistic Fuzzy Sets GA, SIFS_GA)[18]、基于參考點(diǎn)的非支配排序的多目標(biāo)遺傳算法(Non-dominated Sorting Genetic Algorithm Ⅲ, NSGAⅢ)[24]、基于IGD-NS指標(biāo)的自適應(yīng)參考點(diǎn)多目標(biāo)進(jìn)化算法(Adaptive Reference points based Multi-objective Evolutionary Algorithm, AR_MOEA)[25]和基于分解的雙準(zhǔn)則多目標(biāo)進(jìn)化算法(Bi-criterion Evolution based MOEA/D, BCE_MOEAD)[26]。

各算法共同的參數(shù)設(shè)置如下：種群大小N=20，外部檔案大小Wmax=20，最大迭代次數(shù)maxIter=100，由于PPGT_GA、SIFS_GA、NSGAⅢ都是基于GA算法，設(shè)GA交叉概率Pc=0.9，變異概率Pm=0.1[23]。采用遺傳算法對(duì)每個(gè)子目標(biāo)單目標(biāo)優(yōu)化次數(shù)Q=10。對(duì)于BCE_MOEAD，根據(jù)文獻(xiàn)[27]推薦的參數(shù)，設(shè)置領(lǐng)域大小T=0.1 N，從領(lǐng)域選擇個(gè)體概率0.9，子代最大替換個(gè)體數(shù)為0.01 N。各種算法采用相同初始解運(yùn)行，采用不同初始解運(yùn)行10次取平均值作為實(shí)驗(yàn)結(jié)果。

選取MaF1、MaF2、MaF7、MaF9、MaF12、MaF13測(cè)試函數(shù)，目標(biāo)個(gè)數(shù)M=4，決策變量個(gè)數(shù)為M+9，標(biāo)準(zhǔn)測(cè)試集函數(shù)參見(jiàn)文獻(xiàn)[21]。

對(duì)于10個(gè)不同規(guī)模的車(chē)間測(cè)試實(shí)例，其規(guī)模從工件數(shù)n=10、機(jī)器數(shù)m=5到工件數(shù)n=100、機(jī)器數(shù)m=20。其他參數(shù)設(shè)置如下：完工工件每批最大運(yùn)輸量h=5，單位庫(kù)存成本αl=1和單位拖期成本βl=2。SIFS_GA、NSGAⅢ的參考解與PPGT_GA一致。

為驗(yàn)證算法性能的優(yōu)劣，采用4個(gè)指標(biāo)從解集分布性、收斂性及綜合性進(jìn)行分析。指標(biāo)為：①分布性指標(biāo)：間隔距離(SP)[28]，用來(lái)評(píng)價(jià)解集在目標(biāo)空間中的分布均勻性,SP值越小，解集在目標(biāo)空間分布越均勻;②收斂性指標(biāo)：當(dāng)代距離(GD)[28]，用來(lái)評(píng)價(jià)解集與參考解的接近程度,GD值越小，Pareto解與參考解越逼近，收斂性越好;③綜合性指標(biāo)：反世代距離(IGD)[29]，用來(lái)評(píng)價(jià)解集的收斂性及分布性,IGD值越小，算法的收斂性及分布性越好;④綜合性指標(biāo)：超體積(HV)[30]，用來(lái)評(píng)價(jià)解集的收斂性及分布性，表示算法所獲得的非支配解集與參考點(diǎn)所圍成的目標(biāo)空間中區(qū)域的體積，HV值越大，算法的收斂性及分布性越好。指標(biāo)的計(jì)算方式參見(jiàn)對(duì)應(yīng)文獻(xiàn)。

6 結(jié)果比較與分析

6.1 CEC測(cè)試集測(cè)試結(jié)果

6個(gè)MaF函數(shù)具有不同特性，理論前沿面具有不同形狀，能夠反映優(yōu)化問(wèn)題具有的復(fù)雜情況，可以檢測(cè)算法高維多目標(biāo)優(yōu)化方法解決實(shí)際優(yōu)化問(wèn)題的性能。各算法求解MaF函數(shù)的性能評(píng)價(jià)指標(biāo)結(jié)果如表2所示。

表2 五種算法求解6個(gè)CEC標(biāo)準(zhǔn)測(cè)試集的性能評(píng)價(jià)指標(biāo)結(jié)果(加粗為最好值)

續(xù)表2

在間隔距離(SP)方面，所有實(shí)例中，PPGT_GA的值均小于其他算法，說(shuō)明PPGT_GA所獲得的Pareto解集分布的均勻性較好。在當(dāng)代距離(GD)方面，函數(shù)MaF7、MaF9、MaF12、MaF13中，PPGT_GA的GD值均小于其他4種算法，表明PPGT_GA求得的Pareto解能更好地逼近參考解，整體上收斂性較好。在反世代距離(IGD)方面，PPGT_GA在兩個(gè)函數(shù)(MaF12，MaF13)上取得最好值，NSGAⅢ在3個(gè)函數(shù)(MaF1，MaF7，MaF9)上取得最好值,表明PPGT_GA算法所求得的解好于其他算法結(jié)果，遜于NSGAⅢ的結(jié)果。超體積(HV)方面，PPGT_GA在兩個(gè)函數(shù)(MaF9，MaF13)上取得最好值，AR_MOEA在4個(gè)函數(shù)(MaF1，MaF2，MaF7，MaF9)上取得最好值，表明PPGT_GA算法所求得解好于其他算法的結(jié)果，遜于AR_MOEA的結(jié)果。

綜合以上分析，PPGT_GA、NSGAⅢ和AR_MOEA算法在不同測(cè)試函數(shù)上具有自己的優(yōu)勢(shì)，它們的整體性能都好于SIFS_GA、BCE_MOEAD。

6.2 流水車(chē)間測(cè)試實(shí)例結(jié)果

4目標(biāo)流水車(chē)間調(diào)度問(wèn)題優(yōu)化，得到各算法的多目標(biāo)最優(yōu)解函數(shù)值和指標(biāo)如表3所示。

表3 10個(gè)置換流水車(chē)間測(cè)試實(shí)例實(shí)驗(yàn)結(jié)果(加粗為最好值)

續(xù)表3

實(shí)例3～實(shí)例10中，PPGT_GA所得最優(yōu)解的4項(xiàng)函數(shù)值均優(yōu)于其他算法；實(shí)例1、2中，PPGT_GA所得最優(yōu)解的函數(shù)值分別有2、3項(xiàng)得到最好值。由此表明，PPGT_GA采用綜合客觀權(quán)重正向投影灰靶模型比其他算法能得到更好的解。在分布性指標(biāo)SP方面，實(shí)例1、2、3、4、6、7、8中，PPGT_GA的SP值最小，在另外的3個(gè)實(shí)例中，PPGT_GA的結(jié)果為第2好,表明本文所提算法能夠獲得均勻性較好的解集，優(yōu)于其他算法。在收斂性指標(biāo)GD方面，PPGT_GA的GD值均小于其他4種算法，這表明PPGT_GA所得Pareto解更接近參考解，其收斂性更好。在綜合指標(biāo)IGD方面，在實(shí)例2、3、5～10中，PPGT_GA的IGD值都小于其他算法，實(shí)例1、4中，PPGT_GA的IGD值為第3小，表明PPGT_GA的綜合性能較好。在綜合指標(biāo)HV方面，除實(shí)例1，其余實(shí)例中，PPGT_GA的HV值都大于其他4種算法，表明PPGT_GA的綜合性能較好。

綜合目標(biāo)函數(shù)值及4種評(píng)價(jià)指標(biāo)，表明PPGT_GA算法在多目標(biāo)置換流水車(chē)間調(diào)度問(wèn)題上能獲得收斂性和分布性較好的高質(zhì)量Pareto解及解集，綜合性能較好。

6.3 工程應(yīng)用仿真

某電路板制造商需對(duì)10種不同的電路板進(jìn)行STM(surface mounting technology)表面貼裝，加工過(guò)程在5臺(tái)機(jī)器上進(jìn)行流水生產(chǎn)，是一個(gè)典型的置換流水車(chē)間調(diào)度問(wèn)題。10種電路板在5臺(tái)機(jī)器上的加工工序時(shí)間如表4所示。為選取合理的調(diào)度方案，利用PPGT_GA算法與4種對(duì)比算法進(jìn)行調(diào)度優(yōu)化，最優(yōu)解目標(biāo)函數(shù)值如圖3所示，對(duì)各算法最優(yōu)結(jié)果利用Flexsim軟件進(jìn)行仿真，確定最優(yōu)調(diào)度方案。

表4 表面貼裝工藝加工時(shí)間 min

從圖3可看出，PPGT_GA算法的最大完工時(shí)間f1、最大延遲時(shí)間f2及拖期成本f4都小于其他3種算法，PPGT_GA算法的優(yōu)化結(jié)果具有優(yōu)勢(shì)，其甘特圖如圖4所示，限于篇幅，僅畫(huà)出PPGT_GA的甘特圖。

用Flexsim軟件對(duì)置換流水車(chē)間調(diào)度進(jìn)行仿真。在Flexsim中輸入5種算法的調(diào)度方案，可以得到各機(jī)器利用率及空閑時(shí)間，如圖5所示。

從圖5a可看出，PPGT_GA調(diào)度方案5臺(tái)機(jī)器的利用率均高于其他4種算法的調(diào)度方案。由圖5b可知，PPGT_GA調(diào)度方案5臺(tái)機(jī)器的空閑時(shí)間均低于其他4種算法的調(diào)度方案。因而，PPGT_GA算法能得到較好的車(chē)間調(diào)度方案，可以為工廠提高生產(chǎn)效率及設(shè)備利用率。

7 結(jié)束語(yǔ)

針對(duì)高維多目標(biāo)流水車(chē)間調(diào)度問(wèn)題，本文提出基于正向投影灰靶模型的多目標(biāo)進(jìn)化算法對(duì)其進(jìn)行求解，得出以下結(jié)論：

(1)在多目標(biāo)優(yōu)化領(lǐng)域中定義灰靶模型，將其用于解決高維多目標(biāo)置換流水車(chē)間調(diào)度問(wèn)題，用靶心距評(píng)判Pareto前端的優(yōu)劣。

(2)為克服多目標(biāo)優(yōu)化領(lǐng)域中灰靶模型存在同一剖切面上不同Pareto前端的靶心距不同的不足，提出正向投影灰靶模型。在該模型中，引入由CRITIC法和熵權(quán)法組合的綜合客觀權(quán)重，提取目標(biāo)數(shù)據(jù)間的波動(dòng)性和相關(guān)性信息，建立綜合客觀權(quán)重法改進(jìn)正向投影灰靶模型。將改進(jìn)模型與進(jìn)化算法的代表遺傳算法結(jié)合，提出基于正向投影灰靶模型的多目標(biāo)進(jìn)化算法求解本文問(wèn)題。

(3)通過(guò)CEC測(cè)試集、流水車(chē)間調(diào)度實(shí)例及工程應(yīng)用，與4種經(jīng)典、新穎的算法比較，可知PPGT_GA算法在求解置換流水車(chē)間調(diào)度問(wèn)題上可以獲得較高質(zhì)量解，好的收斂性和分布性。驗(yàn)證了PPGT_GA算法性能的優(yōu)越性。

本文所提算法依賴于正負(fù)參考解，所用單目標(biāo)求解參考解的好壞一定程度上影響所提算法最終解集質(zhì)量。在未來(lái)研究中，將注重參考解的獲取方式，同時(shí)驗(yàn)證PPGT_GA算法在求解其他調(diào)度問(wèn)題的應(yīng)用效果。