考慮惡化效應(yīng)的MapReduce模型下的同類機調(diào)度

黃基誕

(東華大學(xué)旭日工商管理學(xué)院,上海 200051)

1 引言

許多經(jīng)典的排序問題研究文獻中都假定工件的加工時間是一個常數(shù)[1].而在現(xiàn)實生產(chǎn)制造業(yè)中,尤其在玻璃、醫(yī)療、塑料、鋼鐵等行業(yè)中,工件的加工時間經(jīng)常根據(jù)不同的開工時間而改變.在調(diào)度問題中,部分工件的加工處理時間可能隨著其開工時間的推后而延長,這類工件被稱為惡化工件.PEI等[2]研究的惡化效應(yīng)是指工件實際加工時間與資源數(shù)量有線性依賴關(guān)系的調(diào)度問題,在改進的蝙蝠算法中,利用變鄰域搜索策略對算法進行改進并對問題進行求解.Ding等[3]研究了工件實際加工時間與加工順序產(chǎn)生惡化效應(yīng)的調(diào)度問題.此外,文獻[4–7]研究的惡化效應(yīng)是指實際加工處理時間是起始開工時間的線性函數(shù).Jafari等[8]以工件實際加工處理時間是其開工前等待時間呈線性關(guān)系為惡化效應(yīng)的單機調(diào)度問題,研究了以最小延遲工件數(shù)為優(yōu)化目標,并運用了分支界定法對問題進行求解.與文獻[8]類似,本文考慮的惡化效應(yīng)調(diào)度模型是指實際加工時間與開工前等待時間具有線性不減函數(shù)關(guān)系.

MapReduce是谷歌公司提出的云計算中具有并行處理的核心計算模型.最初MapReduce源于計算機領(lǐng)域的大數(shù)據(jù)處理模型,就是在云平臺上首先對數(shù)據(jù)分而治之,即先將大任務(wù)分解成許多子任務(wù)處理(Map),第2步將這些子任務(wù)合起來處理(Reduce).由于生產(chǎn)制造企業(yè)里某些工件的加工和大數(shù)據(jù)處理具有相似之處,因此,本文將該模型拓展并用于制造業(yè)中工件的加工調(diào)度問題.具體的,MapReduce模型中的工件加工必須經(jīng)過Map和Reduce兩道工序.根據(jù)加工調(diào)度模型特點作如下陳述[9–11]:1)每個工件的加工需經(jīng)過兩道工序,即Map工序和Reduce工序;2)在第1道工序(Map工序)中,一個工件可以分割成多個任務(wù)并行加工,即每個工件可以分割為多個子任務(wù)并在多臺機器上同時加工;3)當該工件在第1道工序中所有子任務(wù)全部加工完成后,方可啟動該工件的第2道工序;4)第2道工序(Reduce工序)是一個整合的過程,每個工件只能在一臺機器上連續(xù)加工直至完成.在實際生活中也能經(jīng)常遇見關(guān)于MapReduce模型的加工制造情形.例如鋼絲繩、錨鏈制造企業(yè).如圖1所示,一根粗的鋼絲繩由若干個細的鋼絲繩合在一起擰成.在Map階段(第1階段),若干根細的鋼絲繩可以分別在幾臺機器上同時加工;在Reduce階段(第2階段),只能在其中某一臺機器上將Map階段完成的細鋼絲繩合成制作為一根粗的鋼絲繩.而在實際生產(chǎn)過程中,工件加工具有惡化效應(yīng)時有發(fā)生,其中工件在每個階段的加工中惡化情形也不相同,因此,這類都是MapReduce模型調(diào)度需考慮的影響因素.

圖1 鋼絲繩制造示意圖Fig.1 Schematic diagram of wire rope manufacture

