求解異構(gòu)并行機(jī)調(diào)度問(wèn)題的混合煙花算法

石 慶 民

(新鄉(xiāng)學(xué)院人事處 河南 新鄉(xiāng) 453000)

0 引 言

異構(gòu)并行機(jī)調(diào)度(Unrelated parallel machine scheduling，UPMS)是實(shí)際生產(chǎn)制造過(guò)程中常見的一類調(diào)度問(wèn)題，具有廣泛的工程應(yīng)用背景，例如：云計(jì)算、半導(dǎo)體加工、紡織生產(chǎn)等[1-2]。傳統(tǒng)的UPMS問(wèn)題多以時(shí)間指標(biāo)為優(yōu)化目標(biāo)，如makespan、提前/拖期總和等?，F(xiàn)如今，低碳節(jié)能調(diào)度已成為實(shí)現(xiàn)低碳制造的重要途徑，并已引起社會(huì)各界的廣泛關(guān)注[3]。與此同時(shí)，快速響應(yīng)客戶需求也構(gòu)成了企業(yè)競(jìng)爭(zhēng)力的重要組成部分。因此，研究以能耗和延遲成本為目標(biāo)的UPMS問(wèn)題具有較高的理論意義和應(yīng)用價(jià)值。

UPMS已經(jīng)被證明是具有NP-hard性質(zhì)的組合優(yōu)化問(wèn)題，因而設(shè)計(jì)有效的求解算法成為這一領(lǐng)域的研究重點(diǎn)。目前，求解UPMS問(wèn)題的算法分為三類：精確求解算法、啟發(fā)式算法和現(xiàn)代優(yōu)化算法[4]。精確求解算法包括分枝定界、動(dòng)態(tài)規(guī)劃等，這類算法能夠獲得該問(wèn)題的精確解，但實(shí)用性較弱，無(wú)法在合理的時(shí)間內(nèi)求解中大規(guī)模算例[5]。啟發(fā)式算法是利用調(diào)度規(guī)則對(duì)問(wèn)題進(jìn)行快速求解，具有運(yùn)算時(shí)間短、求解精度較高等優(yōu)點(diǎn)，但該類算法對(duì)問(wèn)題的設(shè)置具有嚴(yán)格限制，通用性較差[6]。近年來(lái)，隨著現(xiàn)代優(yōu)化算法的快速發(fā)展，學(xué)者們逐步開始使用智能算法來(lái)求解這一問(wèn)題，相關(guān)算法包括遺傳算法、禁忌搜索算法、模擬退火算法等。研究表明，這類算法能夠在較短的時(shí)間內(nèi)獲得中大規(guī)模算例的滿意解，且具有較強(qiáng)的通用性[7]。因此，本文基于基本煙花算法(Firework algorithm,FWA)設(shè)計(jì)了改進(jìn)算法用于求解考慮節(jié)能的異構(gòu)并行機(jī)調(diào)度問(wèn)題。

FWA是Tan等[8]提出的新型現(xiàn)代優(yōu)化算法，屬于群智能優(yōu)化算法，該算法受煙花爆炸行為的啟發(fā)通過(guò)煙花爆炸生成火花這一過(guò)程實(shí)現(xiàn)迭代進(jìn)化。FWA具有收斂速度快、求解精度高等優(yōu)點(diǎn)，目前已經(jīng)在數(shù)據(jù)挖掘、神經(jīng)網(wǎng)絡(luò)訓(xùn)練、車輛路徑規(guī)劃等多個(gè)方面獲得了成功應(yīng)用[9]。即便如此，F(xiàn)WA在中大規(guī)模測(cè)試問(wèn)題的求解過(guò)程中仍然存在易陷入局部最優(yōu)、收斂速度慢等缺點(diǎn)。因此，提升FWA的尋優(yōu)性能仍然是該鄰域的一個(gè)重難點(diǎn)。

