基于新型人工蜂群算法的分布式不相關(guān)并行機(jī)調(diào)度

劉美瑤,雷德明

(武漢理工大學(xué)自動(dòng)化學(xué)院,湖北武漢 430070)

1 引言

隨著經(jīng)濟(jì)和貿(mào)易全球化的不斷發(fā)展,制造業(yè)從集中式制造轉(zhuǎn)變?yōu)榉植际街圃?分布式制造已成為常見(jiàn)制造模式,相應(yīng)的生產(chǎn)調(diào)度問(wèn)題也變成分布式調(diào)度問(wèn)題[1–2],分布式調(diào)度比傳統(tǒng)的調(diào)度更復(fù)雜,在快速響應(yīng)市場(chǎng)需求方面優(yōu)勢(shì)更大.并行機(jī)調(diào)度是實(shí)際制造過(guò)程中一類典型的調(diào)度問(wèn)題,它在分布式環(huán)境下擴(kuò)展為分布式并行機(jī)調(diào)度問(wèn)題(distributed parallel machines scheduling problem,DPMSP),DPMSP在實(shí)際分布式制造過(guò)程應(yīng)用廣泛[3–4],如包括Polyvinyl Chloride管[4]在內(nèi)的化學(xué)品生產(chǎn),其研究具有重要的理論和現(xiàn)實(shí)意義.

近年來(lái),DPMSP研究取得了一些進(jìn)展[4–10].Lei等[4]設(shè)計(jì)了一種帶記憶的帝國(guó)競(jìng)爭(zhēng)算法.Behnamian等分別應(yīng)用遺傳算法(genetic algorithm,GA),變鄰域搜索和雙階段算法等解決了多種類型的DPMSP[8–10].只是現(xiàn)有研究主要關(guān)注了各工廠機(jī)器數(shù)量和機(jī)器加工能力等完全一樣的同構(gòu)工廠DPMSP,較少關(guān)注異構(gòu)工廠環(huán)境下的DPMSP,且并行機(jī)多為同速并行機(jī),很少考慮不相關(guān)并行機(jī).由于不相關(guān)并行機(jī)在制造過(guò)程中普遍存在[4],且實(shí)際多工廠往往為異構(gòu)工廠,導(dǎo)致相應(yīng)的調(diào)度問(wèn)題更復(fù)雜,求解困難更大,因此,有必要研究異構(gòu)工廠下的分布式不相關(guān)并行機(jī)調(diào)度問(wèn)題(distributed unrelated parallel machines scheduling problem,DUPMSP).

調(diào)度問(wèn)題建模時(shí),通常假設(shè)所有機(jī)器在調(diào)度過(guò)程中一直可用,而實(shí)際制造過(guò)程中機(jī)器難免會(huì)因?yàn)槔匣?、違規(guī)操作、零件磨損、管理不善和外界因素等需要進(jìn)行預(yù)防性維修(preventive maintenance,PM)[11–12].PM的時(shí)間窗固定或動(dòng)態(tài)變化.動(dòng)態(tài)時(shí)間窗更靈活,能有效地減少機(jī)器空閑時(shí)間,從而大幅提高機(jī)器的利用率,因此,具有動(dòng)態(tài)時(shí)間窗的PM受到廣泛關(guān)注.目前,考慮PM的調(diào)度問(wèn)題有一些進(jìn)展[13–24],不過(guò),以上研究主要在單工廠環(huán)境下進(jìn)行,分布式環(huán)境下考慮PM 的調(diào)度問(wèn)題,尤其是具有PM的DUPMSP,未引起研究者的關(guān)注.

人工蜂群算法(artificial bee colony,ABC)[25]由土耳其學(xué)者Karaboga于2005年提出,它具有控制參數(shù)少、操作簡(jiǎn)單、易于實(shí)現(xiàn)等優(yōu)點(diǎn).目前ABC已成功解決了單工廠環(huán)境下的多種調(diào)度問(wèn)題[26–30],不過(guò),ABC在分布式調(diào)度方面的應(yīng)用研究才剛剛起步[31–32].由于ABC的顯著特點(diǎn)及其在求解調(diào)度問(wèn)題方面的優(yōu)勢(shì),本文探討ABC在DUPMSP方面的應(yīng)用可能.