關(guān)于MapReduce模型的調(diào)度研究已引起國內(nèi)外學(xué)者高度關(guān)注,一部分學(xué)者研究了MapReduce問題的在線調(diào)度算法[9–10],而更多的文獻則借助混合整數(shù)規(guī)劃等方法來研究MapReduce模型調(diào)度問題.黃基誕等[11]研究了MapReduce模型下具有安裝(準備)時間的平行機調(diào)度問題,利用改進正余弦算法進行求解.Ling等[12]探討了MapReduce模型中不同級別的任務(wù),通過建立混合整數(shù)規(guī)劃模型來分析問題.而大部分學(xué)者針對MapReduce模型的研究則是關(guān)于大數(shù)據(jù)的處理方面[13–15],即研究大數(shù)據(jù)在多臺PC服務(wù)器上加工的時候進行分割(Map)并行處理,然后歸攏(Reduce)的一個過程.針對大數(shù)據(jù)加工處理的調(diào)度問題,對數(shù)據(jù)可以任意大小分割,沒有大小限定,而本文是將MapReduce模型與實際生產(chǎn)制造企業(yè)相結(jié)合,考慮到實際制造企業(yè)中的每個工件分割的數(shù)量由工件本身屬性而定,因此難以做到任意分割.此外,也有學(xué)者研究了帶任務(wù)分割的平行機調(diào)度問題[16],建立了混合整數(shù)規(guī)劃模型,并利用分支定界法和差分算法進行求解.

平行機調(diào)度問題本身就屬于NP難,主要以設(shè)計元啟發(fā)式算法,如遺傳算法[1]、正余弦算法[11]、蛙跳算法[17]等為求解思想.其中蝙蝠算法(bat algorithm,BA)是模擬自然界中蝙蝠利用回聲定位捕食原理的智能仿生優(yōu)化算法[18],同時該算法具有數(shù)學(xué)模型簡單、并行處理和收斂速度快等優(yōu)點,主要用于求解連續(xù)函數(shù)的優(yōu)化問題.近期陸續(xù)有學(xué)者將其拓展用于求離散型方面的優(yōu)化問題,張文鵬等[19]將蝙蝠算法加入GT算法,同時引入變鄰域搜索策略來求解車間調(diào)度問題.但是該算法應(yīng)用集中于流水車間的調(diào)度問題[20–21],戚遠航等[22]針對多車場車輛路徑問題提出一種泰森多邊形的離散蝙蝠算法.因此,本文將對該算法的應(yīng)用進行拓展,用于求解帶有惡化效應(yīng)的MapReduce模型下同類機調(diào)度問題.

綜上所述,MapReduce模型調(diào)度問題與經(jīng)典的流水車間調(diào)度和可拆分平行機調(diào)度問題不同,可歸納為:流水車間調(diào)度問題一般考慮工件不可分割;而可拆分平行機調(diào)度模型中通常假設(shè)只有一個工序.但是,在MapReduce模型中,每個工件有兩道加工工序,且第1道工序中可將一個工件分割成若干個子任務(wù)并行加工.此外,該模型與傳統(tǒng)具有惡化效應(yīng)的同類機調(diào)度不同,傳統(tǒng)的具有惡化效應(yīng)的同類機調(diào)度問題中,工件加工雖具有惡化效應(yīng),但通常一個工件有且只有一個固定惡化加工時間.而MapReduce模型里同一工件上分配在每臺機器上的Map子任務(wù)大小不同,且Map子任務(wù)在各自分配的機器上開工時間也不相同,因此造成不同機器加工同一工件拆分的Map子任務(wù)的加工時間具有差異,因此,該模型比經(jīng)典的具有惡化效應(yīng)的平行機調(diào)度更加復(fù)雜,在數(shù)學(xué)模型建立和算法設(shè)計上將會更具挑戰(zhàn).

2 問題建模

2.1 問題描述

假設(shè)有M臺同類機(每臺機器m具有各自加工速度vm,而且加工速度vm與工件類型無關(guān))加工N個工件,工件i的下達(釋放)時間為ri,每個工件i均包含Map和Reduce兩道工序,其中Map工序包含ni個單位子任務(wù)(即Map部分的工件可最多分割為ni個單位子任務(wù)),各Map子任務(wù)沒有嚴格的先后加工順序,拆分的Map子任務(wù)可同時在不同的機器上加工.每個工件i的Map工序單位子任務(wù)正常加工時間長度為Reduce工序正常加工時間長度由于工件的Reduce工序必須在該工件Map工序中所有子任務(wù)完成后才可以啟動,且只能在一臺機器上加工同時工件在該工序中不能分割.工件i實際加工時間是關(guān)于開工時間的線性不減函數(shù),工件在Map工序和Reduce工序中的加工時間隨著等待時間延長而線性増加,出現(xiàn)惡化效應(yīng).因此,為了減少生產(chǎn)中的惡化效應(yīng),本文設(shè)計一個調(diào)度方案以滿足所有工件從釋放到完成的逗留時間和最小.