基于以上研究?jī)?nèi)容，本文考慮一類加工時(shí)間可控的并行機(jī)調(diào)度問(wèn)題，并以能耗和拖期懲罰成本為優(yōu)化目標(biāo)構(gòu)建了混合整數(shù)線性規(guī)劃(Mixed Integer Linear Programming,MILP)模型。算法設(shè)計(jì)中創(chuàng)建了特定的編解碼方法以表示問(wèn)題的解，同時(shí)融入了反向?qū)W習(xí)初始化方法以提升初始解的質(zhì)量，并構(gòu)建了基于變鄰域搜索算法的局部?jī)?yōu)化流程用以強(qiáng)化基本算法的尋優(yōu)性能。仿真測(cè)試中，利用正交實(shí)驗(yàn)對(duì)算法參數(shù)進(jìn)行校驗(yàn)，并將HFWA的優(yōu)化結(jié)果與多種經(jīng)典的優(yōu)化算法進(jìn)行比較，測(cè)試結(jié)果驗(yàn)證了HFWA的可行性和有效性。

1 問(wèn)題模型

1.1 問(wèn)題描述

在UPMS-ETC問(wèn)題中，假設(shè)有n個(gè)任務(wù)需要在m臺(tái)機(jī)器上加工，各個(gè)機(jī)器存在多種不同的加工速度，各機(jī)器在不同加工速度下的能耗存在差異性。此外，已知各個(gè)訂單的交貨期，晚于規(guī)定的時(shí)間交貨將會(huì)產(chǎn)生延遲懲罰成本。

本文以最小化所有任務(wù)的加工能耗成本和延遲懲罰成本總和為目標(biāo)，決策內(nèi)容包含以下三點(diǎn)：1) 各個(gè)機(jī)器所加工的任務(wù)集合；2) 各個(gè)機(jī)器上加工任務(wù)的排序；3) 各任務(wù)的加工速度。

1.2 數(shù)學(xué)建模

為了構(gòu)建UPMS-ETC問(wèn)題的MILP模型，定義以下數(shù)學(xué)符號(hào)。

問(wèn)題參數(shù)：

m：機(jī)器總數(shù)，i∈{1,2,…,m}。

n：任務(wù)總數(shù)，v∈{1,2,…,n}。

l：加工位置編號(hào)，l∈{1,2,…,n}，各臺(tái)機(jī)器均設(shè)有n個(gè)加工位置。

Qi：機(jī)器i可選的速度類別總數(shù)，s∈{1,2,…,Qi}。

lv：任務(wù)v的標(biāo)準(zhǔn)加工時(shí)間。

ris：機(jī)器i以第s種加工速度的取值。

tvis：任務(wù)v在機(jī)器i上以速度ris加工時(shí)相應(yīng)的加工時(shí)間，tvis=lv/ris。

eis：機(jī)器i在單位時(shí)間內(nèi)以速度ris運(yùn)行所產(chǎn)生的能耗。

dv：任務(wù)v的交貨期。

Cv：任務(wù)v的完成時(shí)間。

τv：任務(wù)v的延誤時(shí)間，τv=max{0,Cv-dv}。

μv：任務(wù)v單位時(shí)間的延誤懲罰成本。

決策變量：

xvils：0-1變量，任務(wù)v在機(jī)器i以速度ris進(jìn)行加工，xvils取值為1；否則，xvils取值為0。

Bil：機(jī)器i上位置l任務(wù)開始加工的時(shí)間。

基于以上問(wèn)題描述和符號(hào)定義，構(gòu)建了UPMS-ETC問(wèn)題的MILP模型。

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

(1)

約束條件：

(2)

(3)

(4)

τv≥Bi,l+tvis·xvils-(1-xvils)·M-dj
i∈{1,2,…,m},s∈{1,2,…,Qi},v∈{1,2,…,n},
l∈{1,2,…,n}

(5)

τv≥0v∈{1,2,…,n}

(6)

xvils∈{0,1},i∈{1,2,…,m},s∈{1,2,…,Qi},
v∈{1,2,…,n},l∈{1,2,…,n}

