交換突變策略改進螢火蟲算法的異構并行機調度

羅冬梅，陳玲清，張瑀鑫，黃興旺

(集美大學計算機工程學院，福建 廈門 361021)

0 引言

經典的異構并行機調度問題(parallel machine scheduling problem，PMSP)[1]廣泛存在于科學和工業(yè)生產中，包括印刷電路板制造[2]、半導體晶圓制造[3]的切割操作等應用領域。在云計算[4]、邊緣計算[5]中通常還會涉及到作業(yè)排序的等待時間、作業(yè)數(shù)據傳輸時間等設置時間，并且由于設備的異構性，相當部分類型作業(yè)還會有序相關設置時間的異構并行機調度問題(the unrelated parallel machines scheduling problem，UPMSP)[1]。

在UPMSP問題中，優(yōu)化目標通常是最小化任務完工時間。大多數(shù)問題需要使用兩臺或多臺機器并行調度，在某些情況下，設置時間和處理時間同等重要，因而需要同等考慮。Paula等[6]第一次將可變鄰域搜索算法(variable neighborhood search，VNS)用于求解高維的序相關設置時間的UPMSP問題。Vallada等[7]提出一種基于局部搜索增強交叉算子的遺傳算法(genetic algorithm，GA)來求解UPMSP問題，該研究也考慮了機器和作業(yè)之間的序相關設置時間影響。Behnamian等[8]提出一個結合了蟻群(ant colony optimization，ACO)、模擬退火(simulated annealing，SA)和VNS算法的混合元啟發(fā)式算法，求解同樣考慮了序相關設置時間的UPMSP問題，使得任務完成時間最小化。Arnaout等的研究[8-9]使用增強的ACO算法在機器數(shù)多達10且作業(yè)數(shù)多達120的用例中求解序相關設置時間的UPMSP問題。Ezugwu 等[3]實現(xiàn)了一種改進的樽海鞘群算法(salp swarm algorithm，SSA)，得到與序列相關的UPMSP算法的新的復雜度結果。牛群等[10]基于改進的克隆選擇算法實現(xiàn)了含調整時間的并行機調度，其性能較遺傳算法和基本克隆選擇算法都有所提高。但是上述算法在高維情況下，搜索性能有所下降。

標準螢火蟲算法(firefly algorithm，F(xiàn)A)[11]具有超參數(shù)少、易實現(xiàn)等優(yōu)點，在連續(xù)域數(shù)值優(yōu)化問題中表現(xiàn)出了高效的性能。由于序相關設置時間UPMSP問題具有非確定多項式難的性質，求解難度大，而FA采用的吸引度因子存在快速減小情況，又容易面臨提前終止搜索、達到局部最優(yōu)的問題。為此，本文提出了一種基于交換突變策略改進的螢火蟲算法(improved firefly algorithm based on mutation strategy，IFAMS)用于求解具有序相關設置時間的UPMSP問題。

1 數(shù)學建模

1.1 問題描述

本文所改進的求偶學習的螢火蟲算法求解序相關設置時間的UPMSP問題描述如下：

a)該調度問題假定在時間零點有N個可用的作業(yè)待分配到M臺異構的機器上處理，機器之間相互獨立。

b)不存在搶占執(zhí)行作業(yè)情況。

c)數(shù)據集中，由Pj，k表示的機器k處理分配到的作業(yè)j所需的時間，和由Si，j，k給出的機器k上的作業(yè)i之后處理作業(yè)j的序相關設置時間，都是先驗和確定的。其中，i，j={1，2，…，N}，k={1，2，…，M}，通常Si，j，k≠Sj，i，k。

d)優(yōu)化目標為最小化任務完工時間Cmax，因此該模型可以用(Pj，k|Si，j，k|Cmax)表示。

1.2 模型構建