此模型主要決策的內(nèi)容如下:1)Map部分分割的子任務(wù)的個數(shù)及各個子任務(wù)的大小;2)Map部分各子任務(wù)在機器上的分配方案;3)Reduce工序在機器上的分配.

2.2 任務(wù)分割的優(yōu)勢分析

現(xiàn)通過一個例子來說明任務(wù)分割的優(yōu)勢.例如有2臺機器處理3個工件(按釋放時間排序),為便于描述,假設(shè)2臺機器加工速度一致vm1,

其中:未進行任務(wù)分割的最優(yōu)調(diào)度(見圖2),完成時間為33;而進行任務(wù)分割的最優(yōu)調(diào)度(見圖3),完成時間為26;時間節(jié)約7,最后完成時間節(jié)約21%.因此任務(wù)分割可以有效的提高生產(chǎn)效率.接下來本文將研究的Map任務(wù)分割和加工任務(wù)分配方案.

圖2 未進行任務(wù)分割的最優(yōu)調(diào)度Fig.2 Scheduling without task splitting

圖3 進行任務(wù)分割的最優(yōu)調(diào)度Fig.3 Scheduling with task splitting

2.3 模型假設(shè)

問題基于以下基本假設(shè):

1)在任意時刻每臺機器只能加工一個Map工序子任務(wù)或Reduce工序(即機器同一時刻不能加工兩個任務(wù));

2)任何工序在加工過程中均不可中斷;

3)每臺機器都有各自恒定的加工速度;

4)允許機器在加工過程中出現(xiàn)空閑;

5)在同一臺機器上處理同一個工件的同一種任務(wù)應(yīng)連續(xù)加工;即同一個工件的同種任務(wù)中間不許有其他工件的任務(wù).

2.4 參數(shù)符號

本文其他所使用的符號如下: i,j:工件編號;?:機器集合;M為機器的數(shù)量;m,k表示機器的編號,k ∈?,?{1,2,···,M};I:工件集合;N為最后一個加工任務(wù);i,j ∈I,I{1,2,···,N};H:Map工序子任務(wù)或Reduce工序在機器上的加工位置集合;如果所有的Map工序和Reduce工序都在一臺機器上加工,那么位置最多為2N,即H{1,2,3,···,2N};h:Map工序子任務(wù)或Reduce工序在機器上的加工位置,h1,2,3,···,2N,h ∈H;ri:工件i的釋放時間;αi:在Map 階段工件i 的惡化系數(shù);βi:在Reduce階段工件i的惡化系數(shù);vm:機器m的加工速度為vm;L:一個足夠大的正數(shù).

2.5 決策變量

以下是決策變量:

1)xh,i,m∈{0,1}:如果工件i的Map工序子任務(wù)在機器m上的第h個位置加工,則xh,i,m1;否則為0.

2)yh,i,m:工件i的Map工序在機器m上的第h個位置加工量或子任務(wù)數(shù)量.

3)zi,m∈{0,1}:如果工件i的Map工序在機器m上加工,則zi,m1;否則為0.

4)Qi,m:工件i的Map工序在機器m上加工的子任務(wù)數(shù)量.

5)Ri,h,m∈{0,1}:如果工件i的Reduce工序在機器m上的第h個位置執(zhí)行,則Ri,h,m1;否則為0.

6)δi,m∈{0,1}:如果工件i的Reduce工序在機器m上加工,則δi,m1;否則為0.

13)pi,m:工件i的Map工序惡化加工時間.如果工件i的Map工序子任務(wù)在機器m上加工,那么單位任務(wù)實際加工時間與其開工前等待時間的長度呈線性遞增關(guān)系,

2.6 目標函數(shù)

本文考慮的問題模型以最小化所有工件逗留時間和為目標:

