王文濤，穆曉峰，王玲霞

(中南民族大學(xué) 計算機(jī)科學(xué)學(xué)院，武漢 430074)

?

基于蟻群算法的無聯(lián)系并行機(jī)調(diào)度問題的仿真研究

王文濤，穆曉峰，王玲霞

(中南民族大學(xué) 計算機(jī)科學(xué)學(xué)院，武漢 430074)

摘要針對無聯(lián)系并行機(jī)調(diào)度求解問題，引入了蟻群算法的思想.基于轉(zhuǎn)移概率構(gòu)建的信息素迭代模型，研究了無聯(lián)系并行機(jī)調(diào)度問題的求解過程.基于Python的仿真實(shí)驗(yàn)結(jié)果表明：通過蟻群算法可以得到其近似解；更進(jìn)一步探求了任務(wù)次序?qū)獾挠绊?；通過實(shí)驗(yàn)探索了此算法的時間性能.

關(guān)鍵詞并行機(jī)；任務(wù)調(diào)度；蟻群算法

Study on Unrelated Parallel Machine Scheduling Problem Based on the Ant Colony Algorithm

WangWentao,MuXiaofeng,WangLingxia

(College of Computer Science, South-Central University for Nationalities,Wuhan 430074,China)

AbstractAiming at unrelated parallel machine scheduling problem, we introduced the idea of ant colony algorithm. Based on pheromone iterative model constructed by transfer probability, we researched the solving process of unrelated parallel machine scheduling problem. The results of the simulation test based on Python illustrate that ant colony algorithm can reach an approximate solution. Furthermore, we explored the influence of different task sequence on solution. At last, we performed some experiment to analyze time performance of the algorithm.

Keywordsparallel machine；task scheduling；ant colony algorithm

在人們生產(chǎn)生活的諸多領(lǐng)域都存在著調(diào)度問題，例如工廠如何分配工件在合適的機(jī)器上執(zhí)行；此外，隨著互聯(lián)網(wǎng)的發(fā)展，云計算已經(jīng)成為一大熱點(diǎn)，如何對云環(huán)境下的資源進(jìn)行調(diào)度，本質(zhì)上也是此類問題.優(yōu)良的調(diào)度策略能夠極大地提高生產(chǎn)效率.

本文對無聯(lián)系并行機(jī)器調(diào)度問題(UPMSP)[1]進(jìn)行研究.問題可以描述如下：有N個任務(wù)在時間點(diǎn)0處開始，有M臺機(jī)器可供這些任務(wù)運(yùn)行，最終的調(diào)度目標(biāo)是使這些任務(wù)總的完成時間(makespan)最小，其中M

在M不大的情況下可以在多項(xiàng)式時間內(nèi)找到最優(yōu)解；反之，是一個NP-hard問題，采用啟發(fā)式的算法可以在合理的時間內(nèi)找到一個近似解[2,3].

一些研究者開發(fā)了確定性算法來解決UPMSP問題.在文[4]和[5]中，Liaw和Lancia開發(fā)了分支定界法來找出最優(yōu)解.

另外一些研究者考慮采用啟發(fā)式的方法來解決此問題.在文[6]中，作者考慮了增加負(fù)載均衡這一條件，并采用蟻群算法求調(diào)度策略的解.Arnaout采用蟻群算法來解決有安裝時間限制和有任務(wù)依賴下的UPMSP問題，經(jīng)過實(shí)驗(yàn)表明此算法性能更好[7].最近，Arnaout又提出了一個兩階段蟻群算法來最小化總?cè)蝿?wù)的完成時間[8]，該算法在第一階段通過蟻群算法找出放置在機(jī)器上的合適的任務(wù)，第二階段在機(jī)器上對這些任務(wù)進(jìn)行合適的調(diào)度使得總完成時間最少.

本文的關(guān)注點(diǎn)在于利用蟻群算法解決機(jī)器數(shù)目與任務(wù)數(shù)目都較大情況下的UPMSP問題.通過仿真實(shí)驗(yàn)說明蟻群算法可以解決UPMSP問題.