(7)

式(1)表示目標(biāo)函數(shù)，即所有任務(wù)的加工能耗成本和延誤懲罰成本之和；式(2)用于確保各個(gè)加工任務(wù)所選的加工機(jī)器、加工位置和加工速度的唯一性；式(3)表示各臺(tái)機(jī)器上每個(gè)加工位置處最多只能安排一個(gè)加工任務(wù)；式(4)用于計(jì)算機(jī)器i上位置l處加工任務(wù)的開始時(shí)間；式(5)-式(6)用于計(jì)算各個(gè)任務(wù)的延誤時(shí)間；式(7)定義了決策變量的取值范圍。

2 基本煙花算法

FWA以煙花表示待優(yōu)化問(wèn)題的解，并通過(guò)煙花爆炸生成火花這一過(guò)程迭代進(jìn)化。首先依據(jù)各煙花個(gè)體的評(píng)價(jià)函數(shù)值計(jì)算相應(yīng)的爆炸火花數(shù)目和爆炸半徑數(shù)值；其次，采用均分分布和高斯分布生成新個(gè)體；最后，利用選擇規(guī)則構(gòu)建新種群以進(jìn)入下一次迭代。具體實(shí)現(xiàn)步驟歸納如下：

Step1初始化算法參數(shù)，利用隨機(jī)方法構(gòu)建初始種群并對(duì)每個(gè)煙花個(gè)體進(jìn)行評(píng)價(jià)。

Step2依據(jù)評(píng)價(jià)函數(shù)計(jì)算當(dāng)前種群中各個(gè)煙花的爆炸火花數(shù)目和爆炸半徑。

Step3利用均分分布和高斯分布生成爆炸火花和高斯變異火花。

Step4利用煙花、爆炸火花和高斯變異火花構(gòu)建候選種群，并依據(jù)篩選規(guī)則生成新種群。

Step5判斷是否滿足終止條件。若滿足則停止迭代搜索并輸出當(dāng)前最優(yōu)解；否則，轉(zhuǎn)Step 2。

FWA的核心內(nèi)容包含以下四點(diǎn)：(1) 計(jì)算爆炸火花數(shù)目和爆炸半徑；(2) 生成爆炸火花；(3) 生成高斯變異火花；(4) 基于選擇規(guī)則構(gòu)建新種群。

計(jì)算爆炸火花數(shù)目和爆炸半徑：以N表示煙花數(shù)目，以xi表示當(dāng)前種群中的第i個(gè)煙花，N個(gè)煙花數(shù)目生成的爆炸火花總數(shù)記為SN。以最小化問(wèn)題為例，對(duì)于煙花xi，以符號(hào)fi表示其評(píng)價(jià)函數(shù)值，以Si和Ri表示由xi生成的爆炸火花數(shù)目和相應(yīng)的爆炸半徑。Si和Ri的計(jì)算公式歸納如下：

(8)

(9)

式中：fmax和fmin分別表示當(dāng)前煙花種群中最大和最小的評(píng)價(jià)函數(shù)值；A表示基本爆炸半徑，需要預(yù)先設(shè)定；ε為機(jī)器最小值，用以避免除零操作。同時(shí)，為了對(duì)上述Si計(jì)算公式做修正以確保優(yōu)勢(shì)煙花個(gè)體生成的火花數(shù)不過(guò)多、劣勢(shì)煙花個(gè)體生成的火花數(shù)不過(guò)少，修正公式為：

(10)

式中：常數(shù)a和b滿足0

生成爆炸火花：依據(jù)計(jì)算所得Si和Ri值，生成當(dāng)前煙花個(gè)體xi對(duì)應(yīng)的爆炸火花。以D表示待優(yōu)化問(wèn)題的維度，隨機(jī)選取維度集合{1,2,…,D}的一個(gè)子集Dz，利用式(11)更新xi的相應(yīng)維度的編碼數(shù)值取值生成新個(gè)體。