在實際生產(chǎn)問題中存在許多MapReduce模型的特性和約束,而本文模型中的約束用數(shù)學(xué)刻畫如下:

處理時間約束:

式(2)表示最大完工時間不小于每個工件的Reduce工序完成時間.式(3)表示工件i的Map工序完成時間必須不早于該工序的每個分割子任務(wù)完成時間.式(4)表示工件i的Reduce工序開始時間不得早于Map工序的完成時間.式(5)表示工件i的Reduce工序在同類機m上加工的完成時間和開始時間的關(guān)系.式(6)表示工件i的Map工序在同類機m上分配的任務(wù)開始加工時間必須大于等于工件釋放時間.式(7)表示工件i的Map工序在各同類機m上分配的任務(wù)量、加工開始時間與加工結(jié)束時間之間的關(guān)系.式(8)–(9)表示工件i的Map工序在同類機m的位置h上開始加工時間,必須大于等于前一個位置h ?1上加工的Map或Reduce的完成時間.式(10)–(11)表示工件i的Reduce工序在同類機m的位置h上開始加工時間,必須大于等于前一個位置h ?1上加工的Map或Reduce的完成時間.式(12)如果工件i的Map工序子任務(wù)在同類機m上加工,那么子任務(wù)的實際加工時間是關(guān)于開工時間的線性不減函數(shù).式(13)如果工件i的Reduce工序任務(wù)在同類機m上加工,則實際加工時間是關(guān)于其開工時間的線性不減函數(shù).

任務(wù)分配約束:

式(14)–(15)表示工件i的Map工序加工機器的選擇及加工工作量的相互關(guān)系.式(16)–(18)表示工件i的Map工序在機器m上的同一個位置上只加工一次.式(19)表示工件i的Map工序在m機器上的加工量應(yīng)與該機器上分配的工作量一致.式(20)表示工件i的Map工序工作量等于該工件分配給所有機器的Map工序子任務(wù)工作量之和.式(21)–(24)表示工件i的Reduce工序只能在機器m上加工,并且只能加工一次.式(25)表示在機器m的位置h上安排Map工序任務(wù)量的上下限約束.式(26)表示在機器m的h位置上只能安排某一工件的一個任務(wù).式(27)表示在平行機m上安排任務(wù)的位置是連續(xù)的.式(28)表示決策變量的取值范圍.

3 蝙蝠算法

本文提出的混合整數(shù)規(guī)劃模型在小數(shù)據(jù)量算例可以用CPLEX軟件進行精確求解,然而在數(shù)據(jù)規(guī)模較大的時CPLEX無法在合理的時間內(nèi)求取最優(yōu)解,因此可借助智能優(yōu)化算法求其近似解.蝙蝠算法(BA)是通過模擬自然界中的蝙蝠利用自身發(fā)出聲波的響度及脈沖的變化,即利用回聲來探測與定位食物位置,從而在飛行中不斷的動態(tài)改變自己的速度及位置,最終獲得食物(最優(yōu)解)的一種過程.該算法規(guī)則主要有4個參數(shù):波頻率、飛行速度、響度(音量)以及脈沖發(fā)射頻度[16–19].這些參數(shù)決定了蝙蝠算法尋優(yōu)速度和精度.

全局搜索:隨機飛行蝙蝠的聲波頻率:

式中: fi表示蝙蝠個體的聲波頻率;[fmin,fmax]為頻率的范圍;是一個隨機擾動,在[0,1]上服從均勻分布.

蝙蝠的飛行速度:

式中:xi代表蝙蝠在i次迭代的空間位置;x?為當前空間最優(yōu)位置.

蝙蝠i的位置移動更新:

式中: xold為從當前最優(yōu)解集中隨機選擇的一個解;rand1是[0,1]內(nèi)服從均勻分布的隨機數(shù);At為當前代蝙蝠的響度;ε為[0,1]上的D維隨機向量.

接受新解:通過全局搜索和局部搜索并產(chǎn)生新個體后,如果rand2<,且同時滿足函數(shù)值也是新解更優(yōu)f(xnew)

參數(shù)調(diào)整:當接受新解后,響度A和脈沖頻度?r的將得到更新,