針對(duì)考慮PM的DUPMSP,提出一種新型ABC以最小化最大完成時(shí)間.該算法將整個(gè)種群劃分成4部分,其中跟隨蜂群劃分為3部分,跟隨蜂有自己的蜜源,引領(lǐng)蜂、跟隨蜂和偵查蜂搜索策略各異,并利用優(yōu)化數(shù)據(jù)更新整個(gè)種群.通過(guò)大量的仿真實(shí)驗(yàn)驗(yàn)證了新型ABC在求解所研究問(wèn)題方面的有效性和優(yōu)勢(shì).

2 問(wèn)題描述

DUPMSP描述如下:假設(shè)n個(gè)工件分配在F個(gè)工廠內(nèi)加工,工廠f內(nèi)有mf臺(tái)不相關(guān)并行機(jī)Msf+1,…,Msf+mf,其 中總共W臺(tái)機(jī)器.每個(gè)工件只有一道加工工序,只需在任一臺(tái)機(jī)器上加工一次,工件Ji在機(jī)器Mk上的加工時(shí)間為pik.

每臺(tái)機(jī)器都有多個(gè)PM時(shí)間窗,機(jī)器Mk必須在動(dòng)態(tài)時(shí)間窗[ukl,vkl]內(nèi)進(jìn)行PM,維護(hù)時(shí)長(zhǎng)為wkl,其中(vkl ?ukl)wkl,l=1,2,….機(jī)器Mk第l次PM的起始時(shí)間,結(jié)束時(shí)間分別為Skl和Ekl,Sklukl且Eklvkl,Ekl=Skl+wkl.

還需滿足以下約束:所有機(jī)器在零時(shí)刻均可加工工件,工件在加工過(guò)程中一經(jīng)打斷需重新開(kāi)始,一臺(tái)機(jī)器同一時(shí)刻只能加工一個(gè)工件,每個(gè)工件在同一時(shí)刻只能在一臺(tái)機(jī)器上加工等.

DUPMSP包括3個(gè)子問(wèn)題[9]:1)工廠分配,確定所有工件在各工廠之間的分配;2)機(jī)器分配,在每個(gè)工廠為工件確定合適的機(jī)器;3)調(diào)度,確定各機(jī)器上工件的加工順序.兩個(gè)分配子問(wèn)題之間具有非常緊密的聯(lián)系,工廠分配決定了機(jī)器分配的內(nèi)容,而工廠分配的效果取決于機(jī)器分配和調(diào)度.若擴(kuò)展機(jī)器分配,在所有工廠為工件確定合適的機(jī)器,一旦機(jī)器分配確定,就可通過(guò)統(tǒng)計(jì)各工廠內(nèi)的機(jī)器所分配的工件,而確定工廠分配,這樣可將兩個(gè)分配問(wèn)題集成為擴(kuò)展的機(jī)器分配問(wèn)題.

問(wèn)題的目標(biāo)為在滿足所有約束條件下最小化最大完成時(shí)間.

其中:Ci表示工件Ji的完成時(shí)間,Cmax為最大完成時(shí)間.

表1給出了DUPMSP的一個(gè)實(shí)例的加工時(shí)間,有2個(gè)工廠和30個(gè)工件,其中工廠1有2臺(tái)不相關(guān)并行機(jī),工廠2有3臺(tái)不相關(guān)并行機(jī),對(duì)應(yīng)的一種調(diào)度方案如圖1所示.

表1 加工時(shí)間Table 1 Processing time

圖1 實(shí)例的甘特圖Fig.1 The Gantt chart of the example

3 基于新型ABC的DUPMSP

3.1 初始化

由于工廠分配和機(jī)器分配集成為擴(kuò)展的分配問(wèn)題,整個(gè)問(wèn)題由擴(kuò)展的機(jī)器分配和調(diào)度組成,為此,采用雙串編碼方式.對(duì)于具有n個(gè)工件和W臺(tái)機(jī)器的問(wèn)題,其解由機(jī)器分配串和調(diào)度串組成,其中機(jī)器分配串[Mh1Mh2… Mhi … Mhn]中,Mhi為加工Ji的機(jī)器;調(diào)度串[q1q2… qi … qn]中,qi為工件Ji對(duì)應(yīng)的實(shí)數(shù).

調(diào)度串為實(shí)數(shù)串,假設(shè)工件Ji,Ji+1,…,Jj在同一臺(tái)機(jī)器上加工,即Mhi=Mhi+1=…=Mhj,則這些工件的加工順序由ql的升序決定,其中l(wèi)∈[i,j].