xiz←xiz·rand(-1,1) ?Z∈Dz

(11)

式中：rand(-1,1)表示區(qū)間[-1,1]的均分分布。

生成高斯變異火花：首先，利用隨機(jī)的方法從當(dāng)前種群中選擇GN個(gè)煙花；其次，對(duì)所選的各個(gè)煙花，隨機(jī)選擇一些維度并利用高斯分布進(jìn)行更新，以Dz表示所選煙花xi的一個(gè)維度子集。相應(yīng)的更新公式如下：

xiz←xiz·N(1,1) ?Z∈Dz

(12)

式中：N(1,1)表示均值為1、方差為1的高斯分布。

基于選擇規(guī)則構(gòu)建新種群：首先，將當(dāng)前煙花種群、爆炸火花種群和高斯變異火花種群合并，將其中最優(yōu)個(gè)體直接選入下一代種群；其次，依據(jù)輪盤賭規(guī)則選出其余N-1個(gè)解構(gòu)建新種群。以K表示候選種群規(guī)模，則其中第i個(gè)煙花解xi被選擇的概率取值為：

(13)

式中：d(xi,xj)表示個(gè)體xi和xj的距離。

此外在算法進(jìn)化中，變異操作往往使得新生成的煙花個(gè)體中某些維度的取值在規(guī)定的范圍之外，為此采用如下公式修復(fù)不可行解：

(14)

3 混合煙花算法

為了有效地求解UPMS-ETC問(wèn)題的數(shù)學(xué)模型，本文基于標(biāo)準(zhǔn)FWA構(gòu)建了HFWA。算法設(shè)計(jì)了雙層編碼方式和解碼方法，用于表示UPMS-ETC問(wèn)題的解；融入了反向?qū)W習(xí)初始化方法，致力于提升初始解的質(zhì)量；構(gòu)建了基于變鄰域搜索算法的局部?jī)?yōu)化流程，用以強(qiáng)化基本FWA的尋優(yōu)性能。

3.1 編碼與解碼

標(biāo)準(zhǔn)FWA采用實(shí)數(shù)編碼方式，無(wú)法直接用于求解離散組合優(yōu)化問(wèn)題。為此，本文結(jié)合問(wèn)題的性質(zhì)，構(gòu)建了UPMS-ETC問(wèn)題的編碼與解碼機(jī)制。

編碼過(guò)程：采用雙層實(shí)數(shù)編碼，兩層編碼長(zhǎng)度值均為n；編碼第一層用于各個(gè)機(jī)器的加工任務(wù)序列，各維度編碼的取值范圍為[1,m+1)；編碼第二層用于確定各任務(wù)在機(jī)器上的加工速度，各維度編碼的取值范圍為[0,1]。

UPMS-ETC問(wèn)題需要決策以下三點(diǎn)：(1) 各個(gè)機(jī)器所加工的任務(wù)集合；(2) 各個(gè)機(jī)器上加工任務(wù)的排序；(3) 各訂單的加工速度。相應(yīng)的解碼過(guò)程歸納如下：

? 取第一層編碼的整數(shù)部分，用于確定各任務(wù)的加工機(jī)器編號(hào)，進(jìn)而得到各個(gè)機(jī)器的加工任務(wù)集合。

? 基于各個(gè)機(jī)器的加工任務(wù)集合，取第一層編碼的小數(shù)部分用于確定各個(gè)機(jī)器上的任務(wù)加工順序，小數(shù)部分取值小所對(duì)應(yīng)的加工任務(wù)優(yōu)先加工。

? 針對(duì)各個(gè)機(jī)器，構(gòu)建選擇加工速度的輪盤賭模型，并依據(jù)輪盤賭規(guī)則確定各個(gè)機(jī)器所分得的加工任務(wù)的加工速度。如圖1所示，假設(shè)某一機(jī)器共有三種不同的加工速度，則當(dāng)該任務(wù)對(duì)應(yīng)第二編碼的數(shù)值在區(qū)間[0,1/3)上，則采用加工速度1；若其數(shù)值在區(qū)間[1/3,2/3)上，則采用加工速度2；若其數(shù)值在區(qū)間[2/3,1]上，則采用加工速度3。