4 改進蝙蝠算法

4.1 編碼方式

在改進的蝙蝠算法(improved bat algorithm,IBA)的平行機調(diào)度中,運用實數(shù)編碼的位置向量來表示Map工序的分割數(shù)量情況和二個階段的機器調(diào)度序列.考慮N個工件和M臺同類機,按工件的釋放時間ri排序(若釋放時間相同,就根據(jù)Reduce工序從大到小排序).為便于編程,蝙蝠編碼采用至多N(2+M)維實數(shù)向量表示N個工件在M臺同類機器上加工的調(diào)度序列.向量中每一個實數(shù)的取值范圍是[1,M +1).整個編碼分成3個部分:1)前N位的整數(shù)部分表示N個工件的Map工序劃分的子任務(wù)個數(shù);2)接下來的N ·M的實數(shù)數(shù)字中:整數(shù)部分表示Map工序子任務(wù)所分配的機器號,小數(shù)部分表示Map工序分割部分的大小;3)最后N位的整數(shù)部分表示N個工件的Reduce工序?qū)?yīng)加工的機器號.

針對隨機產(chǎn)生N(2+M)維實數(shù),先分析前N個數(shù)(x1,x2,···,xi,···,xN)(其中xi∈[1,M+1)),?xi?代表每個工件的Map工序劃分子任務(wù)的個數(shù),表示第i個工件由數(shù)量?xi?臺機器來執(zhí)行.針對部分算列中存在nini,則對解進行合法性修正,用可分數(shù)量ni代替該數(shù)字xi的整數(shù)部分.其中?·?表示向下取整,接下來分析維數(shù)值.

4.2 解碼方式

用一個例子說明編/解碼的過程.有2臺機器處理3個工件,其中3個工件的基礎(chǔ)信息見第2.2節(jié)中任務(wù)分割優(yōu)勢部分.

解碼:

1)首先分析前N位數(shù)字,根據(jù)這N位的整數(shù)部分算出每個工件的Map工序被分割的部分.在本算例中有3個工件,因而N3;表1分別可以看出工件1–3的Map工序分割成2個部分;

表1 3個工件2臺機器的編碼信息Table 1 Code information for 3 jobs 2 machines

這里[·]表示取整.對于工件1,可以得出機器1分配到的Map工序子任務(wù)數(shù)為2;從而可推算出機器2分配的Map工序子任務(wù)數(shù)n1?21;

4.3 正余弦差分擾動

BA算法進行局部搜索,步長和響度會隨著迭代增加逐漸遞減,在這種數(shù)值變化趨勢下,若缺乏行之有效的變異機制,很容易使種群陷入局部最優(yōu).為此,對算法要適當加以改進,采用正余弦擾動增加其尋優(yōu)能力.表示第t代第i(i1,2,···,N)個個體的位置,當前最好位置個體表示為X?,正弦余弦擾動數(shù)學(xué)表達式如下:

其中: t為當前迭代次數(shù);θ ∈[0,2π]為隨機參數(shù);ε1,ε2∈[0,1]稱為控制參數(shù),是一個隨機數(shù),取值的大小會影響算法開發(fā)和探索能力.

差分進化算法[23]優(yōu)點是收斂速度快.能引導(dǎo)群體快速朝最優(yōu)方向移動,本文在差分進化算法的基礎(chǔ)上提出了差分變異策略,如式(36)所示:

本文的正余弦差分擾動策略的步驟如下:選取一個蝙蝠Xb,分別計算出Xc,Xs,Xw比較這些目標函數(shù)值,選取擾動中最優(yōu)的值和當前最優(yōu)函數(shù)值比較,如果擾動后的解更優(yōu),則替換X?.其中這里的選取規(guī)則,產(chǎn)生一隨機概率p?∈(0,1),當概率p?0.1時(即選取數(shù)量約為個蝙蝠,NP為種群規(guī)模),進行正余弦擾動.

4.4 改進蝙蝠算法流程

綜上所述,求解MapReduce問題的改進蝙蝠優(yōu)化算法流程可歸結(jié)如下:

步驟1初始化參數(shù).設(shè)定蝙蝠種群規(guī)模為NP,脈沖頻率的上下限,響度A,最大脈沖率?r,音量的衰減系數(shù),最大迭代次數(shù)為Tmax等參數(shù);

