王建華，楊 琦，朱 凱

(江蘇大學(xué) 管理學(xué)院，江蘇 鎮(zhèn)江 212013)

0 引言

在并行機(jī)調(diào)度問(wèn)題中，設(shè)置操作長(zhǎng)期以來(lái)被認(rèn)為是可以忽略或被認(rèn)為是處理時(shí)間的一部分，雖然這對(duì)于一些調(diào)度來(lái)說(shuō)是合理的，但對(duì)于有些情況下是需要明確的[1]。例如，化工廠在加工一種混合物轉(zhuǎn)換到另一種混合物時(shí)，反應(yīng)器必須經(jīng)過(guò)清洗，清洗時(shí)間取決于之前的工作和后續(xù)的工作。如果前一種化學(xué)物質(zhì)影響后一種化學(xué)物質(zhì)，可能需要很長(zhǎng)的清洗時(shí)間，以相反順序只需更短時(shí)間[2]。另一方面，當(dāng)今社會(huì)環(huán)境問(wèn)題日益嚴(yán)重，綠色制造研究備受關(guān)注。作為現(xiàn)代制造模式，綠色制造旨在保證產(chǎn)品功能與質(zhì)量的同時(shí)減少能源浪費(fèi)，實(shí)現(xiàn)經(jīng)濟(jì)指標(biāo)和綠色指標(biāo)的協(xié)同優(yōu)化[3-4]。因此，形成了本文所研究的具有設(shè)置時(shí)間的綠色并行機(jī)調(diào)度問(wèn)題(Green Parallel Machine Scheduling Problem with Set-up Time, GPMSP-ST)。