圖1 基于輪盤賭規(guī)則的加工速度選擇

為了清晰地說(shuō)明該編解碼方法，給出如下算例：任務(wù)總數(shù)為8，機(jī)器總數(shù)為3，機(jī)器1和機(jī)器3具有3種加工速度，機(jī)器2具有兩種加工速度。已知如下編碼：第一層(3.19,1.80,2.97,2,90,1.47,1.35,2.45,3.78)，第二層(0.13,0.05,0.84,0.93,0.20,0.48,0.15,0.83)，圖2給出了完整的解碼過(guò)程。

(a)

(b)

(c)

3.2 反向?qū)W習(xí)初始化方法

基本FWA采用隨機(jī)的方法構(gòu)建初始種群，一定程度上限制了算法的優(yōu)化性能。為此，本文利用反向?qū)W習(xí)初始化方法構(gòu)建初始解，力求提升初始種群的質(zhì)量[10]。該方法的基本思路為：借助隨機(jī)方法生成多個(gè)初始解和相應(yīng)的反向解，結(jié)合評(píng)價(jià)函數(shù)進(jìn)行篩選，選取較優(yōu)的解構(gòu)造初始種群。結(jié)合以上描述，反向?qū)W習(xí)初始化方法的實(shí)現(xiàn)步驟歸納如下：

Step1令i←1，d←1，轉(zhuǎn)Step 2。

Step2若i≤N，轉(zhuǎn)Step 3；否則，轉(zhuǎn)Step 7。

Step3若d≤D，轉(zhuǎn)Step 4；否則，轉(zhuǎn)Step 5。

Step5令d←d+1，若d>D，轉(zhuǎn)Step 6,否則，轉(zhuǎn)Step 3。

Step6令i←i+1，轉(zhuǎn)Step 2。

3.3 基于變域搜索算法的局部?jī)?yōu)化流程

在算法迭代后期，基本FWA存在尋優(yōu)性能不佳、易陷入局部最優(yōu)的缺點(diǎn)。為此，本文基于變域搜索算法構(gòu)建了局部?jī)?yōu)化流程，力求增強(qiáng)基本FWA的性能[11]。

變域搜索算法通過(guò)系統(tǒng)地改變當(dāng)前解以拓展算法的搜索范圍，進(jìn)而獲得待優(yōu)化問(wèn)題的局部最優(yōu)解；同時(shí)，基于此局部最優(yōu)解，再次系統(tǒng)地進(jìn)行解空間的拓展，力求獲得另一局部最優(yōu)解。圖3為變鄰域搜索算法的示意圖。

圖3 變鄰域搜索算法示意圖

鄰域結(jié)構(gòu)設(shè)計(jì)構(gòu)成了變鄰域搜索算法的一項(xiàng)核心內(nèi)容，對(duì)于當(dāng)前研究的PMS-CPT問(wèn)題，本文采用交換和翻轉(zhuǎn)兩種鄰域結(jié)構(gòu)實(shí)現(xiàn)從當(dāng)前解到新解的變換，具體描述如下：

? 交換變異：隨機(jī)選擇當(dāng)前解編碼的兩處位置，交換這兩處位置上的編碼數(shù)值生成新解。

? 翻轉(zhuǎn)變異：隨機(jī)選擇當(dāng)前解編碼的兩處位置，翻轉(zhuǎn)這兩處位置間的編碼數(shù)值生成新解。

圖4所示的鄰域結(jié)構(gòu)示意圖清晰地說(shuō)明了以上兩種變異算子。當(dāng)前編碼方法中，編碼第一層用于各個(gè)機(jī)器的加工任務(wù)序列，編碼第二層用于確定各任務(wù)在機(jī)器上的加工速度。因此，以上鄰域變換能夠?qū)Ω纳频慕猱a(chǎn)生擾動(dòng)，探索其周圍的解。