步驟2初始化蝙蝠的初始位置和速度等,計算初始種群的個體適應(yīng)度值,選擇適應(yīng)度值最優(yōu)的個體位置作為最優(yōu)位置;

步驟3根據(jù)式(29)–(31)更新脈沖頻率、速度和位置;

步驟4產(chǎn)生一隨機數(shù)rand1,若rand1>ri,則對當前最優(yōu)蝙蝠位置進行按式(32)擾動得到新的位置,然后比較原解,若適應(yīng)度更優(yōu)則替換原位置;否則產(chǎn)生一隨機概率p?∈(0,1),當p?0.1時按式(34)–(36)進行正余弦差分擾動策略,然后比較原解,若適應(yīng)度更優(yōu)則替換原位置;

步驟5產(chǎn)生一個隨機數(shù)rand2,如果rand2

步驟6若達到終止條件,則輸出最優(yōu)個體,即算法找到的最優(yōu)解;否則,返回步驟3.

5 數(shù)值實驗

本文提出的算法采用MATLAB 2014a編程,實驗運行環(huán)境:CPU 2.8 GHz,內(nèi)存4 GB,Windows 7操作系統(tǒng)(64位).為驗證算法尋優(yōu)性能進行數(shù)據(jù)仿真試驗,當小規(guī)模數(shù)據(jù)算例可用CPLEX 12.5軟件進行精確求解;其中本文CPLEX的運行時間上限設(shè)置為2 h.而當數(shù)據(jù)到一定規(guī)模時,在規(guī)定的時間內(nèi)無法用該軟件進行求解,則運用蝙蝠算法近似求解.

5.1 松弛下界

為了評價算法解的質(zhì)量,本文對問題解的下界進行研究.

定理1假設(shè)機器的加工速度v1v2···vM.由于Map工序的子任務(wù)可在多臺機器上加工,相應(yīng)的機器數(shù)量比較難以確定,故松弛一個條件.假設(shè)工件一下達,目前機器都是空閑的,該問題的下界為

證假設(shè)工件一下達,目前機器都是空閑的.將該工件的Map工序加工時間平攤到M臺機器,那么工件的Map部分加工時間至少為從而推導(dǎo)出Reduce工序的從下達到開始加工這個時間間隔至少為考慮到Reduce工序的惡化效應(yīng),把該Reduce工序也交給最快的機器加工,可推出Reduce工序的加工時間至少為從而推出這2個工序的加工時間和該工件的最少逗留時間.顯然表達式是目標函數(shù)最優(yōu)解的一個下界.

5.2 評判指標

為了說明改進算法的有效性,評價指標為相對百分比偏差[17](relative percentage deviation,RPD).因此,各類算法所求得的解的質(zhì)量可用RPD來衡量[17]:

其中: falg是算法alg中計算獲得的目標函數(shù)值,LB就根據(jù)式(37)計算.

Time(s):CPU平均運行時間,指算法求得最優(yōu)解所花費的平均計算時間,算例運行6次,取6次的平均計算時間,以秒(s)為單位.

5.3 實驗參數(shù)

用傳統(tǒng)經(jīng)典算法遺傳算法(genetic algorithm,GA)作比較.算法的參數(shù)設(shè)定中,GA,BA和IBA的種群數(shù)量NP都設(shè)定為100,迭代次數(shù)200;其中:GA的變異概率pc0.83,BA和IBA設(shè)定fmin0,fmax1,A0.25,γ0.05.隨機產(chǎn)生算例,算例規(guī)模和參數(shù)見表2.

5.4 實驗分析

對于上述實例用IBA,BA和GA3種算法做實驗結(jié)果對比.針對不同的機器數(shù)量和工件規(guī)模,完成了16組實驗算例,每個實驗算例在同一算法下運行6次.計算出每個算法的評判指標,然后取其平均值.具體運行結(jié)果數(shù)據(jù)列于表3.由于篇幅有限,隨機選取N100,M10,αiβi0.05 和N200,M20,αiβi0.05兩種情形的算法運行圖如圖4–5所示.