1基于UPMSP的ACO算法

1.1UPMSP模型

ti(i=1,2,3，…,n)表示第i個任務(wù)，T={t1,t2,…,tn}表示這n個任務(wù)的集合；mj(j=1，2，3,…,m-1,m)表示第j臺機(jī)器，M={m1,…,mm}表示m臺機(jī)器的集合.ti放置在mj機(jī)器上執(zhí)行，其運(yùn)行時間記為pij，N個任務(wù)運(yùn)行在M臺機(jī)器上的運(yùn)行時間用pij組成的矩陣P表示；kij代表指標(biāo)矩陣中的某一元素，若為1表示第i個任務(wù)分配在第j臺機(jī)器上，否則為0，這標(biāo)明了在P矩陣中選出哪些元素.模型如下：

(1)

Subjectto:

(2)

kij∈{0,1},i=1,2,…,n;j=1,2,…,m.

(3)

限制如下：(1)n個任務(wù)之間沒有依賴，即任意一個任務(wù)可以在任意時刻執(zhí)行；(2)任一任務(wù)不能被搶占；(3)一個任務(wù)在任一機(jī)器上執(zhí)行完畢就不再參與.

1.2算法流程及說明

(1) 總體流程.算法總體流程見表1.

表1　ACO 算法

算法首先對如下數(shù)據(jù)進(jìn)行初始化：信息素矩陣、任務(wù)序列、迭代次數(shù)(算法1第2句).之后不斷迭代直至迭代次數(shù)達(dá)到最大值(算法1第3句)，在每輪迭代中每個螞蟻會爬一條路徑，這條路徑經(jīng)過的點(diǎn)就是解(算法1第4句)，之后對螞蟻爬過的信息素進(jìn)行更新(算法1第5句).

(2) 初始化.信息素矩陣的所有元素初始化為1，同時生成一個任務(wù)序列.τij表示分配任務(wù)i到機(jī)器j上的信息素.信息素τij組成信息素矩陣T.

在構(gòu)建解的過程中，螞蟻需要重復(fù)一個基本的決策過程[9]：選擇哪個機(jī)器來完成這項(xiàng)任務(wù)，其中任務(wù)的次序不進(jìn)行學(xué)習(xí)，即預(yù)先給定一個任務(wù)序列，每個螞蟻都按這個序列的次序行進(jìn)，在爬取的過程中只學(xué)習(xí)任務(wù)與機(jī)器之間的信息素.信息素與任務(wù)和機(jī)器的組合有關(guān).

(3) 任務(wù)選擇. 選擇執(zhí)行指定任務(wù)的機(jī)器的概率如下：

(4)

(4) 信息素的更新. 如果此輪迭代某個螞蟻得到的最優(yōu)解優(yōu)于全局最優(yōu)解，那么對信息素進(jìn)行如下更新：

(5)

1.3實(shí)驗(yàn)設(shè)計

機(jī)器硬件配置如下：CPU為Intel core i5 4590，內(nèi)存為16GB.本仿真實(shí)驗(yàn)在Python2.7上實(shí)現(xiàn).

(1) 任務(wù)序列. 本實(shí)驗(yàn)的任務(wù)序列是從小到大的一個有序序列(1,2,3，…,n).

(2) 機(jī)器數(shù)和任務(wù)數(shù)的組合. 在真實(shí)環(huán)境中為了使機(jī)器得到充分利用，任務(wù)數(shù)需要大于機(jī)器數(shù).基于文獻(xiàn)[8]，在實(shí)驗(yàn)中設(shè)置任務(wù)數(shù)和機(jī)器數(shù)的比值為N/M≥15，具體設(shè)置如下：機(jī)器數(shù)目為2與任務(wù)數(shù)集合(40,60,80,100,120)中任一元素的組合；機(jī)器數(shù)目4與集合(60,80,100,120)中任一元素的組合；機(jī)器數(shù)目6與集合(100,120)任一元素的組合；機(jī)器數(shù)目8與任務(wù)數(shù)120的組合.由此，共得到12個機(jī)器數(shù)目和任務(wù)數(shù)目的組合.