圖4 鄰域結(jié)構(gòu)示意圖

由編解碼方法可知，編碼第一層用于各個(gè)機(jī)器的加工任務(wù)序列，編碼第二層用于確定各任務(wù)在機(jī)器上的加工速度。因此，以上鄰域變換能夠?qū)Ξ?dāng)前解產(chǎn)生擾動(dòng)，從而探索當(dāng)前解附近的其他解。

3.4 混合煙花算法流程

Step1初始化算法各參數(shù)，利用反學(xué)習(xí)初始化方法生成初始解，并對(duì)每個(gè)煙花個(gè)體進(jìn)行評(píng)價(jià)。

Step2依據(jù)評(píng)價(jià)函數(shù)計(jì)算當(dāng)前種群中各個(gè)煙花的爆炸火花數(shù)目和爆炸半徑。

Step3利用均分分布和高斯分布生成爆炸火花和高斯變異火花。

Step4利用煙花、爆炸火花和高斯變異火花構(gòu)建候選種群，并依據(jù)篩選規(guī)則生成新種群。

Step5對(duì)于各個(gè)煙花個(gè)體，利用基于變域搜索算法的局部?jī)?yōu)化流程進(jìn)一步改善其性能。

Step6判斷是否滿足終止條件。若滿足則停止迭代搜索并輸出當(dāng)前最優(yōu)解；否則，轉(zhuǎn)Step 2。

4 仿真測(cè)試

4.1 實(shí)驗(yàn)準(zhǔn)備

在MATLAB 2015a平臺(tái)上進(jìn)行仿真測(cè)試，設(shè)備參數(shù)為1.6 GHz、內(nèi)存8 GB、Intel Core i5-8250U CPU，并利用CPLEX 12.4和CPLEX-MATLAB接口求解UPMS-ETC問(wèn)題的MILP模型，CPLEX最大求解時(shí)間設(shè)置為3 600 s?？紤]到難以從現(xiàn)有文獻(xiàn)中獲取與當(dāng)前UPMS-ETC問(wèn)題相似的測(cè)試算例，本文依據(jù)相關(guān)機(jī)器調(diào)度問(wèn)題生成方法采用隨機(jī)方法構(gòu)建測(cè)試算例集，具體包括小規(guī)模和中大規(guī)模兩類算例[12]。

在小規(guī)模算例中，機(jī)器數(shù)目m∈{2,3}，任務(wù)數(shù)目n∈{5,8,10,12,15}，共計(jì)10個(gè)算例；在中大規(guī)模算例中，機(jī)器數(shù)目m∈{2,3,5}，任務(wù)數(shù)目n∈{20,40,60,80,100}，共計(jì)15個(gè)算例。對(duì)于算例(m,n)，其他參數(shù)設(shè)置如下：

? 任務(wù)的標(biāo)準(zhǔn)加工時(shí)間lv在均分分布U(50,200)上隨機(jī)產(chǎn)生；

? 任務(wù)v單位時(shí)間的拖期成本μv的數(shù)值在均分分布U(0.1,1)上隨機(jī)產(chǎn)生；

? 加工速度類型總數(shù)Qi均設(shè)置為5，加工速度ris在均分分布U(1,20)上隨機(jī)產(chǎn)生；

? 各機(jī)器在不同速度下的能耗參數(shù)eis在均分分布U(0.1,2)上隨機(jī)產(chǎn)生，且對(duì)于同一機(jī)器而言，加工速度越快，其能耗越高；

? 任務(wù)v的交貨期dv在均分分布U(D,3·D)上隨機(jī)產(chǎn)生，參數(shù)D的計(jì)算公式為：

(15)

