呂順風(fēng),馬 科

(中國(guó)科學(xué)技術(shù)大學(xué) 管理學(xué)院,合肥 230026)

1 引言

調(diào)度問(wèn)題是組合優(yōu)化領(lǐng)域中一類(lèi)重要的問(wèn)題,在生產(chǎn)管理、通信等方面有著重要作用.批調(diào)度問(wèn)題是其中的一個(gè)重要的分支,而且與經(jīng)典調(diào)度問(wèn)題不同的是:一臺(tái)機(jī)器可以同時(shí)處理多個(gè)工件;批的加工時(shí)間等于批中工件的最大完成時(shí)間;批的完成時(shí)間等于批的開(kāi)始時(shí)間加上批的最大加工時(shí)間;批的完成時(shí)間等于批中工件的最大完成時(shí)間.批調(diào)度問(wèn)題考慮了工件的尺寸和機(jī)器的容量,這在實(shí)際的活動(dòng)中經(jīng)常需要考慮到,例如半導(dǎo)體芯片的預(yù)燒、電路測(cè)試、港口貨物裝卸、金屬加工等等.這些問(wèn)題中,工件的尺寸是有差異的,及其加工需要分批進(jìn)行,批的尺寸不能超過(guò)機(jī)器的容量.這類(lèi)問(wèn)題是經(jīng)典調(diào)度問(wèn)題在空間上的拓展,也是生產(chǎn)調(diào)度領(lǐng)域中一個(gè)新的研究方向.

1.1 問(wèn)題的描述

針對(duì)此類(lèi)問(wèn)題,首先作如下假設(shè)[1]:

(1)有n個(gè)待加工的工件{1,2,…,n},工件的加工時(shí)間為pj,工件的尺寸為sj;

(2)機(jī)器的容量為B,批中工件的總尺寸都小于B,假設(shè)沒(méi)有工件尺寸大于B的工件;

(3)假設(shè)批一旦開(kāi)始加工,在批加工完成之前,不可以被打斷或者添加新的工件,批k的加工時(shí)間為T(mén)k,等于批中最大加工時(shí)間的工件;

(4)目標(biāo)是最大加工時(shí)間Cmax最小,其中最大加工時(shí)間等于批中最后一個(gè)離開(kāi)機(jī)器的工件完成時(shí)間,NSBM問(wèn)題的制造跨度為所有批的加工時(shí)間總和.

其中,k是分批的批數(shù),xij是0–1變量,式(1)表示優(yōu)化的目標(biāo)是制造跨度;式(2)限定每個(gè)工件只能分到一個(gè)批次中;式(3)表示機(jī)器容量約束;式(4)表示批加工時(shí)間;式(5)、式(6)和式(7)是基本約束.

Uzsoy首先提出了該類(lèi)問(wèn)題的單機(jī)器模型,即工件尺寸不同的單機(jī)批調(diào)度問(wèn)題(single batch-processing machine with non-identical job sizes,NSBM),證明了當(dāng)所有工件加工時(shí)間相同時(shí),問(wèn)題等價(jià)于容量為B物品尺寸為si的裝箱問(wèn)題.由于裝箱問(wèn)題是強(qiáng)NP難的,所以問(wèn)題也是強(qiáng)NP難的[2].

2 蟻群算法和魚(yú)群算法

由于在構(gòu)建差異工件(即工件有尺寸差異)單機(jī)批調(diào)度問(wèn)題的解時(shí),批的加工時(shí)間是不確定的,從而不能類(lèi)似于經(jīng)典調(diào)度問(wèn)題的蟻群算法,把批加工時(shí)間的倒數(shù)作為蟻群算法中的啟發(fā)式信息.針對(duì)這一問(wèn)題,我們引入批的利用率和批的負(fù)載均衡率作為蟻群算法中的啟發(fā)式信息,提出了JACO (ant colony optimization based a job sequence)和BACO (ant colony optimization based a batch sequence)兩種蟻群優(yōu)化算法[5].

2.1 啟發(fā)式信息

在一組給定的批次下,當(dāng)批的總剩余空間越小,方案越佳.此外,批的加工時(shí)間等于批中加工時(shí)間的最大值,如果在加工完之前,有的工件已經(jīng)加工完畢卻沒(méi)有辦法交付使用,那么這段浪費(fèi)掉的時(shí)間我們稱(chēng)之為冗余時(shí)間.很顯然,對(duì)于白白浪費(fèi)掉的時(shí)間,冗余時(shí)間越小的方案往往是最優(yōu)的方案.