目前，解決并行機(jī)調(diào)度問(wèn)題常用到精確算法、近似算法以及智能優(yōu)化算法。精確算法包括分支界定，最速下降法等運(yùn)籌學(xué)算法[5-6]，該類(lèi)算法在小規(guī)模問(wèn)題中能在短時(shí)間內(nèi)獲得最佳解，但面對(duì)較大規(guī)模問(wèn)題時(shí)，求解時(shí)間較長(zhǎng)，若問(wèn)題具有非凸性，則不存在通用的最優(yōu)解求解算法。基于動(dòng)態(tài)規(guī)劃的近似算法可以提出能夠保證最優(yōu)解不丟失的遞推方程，在較長(zhǎng)時(shí)間內(nèi)能夠保證算法獲得最優(yōu)解，但其本質(zhì)上仍屬于窮舉法，時(shí)間復(fù)雜度基本為指數(shù)型，且只能應(yīng)用于能提出相應(yīng)規(guī)則的簡(jiǎn)單并行機(jī)調(diào)度問(wèn)題[7-9]。相較于前兩種算法，智能優(yōu)化算法具有求解速度快、普適性強(qiáng)、求解質(zhì)量高等優(yōu)點(diǎn)，近年來(lái)得到了廣泛研究。軒華等[10]基于遺傳算法和禁忌搜索算法提出一種混合啟發(fā)式算法求解了每階段含不相關(guān)并行機(jī)的多階段混合流水車(chē)間問(wèn)題。宋強(qiáng)[11]以異構(gòu)并行機(jī)為研究對(duì)象，提出混合多目標(biāo)教與學(xué)算法解決了最小化makespan和提前、延誤懲罰總成本的多目標(biāo)問(wèn)題。時(shí)維國(guó)等[12]以最小化最大完工時(shí)間為單目標(biāo)，提出一種改進(jìn)灰狼算法，有效解決了帶相同并行機(jī)的混合流水車(chē)間調(diào)度問(wèn)題。付亞平等[13]針對(duì)生產(chǎn)中存在的串并聯(lián)共存的布局環(huán)境，研究了特殊的混合并行機(jī)調(diào)度問(wèn)題，并提出一種改進(jìn)的非支配遺傳算法進(jìn)行求解。張潔等[14]構(gòu)建了一種兩階段蟻群并行搜索算法，對(duì)于非等效并行機(jī)車(chē)間調(diào)度問(wèn)題，明顯提高了獲得較優(yōu)解的概率。以上文獻(xiàn)并未涉及工序間的設(shè)置時(shí)間，當(dāng)加工不同工件由于設(shè)置操作產(chǎn)生序列相關(guān)準(zhǔn)備時(shí)間時(shí)，設(shè)置時(shí)間就必須明確。胡大勇等[15]以最小化最大完工時(shí)間為目標(biāo)，研究了設(shè)置時(shí)間與順序相關(guān)的等同并行機(jī)調(diào)度，對(duì)建立的數(shù)學(xué)規(guī)劃模型所求問(wèn)題下界評(píng)價(jià)了遺傳算法所得近似最優(yōu)解的質(zhì)量。何雨潔等[16]驗(yàn)證了所提出的混合離散教與學(xué)算法可以有效解決廣泛存在的復(fù)雜并行機(jī)調(diào)度問(wèn)題，即帶到達(dá)時(shí)間、加工約束、多工序和工序間設(shè)置時(shí)間的并行機(jī)調(diào)度問(wèn)題。李作成等[17]針對(duì)帶工件加工約束和序相關(guān)設(shè)置時(shí)間的異構(gòu)并行機(jī)調(diào)度問(wèn)題，提出一種分布估算方法并驗(yàn)證了其有效性和魯棒性。FANJUL-PEYRO等[18]提出了新的混合整數(shù)線性規(guī)劃和基于數(shù)學(xué)規(guī)劃的算法，經(jīng)過(guò)測(cè)試比較現(xiàn)有模型和算法，證實(shí)了該算法在具有作業(yè)序列設(shè)置時(shí)間的不相關(guān)并行機(jī)調(diào)度問(wèn)題上的求解效果更好。VALLADA等[19]針對(duì)帶工序設(shè)置時(shí)間的異構(gòu)并行機(jī)問(wèn)題，提出一種性能優(yōu)異的增強(qiáng)局部搜索的遺傳算法。YEPES-BORRERO等[20]考慮了異構(gòu)并行機(jī)中具有設(shè)置時(shí)間和設(shè)置中附帶額外資源的情況，設(shè)計(jì)了3種元啟發(fā)式算法，并證實(shí)了考慮資源約束的算法能產(chǎn)生更好結(jié)果。在關(guān)于并行機(jī)調(diào)度的研究中，基本以最小化完工時(shí)間這類(lèi)經(jīng)濟(jì)指標(biāo)為優(yōu)化目標(biāo)，近年來(lái)，逐漸有學(xué)者考慮能耗等綠色因素。李凱等[21]考慮了具有能耗成本約束的并行機(jī)調(diào)度問(wèn)題，提出了改進(jìn)的最早交貨期優(yōu)先(Earliest Due Date firstly, EDD)算法并驗(yàn)證了其有效性。

根據(jù)已有文獻(xiàn)來(lái)看，在考慮設(shè)置時(shí)間的并行機(jī)調(diào)度問(wèn)題上，考慮能耗、碳排放等綠色指標(biāo)的文獻(xiàn)尚不多見(jiàn)，且大多研究采用傳統(tǒng)智能優(yōu)化算法。VENKATA RAO教授[22]在2016年提出的Jaya算法相較于其他智能優(yōu)化算法具有無(wú)參數(shù)控制、求解速度快、全局搜索能力強(qiáng)等優(yōu)點(diǎn)。近年來(lái)，Jaya算法也逐步應(yīng)用到車(chē)間調(diào)度領(lǐng)域，但大部分研究集中在流水車(chē)間調(diào)度問(wèn)題領(lǐng)域，少有應(yīng)用于并行機(jī)調(diào)度領(lǐng)域內(nèi)。因此，本文建立了最小化最大完工時(shí)間與最小化機(jī)器總能耗的雙目標(biāo)優(yōu)化模型，在Jaya算法的基礎(chǔ)上，設(shè)計(jì)子種群數(shù)量可隨搜索情況自適應(yīng)改變的多種群策略，形成可以求解多目標(biāo)的自適應(yīng)多種群Jaya算法(Self-Adaptive Multi-Population Jaya algorithm, SAMP-Jaya)，經(jīng)過(guò)測(cè)試分析，驗(yàn)證了該算法求解GPMSP-ST問(wèn)題的有效性與魯棒性。