表2 算例的參數(shù)取值范圍Table 2 The range of parameters

表3 各算法計算時間比較Table 3 Comparison of computing time of each algorithm

從圖4–5分別描繪了最優(yōu)值的分布.從圖中可以看出,迭代初期的時候,各類算法的計算所得目標值基本上相差不大.當達到一定的迭代次數(shù)的時候,優(yōu)化目標無法再改進,而且BA和GA算法有著類似的收斂速度,改進蝙蝠算法IBA有著較為明顯的優(yōu)勢,具有更好的收斂性和穩(wěn)定性.

圖4 10臺機器100個工件的算法收斂曲線圖Fig.4 The algorithm convergence curve of 100 jobs of 10 machines

圖5 20臺機器200個工件的算法收斂曲線圖Fig.5 The algorithm convergence curve of 200 jobs of 20 machines

總之,從圖4–5可以看出,改進算法的收斂性與穩(wěn)定性能優(yōu)于BA和GA,說明了該改進方法的有效性.

從表3可以看出,工件數(shù)量增加一倍時,CPU計算時間并不是相應(yīng)的成倍增加,而增加的更多.通過16組數(shù)據(jù)規(guī)模的實驗,從表4中的第3–6列對應(yīng)第8–11列可看出,惡化系數(shù)越大,惡化越嚴重,RPD值比較大.第2列的LB1是根據(jù)惡化系數(shù)αiβi0.05和式(37)計算出來的;而第7列的LB2是根據(jù)惡化系數(shù)αiβi0.1和式(37)計算出來的.下界值忽略了Map階段的惡化效應(yīng),只考慮Reduce階段的惡化效應(yīng);同時下界隨著惡化系數(shù)的增加而增加.當工件數(shù)量只有10個時,模型可以通過軟件CPLEX進行精確求解,精確解比較接近問題的下界,并且其相對偏差RPD都小于5%.當工件數(shù)量大于10時,CPLEX軟件無法在規(guī)定的短時間內(nèi)求出該問題的精確解.因此只能借助智能算法求得的近似解,問題下界值通過式(37)求得.因為計算RPD的下界值是忽略了Map工序的惡化效應(yīng)和加工速度差異,故RPD值比較大.但總體低于25%,這說明改進的算法運行性能較好.從圖和表中都可以看出,改進蝙蝠算法的數(shù)值仿真結(jié)果優(yōu)于GA和基本蝙蝠算法的運行結(jié)果,因此,有效驗證了改進的蝙蝠算法尋優(yōu)能力更強.從表中數(shù)據(jù)看出,RPD值的大小與生成的工件釋放流量有關(guān),即與給定機器數(shù)量下單位時間內(nèi)工件釋放數(shù)量有關(guān).如果在給定的機器數(shù)量情況下單位時間內(nèi)工件釋放數(shù)量越多(工件釋放流量越大),造成工件堆積,來不及加工,等待時間延長,該模型越容易產(chǎn)生惡化效應(yīng),RPD值越大.所以50個工件,2臺機器的時候,數(shù)據(jù)顯示RPD值最大.

表4 各算法RPD指標比較Table 4 Comparison of RPD indicators of each algorithm

6 結(jié)束語

本文探討了具有惡化效應(yīng)的MapReduce模型同類機調(diào)度問題,建立了混合整數(shù)規(guī)劃模型,設(shè)計了改進蝙蝠算法(IBA)進行求解,同時討論了問題的下界.通過比較發(fā)現(xiàn),RPD值和工件的釋放流量大小及惡化系數(shù)有關(guān).釋放流量越大或惡化系數(shù)越大,惡化越嚴重,則工件在機器間逗留時間越久,RPD值越大.最后,通過數(shù)值實驗驗證了應(yīng)用改進蝙蝠算法求解MapReduce模型下的同類機調(diào)度問題的可行性和有效性.下一步研究考慮從以下幾個方面展開:1)是將所設(shè)計的算法推廣到不確定性的MapReduce調(diào)度模型中,如加工時間是一個隨機數(shù)、區(qū)間數(shù)或模糊數(shù)的情形;2)是探討考慮能耗的基于Map-Reduce的多目標調(diào)度模型.