(3) 任務(wù)運(yùn)行時間矩陣. 在此采用文[8]的做法，設(shè)置了運(yùn)行時間滿足均勻分布：U～(50,100).為說明問題簡單起見，單位設(shè)置為秒.

(4) 參數(shù). 經(jīng)過多次試驗(yàn)，ρ和Φ分別設(shè)置為0.01和0.3算法可以達(dá)到較好的性能.

(5) 迭代次數(shù). 在處理任務(wù)數(shù)目與機(jī)器數(shù)目比值相對較大的情況下，可能在迭代終止時蟻群算法并沒有收斂，因此迭代次數(shù)需要相應(yīng)增加.經(jīng)過試驗(yàn)，迭代次數(shù)設(shè)置為3種：300，500，1000.在300的情況下，算法可以較快結(jié)束；在1000的情況下算法基本可以收斂；500次迭代是為了取上述兩種的中間情況.

(6) 螞蟻個數(shù). 通過不同的螞蟻數(shù)目，觀察其對解的影響.本實(shí)驗(yàn)中個數(shù)設(shè)置為8和12.

(7) 重復(fù)次數(shù). 為了比較在同一條件下算法的性能，進(jìn)行重復(fù)實(shí)驗(yàn)10次.

故在10次重復(fù)實(shí)驗(yàn)、3種迭代參數(shù)、2種螞蟻數(shù)量、12種組合的情況，共計進(jìn)行了720(10×3×2×12)次實(shí)驗(yàn).

2實(shí)驗(yàn)結(jié)果及分析

實(shí)驗(yàn)結(jié)果及統(tǒng)計數(shù)據(jù)見圖1和表2.

圖1是在機(jī)器數(shù)為2和任務(wù)數(shù)為40的情況下蟻群算法的收斂圖.minMakespan和maxMakespan分別代表每輪迭代中的最小完成時間和最大完成時間.由此可知，在迭代次數(shù)接近150處最小完成時間開始收斂，在180左右，最大完成時間開始收斂.其它組合情況類似.

圖1　收斂情況Fig.1　Convegence situation

由表2可以看出，相鄰組試驗(yàn)中，隨著螞蟻數(shù)目的增加，有的解變得更好，而有的則不然，所以不能看出螞蟻數(shù)量對于解的好壞的決定性因素.原因有兩個：一是每只螞蟻只搜索了一條路徑，螞蟻數(shù)量越多得出的解就越精確，但是若很多螞蟻都沒有找到一條比以前更優(yōu)解，那么解不見得會更好；二是蟻群算法過早收斂陷入了局部解，這樣算法不能找到更優(yōu)解.針對陷入局部解的解決方法有兩個：(1)多次試驗(yàn)，設(shè)置合適的揮發(fā)因子等其他參數(shù)，但是此種方法或會導(dǎo)致算法只能適用在特定問題的特定數(shù)據(jù)集上，算法的通用性較差；(2)增加局部搜索算法，這樣每個螞蟻得到一個最優(yōu)解之后都會繼續(xù)進(jìn)行搜索，此方法的問題是不僅增加了算法的復(fù)雜度，而且也需要對特定問題進(jìn)行局部搜索的算法設(shè)計.針對上述問題及解決方案，在后續(xù)的研究中會作進(jìn)一步探索.

表2　近似解統(tǒng)計數(shù)據(jù)

圖2　重復(fù)實(shí)驗(yàn)的結(jié)果Fig.2　The results of repeated experiments

圖2是機(jī)器數(shù)為2、任務(wù)數(shù)為40、螞蟻數(shù)為8的情況下10次重復(fù)試驗(yàn)的解.10次實(shí)驗(yàn)中最小值和最大值的差異并不大，比如在(2,120,12)行中，最小值為4001，最大值為4088，差值僅為4001的2.1%.所以在實(shí)際生產(chǎn)環(huán)境下可以不進(jìn)行多次重復(fù)實(shí)驗(yàn).同理在表1其他行也可以看出類似的情況.