1 具有設(shè)置時(shí)間的綠色并行機(jī)調(diào)度問(wèn)題

1.1 問(wèn)題描述

考慮序列相關(guān)準(zhǔn)備時(shí)間的異速并行機(jī)調(diào)度問(wèn)題由m臺(tái)并行機(jī)器和n個(gè)工件組成，每個(gè)工件可以在任意機(jī)器上加工且每個(gè)工件只需加工一次。工件加工時(shí)間取決于機(jī)器的性能，在不同的機(jī)器上加工時(shí)間往往不同。同一機(jī)器上加工不同工件時(shí)，需要一定加工準(zhǔn)備時(shí)間，不同工件間加工準(zhǔn)備時(shí)間基本不同，處于加工準(zhǔn)備時(shí)間時(shí)，機(jī)器為空載狀態(tài)，能耗為空載能耗。綠色并行機(jī)調(diào)度問(wèn)題在優(yōu)化最大完工時(shí)間的同時(shí)，也需考慮機(jī)器能耗，保證經(jīng)濟(jì)指標(biāo)與綠色指標(biāo)的優(yōu)化同步進(jìn)行。

1.2 問(wèn)題模型

為了構(gòu)建當(dāng)前調(diào)度的數(shù)學(xué)模型，現(xiàn)定義相關(guān)符號(hào)如表1所示。

表1 符號(hào)定義

根據(jù)上述定義，建立如下數(shù)學(xué)模型，優(yōu)化目標(biāo)為最小化最大完工時(shí)間和最小化機(jī)器總能耗。

(2)

s.t.

(3)

k=1,2,…,m;h=1,2,…,qk。

(4)

k=1,2,…,m;h=1,2,…,qk。

(5)

k=1,2,…,m;h=1,2,…,qk。

(6)

(7)

(8)

Xikh={0,1};i=1,2,…,n;k=1,2,…,m;h=1,2,…,qk。

(9)

其中：式(1)和式(2)為數(shù)學(xué)模型中的雙目標(biāo)函數(shù)；約束(3)表示每個(gè)作業(yè)都能調(diào)度到一臺(tái)機(jī)器上；約束(4)確保每臺(tái)機(jī)器同一加工位置只能加工一個(gè)工件；約束(5)保證工件一旦開(kāi)始加工，則不能中斷；約束(6)表示同一機(jī)器上相鄰加工位置存在前后緊前關(guān)系；約束(7)表示每臺(tái)機(jī)器加工時(shí)間起始時(shí)間為0時(shí)刻；約束(8)表示每臺(tái)機(jī)器的第一個(gè)加工工件不需要設(shè)置時(shí)間；約束(9)表示Xikh只能為0或1。

2 自適應(yīng)多種群Jaya算法

GPMSP-ST為離散型問(wèn)題，對(duì)于求解連續(xù)性問(wèn)題的Jaya算法而言，本文設(shè)計(jì)了一種排序機(jī)制將離散與連續(xù)結(jié)合起來(lái)。此外，為了提升初始種群的質(zhì)量，隨機(jī)選擇兩種機(jī)器分配規(guī)則中的一種。相較于固定種群，多種群方法可以將整個(gè)種群分為多個(gè)子種群并將其分配至整個(gè)搜索空間，每個(gè)子種群具有在不同區(qū)域搜索的能力，從而可以提高搜索多樣性，有效檢驗(yàn)問(wèn)題的變化。GPMSP-ST為多目標(biāo)問(wèn)題，解的優(yōu)劣性需要衡量多個(gè)目標(biāo)值，本文采用非支配排序的方法給解劃分等級(jí)，通過(guò)計(jì)算各等級(jí)擁擠度得到最優(yōu)解與最劣解。SAMP-Jaya算法不需要調(diào)整特定于算法的參數(shù)，求解效果具有良好的魯棒性。多種群的搜索有助于提升算法全局搜索能力，不易陷入局部最優(yōu)。