本文采用基于混合整數(shù)規(guī)劃(mixed integer programming，MIP)拓展的模型[1，3，7]來表示(Pj，k|Si，j，k|Cmax)模型，方便最小化任務完工時間Cmax的求解。為了描述該問題的數(shù)學模型，本文給出了部分符號定義：Cj—機器上最后一個作業(yè)j的完成時間；xi，j，k—在機器k上處理完作業(yè)i后立即處理作業(yè)j時為1，否則為0；x0，j，k—機器k首先處理作業(yè)j為1，否則為0；V—一個充分大的正數(shù)；APi，j，k—校正后的機器處理時間矩陣。

本文建立了(Pj，k|Si，j，k|Cmax)的數(shù)學模型為：

MinimizeCmax。

(1)

約束條件有：

5)Cj≤Cmax，?j=1，…，N；

6)C0=0；

7)Cj≥0，?j=0，…，N；

8)xi，j，k∈{0，1}，?i=0，…，N，?j=0，…，N，?k=1，…，M。

其中：公式(1)的目標是最小化任務完工時間；約束條件1)確保作業(yè)只會被執(zhí)行一次；約束條件2)表示每臺機器最先被處理的作業(yè)數(shù)為1；約束條件3)確保每個作業(yè)最先被處理或者構成其他作業(yè)的緊后處理作業(yè)；約束條件4)用于計算各個作業(yè)的完工時間；約束條件5)將Cmax定義為必須大于任何其他作業(yè)完成時間的變量；約束條件6)確保虛擬作業(yè)0的完成時間為0；約束條件7)確保作業(yè)完成時間非負；約束條件8)定義了決策變量x的取值范圍。

2 基于改進螢火蟲算法的UPMSP

2.1 標準螢火蟲算法

螢火蟲的熒光亮度(相互吸引度)可表示為：βi，j(ri，j)=β0e-γri，j2。其中：ri，j是兩只螢火蟲xi和xj之間的歐幾里德距離；β0表示初始吸引度因子，通常取值為1；參數(shù)γ表示光吸收系數(shù)的固定值，一般也取值為1。對于同一搜索空間隨機選取的兩只螢火蟲xi和xj，它們之間的距離

其中：D代表問題的維數(shù)；d表示處于螢火蟲位置向量的維數(shù)。

搜索過程中，螢火蟲xj受更亮的螢火蟲xi吸引，向xi移動，其位置更新方式為：xj(t+1)=xj(t)+βi，j(xi(t)-xj(t))+α。其中：t表示算法的迭代次數(shù)；α是步長參數(shù)，通常取值為[0，1]的隨機數(shù)；是[-0.5，0.5]之間的隨機數(shù)。

在FA的尋優(yōu)過程中，所有螢火蟲會向較亮的螢火蟲移動，最終螢火蟲個體將集結在最亮的螢火蟲周圍，完成尋優(yōu)過程。

2.2 改進FA算法

仔細分析FA算法中的吸引度因子β隨螢火蟲距離r的變化可知，當這兩個螢火蟲之間的距離r較大時，β隨r增加快速下降至近0，螢火蟲間的吸引度快速下降，個體之間無法充分地進行信息交互，此時FA算法面臨移動提前終止、螢火蟲種群進化出現(xiàn)停滯的情況。一旦陷入局部最優(yōu)，由于此時螢火蟲不具備變異特性，將無法跳出。

本文在FA框架[11]的基礎上，提出一種改進的螢火蟲算法。該算法通過引入交換突變策略，保證算法在距離r較遠時螢火蟲個體間仍有機會進行信息交互，從而跳出局部最優(yōu)，提高全局搜索能力。該算法既保持了FA原有的簡單結構，又能提高尋優(yōu)精度。

選擇種群中適應度函數(shù)值最小即最優(yōu)的螢火蟲cbest，應用交換突變策略進行操作，從而引入隨機漫游，增加種群多樣性，避免過早收斂。該操作過程的偽代碼如下所示：

Input: cbest 從整數(shù)1到D中無放回隨機均勻抽取2個值(i1和i2)作為突變位置 newbest=cbest; /*用cbest第i2維和第i1維的值分別對newbest的第i1維和第i2維進行交換*/ newbest([ i1i2])=cbest([ i2i1]); if f(newbest)