在實(shí)驗(yàn)中，隨著迭代次數(shù)的增加，算法運(yùn)行時間也會增加，所以基于此可以減少算法的運(yùn)行時間：本次實(shí)驗(yàn)中迭代次數(shù)是固定的，以后的實(shí)驗(yàn)中可以對此進(jìn)行改進(jìn)，一旦算法已經(jīng)收斂，就不需要運(yùn)行至已設(shè)的最大迭代次數(shù).

綜上說明無聯(lián)系任務(wù)的調(diào)度策略可以通過蟻群算法得到近似解.

3擴(kuò)展實(shí)驗(yàn)

上文中，每個螞蟻都是從第一個任務(wù)按序爬至最后一個任務(wù)，并沒有對任務(wù)之間的信息素進(jìn)行更新，而只更新了任務(wù)在機(jī)器中的信息素，下面通過實(shí)驗(yàn)探求不同的任務(wù)次序?qū)獾挠绊懺诒疚牡脑囼?yàn)中，如果任務(wù)有40個，任務(wù)次序的排列有40!種，對全部排列進(jìn)行實(shí)驗(yàn)是不可能的.故實(shí)驗(yàn)設(shè)計為兩組，在任務(wù)數(shù)和機(jī)器數(shù)的組合為40和2的情況下隨機(jī)選取了30000個不同的任務(wù)次序進(jìn)行實(shí)驗(yàn)；對于80和4的情況下則選取了3000個，統(tǒng)計得到解的分布.對上述算法1的初始化部分進(jìn)行修改，每次實(shí)驗(yàn)生成一個不同于之前的排列.

對3000和30000個不同任務(wù)次序進(jìn)行實(shí)驗(yàn)，表3的結(jié)果表明：最小值與均值的差異并不大，但最大值與均值相差較大，說明較多的解分布在均值附近，較差的解出現(xiàn)的次數(shù)較少.

表3　統(tǒng)計數(shù)據(jù)

如圖3所示，任務(wù)數(shù)40和機(jī)器數(shù)2情況下，大多數(shù)解密集分布在1400左右，圖像出現(xiàn)了某些毛刺，說明這些解較差.從總體上看，沒有出現(xiàn)解的某種分布傾向，圖4類似.在UPMSP問題中，因?yàn)槿蝿?wù)與任務(wù)間并沒有先后順序的約束，所以并不需要學(xué)習(xí)任務(wù)之間的信息素.綜上得出結(jié)論，任務(wù)次序?qū)PMSP問題解的影響可以忽略.

圖3　30000次試驗(yàn)下解的分布Fig.3　Distribution of solution in the 30000 case

圖4　3000次試驗(yàn)下解的分布Fig.4　Distribution of solution in the 3000 case

4性能分析

引入文[10]中的時間性能評價指標(biāo)，同時為了適應(yīng)本研究的目的，對其做了些許修改，如下：

(6)

Ia為算法滿足終止條件時平均的迭代次數(shù)，Imax為給定的最大迭代次數(shù).顯然，E值越小，算法的收斂速度越快.該指標(biāo)直接衡量了算法搜索可行解的快慢程度.

為簡單起見，同時能說明問題，實(shí)驗(yàn)設(shè)置的最大迭代次數(shù)Imax為1000，在10次重復(fù)實(shí)驗(yàn)、1種迭代參數(shù)、2種螞蟻數(shù)量、12種組合的情況下，共計進(jìn)行了240(10×1×2×12)次實(shí)驗(yàn)，實(shí)驗(yàn)數(shù)據(jù)見表4.

表4　E的統(tǒng)計數(shù)據(jù)

在實(shí)驗(yàn)中，有24組條件，每組重復(fù)實(shí)驗(yàn)10次.在24組條件中，有5組條件的10次重復(fù)實(shí)驗(yàn)有9次收斂，其他19組條件下的10次重復(fù)實(shí)驗(yàn)都收斂.