2.1 編碼與解碼

GPMSP-ST可以分為工件排序與機(jī)器分配兩個(gè)子問(wèn)題。本文采用二維實(shí)數(shù)編碼方式，可以有效映射問(wèn)題的解空間。設(shè)每一個(gè)解矩陣X包含兩個(gè)向量，分別為基于工件排序的向量X1和基于機(jī)器分配X2，現(xiàn)有一個(gè)9×3 GPMSP-ST的例子，X1=[1,5,4,9,8,2,6,3,7]，X2=[2,3,2,1,3,2,2,1,3]，表示工件1在2號(hào)機(jī)器加工，工件5在3號(hào)機(jī)器加工，以此類(lèi)推。3臺(tái)機(jī)器的加工工件順序矩陣分別為Y1=[9,3]，Y2=[1,4,2,6]，Y3=[5,8,7]。編碼示例如圖1所示。

工件在各機(jī)器加工時(shí)間和工件間設(shè)置時(shí)間如表2和表3所示。

表2 工件加工時(shí)間

表3 各工件間設(shè)置時(shí)間

此例中，經(jīng)解碼后，其調(diào)度甘特圖如圖2所示。

2.2 多規(guī)則種群初始化

高質(zhì)量種群有助于算法的尋優(yōu)，但是為避免算法陷入局部最優(yōu)，同時(shí)也要考慮種群多樣性，因此本文采用多規(guī)則初始化種群，依然以2.1節(jié)中9×3的問(wèn)題為例。

工件加工向量初始化：首先為加工工件序列創(chuàng)建數(shù)值為0～1隨機(jī)值的位置向量Z1=[A1,A2,A3,…,A9]，然后將所有數(shù)值按降序進(jìn)行排序，最后將位置向量數(shù)值所對(duì)應(yīng)的原工件序列更換位置，具體步驟如圖3所示。

機(jī)器分配向量初始化：每個(gè)種群個(gè)體初始化時(shí)會(huì)隨機(jī)產(chǎn)生一個(gè)0～1的隨機(jī)數(shù)，然后根據(jù)CALDEIRA等[23]提出的規(guī)則結(jié)合本文問(wèn)題形成如下規(guī)則進(jìn)行機(jī)器分配：

(1)隨機(jī)規(guī)則 若隨機(jī)數(shù)小于0.8，為每個(gè)工件隨機(jī)分配相應(yīng)的機(jī)器。

(2)工作量均衡規(guī)則 若隨機(jī)數(shù)大于等于0.8，根據(jù)工件加工順序逐一為每個(gè)工件分配機(jī)器，每當(dāng)為一個(gè)新工件分配機(jī)器時(shí)，將統(tǒng)計(jì)所有機(jī)器被使用次數(shù)，優(yōu)先分配尚未達(dá)到使用平均數(shù)的機(jī)器給待分配機(jī)器的加工工件，倘若有若干機(jī)器可供選擇，隨機(jī)選擇一臺(tái)機(jī)器。

2.3 種群的劃分與合并

多種群相比于固定數(shù)量的種群，子種群的數(shù)目與選擇將是算法性能的關(guān)鍵問(wèn)題。為了滿(mǎn)足種群的多樣性，SAMP-Jaya算法將對(duì)VENKATA RAO等[24]提出的多目標(biāo)Jaya算法(Multi-Objective Jaya algorithm, MO-Jaya)作出如下修改：

(1)根據(jù)解的質(zhì)量劃分多個(gè)子種群，使用子種群的數(shù)量將解分布在搜索空間上，而不是集中在某個(gè)特定的區(qū)域內(nèi)，因此，算法有望產(chǎn)生最優(yōu)解。