批的利用率為批的加工尺寸所占機(jī)器容量的比例,公式為:

批的負(fù)載率為批中加工時(shí)間的變異系數(shù)與1的差值,公式為:

Wk為加工時(shí)間的平均值,σk表示批加工時(shí)間的方差,批的負(fù)載率越大,表示批中加工時(shí)間分布越均勻,加工方案越好[6].

2.2 算法的描述

2.2.1 JACO蟻群算法

在本文中,我們采用JACO蟻群算法算法,直接考慮工件序列,以方便算法的比較.具體描述如下[7]:

(1)信息素的定義:τij表示工件j排列在工件i之后的信息素濃度,分批的規(guī)則采用BF (Best Fit)規(guī)則.

(2)啟發(fā)式信息:利用BF規(guī)則進(jìn)行分批,實(shí)際上就是利用批利用率最大這個(gè)啟發(fā)式信息,在生成工件序列后,利用BF規(guī)則進(jìn)行分批,工件中間隔較小的工件被分在同一批中概率較大.為方便計(jì)算,定義工件j排列在工件i之后的啟發(fā)式信息為:

(3)狀態(tài)轉(zhuǎn)移概率公式記為alloweda={j|工件j未被a訪問(wèn)到},螞蟻a當(dāng)前位置工件i,那么它的狀態(tài)轉(zhuǎn)移選擇下一個(gè)工件概率為[8]:

2.2.2 魚(yú)群算法

(1)覓食行為(prey)

覓食行為的行為選擇為:

(2)聚群行為(swarm)

聚群行為的行為選擇為:

Xc表示領(lǐng)域內(nèi)伙伴的中心位置.

(3)追尾行為(follow)

追尾行為的行為選擇:

3 混合算法

3.1 蟻群算法和魚(yú)群算法的優(yōu)化機(jī)理

蟻群算法和魚(yú)群算法雖然都屬于群體優(yōu)化算法,但是算法中的個(gè)體并沒(méi)有表現(xiàn)出智能性,個(gè)體的行為簡(jiǎn)單,只具有基礎(chǔ)的判斷能力,無(wú)法智能的遵循相應(yīng)行為規(guī)則,但是當(dāng)它們形成一個(gè)群體的時(shí)候,整個(gè)群體會(huì)表現(xiàn)出一定的智能性.這兩種算法的個(gè)體規(guī)律有一定的相似性,人工魚(yú)群算法初期,人工魚(yú)的覓食行為是隨機(jī)的,這和蟻群算法是相似的;人工魚(yú)群算法后期,人工魚(yú)的聚集是由伙伴中心的最優(yōu)狀態(tài)決定的,這與蟻群算法中信息素濃度和啟發(fā)式信息大小有著相同的作用.而人工魚(yú)的數(shù)量越多,就越容易尋找局部最優(yōu)值,這將有更多的人工魚(yú)游到該位置,這相當(dāng)于蟻群算法信息素濃度增加,類(lèi)似于螞蟻群算法中信息素正反饋的過(guò)程.

和蟻群算法不同的是,人工魚(yú)前進(jìn)的方向是由當(dāng)前狀態(tài)最優(yōu)的情況決定的,并且在某些條件下會(huì)受到擁擠度的限制.如果該地區(qū)人工與數(shù)量過(guò)多,超過(guò)擁擠度的約束,即使該地區(qū)有很高的價(jià)值,人工魚(yú)也不會(huì)聚集.而在蟻群算法中,信息素關(guān)聯(lián)著蟻群個(gè)體之間的聯(lián)系,并且和啟發(fā)式信息一起共同指導(dǎo)個(gè)體行為,最終所有的螞蟻都會(huì)聚集到同一條最佳路徑上來(lái)[11].