解碼過(guò)程如下:對(duì)每臺(tái)機(jī)器,根據(jù)第1個(gè)串確定所分配的所有工件并按這些工件對(duì)應(yīng)的ql的升序排列,確定該機(jī)器上所有工件的加工順序.假設(shè)機(jī)器Mk上工件的加工順序?yàn)镴k1,Jk2,…,Jkg,對(duì)于機(jī)器的第l次PM,根據(jù)如下3種情況之一安排工件加工:

1)如果αk+pkhkukl,則Ckh=αk+pkhk,αk=Ckh;

2)如果αk+pkhk >ukl且αk+pkhk+wklvkl,則Skl=αk+pkhk,αk=Skl+wkl,l=l+1;

3)如果αk+pkhk+wkl >vkl,則Skl=ukl,αk=Skl+wkl,l=l+1.

其中αk表示Mk最早空閑的時(shí)間.

如上所示,部分工件的開(kāi)始時(shí)間和完成時(shí)間與PM的開(kāi)始時(shí)間密切相關(guān),增加了解碼過(guò)程的復(fù)雜性.如果不考慮PM且目標(biāo)函數(shù)僅為最大完成時(shí)間,則無(wú)須優(yōu)化調(diào)度子問(wèn)題;隨著PM的加入,需要考慮調(diào)度串的優(yōu)化,主要在于PM的開(kāi)始時(shí)間會(huì)隨工件的加工順序的變化而改變.

圖2給出了表1實(shí)例的一種可能解,工件J1,J3,J11,J12,J17,J24分配給M2,這些工件對(duì)應(yīng)的qi的升序排列為0.31,0.33,0.42,0.49,0.68,0.86,故先加工J12,再加工J1,依此類推,對(duì)應(yīng)的甘特圖如圖1所示.

圖2 實(shí)例的一個(gè)解Fig.2 A solution of the example

如圖1所示,解碼過(guò)程所得到的調(diào)度方案是可行的.實(shí)際上,機(jī)器分配串保證了每個(gè)工件不能同時(shí)分配到兩臺(tái)機(jī)器上,從而保證一個(gè)工件無(wú)法同時(shí)在兩臺(tái)機(jī)器上加工;而每臺(tái)機(jī)器上工件都按調(diào)度串決定的順序依次加工,不可能在同一時(shí)間同時(shí)加工兩個(gè)工件,也就是編碼串已保證每個(gè)解都是可行的,無(wú)不可行解存在.

隨機(jī)產(chǎn)生初始種群P,并根據(jù)如下過(guò)程將種群劃分為1個(gè)引領(lǐng)蜂群EB 和3 個(gè)跟隨蜂群OB1,OB2,OB3:將初始種群的N個(gè)解根據(jù)Cmax非降序排列,前β1×N個(gè)解作為引領(lǐng)蜂的蜜源,剩余解分配給跟隨蜂作為蜜源,并且所有跟隨蜂細(xì)分為3類,在剩余解中,前β2×N個(gè)解組成OB1,作為第1類跟隨蜂的蜜源,第2類跟隨蜂群OB2的蜜源為剩下的解中Cmax最小的β3×N個(gè)解,剩余的β4×N個(gè)解分配給第3類跟隨蜂群,其中β1+β2+β3+β4=1.基于大量實(shí)驗(yàn)將參數(shù)β1,β2,β3,β4分別設(shè)置為0.4,0.1,0.25,0.25.

劃分種群后,不同蜂群采用不同的搜索方式,這樣可以運(yùn)用多種策略產(chǎn)生新解,保持種群的多樣性,并高效利用質(zhì)量較好的解.

3.2 引領(lǐng)蜂階段

通常,ABC不能直接用于離散型問(wèn)題的求解,為此,在兩個(gè)解之間采用兩點(diǎn)交叉進(jìn)行全局搜索.兩點(diǎn)交叉可作用于兩個(gè)串,且作用過(guò)程類似,主要包括隨機(jī)確定兩個(gè)位置,然后將一個(gè)解位于兩個(gè)位置間的基因用另一個(gè)解對(duì)應(yīng)位置上的基因替代.局部搜索包括4個(gè)鄰域結(jié)構(gòu)N1,N2,N3,N4,由于調(diào)度串對(duì)整個(gè)解的影響有一定限制,未設(shè)計(jì)調(diào)度串的鄰域結(jié)構(gòu).