(2)根據(jù)解的變化情況自適應(yīng)改變子種群數(shù)量，以跟蹤最佳解決方案并改進(jìn)搜索過(guò)程多樣化，此外，重復(fù)解被新生解所代替，以保持算法多樣性和勘探性。若第n代種群被劃分為m個(gè)子種群，經(jīng)過(guò)更新后形成新子種群并且合并成第n+1代新種群。當(dāng)新種群的最優(yōu)解優(yōu)于舊種群時(shí)，則m=m+1，目的是為了增加搜索過(guò)程的探索特性，否則m=m-1，因?yàn)樗惴ǜ枰_(kāi)發(fā)性而不是探索性。

種群的劃分與合并過(guò)程如圖4所示。

2.4 Pareto尋優(yōu)及個(gè)體擁擠度計(jì)算

在單目標(biāo)優(yōu)化的情況下，很容易根據(jù)解的適應(yīng)度來(lái)判斷解的優(yōu)劣性。但是在存在多個(gè)沖突目標(biāo)的情況下，很難從一組解中決定最優(yōu)解與最劣解。為了有效處理多個(gè)目標(biāo)，本文利用非支配等級(jí)以及個(gè)體擁擠度兩種指標(biāo)來(lái)評(píng)價(jià)個(gè)體解?；趦?yōu)勢(shì)概念可以將群體劃分幾個(gè)等級(jí)。其規(guī)則如下：設(shè)有兩個(gè)解方案Xi和Xj，只有當(dāng)Xi在所有目標(biāo)方面不比Xj差，并且至少在一個(gè)目標(biāo)上嚴(yán)格優(yōu)于Xj時(shí)，解Xi支配解Xj，即解Xi具有更高的等級(jí)。等級(jí)高的解被認(rèn)為優(yōu)于其他的解。若兩個(gè)解擁有相同的等級(jí)，具有較高擁擠距離的解被視為優(yōu)于其他解[25]。這保證了從搜索空間的稀疏區(qū)域中選擇解決方案，有助于提升解的多樣性。擁擠度(Crowding Distance, CD)計(jì)算步驟如下：

步驟1對(duì)于每一個(gè)目標(biāo)函數(shù)，將等級(jí)相同的解按相應(yīng)目標(biāo)函數(shù)值遞增順序排序。

步驟2設(shè)排序集合中有n個(gè)解，將邊界解(第一個(gè)解和第n個(gè)解)分配最大擁擠距離CD=∞，對(duì)于排序集合j=2到n-1中所有其他解，擁擠距離為：

(10)

具有最高等級(jí)且擁擠度最高的為最優(yōu)解，反之為最劣解。當(dāng)二者確定后，新種群中每個(gè)個(gè)體將根據(jù)2.5節(jié)中更新公式進(jìn)行更新。

2.5 種群個(gè)體變量更新策略

Jaya算法在每一輪迭代時(shí)會(huì)更新每個(gè)變量值，變量的值更新后，其新目標(biāo)值將與舊值比較，只有更好的解才被考慮用于下一代。其更新公式如下所示：

H(i+1,k)=H(i,k)+r1(H(i,b)-

|H(i,k)|)-r2(H(i,w)-|H(i,k)|)。

(11)

式中：i，k分別表示迭代和候選解的索引；H(i,k)表示第k個(gè)候選解在第i次迭代后的變量值；r1和r2是[0,1]范圍內(nèi)產(chǎn)生的隨機(jī)數(shù)，二者充當(dāng)比例因子，確保解良好的多樣化。與此同時(shí)，每次更新，候選解都嘗試接近最佳解并遠(yuǎn)離最差解，因此，實(shí)現(xiàn)了搜索過(guò)程良好強(qiáng)化與多樣化的同步性。