兩種算法搜索的方式不同,從而個(gè)體的運(yùn)動(dòng)方式也各不相同,這種差異也是由個(gè)體運(yùn)動(dòng)的目的不同造成的.啟發(fā)式信息在兩種算法的優(yōu)化中起到了作用,因?yàn)閭€(gè)體的目的都是盡快尋找食物.但是擁擠程度并完全不適用于蟻群算法,因?yàn)橄伻簩ふ业绞澄锖髸?huì)搬回巢穴,而魚(yú)群在尋找到食物后會(huì)直接吃掉,并不會(huì)存儲(chǔ),而過(guò)多的人工魚(yú)會(huì)導(dǎo)致其它人工魚(yú)到這里之前,食物已經(jīng)被吃光,所以擁擠度對(duì)算法的全局性起著關(guān)鍵的作用.螞蟻在尋找到食物并且搬回的過(guò)程中,如果發(fā)現(xiàn)了更高效的路徑,則會(huì)轉(zhuǎn)移到其他路徑上去,在選擇最短路徑上,螞蟻的數(shù)量并不受到擁擠度的限制,選擇的螞蟻越多,對(duì)結(jié)果越好,但是如果這條路徑并非最優(yōu)選擇,算法可能會(huì)被局限在局部最優(yōu)解中.

因此,兩種算法之間的核心區(qū)別是擁擠程度在優(yōu)化過(guò)程中起著指導(dǎo)作用.換句話說(shuō),魚(yú)群算法類(lèi)似于于在蟻群算法中引入擁擠度的概念,并且算法優(yōu)化過(guò)程中的擁擠程度總是有著重要作用.擁擠程度的引入可以避免蟻群算法早期,螞蟻過(guò)早地聚集到信息素高的路徑上來(lái),避免算法的早熟,提高算法的全局優(yōu)化能力.算法后期,擁擠度的作用便會(huì)從正作用慢慢轉(zhuǎn)向副作用,對(duì)算法的收斂速度產(chǎn)生影響.換句話說(shuō),在早期優(yōu)化中的擁擠程度可以提高算法的優(yōu)越性能,但是在后期優(yōu)化中對(duì)性能會(huì)有一定的負(fù)面影響.如何正確使用擁擠度這個(gè)因素,是保證算法高效,準(zhǔn)確的關(guān)鍵[12].

3.2 先魚(yú)群再蟻群的混合算法

為了保證較優(yōu)的可行解,產(chǎn)生初始信息素分布,防止解過(guò)早集中到信息素較高的路徑上來(lái),首先使用魚(yú)群算法保證求解的寬度,并設(shè)置更新迭代率,當(dāng)算法的更新率少于設(shè)定值時(shí),轉(zhuǎn)入蟻群算法;轉(zhuǎn)入蟻群算法后,更新信息素,迭代尋找較優(yōu)解,當(dāng)結(jié)果不再變化時(shí),再次轉(zhuǎn)入魚(yú)群算法,并且調(diào)整更新率[13].算法步驟如下:

Step 1.初始化模型和子空間.

Step 2.設(shè)置AFSA的最大最小迭代次數(shù)Imax,Imin,更新率Rratio和擁擠度.生成m條人工魚(yú),視野長(zhǎng)度Vd,擁擠度δ和移動(dòng)步長(zhǎng)Dstep,產(chǎn)生初始人工魚(yú)群F(0).

Step 3.每條人工魚(yú)進(jìn)行一次迭代,迭代過(guò)程中分別執(zhí)行覓食,聚群,追尾三種行為,迭代結(jié)束后,將結(jié)果與公告板相比較,更新最優(yōu)值.

Step 4.在迭代次數(shù)的范圍內(nèi),將此次的迭代結(jié)果和上一次結(jié)果相比較,計(jì)算更新率R.如果R＜Rratio,說(shuō)明優(yōu)化效果降低,轉(zhuǎn)入Step 5,如果R＞Rratio,說(shuō)明魚(yú)群算法依然優(yōu)化效果良好,轉(zhuǎn)入Step 3.

Step 5.根據(jù)魚(yú)群算法的迭代結(jié)果,生成m只螞蟻,初始化信息素τi,j(0).

其中,M代表算法中螞蟻的總數(shù)量,n是工件數(shù)目,∑Cmn表示總完工時(shí)間.

Step 6.m只螞蟻隨機(jī)放入工件上,根據(jù)每條路徑上的信息素濃度,計(jì)算狀態(tài)轉(zhuǎn)移概率并且由位置i轉(zhuǎn)移到位置j,多次迭代后,得到最優(yōu)結(jié)果.

Step 7.判斷算法是否達(dá)到最大迭代次數(shù)后者滿足輸出條件,若滿足,輸出結(jié)果;若不滿足,以蟻群算法的結(jié)果為新的人工魚(yú)群F(1),并且調(diào)整擁擠度閾值和更新率Rratio,轉(zhuǎn)入Step 3.