鄰域結(jié)構(gòu)N1描述如下:先確定完成時(shí)間最大的機(jī)器Ml并任選一臺(tái)機(jī)器Mr,從Ml上隨機(jī)選擇一個(gè)工件轉(zhuǎn)移到Mr上.N2過(guò)程如下:確定完成時(shí)間最大的機(jī)器Ml以及Ml上加工時(shí)間最大的工件Jh,任選一臺(tái)機(jī)器Mr并確定其上加工時(shí)間最大的工件Jg,在機(jī)器分配串中互換Jh,Jg的位置.N3的過(guò)程與N2類似,只是兩臺(tái)機(jī)器是隨機(jī)選擇的,而N4則將隨機(jī)選擇的兩臺(tái)機(jī)器上隨機(jī)選擇的兩個(gè)工件互換.

引領(lǐng)蜂群的搜索過(guò)程如下:對(duì)于解x∈EB,

1)如果隨機(jī)數(shù)s<δ1,則隨機(jī)選擇y∈EB,對(duì)解x,y執(zhí)行機(jī)器分配串的兩點(diǎn)交叉,產(chǎn)生新解z1,若z1優(yōu)于x,則z1替代x且?=? ∪{x}.否則對(duì)解x,y執(zhí)行調(diào)度串的兩點(diǎn)交叉,得到z2,?=? ∪{z2}并更新x.

2)如果隨機(jī)數(shù)s<ε1,則g=1,重復(fù)執(zhí)行如下過(guò)程R次:產(chǎn)生鄰域解z∈Ng(x),?=? ∪{z},并用z更新x;否則g=g+1 并令g=1 若g=5.

解的更新規(guī)則遵循貪婪選擇策略即若新解優(yōu)于x,則新解替代x.集合?用來(lái)保留算法搜索過(guò)程產(chǎn)生的解.

上述過(guò)程中,參數(shù)δ1,ε1為實(shí)數(shù),通過(guò)實(shí)驗(yàn)分別設(shè)置為0.7,0.1.

3.3 跟隨蜂階段

通常,跟隨蜂本身并無(wú)蜜源,而是根據(jù)概率選擇一個(gè)引領(lǐng)蜂的蜜源,且由于跟隨蜂只是利用引領(lǐng)蜂群的蜜源進(jìn)行搜索,往往采用和引領(lǐng)蜂同樣的搜索方式.本文為跟隨蜂分配了蜜源,并應(yīng)用幾種彼此各異的搜索策略產(chǎn)生新解.

3種跟隨蜂群的具體搜索過(guò)程如下:

1)對(duì)于每個(gè)解x∈OB1.

a)如果隨機(jī)數(shù)s<δ2,則對(duì)解x和EB中的最優(yōu)解x?執(zhí)行第3.2節(jié)中x,y之間的交叉過(guò)程;

b)如果隨機(jī)數(shù)s<ε2,則對(duì)解x執(zhí)行第3.2節(jié)所述的多鄰域搜索.

2)對(duì)于每個(gè)解x∈OB2.

a)如果tT,當(dāng)隨機(jī)數(shù)s<δ3時(shí),對(duì)解x和EB中的最優(yōu)解x?執(zhí)行第3.2節(jié)中x,y之間的交叉過(guò)程;

b)否則,當(dāng)s<ε3時(shí),隨機(jī)選擇y∈EB,g=1,執(zhí)行如下過(guò)程R次:產(chǎn)生鄰域解z∈Ng(y),若z優(yōu)于x,則z替代x,?=? ∪{x};否則g=g+1,令g=1若g=5.

3)對(duì)于每個(gè)解x∈OB3.

如果隨機(jī)數(shù)s<ε4,則隨機(jī)選擇y∈EB,執(zhí)行和x∈OB2第2種情況下同樣的多鄰域搜索.

上述過(guò)程中,參數(shù)δ2,δ3,ε2,ε3,ε4為實(shí)數(shù),通過(guò)實(shí)驗(yàn)分別設(shè)置為0.9,0.9,0.1,0.6,0.5.t,T分別表示實(shí)際的目標(biāo)函數(shù)估計(jì)次數(shù)和給定目標(biāo)函數(shù)估計(jì)次數(shù),基于大量實(shí)驗(yàn)設(shè)置T=2×104.

