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

王文濤，穆曉峰，王玲霞

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

?

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

王文濤，穆曉峰，王玲霞

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

摘要針對無聯(lián)系并行機調度求解問題，引入了蟻群算法的思想.基于轉移概率構建的信息素迭代模型，研究了無聯(lián)系并行機調度問題的求解過程.基于Python的仿真實驗結果表明：通過蟻群算法可以得到其近似解；更進一步探求了任務次序對解的影響；通過實驗探索了此算法的時間性能.

關鍵詞并行機；任務調度；蟻群算法

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

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

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

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

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

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

1基于UPMSP的ACO算法

1.1UPMSP模型

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

(1)

Subjectto:

(2)

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

(3)

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

1.2算法流程及說明

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

表1　ACO 算法

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

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

在構建解的過程中，螞蟻需要重復一個基本的決策過程[9]：選擇哪個機器來完成這項任務，其中任務的次序不進行學習，即預先給定一個任務序列，每個螞蟻都按這個序列的次序行進，在爬取的過程中只學習任務與機器之間的信息素.信息素與任務和機器的組合有關.

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

(4)

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

(5)

1.3實驗設計

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

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

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

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

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

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

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

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

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

2實驗結果及分析

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

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

圖1　收斂情況Fig.1　Convegence situation

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

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

圖2　重復實驗的結果Fig.2　The results of repeated experiments

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

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

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

3擴展實驗

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

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

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

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

圖3　30000次試驗下解的分布Fig.3　Distribution of solution in the 30000 case

圖4　3000次試驗下解的分布Fig.4　Distribution of solution in the 3000 case

4性能分析

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

(6)

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

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

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

在實驗中，有24組條件，每組重復實驗10次.在24組條件中，有5組條件的10次重復實驗有9次收斂，其他19組條件下的10次重復實驗都收斂.

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

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

5結論

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

參考文獻

[1]唐國春. 現(xiàn)代排序論[M]. 上海: 上?？茖W普及出版社, 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]張煥青, 張學平, 王海濤, 等. 基于負載均衡蟻群優(yōu)化算法的云計算任務調度[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]譚明交, 張宏梅, 呂艷秋. 群體智能算法及其性能評價指標研究[J]. 計算機與數(shù)字工程, 2008, 36(8): 10-12.

中圖分類號TP301.6

文獻標識碼A

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

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

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

收稿日期2016-01-07