其中，cbest表示當前最優(yōu)解，D代表問題的維數(shù)，f(.)表示適應度函數(shù)。

基于上述操作，改進的螢火蟲算法IFAMS的完整搜索過程如下：

步驟1)采用均勻分布隨機生成Np只雄性螢火蟲作為初始種群{Xi|i=1，2，…，Np}；

步驟2)計算每只雄性螢火蟲的發(fā)光亮度；

步驟3)如果雄性螢火蟲Xj的亮度低于雄性Xi的亮度，則采用FA原來的移動策略更新雄性螢火蟲位置，并更新最優(yōu)解；

步驟4)執(zhí)行交換突變操作；

步驟5)判斷算法是否達到終止迭代的條件，若達到，則停止迭代，算法終止，否則返回并繼續(xù)執(zhí)行步驟3)。

2.3 IFAMS應用于含序相關設置時間的UPMSP

2.3.1 個體編碼表示

設計適當?shù)膫€體編碼方案，能夠增加IFAMS算法處理候選可行方案與螢火蟲個體之間的映射效率。基于文獻[1]，本研究設計了兩階段個體編碼表示方案處理該問題。

1)機器分配編碼

第一階段是機器分配過程，描述了將N個任務分配給M臺異構并行機，以使所有機器的最大完成時間Cmax最小的可行解，可用維數(shù)等于作業(yè)數(shù)的整數(shù)向量x表示。以10個作業(yè)、3個并行機的作業(yè)分配為例，若序列S1=[3，1，3，2，1，2，2，3，1，1]，則表示機器1分配到的作業(yè)序號為{2，5，9，10}，機器2分配到的作業(yè)序號為{4，6，7}，機器3分配到的作業(yè)序號為{1，3，8}。因此，這也要求IFAMS算法在迭代尋優(yōu)過程中需要采用floor(.)函數(shù)將IFAMS中螢火蟲的位置信息進行整數(shù)離散化。

2)序列調度編碼

第二階段則是確定每臺機器上的作業(yè)序列。該序列可以矩陣的形式表示，矩陣的長度與機器分配向量的長度相同。因此，作業(yè)序列S2可以表示為M×N矩陣，表明每臺機器上作業(yè)的執(zhí)行順序。以上文的例子為例，有

為方便求解任務完工時間，本文以校正后的處理時間矩陣APk替代兩個獨立階段的時間(機器處理時間P和序相關設置時間T)進行處理。APk可以表示為上述兩個階段耗時的線性組合，數(shù)學式為：AP=θ1×T+θ2×P。

為簡單起見，通常可取θ1=θ2=1，因而有：?j=1，2，…，N，?k=1，2，…，M；APi，j，k=Si，j，k+Pj，k，?i=1，2，…，N。代入式(1)中，可得序相關設置時間的UPMSP問題的優(yōu)化目標函數(shù)(即適應度函數(shù))為：

2.3.2 算法應用過程

在初始化階段，IFAMS算法首先將N個計劃內的作業(yè)隨機分配給M臺可用的處理機器，生成由Np只雄性螢火蟲個體構成的初始雄性螢火蟲種群(用矩陣X表示)。每只雄性螢火蟲個體對應于M×N矩陣中編碼后選定的特定機器上的作業(yè)序列。外部檔案A中的雌性螢火蟲種群可借由雄性螢火蟲種群初始化完成。

具體應用步驟如下：

步驟1)初始化。根據序相關設置時間UPMSP的數(shù)學模型和給定的機器處理時間、序相關設置時間的范圍，初始化改進求偶學習螢火蟲算法的各項參數(shù)。

步驟2)種群進化。IFAMS的種群進化過程如2.2節(jié)所述。

步驟3)當進化滿足停止條件時，輸出最優(yōu)雌性螢火蟲的相關信息作為近似最優(yōu)調度方案。

3 仿真實驗