SAMP-Jaya算法繼承了Jaya算法的更新思想，即試圖接近成功(達(dá)到最佳解)，并試圖避免失敗(遠(yuǎn)離最差解)。并在此基礎(chǔ)上設(shè)計(jì)了一種位置向量更新機(jī)制來(lái)解決離散型變量更新問(wèn)題。工件加工順序碼更新過(guò)程如圖5所示。

機(jī)器分配經(jīng)過(guò)初始化規(guī)則后，其更新過(guò)程與圖5類(lèi)似。

2.6 SAMP-Jaya算法流程

SAMP-Jaya算法具體步驟如下：

步驟1根據(jù)2.1節(jié)描述設(shè)計(jì)變量，2.2節(jié)中的規(guī)則初始化種群，并設(shè)置迭代次數(shù)為終止條件。

步驟2計(jì)算種群中每個(gè)候選解的所有目標(biāo)值。

步驟3基于解的質(zhì)量，將整個(gè)種群劃分為m個(gè)組(m的初始值為2)。

步驟4每個(gè)子種群使用2.5節(jié)描述的更新規(guī)則獨(dú)立更新每個(gè)種群的解，每一個(gè)修改后的解只有比舊方案更好的情況下才被接受(修改后的解被支配)。

步驟5將所有子種群合并為一個(gè)整體，并根據(jù)2.3節(jié)描述修改m值。

步驟6檢查終止條件。若搜索過(guò)程已經(jīng)達(dá)到終止條件，則終止循環(huán)并輸出最佳解決方案，否則返回步驟2。

3 算例測(cè)試與分析

3.1 測(cè)試準(zhǔn)備

在頻率為2.10GHz，內(nèi)存4GB，AMDA8-5550MAPU的計(jì)算機(jī)上進(jìn)行仿真，選用NetBeansIDE8.2進(jìn)行編程，為體現(xiàn)實(shí)驗(yàn)結(jié)果的公平性，各算法相同參數(shù)設(shè)置為：種群大小為50，終止條件為迭代次數(shù)為200代。

3.2 SAMP-Jaya與兩種智能算法比較分析

為了驗(yàn)證本文所提出的SAMP-Jaya算法的優(yōu)越性，將SAMP-Jaya算法與ABREU等[26]提出的混合遺傳算法(HybridGeneticAlgorithm,HGA)、何雨潔等[16]提出的混合離散教與學(xué)算法(Hybridmulti-objectiveTeaching-Learning-basedOptimization,HDTLBO)進(jìn)行比較。根據(jù)上述兩篇文獻(xiàn)已有測(cè)試結(jié)果表明，取兩種算法較優(yōu)表現(xiàn)參數(shù)如表4所示。

表4 兩種算法參數(shù)取值

以最大完工時(shí)間為單目標(biāo)，測(cè)試算例是隨機(jī)生成的，其中處理和設(shè)置時(shí)間是從U(50,100)和U(125,175)中兩個(gè)均勻分布中隨機(jī)提取。共有如下3種情況：①當(dāng)處理和設(shè)置時(shí)間平衡(ProcessingSetupBalanced,PSB)時(shí)，它們都是從U(50,100)中提取的；②當(dāng)處理時(shí)間占據(jù)主導(dǎo)(ProcessingDominant,PD)時(shí)，處理時(shí)間和設(shè)置時(shí)間分別從U(125,175)和U(50,100)中提取；③當(dāng)設(shè)置時(shí)間占據(jù)主導(dǎo)(SetupDominant,SD)時(shí)，處理時(shí)間和設(shè)置時(shí)間分別從U(50,100)和U(125,175)中提取。測(cè)試問(wèn)題的規(guī)模n和m的集合分別為{20,40,60,80,100,120}和{2,4,6}。將SAMP-Jaya算法運(yùn)行15次，比較各算法的最優(yōu)解與標(biāo)準(zhǔn)偏差(StandardDeviation,STD)如表5所示。表中粗體表示相同算例中優(yōu)于其他算法的最優(yōu)解。

表5 各算法最優(yōu)解與標(biāo)準(zhǔn)差對(duì)比