從表4可以看出，有的條件下，螞蟻數(shù)目變多，收斂會加快；而有的則不然，螞蟻數(shù)量對收斂速度的影響需要作進(jìn)一步研究.另外，在機(jī)器數(shù)不變的情況下，任務(wù)數(shù)變多，收斂所需的時間會變多，如在機(jī)器數(shù)為2的情況下，任務(wù)數(shù)增加，E值的趨勢是變大的，這是因?yàn)樗阉骺臻g變大，故搜索的時間也相應(yīng)增多.在任務(wù)數(shù)不變、機(jī)器數(shù)目變多的情況下，并沒有表現(xiàn)出明顯規(guī)律，如任務(wù)120、螞蟻12的情況下，E值分別為21.00%、22.47%、18.34%和17.72%，對其可能存在的規(guī)律還需要進(jìn)一步的探索.

本性能實(shí)驗(yàn)僅僅是通過仿真的方法來探索不同條件下此問題蟻群算法的收斂時間，因此在以后的工作中，還需要對其收斂性進(jìn)行理論研究.

5結(jié)論

合理的資源調(diào)度能有效地增加生產(chǎn)效率，因此對調(diào)度策略的研究具有重大價值.本文仿真實(shí)驗(yàn)結(jié)果表明：可以通過蟻群算法得到UPMSP近似解；基于任務(wù)次序的研究說明，任務(wù)次序?qū)平庠诮y(tǒng)計意義上沒有顯著影響；關(guān)于性能分析的實(shí)驗(yàn)說明隨著任務(wù)數(shù)目的增加，此算法需要更長的時間才能收斂.

參考文獻(xiàn)

[1]唐國春. 現(xiàn)代排序論[M]. 上海: 上?？茖W(xué)普及出版社, 2003:5-14.

[2]Garey M R, Johnson D S. Computers and intractability: a guide to the theory of NP-completeness[M]. San Francisco: Freeman, 1979: 236-243.

[3]Karp R M. Reducibility among combinatorial problems[M]. New York: Springer US, 1972: 85-103.

[4]Liaw C F, Lin Y K, Cheng C Y, et al. Scheduling unrelated parallel machines to minimize total weighted tardiness[J]. Computers & Operations Research, 2003, 30(12): 1777-1789.

[5]Lancia G. Scheduling jobs with release dates and tails on two unrelated parallel machines to minimize the makespan[J]. European Journal of Operational Research, 2000, 120(2): 277-288.

[6]張煥青, 張學(xué)平, 王海濤, 等. 基于負(fù)載均衡蟻群優(yōu)化算法的云計算任務(wù)調(diào)度[J]. 微電子學(xué)與計算機(jī), 2015, 5: 7.

[7]Arnaout J P, Rabadi G, Musa R. A two-stage ant colony optimization algorithm to minimize the makespan on unrelated parallel machines with sequence-dependent setup times[J]. Journal of Intelligent Manufacturing, 2010, 21(6): 693-701.

[8]Arnaout J P, Musa R, Rabadi G. A two-stage ant colony optimization algorithm to minimize the makespan on unrelated parallel machines—part II: enhancements and experimentations[J]. Journal of Intelligent Manufacturing, 2014, 25(1): 43-53.

[9]Dorigo M, Birattari M. Ant colony optimization[M]. New York: Springer US, 2010: 36-39.

[10]譚明交, 張宏梅, 呂艷秋. 群體智能算法及其性能評價指標(biāo)研究[J]. 計算機(jī)與數(shù)字工程, 2008, 36(8): 10-12.

中圖分類號TP301.6

文獻(xiàn)標(biāo)識碼A

文章編號1672-4321(2016)01-0127-05

基金項(xiàng)目國家民委教改基金資助項(xiàng)目(15013)；中南民族大學(xué)研究生創(chuàng)新基金資助項(xiàng)目(2016sycxjj199)

作者簡介王文濤(1967-)，男，副教授，博士，研究方向：計算機(jī)網(wǎng)絡(luò)與控制，E-mail：wangwt@mail.scuec.edu.cn

收稿日期2016-01-07