如上所述,OB1的搜索過(guò)程和EB中的解搜索過(guò)程類似,只是全局搜索的對(duì)象不一樣,其他兩個(gè)跟隨蜂群中的解的搜索過(guò)程和方式也各異.通過(guò)多種不同途徑產(chǎn)生新解,有助于避免算法搜索停滯,增加種群多樣性.

3.4 算法描述

新型ABC的具體步驟描述如下:

1)初始化.隨機(jī)產(chǎn)生初始種群P,令t=1.

2)如果tmax_it,則

a)令集合?為空,將種群P劃分為EB,OB1,OB2,OB3,?=? ∪EB;

b)引領(lǐng)蜂階段;

c)跟隨蜂階段;

d)偵查蜂階段;

e)對(duì)集合?中的解非降序排序,排名靠前的N個(gè)解組成新種群.

3)輸出最終結(jié)果.

其中max_it表示最大目標(biāo)函數(shù)估計(jì)次數(shù),在搜索過(guò)程中,每產(chǎn)生一個(gè)解,t自動(dòng)增1.

偵查蜂階段針對(duì)OB3中的最差解xw,如果隨機(jī)數(shù)s<θ,則隨機(jī)選擇一個(gè)解x∈EB,然后,對(duì)x執(zhí)行跟隨蜂搜索過(guò)程第2步的第2種情況下的多鄰域搜索過(guò)程,如果所得到的最好解優(yōu)于xw則用前者更新后者,其中參數(shù)θ為實(shí)數(shù)，通過(guò)實(shí)驗(yàn)設(shè)置為0.4.

由于OB3中的最差解往往是種群內(nèi)的最差解,故直接從OB3中選擇.和常規(guī)偵查蜂階段不一樣,本文未采用隨機(jī)搜索,而是從EB中隨機(jī)確定一個(gè)解進(jìn)行多鄰域搜索,這樣可大概率地保證最差解得到更新和改進(jìn).

集合?用來(lái)存儲(chǔ)ABC搜索過(guò)程產(chǎn)生的優(yōu)化數(shù)據(jù),每一次循環(huán)中,?都會(huì)清空,搜索開(kāi)始后,先將EB中的解加入到?中,EB 搜索過(guò)程中兩點(diǎn)交叉產(chǎn)生的新解,無(wú)論是否優(yōu)于x,都放入?中,多鄰域搜索產(chǎn)生的解也直接放入?中,跟隨蜂群產(chǎn)生的新解處理方式類似,這樣引領(lǐng)蜂群和跟隨蜂群一次搜索至少產(chǎn)生N個(gè)解,再加上EB中的解,使得集合?的解至少N個(gè),且搜索過(guò)程得到的好解都保留在集合?中,精英解也保留在?中,為此,將?中N個(gè)Cmax最小的解直接替換當(dāng)前種群內(nèi)所有解.

新型ABC搜索過(guò)程中,PM的處理始終在解碼時(shí)進(jìn)行,這樣無(wú)需在兩點(diǎn)交叉和鄰域搜索時(shí)考慮PM的處理,簡(jiǎn)化了搜索算子的設(shè)計(jì);而且,兩點(diǎn)交叉和鄰域搜索不改變兩個(gè)編碼串的可行性,不會(huì)產(chǎn)生不可行解,其流程圖如圖3所示,時(shí)間復(fù)雜度為O(N ×G),其中G為步驟2循環(huán)的次數(shù).

圖3 新型ABC流程圖Fig.3 Flow chart of new ABC

新型ABC具有如下特點(diǎn):將種群劃分成4部分,第1部分是由引領(lǐng)蜂的蜜源組成的集合,其余3部分由跟隨蜂的解組成,不同部分采用不同的搜索策略,偵查蜂階段用鄰域搜索的解替代OB3中最差解,并利用?中保留的優(yōu)化數(shù)據(jù)直接更新整個(gè)種群.這些特點(diǎn)有助于ABC保持種群多樣性,避免陷入局部最優(yōu).

4 計(jì)算實(shí)驗(yàn)

為了驗(yàn)證新型ABC在求解考慮PM的DUPMSP的有效性,進(jìn)行了大量的計(jì)算實(shí)驗(yàn),所有測(cè)試實(shí)驗(yàn)均通過(guò)Microsoft visual C++2017編程實(shí)現(xiàn),在4.0 G RAM 2.70 GHz CPU 環(huán)境下運(yùn)行.