為了驗(yàn)證算法的有效性，將本文提出的HFWA與多種優(yōu)化算法進(jìn)行比較，包括：FWA、粒子群算法(Particle swarm optimization, PSO)和蜂群算法(Artificial bee colony, ABC)。其中，與基本FWA進(jìn)行對(duì)比用于加入改進(jìn)方法后對(duì)標(biāo)準(zhǔn)算法性能的改善；與此同時(shí)，PSO與ABC算法作為目前較優(yōu)秀的優(yōu)化算法，其進(jìn)化機(jī)理和HFWA存在些許差異，因而同這兩種算法進(jìn)行對(duì)比能夠凸顯HFWA的競(jìng)爭(zhēng)力。對(duì)于各個(gè)測(cè)試算例，以上四種算法均獨(dú)立運(yùn)行15次，對(duì)測(cè)試結(jié)果進(jìn)行統(tǒng)計(jì)分析，采用最優(yōu)相對(duì)偏差(RPDb)和平均相對(duì)偏差(RPDm)作為評(píng)價(jià)指標(biāo)[13]，公式定義如下：

(16)

(17)

4.2 參數(shù)校驗(yàn)

表1 正交試驗(yàn)參數(shù)設(shè)置

表2 正交試驗(yàn)仿真結(jié)果

表3 正交試驗(yàn)極差分析

由以上測(cè)試結(jié)果可知，局部搜索參數(shù)LS和高斯變異參數(shù)GN對(duì)HFWA的性能影響最大，其次是參數(shù)爆炸火花參數(shù)SN和基本爆炸半徑A，最后是種群規(guī)模N。據(jù)此可知這表明局部?jī)?yōu)化算子和高斯變異對(duì)算法的優(yōu)化性能具有重要影響，因而需要合理設(shè)置LS和GN，若取值過(guò)大將使算法過(guò)分注重局部搜索，若取值過(guò)小則弱化了算法的挖掘能力。與此同時(shí)，其余三個(gè)參數(shù)也需要進(jìn)行合理設(shè)置，才能使HFWA達(dá)到最優(yōu)的搜索性能。各參數(shù)取值歸納如下：N=30，SN=10，GN=30，A=0.6，LS=10。

類似地，借助正交實(shí)驗(yàn)進(jìn)行小規(guī)模情況下的HFWA參數(shù)校驗(yàn)，算法取值歸納如下：N=10，SN=5，GN=20，A=0.6，LS=5。為了確保對(duì)比的公平性，F(xiàn)WA各參數(shù)取值與FWFA相同，PSO和ABC的種群規(guī)模與HFWA相同，其余參數(shù)采用相似方法進(jìn)行校驗(yàn)。小規(guī)模情形下PSO和ABC的其他參數(shù)設(shè)置如下：PSO權(quán)重系數(shù)為1.0，全局學(xué)習(xí)參數(shù)取值為1.5，自身歷史最優(yōu)學(xué)習(xí)參數(shù)2.0，ABC偵察蜂步數(shù)為10；中大規(guī)模情形下PSO和ABC的其他參數(shù)設(shè)置如下：PSO權(quán)重系數(shù)為0.95，全局學(xué)習(xí)參數(shù)取值為1.8，自身歷史最優(yōu)學(xué)習(xí)參數(shù)2.0，ABC偵察蜂步數(shù)為20。

4.3 算法對(duì)比

結(jié)合以上參數(shù)校驗(yàn)的結(jié)果，分別采用HFWA、FWA、PSO和ABC四種優(yōu)化算法對(duì)各個(gè)小規(guī)模算例進(jìn)行求解，測(cè)試結(jié)果見表4和表5。其中Minsol表示CPLEX所得目標(biāo)函數(shù)的最優(yōu)解，計(jì)算時(shí)長(zhǎng)則為CPLEX求解各個(gè)算例的耗時(shí)。表格最后一行優(yōu)勝率表示某一測(cè)試算的RPDm指標(biāo)在所有測(cè)試算例中獲得最優(yōu)性能的比率，例如“2/10”表示對(duì)應(yīng)的算法在共計(jì)10組測(cè)試算例中兩次獲得最優(yōu)RPDm值。此外，對(duì)于各個(gè)算例，以符號(hào)表示某一算法15次運(yùn)行結(jié)果相對(duì)偏差百分比的標(biāo)準(zhǔn)差，圖5給出了各算法在不同算例中的δ取值。