由表4中所有算例可以發(fā)現(xiàn)，相較于其他兩種算法，SAMP-Jaya算法所得最優(yōu)解次數(shù)總計(jì)為15次，只在3種規(guī)模的算例中未取得最優(yōu)；在所有規(guī)模問(wèn)題中均表現(xiàn)良好，在未取得最優(yōu)解的3種算例中也接近其他算法的最優(yōu)解，綜合效果相較其他兩種算法更加優(yōu)越。所得標(biāo)準(zhǔn)差中，SAMP-Jaya算法所得結(jié)果在10次中獲得較小值，HGA算法與HDTLBO算法分別在4種不同算例下取得最小值，所得結(jié)果表明SAMP-Jaya算法離散程度整體更加穩(wěn)定，算法具有良好的魯棒性。

以PD情況下40×6規(guī)模問(wèn)題為例，如圖6所示為其最大完工時(shí)間為1 380的最優(yōu)調(diào)度甘特圖,其中：括號(hào)內(nèi)數(shù)字為工件號(hào)，其余數(shù)字均為加工或設(shè)置時(shí)間。

3.3 SAMP-Jaya求解GPMSP-ST性能分析

為了驗(yàn)證SAMP-Jaya求解GPMSP-ST問(wèn)題的性能，本節(jié)以最大完工時(shí)間與能耗為雙目標(biāo)，在PSB情況下，采用20×8，40×8，60×8，80×8，100×8，120×8規(guī)模問(wèn)題，單位加工能耗在(10 J,30 J)中均勻分布，單位空載能耗在(1 J,5 J)中均勻分布。比較SAMP-Jaya算法與MO-Jaya算法，以及MENG等[27]提出的變鄰域結(jié)構(gòu)遺傳算法Ⅲ(Variable Neighborhood Structure Genetic Algorithm Ⅲ, VNSGAⅢ)在求解質(zhì)量和收斂性能兩個(gè)方面的效果。采用非支配解集數(shù)量(N)、非支配解集占參考解集比率(NR)、世代距離(GD)和反世代距離(IGD)4個(gè)指標(biāo)來(lái)評(píng)價(jià)3種算法所求非支配解集質(zhì)量的優(yōu)劣，后3項(xiàng)指標(biāo)定義如下：

(1)NR。該比率表示所衡量算法所獲得的非支配解占參考解集的比率。較大的NR值表示算法可以獲得更多最優(yōu)解，其計(jì)算公式為：

(12)

(2)GD。表示所測(cè)算法中非支配解集各點(diǎn)與參考解集的平均距離，其計(jì)算公式為：

(13)

式中：di表示Dj中第i個(gè)解到到D*中最近點(diǎn)的歐式距離，n表示Dj中解的個(gè)數(shù)。GD越小，算法性能越好?？紤]到兩個(gè)目標(biāo)量綱不同對(duì)指標(biāo)產(chǎn)生的影響，對(duì)目標(biāo)采用歸一化處理如式(14)所示：

(14)

(3)IGD。為綜合性測(cè)量指標(biāo)，表示參考解集中各點(diǎn)到所測(cè)算法中非支配解集之間的平均距離，其計(jì)算公式為：

(15)

式中：xi表示D*中第i個(gè)解到到Dj中最近點(diǎn)的歐式距離，n*表示D*中解的個(gè)數(shù)。對(duì)所有目標(biāo)值均采用歸一化處理。

對(duì)于各測(cè)試算例，將3種算法均獨(dú)立運(yùn)行15次，所得各指標(biāo)平均值如表6所示，3種算法所得最優(yōu)指標(biāo)加粗顯示。

表6 3種算法4項(xiàng)指標(biāo)對(duì)比

續(xù)表6

