黃基誕

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

1 引言

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

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

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

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

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

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

2 問題建模

2.1 問題描述

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

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

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

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

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

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

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

2.3 模型假設(shè)

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

1)在任意時(shí)刻每臺(tái)機(jī)器只能加工一個(gè)Map工序子任務(wù)或Reduce工序(即機(jī)器同一時(shí)刻不能加工兩個(gè)任務(wù));

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

3)每臺(tái)機(jī)器都有各自恒定的加工速度;

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

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

2.4 參數(shù)符號(hào)

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

2.5 決策變量

以下是決策變量:

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

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

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

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

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

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

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

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

本文考慮的問題模型以最小化所有工件逗留時(shí)間和為目標(biāo):

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

處理時(shí)間約束:

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

任務(wù)分配約束:

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

3 蝙蝠算法

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

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

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

蝙蝠的飛行速度:

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

蝙蝠i的位置移動(dòng)更新:

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

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

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

4 改進(jìn)蝙蝠算法

4.1 編碼方式

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

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

4.2 解碼方式

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

解碼:

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

表1 3個(gè)工件2臺(tái)機(jī)器的編碼信息Table 1 Code information for 3 jobs 2 machines

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

4.3 正余弦差分?jǐn)_動(dòng)

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

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

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

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

4.4 改進(jìn)蝙蝠算法流程

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

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

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

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

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

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

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

5 數(shù)值實(shí)驗(yàn)

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

5.1 松弛下界

為了評(píng)價(jià)算法解的質(zhì)量,本文對(duì)問題解的下界進(jìn)行研究.

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

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

5.2 評(píng)判指標(biāo)

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

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

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

5.3 實(shí)驗(yàn)參數(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.隨機(jī)產(chǎn)生算例,算例規(guī)模和參數(shù)見表2.

5.4 實(shí)驗(yàn)分析

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

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

表3 各算法計(jì)算時(shí)間比較Table 3 Comparison of computing time of each algorithm

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

圖4 10臺(tái)機(jī)器100個(gè)工件的算法收斂曲線圖Fig.4 The algorithm convergence curve of 100 jobs of 10 machines

圖5 20臺(tái)機(jī)器200個(gè)工件的算法收斂曲線圖Fig.5 The algorithm convergence curve of 200 jobs of 20 machines

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

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

表4 各算法RPD指標(biāo)比較Table 4 Comparison of RPD indicators of each algorithm

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

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