表4 小規(guī)模算例測(cè)試結(jié)果1

表5 小規(guī)模算例測(cè)試結(jié)果2

圖5 小規(guī)模算例方差對(duì)比

由測(cè)試結(jié)果可知，在小規(guī)模算例中，各個(gè)測(cè)試算法的性能都較為良好，RPDb指標(biāo)均能達(dá)到0，即能夠獲得小規(guī)模算例的精確解。就RPDm指標(biāo)而言，HFWA的性能最優(yōu)，其優(yōu)勝率為10/10。由圖5可知，HFWA在多數(shù)情形下具有較小的δ值，表明其具有較強(qiáng)的魯棒性，算法優(yōu)化結(jié)果更為穩(wěn)定。此外，由CPLEX計(jì)算時(shí)長(zhǎng)參數(shù)可知，隨著問(wèn)題規(guī)模的擴(kuò)大，求解MILP模型所需的時(shí)間急劇增加，算例(3,15)的計(jì)算時(shí)長(zhǎng)達(dá)到2 670.20 s，因此有必要設(shè)計(jì)高效的智能算法來(lái)求解UPMS-ETC問(wèn)題。

進(jìn)一步地，利用HFWA、FWA、PSO和ABC四種測(cè)試算法求解各種大規(guī)模算例，測(cè)試結(jié)果見表6和表7。其中Minsol表示表示四種算法在共計(jì)60次仿真中所得最優(yōu)解。對(duì)于各個(gè)算例，圖6給出了各算法在不同算例中的δ取值。

表6 中大規(guī)模算例測(cè)試結(jié)果1

續(xù)表6

表7 中大規(guī)模算例測(cè)試結(jié)果2

圖6 中大規(guī)模算例方差對(duì)比

由測(cè)試結(jié)果可知，四種算法中，HFWA表現(xiàn)值最優(yōu)秀，其RPDb指標(biāo)均為0，表明HFWA能夠獲得各個(gè)算例的已知最優(yōu)解。就RPDm指標(biāo)而言，HFWA的性能最優(yōu)，其優(yōu)勝率為12/15，表明本文算法在15組測(cè)試算例中12次獲勝；在剩余三組算例中，HFWA的表現(xiàn)同樣較為優(yōu)秀，與最優(yōu)RPDm值較為接近。此外，由圖6可知，HFWA在多數(shù)情形下具有較小的δ值，表明算法優(yōu)化結(jié)果更為穩(wěn)定，即算法具有較強(qiáng)的魯棒性。

5 結(jié) 語(yǔ)

本文以加工時(shí)間可控的UPMS問(wèn)題為研究對(duì)象，構(gòu)建了該問(wèn)題的MILP模型，并提出了HFWA求解算法以最小化作業(yè)期間的能耗和延遲懲罰成本總和。算法設(shè)計(jì)中，創(chuàng)建了特定的編解碼方法以表示問(wèn)題的解，同時(shí)融入了反向?qū)W習(xí)初始化方法以提升初始解的質(zhì)量，并構(gòu)建了基于變鄰域搜索算法的局部?jī)?yōu)化流程用以強(qiáng)化基本算法的尋優(yōu)性能。在實(shí)驗(yàn)部分，借助正交實(shí)驗(yàn)對(duì)算法參數(shù)進(jìn)行校正，并將HFWA與多種智能優(yōu)化算法進(jìn)行對(duì)比，結(jié)果表明本文構(gòu)建的HFWA能夠快速、有效地求解UPMS-ETC問(wèn)題，并具有顯著的優(yōu)越性。