4.1 測(cè)試實(shí)例與對(duì)比算法

本文選用64個(gè)實(shí)例測(cè)試所提算法性能,表2描述了實(shí)例的基本信息,其中具有n=60,70,80的16個(gè)實(shí)例屬于中規(guī)模實(shí)例,其余為大規(guī)模實(shí)例.pik在區(qū)間[30,50]內(nèi)隨機(jī)產(chǎn)生,對(duì)于每臺(tái)機(jī)器Mk,相關(guān)數(shù)據(jù)為

其中rk(l?1)表示第(l ?1)次PM結(jié)束時(shí)間.

表2 實(shí)例信息Table 2 Information on instances

目前,DPMSP相關(guān)研究進(jìn)展不大,關(guān)于DUPMSP的研究更少,故難以找到能直接應(yīng)用于DUPSMP求解的對(duì)比算法.Behnamian和Ghomi[9]提出了一種基于矩陣編碼的GA來(lái)求解DPMSP.在GA中,隨機(jī)生成初始種群,通過(guò)復(fù)雜的交叉操作和特殊的變異產(chǎn)生新解,適應(yīng)度最高的個(gè)體自動(dòng)復(fù)制到下一代,并采用局部搜索來(lái)提高搜索能力.該算法無(wú)須任何修改就可直接用來(lái)求解帶有PM的DUPMSP,因此選擇GA作為對(duì)比算法.

Mir等[33]針對(duì)不相關(guān)并行機(jī)調(diào)度問(wèn)題提出了混合粒子群遺傳算法(hybrid particle swarm optimization and genetic algorithm,HPSOGA),在解碼過(guò)程中加入本文描述的關(guān)于PM的處理過(guò)程后,該算法可直接應(yīng)用于DUPMSP的優(yōu)化,故選擇它作為一種對(duì)比算法.

模擬退火算法(simulated annealing,SA)具有避免陷入局部最優(yōu)的特點(diǎn),已被廣泛應(yīng)用于求解多種組合優(yōu)化問(wèn)題.Yeh等[34]研究了具有學(xué)習(xí)效應(yīng)的并行機(jī)調(diào)度問(wèn)題,將SA應(yīng)用于該問(wèn)題的求解并獲得了良好的效果.只需修改該算法的解碼部分,便可直接用于求解DUPMSP.為驗(yàn)證本文所提算法性能,故選擇該局部搜索算法作為對(duì)比算法.

新型ABC的主要策略是種群劃分和不同蜂群采用不同的搜索方式.為驗(yàn)證這些策略的有效性,構(gòu)建了新型ABC算法的變體ABC1,該算法沒(méi)有種群劃分,跟隨蜂階段中,跟隨蜂隨機(jī)選擇一只引領(lǐng)蜂,并采用引領(lǐng)蜂相同的方式搜索.

所有算法對(duì)每個(gè)實(shí)例隨機(jī)運(yùn)行20次,指標(biāo)MIN和MAX分別表示最優(yōu)解和最差解,AVG為20次運(yùn)行結(jié)果的平均值.圖4描述了兩個(gè)實(shí)例的收斂曲線.

圖4 收斂曲線Fig.4 Convergence curves

新型ABC主要參數(shù)包括maxit,N,β1和R,通過(guò)對(duì)所有實(shí)例進(jìn)行參數(shù)測(cè)試實(shí)驗(yàn),可發(fā)現(xiàn),當(dāng)N=100,R=4,max_it=8×104和β1=0.4時(shí),算法性能最好,故采用上述參數(shù)設(shè)置.HPSOGA、GA和SA除終止條件之外的所有參數(shù)直接來(lái)自文獻(xiàn)[9]和文獻(xiàn)[33–34],所有算法采用和新型ABC相同的終止條件,實(shí)驗(yàn)結(jié)果如表3–5所示,表6描述了算法的計(jì)算時(shí)間,時(shí)間單位為s.

4.2 實(shí)驗(yàn)結(jié)果與比較