3.3 直接嵌入擁擠度的蟻群算法

將擁擠度直接嵌入蟻群算法的迭代過(guò)程中,在螞蟻選擇每條路徑時(shí),首先判斷路徑上的擁擠度,如果擁度小于閾值,則繼續(xù)選擇該路徑,如果擁擠度大于閾值,則隨機(jī)選擇可行的其它路徑.蟻群算法路徑上的擁擠度為:

算法步驟如下:

Step 1.初始化時(shí)刻t、信息素、擁擠度閾值δt和迭代次數(shù)限制Ir.

Step 2.m只螞蟻隨機(jī)放入工件上,每只螞蟻根據(jù)信息素選擇路徑,狀態(tài)轉(zhuǎn)移概率表示t時(shí)刻螞蟻由位置i轉(zhuǎn)移到位置j的概率,如公式(8).

Step 3.每當(dāng)螞蟻選擇一條路徑,通過(guò)公式(10)計(jì)算路徑的擁擠度表示路徑過(guò)于擁擠,螞蟻從可行領(lǐng)域內(nèi)隨機(jī)選擇其它路徑;如果表示路徑不太擁擠,螞蟻從i轉(zhuǎn)移到j(luò).

Step 4.利用BF分批規(guī)則對(duì)工件序列分批,計(jì)算目標(biāo)函數(shù)值;更新信息素τij,如公式(9),和擁擠度閾值δt:

其中,c為閾值變化系數(shù).

Step 5.重復(fù)Step 2、3和4,直到所有螞蟻都選擇一條路徑或者達(dá)到最大迭代次數(shù).

兩種算法的流程圖如圖1所示.

4 仿真實(shí)驗(yàn)與分析

4.1 實(shí)驗(yàn)設(shè)計(jì)

為了驗(yàn)證本文提出的算法有效性,本文的實(shí)驗(yàn)需要兼顧三個(gè)方面要素:工件尺寸的變化,工件數(shù)的變化,工件加工時(shí)間的變化.如表1所示,工件尺寸的大小和加工時(shí)間我們采用離散型隨機(jī)分布的方式,隨機(jī)決定工件尺寸的大小;工件數(shù)量方面,我們通過(guò)數(shù)量遞增的對(duì)比結(jié)果來(lái)對(duì)比算法的有效性;算法的有效性我們考慮算法的加工時(shí)間和批利用率、負(fù)載率的均值.

各個(gè)參數(shù)的設(shè)置為:螞蟻數(shù)量m為20、Q=100、τi,j=1/n、ρ=0.5、α=1、β=1.

4.2 實(shí)驗(yàn)結(jié)果與分析

加工時(shí)間和工件數(shù)都是離散的,為了保證實(shí)驗(yàn)的有效性,我們根據(jù)工件的數(shù)量分為三類(lèi),分別對(duì)結(jié)果加以對(duì)比,分別如表2和表3所示.

在表2,表3中可以看出,在算法尋優(yōu)的過(guò)程中,蟻群算法的性能要優(yōu)于魚(yú)群算法,但是蟻群算法本身的早熟性,導(dǎo)致尋優(yōu)結(jié)果局部最優(yōu),但是將蟻群算法和魚(yú)群算法相結(jié)合,利用魚(yú)群算法中擁擠度因子,并與蟻群算法相結(jié)合,可以有效地避免早熟,并且對(duì)于尋找最優(yōu)解,減少尋優(yōu)時(shí)間有著一定的幫助.通過(guò)混合算法3.1和3.2的比較,混合算法3.2對(duì)于工件數(shù)量較小,迭代次數(shù)較少的問(wèn)題有較高效率.而混合算法3.1對(duì)于工件數(shù)量較多,迭代次數(shù)較多的算法有較高的性能.

圖1 兩種算法流程圖

表1 實(shí)驗(yàn)中的參數(shù)設(shè)置

5 總結(jié)