由表中測(cè)試結(jié)果可知，就N指標(biāo)而言，SAMP-Jaya算法在5種算例中取得最優(yōu)值，說(shuō)明該算法全局搜索能力更強(qiáng)，意味著更多種方案可供選擇；在NR、GD、IGD三種指標(biāo)中，SAMP-Jaya算法均表現(xiàn)良好。就NR指標(biāo)而言，SAMP-Jaya算法所有測(cè)試結(jié)果均等于或接近1，說(shuō)明該算法在各算例中所得非支配解大多數(shù)優(yōu)于其他算法的非劣解；以GD、IGD指標(biāo)而言，SAMP-Jaya算法在5種算例測(cè)試結(jié)果中均為最小值，說(shuō)明該算法所得非支配解集更加接近問(wèn)題真實(shí)Pareto前沿，相較于其他兩種算法收斂性能更佳。

以100×8的問(wèn)題為例，如圖7所示為3種算法所得非支配解集，由圖可知，相較其他兩種算法，SAMP-Jaya算法所求非劣解集在分布面上更加廣泛，分布均勻性更優(yōu)；MO-Jaya算法獲得13個(gè)非支配解，SAMP-Jaya算法獲得15個(gè)非支配，且其極端解均優(yōu)于MO-Jaya算法，說(shuō)明所設(shè)計(jì)自適應(yīng)多種群策略有助于提升算法的全局搜索能力。

如圖8所示為某次運(yùn)行時(shí)3種算法各目標(biāo)值的收斂曲線。SAMP-Jaya算法、VNSGAⅢ算法、MO-Jaya算法分別在140代左右、145代左右、160代左右時(shí)達(dá)到最優(yōu)值；SAMP-Jaya算法的初始解為(2 098,180.25)優(yōu)于VNSGAⅢ算法、MO-Jaya算法的初始解(2 120,180.88)、(2 150,180.96)，說(shuō)明所設(shè)計(jì)多規(guī)則初始化種群可以提升初始種群的質(zhì)量。綜上所述，SAMP-Jaya算法兩個(gè)目標(biāo)值收斂速度更快，收斂性更為優(yōu)異。根據(jù)圖7和圖8可知SAMP-Jaya算法的求解質(zhì)量和收斂性能更好。

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

在如今提倡綠色制造的生產(chǎn)背景下，本文建立了以最大完工時(shí)間和能耗為雙目標(biāo)的帶有設(shè)置時(shí)間的并行機(jī)調(diào)度模型。針對(duì)問(wèn)題模型，運(yùn)用一種二維實(shí)數(shù)編碼方案。為有效求解問(wèn)題，在Jaya算法的基礎(chǔ)上設(shè)計(jì)以下3種策略形成SAMP-Jaya算法：①采用多規(guī)則初始化種群來(lái)提升初始種群質(zhì)量；②提出多種群的策略提升算法的全局搜索性與局部開(kāi)發(fā)性，自適應(yīng)調(diào)整子種群數(shù)目提升算法收斂速度；③提出位置向量排序機(jī)制解決離散型變量更新問(wèn)題。經(jīng)過(guò)測(cè)試分析，從單目標(biāo)而言，將SAMP-Jaya算法與HGA算法和HDTLBO算法比較，證明了SAMP-Jaya算法的優(yōu)越性；進(jìn)而運(yùn)用SAMP-Jaya算法求解GPMSP-ST，并與MO-Jaya、VNSGAⅢ對(duì)比，驗(yàn)證了所設(shè)計(jì)策略有效地提升了算法求解質(zhì)量和收斂速度。

未來(lái)將從以下幾個(gè)方面展開(kāi)進(jìn)一步研究：①針對(duì)如機(jī)器故障，訂單緊急插入等不確定性因素下對(duì)初始調(diào)度方案作出調(diào)整，形成動(dòng)態(tài)調(diào)度；②本文所提種群初始化規(guī)則雖然改善了初始種群質(zhì)量，但效果并不突出，未來(lái)可利用啟發(fā)式規(guī)則作進(jìn)一步改善；③本文問(wèn)題模型中的工件僅需加工一道工序，針對(duì)多工序并行機(jī)問(wèn)題還需深入研究。