如表3–5所示,和ABC1相比,新型ABC關(guān)于64個(gè)實(shí)例中的56個(gè)取得了更優(yōu)的MIN,關(guān)于56個(gè)實(shí)例所獲得的MAX更小或者等于ABC1的MAX,關(guān)于62個(gè)實(shí)例取得了更小的AVG,這表明了新型ABC明顯優(yōu)于ABC1,從而驗(yàn)證了種群劃分和不同部分采用不同搜索策略改進(jìn)算法性能的有效性.將種群劃分為1個(gè)引領(lǐng)蜂群和3個(gè)跟隨蜂群,蜂群的搜索策略各異,這樣有助于避免ABC陷入局部最優(yōu),提高搜索效率.配對(duì)樣本均值t檢驗(yàn)的結(jié)果如表7所示,t-test(A,B)表示一次配對(duì)t-test,用來(lái)判斷算法A是否給出了優(yōu)于B的樣本均值,假設(shè)顯著水平為0.05,若p-value<0.05,說(shuō)明算法A優(yōu)于算法B.

如表3–6 所示,和3 個(gè)對(duì)比算法HPSOGA、GA與SA相比,新型ABC在較短的計(jì)算時(shí)間內(nèi)所獲得的搜索性能明顯占優(yōu),其中關(guān)于指標(biāo)MIN,新型ABC關(guān)于55個(gè)實(shí)例的結(jié)果比HPSOGA最少低70,關(guān)于58個(gè)實(shí)例比GA最少低150,關(guān)于55個(gè)實(shí)例的結(jié)果比SA最少低75,對(duì)于其他兩個(gè)指標(biāo)MAX和AVG也可以得到類似結(jié)論,而且新型ABC關(guān)于所有測(cè)試實(shí)驗(yàn)的計(jì)算時(shí)間也明顯優(yōu)于HPSOGA和GA.表7所示的結(jié)果也顯示,新型ABC和3種對(duì)比算法之間的性能差異是顯著的.

表3 5種算法關(guān)于指標(biāo)MIN的計(jì)算結(jié)果Table 3 Computational results of five algorithms on metric MIN

表4 5種算法關(guān)于指標(biāo)MAX的計(jì)算結(jié)果Table 4 Computational results of five algorithms on metric MAX

表5 5種算法關(guān)于指標(biāo)AVG的計(jì)算結(jié)果Table 5 Computational results of five algorithms on metric AVG

表6 ABC,HPSOGA,GA和SA的計(jì)算時(shí)間Table 6 Computational times of ABC,HPSOGA,GA and SA

和GA相比,新型ABC的編碼方式更簡(jiǎn)單,局部搜索和全局搜索之間的平衡更好;和HPSOGA相比,新型ABC將種群劃分為多個(gè)蜂群,且不同蜂群的搜索策略各異,這樣有利于提高搜索效率,避免陷入局部最優(yōu);和SA相比,新型ABC除了局部搜索還運(yùn)用了全局搜索,種群內(nèi)不同解之間進(jìn)行信息交流,有助于找到全局最優(yōu)解.新型ABC還采取和傳統(tǒng)ABC不同的跟隨蜂跟隨方式,且跟隨蜂自身也有蜜源,并利用優(yōu)化過(guò)程中產(chǎn)生的數(shù)據(jù)來(lái)更新種群,構(gòu)造新種群,這樣策略能有效地實(shí)現(xiàn)探索和利用間的良好平衡,對(duì)獲得高質(zhì)量的優(yōu)化結(jié)果有利,從而表明,新型ABC是解決具有PM的DUPMSP具有較強(qiáng)競(jìng)爭(zhēng)力的方法.

表7 配對(duì)樣本t檢驗(yàn)Table 7 Results of paired sample t-test

5 結(jié)論

在分布式環(huán)境下的調(diào)度問(wèn)題中考慮機(jī)器可用約束如PM更有意義和價(jià)值.針對(duì)考慮PM的DUPMSP,提出一種新型ABC以最小化最大完成時(shí)間.該算法采用全新的種群劃分策略,不同蜂群采用不同的搜索策略,跟隨蜂具有自己的蜜源并采取新的跟隨方式,采用新策略完成偵查蜂搜索和更新整個(gè)種群.運(yùn)用大量的實(shí)例對(duì)算法性能進(jìn)行測(cè)試,實(shí)驗(yàn)結(jié)果驗(yàn)證了新型ABC的有效性和搜索優(yōu)勢(shì).

分布式調(diào)度是目前調(diào)度研究的焦點(diǎn),但現(xiàn)有研究很少討論實(shí)際加工約束,未來(lái)將深入研究具有隨機(jī)故障,零等待和不確定加工條件等的分布式調(diào)度問(wèn)題及其相應(yīng)的高效智能優(yōu)化算法.