本文針對(duì)差異工件批調(diào)度問(wèn)題,并考慮到蟻群算法的早熟性問(wèn)題,將魚(yú)群算法與之相結(jié)合,利用魚(yú)群算法中魚(yú)群防止過(guò)度聚集,擁擠度限制的方法,避開(kāi)蟻群算法在尋優(yōu)前期早熟死循環(huán).對(duì)于算法結(jié)果,本文通過(guò)負(fù)載率和利用率均值的相比較來(lái)判斷算法結(jié)果的優(yōu)劣,迭代次數(shù)的比較來(lái)對(duì)比算法效率.通過(guò)對(duì)比的結(jié)果發(fā)現(xiàn),混合算法前期可以有效避免早熟,而且在算法后期又可以加快收斂,從而使尋優(yōu)個(gè)體能夠加快尋找到滿意解.

但是對(duì)于混合算法中,混合算法3.1的更新率、擁擠的閾值,以及混合算法3.2中迭代次數(shù)限制,都需要人為確定,但是針對(duì)不同情況下,不同的值對(duì)結(jié)果有著不同的影響,那么工件數(shù)量、工件尺寸的分布、工件的加工時(shí)間和機(jī)器的尺寸和這些值的關(guān)系還需要進(jìn)一步的探究.

表2 ACO和AFSA算法對(duì)比

表3 混合算法3.1和3.2對(duì)比

圖2 算法迭代次數(shù)對(duì)比

圖3 利用率負(fù)載率均值對(duì)比

1 王栓獅,陳華平,程八一,等.一種差異工件單機(jī)批調(diào)度問(wèn)題的蟻群優(yōu)化算法.管理科學(xué)學(xué)報(bào),2009,12(6):72–82.

2 Ghazvini FJ,Dupont L.Minimizing mean flow times criteria on a single batch processing machine with non-identical jobs sizes.International Journal of Production Economics,1998,55(3):273–280.[doi:10.1016/S0925-5273(98)00067-X]

3 Melouk S,Damodaran P,Chang PY.Minimizing makespan for single machine batch processing with non-identical job sizes using simulated annealing.International Journal of Production Economics,2004,87(2):141–147.[doi:10.1016/S0925-5273(03)00092-6]

4 Damodaran P,Manjeshwar PK,Srihari K.Minimizing makespan on a batch-processing machine with non-identical job sizes using genetic algorithms.International Journal of Production Economics,2006,103(2):882–891.[doi:10.1016/j.ijpe.2006.02.010]

5 王笑蓉,吳鐵軍.Flowshop問(wèn)題的蟻群優(yōu)化調(diào)度方法.系統(tǒng)工程理論與實(shí)踐,2003,23(5):65–71.

6 姜樺,李莉,喬非,等.蟻群算法在生產(chǎn)調(diào)度中的應(yīng)用.計(jì)算機(jī)工程,2005,31(5):76–78,101.

7 王常青,操云甫,戴國(guó)忠.用雙向收斂蟻群算法解作業(yè)車(chē)間調(diào)度問(wèn)題.計(jì)算機(jī)集成制造系統(tǒng),2004,10(7):820–824.

8 盧輝斌,范慶輝,賈興偉.一種改進(jìn)的自適應(yīng)蟻群算法.計(jì)算機(jī)工程與設(shè)計(jì),2005,26(11):3065–3066.[doi:10.3969/j.issn.1000-7024.2005.11.064]

9 李曉磊,邵之江,錢(qián)積新.一種基于動(dòng)物自治體的尋優(yōu)模式:魚(yú)群算法.系統(tǒng)工程理論與實(shí)踐,2002,22(11):32–38.[doi:10.3321/j.issn:1000-6788.2002.11.007]

10 李曉磊,路飛,田國(guó)會(huì),等.組合優(yōu)化問(wèn)題的人工魚(yú)群算法應(yīng)用.山東大學(xué)學(xué)報(bào)(工學(xué)版),2004,34(5):64–67.

11 侯景偉,孔云峰,孫九林.基于多目標(biāo)魚(yú)群-蟻群算法的水資源優(yōu)化配置.資源科學(xué),2011,33(12):2255–2261.

12 王聯(lián)國(guó),洪毅,趙付青,等.一種改進(jìn)的人工魚(yú)群算法.計(jì)算機(jī)工程,2008,34(19):192–194.[doi:10.3969/j.issn.1000-3428.2008.19.065]

13 修春波,張雨虹.基于蟻群與魚(yú)群的混合優(yōu)化算法.計(jì)算機(jī)工程,2008,34(14):206–207,218.[doi:10.3969/j.issn.1000-3428.2008.14.073]