為了驗證IFAMS算法在求解序相關設置時間的UPMSP問題上的有效性，本文采用大量的測試用例進行了驗證，所有實驗都是通過Matlab 2020a編程實現(xiàn)，在8.0 G RAM 3.6 GHz CPU的Windows環(huán)境下運行?；诟鱾€算法迭代生成過程的次數(shù)，將IFAMS算法在(Pj，k|Si，j，k|Cmax)問題中的性能表現(xiàn)與文獻中現(xiàn)有的一些元啟發(fā)式算法進行了比較，包括GA、SA及標準的FA算法。為了避免測試結果的隨機性，每種算法重復測試15次?？紤]到需要在可接受時間范圍內獲取可行解，因而選取最大迭代次數(shù)為1000次，Np=50，其他所有參數(shù)直接來自文獻[12]。考慮到求解任務調度方案的時間相較于執(zhí)行時間，比值較小，故而本文主要測試算法的求解精度，通過均值Mean和方差SD的大小來衡量。

3.1 測試用例

文獻[13]的測試數(shù)據集已應用于許多相關研究中[3，7，10，12-14]。該數(shù)據集包含兩個類別，即處理時間和設置時間，其數(shù)據都由離散的均勻分布U[50，100]隨機生成。

本研究生成的數(shù)據集包含N個作業(yè)和M個機器，有6種情況。每種情況中的機器數(shù)量分別為2、4、6、8、10 、12，作業(yè)數(shù)量范圍則分別在20、40、60、80、100、120之間。

3.2 實驗結果和性能比較

根據測試用例，本研究構造得到36組算例，這些算例分別在各個算法中運行，所得結果如表2所示。其中，每種算例情況的最優(yōu)值以黑色加粗標注，結果保留2位小數(shù)。由表2的數(shù)據分析可知：

表2 IFAMS算法與4種對比算法的性能比較Tab.2 Performance comparison between IFAMS algorithm and four comparison algorithms

1)從精度角度而言，IFAMS得到最優(yōu)Mean值的次數(shù)遠遠多于FA、GA和SA，說明本文提出的IFAMS算法非常適用于求解序相關設置時間的異構并行機調度問題，表明在FA框架基礎上引入交換突變策略的有效性。

2)IFAMS算法得到的結果與其他3種算法相比，能夠在36個算例中的28個取得最優(yōu)Mean值，并且隨著算例維數(shù)的增大，IFAMS取得最優(yōu)Mean值的頻次逐漸增加，表明IFAMS在處理較大規(guī)模的尋優(yōu)問題時其精度方面的性能優(yōu)勢顯著。此外，在SD值方面，IFAMS也較FA取得了較大提升，其尋優(yōu)穩(wěn)定性僅次于SA。

圖1和圖2展示了機器數(shù)分別為2和10的情況下，這4個算法在不同作業(yè)數(shù)的測試用例上的平均收斂曲線。分析圖1和圖2可知，IFAMS表現(xiàn)出的收斂速度和FA相似，優(yōu)于GA和SA。

4 結論

本文針對序相關設置時間UPMSP問題，提出了一種改進的求偶學習螢火蟲算法IFAMS，以最小化任務完工時間為調度優(yōu)化目標，求解序相關設置時間UPMSP問題。該算法引入交叉算子，在不引入額外參數(shù)的前提下，增強了螢火蟲距離較遠時的搜索表現(xiàn)，使算法能夠更加充分地利用種群社會信息，增強跳出局部最優(yōu)的能力，提升算法全局搜索性能。通過大量算例測試，結果表明本文所提出的調度算法在處理序相關設置時間UPMSP問題時是有效的，具有較高的收斂速度，同時精度方面相較于FA具有較大提升，相較GA和SA也有明顯的優(yōu)勢。

邊緣計算等應用場景的調度問題是調度研究的熱點，但目前還未有較為統(tǒng)一的模型標準，未來將繼續(xù)借鑒UPMSP模型，在考慮到帶寬、不同網絡服務提供商資費等更多約束的條件下進行研究，并提出高效算法進行求解。