云制造環(huán)境下基于蟻群算法資源動態(tài)調(diào)度優(yōu)化

江笑妍　李芳

摘 要：動態(tài)資源調(diào)度是云制造中的一個關鍵問題。通過對資源動態(tài)在云制造環(huán)境下服務特點的了解，提出了基于蟻群算法的資源動態(tài)調(diào)度函數(shù)，以云服務提供者找到相對應的云服務使用者進行任務封裝的時間最短為目標。通過Matlab優(yōu)化了原有的資源動態(tài)服務模型，達到了預期的效果，對以后云制造下資源動態(tài)的調(diào)度具有指導意義。

關鍵詞：云制造；蟻群算法；資源動態(tài)調(diào)度函數(shù)；Matlab

中圖分類號：F253.9 文獻標識碼：A

Abstract： Dynamic resource scheduling is a key problem in cloud manufacturing. Based on resources dynamic characteristics under the environment of cloud manufacturing service，proposed based on ant colony algorithm resources dynamic scheduling function，aiming at the cloud service providers to find the corresponding task encapsulates the cloud service users the shortest time. The original resource dynamic service model was optimized by Matlab， reach the expected effect， under the cloud after manufacturing resources dynamic scheduling has a guiding significance.

Key words： cloud manufacturing； ant colony algorithm； resource dynamic scheduling function； Matlab

0 引 言

隨著現(xiàn)在科技的飛速發(fā)展，制造業(yè)開始逐步與新興云計算、物聯(lián)網(wǎng)等技術交叉融合，產(chǎn)生一種面向服務的制造新模式——云制造，它一改制造長期以來面向設備、面向資源、面向訂單、面向生產(chǎn)等的形態(tài)，從而轉(zhuǎn)而真正面向服務、面向需求。在云制造中，一切能封裝和虛擬化的都作為制造云服務（包括制造資源作為服務、制造能力作為服務、制造知識作為服務等）這種大轉(zhuǎn)變是作為實現(xiàn)生產(chǎn)型企業(yè)向服務型企業(yè)轉(zhuǎn)變、實現(xiàn)制造即服務（Manufacturing-as-a-Service， MFGaaS）的基礎。在云制造中，通過物聯(lián)網(wǎng)、虛擬化等技術實現(xiàn)資源的封裝、發(fā)布、搜索、調(diào)度、執(zhí)行、檢測等功能，滿足云服務提供者（Cloud Sevice Provide， CSP）和云服務使用者（Cloud Service User， CSU）之間的資源對接。本文重點討論資源從CSP動態(tài)調(diào)度到CSU的這個過程，爭取云制造資源的利用率達到最優(yōu)是我們的目標。

目前各學者對云制造進行了相關研究，李伯虎院士為求解更加復雜的制造問題展開大規(guī)模協(xié)同制造，提出了一種面向服務的網(wǎng)絡化制造新模式——云制造。陶飛、張霖等人設計了制造云服務管理原型系統(tǒng)功能結(jié)構(gòu)， 對基于云制造全生命周期運行的云服務組合需求進行了闡述。對云服務組合建模/描述和一致性檢查、云服務關聯(lián)關系、云服務組合柔性、組合網(wǎng)絡及其動力學特性、云服務組合建模與評估、組合優(yōu)選等實現(xiàn)云服務組合的關鍵問題進行了研究， 為未來實現(xiàn)高效智能化的云制造服務管理提供理論支持[1]；張勇凱、李芳等人用ROV編碼對蝙蝠算法進行了重新編碼和解碼，并且對其進行了混沌序列初始化和自適應變步長的運算步長改進，提高了原蝙蝠算法的收斂速度和最優(yōu)解的精度[2]，倪志偉、王會穎等人基于云計算技術和云服務技術研究了云服務的動態(tài)選擇問題，給出了云制造服務層次化模型，提出了一種基于MapReduce和多目標蟻群算法的制造云服務動態(tài)選擇算法（CSSMA）[3]；武超然、江海濤通過改進蝙蝠算法，實現(xiàn)了供需調(diào)度時間的最優(yōu)[4]；唐海波、黃瓊瓊等提出了基于負載資源的均衡的動態(tài)調(diào)度策略，建立了以完成任務的總服務成本為最優(yōu)化目標的模型，并實際驗證了可行性[5]。以上對于云制造資源調(diào)度的研究還有很大的發(fā)展空間，本文將以云制造資源的利用率為目標進行研究討論。

1 云制造資源調(diào)度過程的描述

云制造資源的調(diào)度其實是實現(xiàn)云服務提供者CSP到云服務使用者CSU對接的過程。云服務提供者CSP包括原材料供應商、加工生產(chǎn)商、物流配送商等，他們各自將自身可以提供的資源登記在云服務的平臺，等待云制造資源的出租銷售；而云制造資源這個虛擬的資源是游離在云服務平臺的，毫無序列而言，只等待搜索到相對應的云服務使用者CSC后，封裝到某個生產(chǎn)生命周期，供云服務使用者USU使用；而云服務使用者CSU向云服務平臺提出自己的需求，等待平臺安排相應的云制造資源供其使用。

1.1 質(zhì)量檢測機制。在已經(jīng)匹配好的一系列生命周期的生產(chǎn)工序中，前一個云服務提供者CSP完成這一項工序后要被檢測合格后才可轉(zhuǎn)交給下一個云服務提供者CSP進行下一項工序，否則重新完成。這樣既可保證服務質(zhì)量，又可減少損失，如若沒有合格標準檢測機制，不光會導致整條服務的不合格，云服務使用者不滿意，而且無法完成這一項任務，整個生命周期需要的云服務提供者CSP都要重新來過，浪費了其他云服務提供者CSP的時間，降低了整個云服務資源的利用率。

1.2 原始資源動態(tài)調(diào)度過程。由于云服務平臺數(shù)據(jù)處理的冗雜性，將有相同需求的云服務使用者CSU作為同一批次進行處理，通過關鍵詞搜索需要的一系列云制造資源，將它們進行封裝，作為一個整體完成任務。只有當所有的云服務使用者CSU的任務需求全部完成時，云服務提供者CSP才可以被釋放，成為原來的游離狀態(tài)，即可以繼續(xù)下一批次的任務所搜索，繼而封裝在另一個整體工作。endprint

從圖1可知，第一批次是有5個云服務提供者CSP1，2，3，4，5完成云服務使用者CSU1，2，3，4，5，6，7，8的任務，隨機產(chǎn)生的任務安排為2，4，1，3，3，5，1，2表示第一個任務由CSP2完成，第二個任務由CSP4完成，第三個任務由CSP1完成，第四、五個任務都由CSP3完成，第六個任務由CSP5完成，第七個任務由CSP1完成，最后一個任務由CSP2完成。

1.3 改進后的資源動態(tài)調(diào)度過程。通過原始的資源動態(tài)調(diào)度過程圖解可以看出，CSP1在完成第七個任務后閑置了一個工序，CSP2一直要完成最后一次才可被釋放，CSP3在完成第五個任務后閑置了三個工序，CSP4在完成第二個任務后閑置了六個工序，CSP5在完成第六個任務后閑置了兩個工序。由此可知，大部分的CSP是閑置的。

現(xiàn)在就將封裝中的CSP進行改進優(yōu)化，如果某個CSP在完成整個封裝中的任務且通過質(zhì)量監(jiān)測后可變成游離狀態(tài)，即可開始搜索CSU進行下一批次的封裝任務。假設：

CSP

在每個CSP從任務完成變成游離狀態(tài)時，它的相應的編碼狀態(tài)也從1變成0，我們在每個批次的封裝任務的最后一道工序設置一個可通過CSP狀態(tài)為0時通過，即可以進行下一批次任務搜索，然后如此循環(huán)往復。所以改進后的資源動態(tài)調(diào)度過程如圖2所示：

2 云資源動態(tài)調(diào)度函數(shù)

提高云制造資源的利用率實際上是盡量讓每個CSP都在任務中，即大部分時間都在工作，減少不必要的時間浪費，所以我們通過CSP完成一定數(shù)量的任務時間來檢測云制造資源的利用率。

其中，R是云制造資源利用率，MaxR是我們的優(yōu)化目標；t 是CSP 完成任務的時間，t 是CSP 通過質(zhì)量檢測的時間，t 包括CSP搜索到匹配的CSU的時間以及等待浪費時間的兩部分時間；CSP 代表CSP狀態(tài)，為0時是閑置狀態(tài)，即此CSP在本次封裝任務中不需要，反之，若為1則是任務狀態(tài)，即此CSP不能進行搜索本次封裝任務。這個時間的比率即可代表云制造資源的利用率。

下面，我們通過將t 最小化來達到整體提高云資源利用率的目標，因為在一定數(shù)量任務前提下，完成任務的時間越短，其浪費的等待時間就越少，云資源的利用率就越高。

3 通過蟻群算法進行優(yōu)化

3.1 蟻群算法的基本思想。蟻群算法（Ant Colony Algorithm， ACA）是由意大利學者M.Dorigo等人提出的一種模擬進化算法，其真實的模擬了自然界螞蟻群體的覓食行為。螞蟻在尋找食物時，會在其經(jīng)過的路上釋放一種信息素，并能夠感知其他螞蟻釋放的信息素。信息素的濃度的大小表征路徑的遠近，信息素濃度越高，表示對應的路徑距離越短。螞蟻在路徑上前進時會根據(jù)前邊走過的螞蟻所留下的分泌物選擇其要走的路徑。其選擇一條路徑的概率與該路徑上分泌物的強度成正比。因此，由大量螞蟻組成的群體的集體行為實際上構(gòu)成一種學習信息的正反饋現(xiàn)象：某一條路徑走過的螞蟻越多，后面的螞蟻選擇該路徑的可能性就越大。螞蟻的個體間通過這種信息的交流尋求通向食物的最短路徑。

將蟻群算法應用于解決優(yōu)化問題的基本思路為：用螞蟻的行走路徑表示優(yōu)化問題的可行解，整個螞蟻群體的所有路徑構(gòu)成優(yōu)化問題的解空間，路徑較短的螞蟻釋放的信息素較多，隨著時間的推進，較短的路徑上累積的信息素濃度逐漸提高，選擇該路徑的螞蟻個數(shù)也愈來愈多。最終，整個螞蟻群體會在正反饋的作用下集中到最佳路徑上，此時對應的便是待優(yōu)化問題的最優(yōu)解。

3.2 改進后螞蟻個數(shù)的設定。螞蟻群在覓食時，分開各自尋找食物，并通過釋放信息素通知其他螞蟻的路徑情況，由于螞蟻個體尋找路徑的不同，尋找到食物的先后順序是不同的，先找到食物的螞蟻，會在其經(jīng)過的路徑上釋放較高濃度的信息素來通知其他螞蟻，在其找到食物到達巢穴的最佳途徑后便不再外出覓食，此時還在外面覓食的蟻群數(shù)量則會相應減少，但整個蟻群的數(shù)量是一定的。

原始的蟻群算法在整個過程中，螞蟻的數(shù)量是一成不變的。在本文中，假設在一定的時間內(nèi)，云資源使用者CSU的個數(shù)是一定的，云資源提供者CSP（即虛擬的螞蟻）的個數(shù)是不定的，即隨著搜索封裝任務的進行，有一部分的CSP是在任務狀態(tài)的，不能參與搜索任務，但是總的CSP的個數(shù)上限是一定的，即在所有的CSP開始和結(jié)束任務搜索時的個數(shù)是一定的，即CSP沒有任務搜索時的個數(shù)是一定的。

3.3 算法過程描述。云制造環(huán)境下應用蟻群算法解決云資源的動態(tài)調(diào)度過程可以在圖形的幫助下轉(zhuǎn)化為蟻群覓食網(wǎng)絡。由CSP1，2，3，4，…，m的集合組成螞蟻群，與之相對應的是由一系列小節(jié)點組成的CSU大節(jié)點，按照任務類型的不同，分成不同的小節(jié)點，而其中的每一個小節(jié)點都是要求類似的CSU群，這一系列的CSU群按照在云平臺登記的時間先后排列。CSP集合中的每個個體對CSU群進行搜索，然后按照時間順序進行任務封裝。S代表虛擬起點，E代表虛擬終點，所以本文的云資源的動態(tài)調(diào)度問題就轉(zhuǎn)化為了尋找從S到E的最短路徑問題。蟻群算法對云制造下資源調(diào)度過程的描述如圖3所示。

3.4 蟻群算法解決云制造下資源調(diào)度問題的基本原理。設整個螞蟻群體中的螞蟻數(shù)量為m，即云制造環(huán)境中云制造資源的提供者CSP的數(shù)量為m，云制造資源的使用者CSU的數(shù)量為n，使用者CSU 與CSU 之間的先后到達時間差為t ，t時刻CSU 與CSU 連接過程中的信息素濃度為τ t。初始時刻，各個CSU之間連接過程中的信息素濃度相同，設為τ 0= τ 。

提供者Kk=1，2，3，…，m根據(jù)各個與使用者之間連接過程中的信息素濃度決定下一個搜索的使用者，設P t表示t時刻提供者K從使用者i轉(zhuǎn)移到使用者j的概率，其計算公式為：

其中，μ t為啟發(fā)函數(shù)，μ t=1/t ，表示提供者從使用者i轉(zhuǎn)移到使用者j的期望程度；allow k=1，2，3，…，m為提供者K待訪問使用者的集合，開始時，allow 中有n-1個元素，即包括除了提供者K除搜索使用者之外的其他使用者，隨著時間的推進，allow 中的元素不斷減少，直至為空，即表示所有的使用者搜索完畢；α為信息素重要程度因子，其值越大，表示信息素的濃度在轉(zhuǎn)移中起的作用越大；β為啟發(fā)函數(shù)重要程度因子，其值越大，表示啟發(fā)函數(shù)在轉(zhuǎn)移中的作用越大，即提供者會以較大的概率轉(zhuǎn)移到距離較短的使用者。endprint

如上所述，在提供者釋放信息素的同時，各個使用者之間的連接過程上的信息素逐漸消失，設參數(shù)ρ（0<ρ<1）表示信息素的揮發(fā)程度。因此，當所有提供者完成一次循環(huán)后，各個使用者之間連接過程上的信息素濃度需進行實時更新，即：

其中，Δτ 表示第k個提供者在使用者i與使用者j搜索過程中釋放的信息素濃度；Δτ 表示所有提供者在使用者i與使用者j搜索過程中釋放的信息素濃度之和。

3.5 蟻群算法的優(yōu)化結(jié)果。第一次迭代時，云資源提供者CSP的個數(shù)是滿值30個，隨著CSP在搜索匹配的云資源使用者CSU的過程中，有部分CSP已經(jīng)搜索到匹配的CSU，即從不匹配的CSU 轉(zhuǎn)移到匹配的CSU ，所以剩下的還未搜索到匹配的CSU的CSP的個數(shù)就產(chǎn)生了變化，在本文中，對云資源提供者CSP的個數(shù)（螞蟻數(shù)量）采用實時更新機制，使其更符合實際的云資源調(diào)度過程。

下面是改進后CSP搜索匹配到匹配的CSU的過程：

圖4、圖5是改進前、后迭代最短距離與平均距離對比。

通過Matlab進行仿真實驗后，得出兩個結(jié)論：

①最短距離的對比

②局部最優(yōu)的改進

改進前，在100次迭代中，第40次已達到最優(yōu)，但此時的最優(yōu)往往是局部最優(yōu)，未能找到全局最優(yōu)；改進后，大概在第72次迭代達到最優(yōu)，避免局部最優(yōu)，找到更好的最優(yōu)解。

我們在初始設置了以月（30）為單位和以天（24）為單位的30組數(shù)據(jù)，以蟻群算法為基礎進行仿真，在100次迭代后，得到了100.8135這個最短距離的最優(yōu)解，比之前的105.3275的更優(yōu)化，迭代次數(shù)由40增加到72，能夠更大可能的找到全局最優(yōu)解，達到了優(yōu)化的目的。

通過在Matlab中的仿真實驗，發(fā)現(xiàn)了改進后，云服務提供者CSP搜索到匹配的云服務使用者CSU的最短距離縮短了，相應的所耗時間也減少了，因為twi包括CSP搜索到匹配的CSU的時間以及等待浪費時間的兩部分時間，所以在這里我們便減少了搜索的時間，即減小了twi，在云資源利用率最大化中，成功的提高了利用率R，達到了預期的目標。

4 結(jié) 論

本文針對云平臺上云資源提供者CSP搜索匹配云資源使用者CSU并進行任務封裝的過程，提出了基于蟻群算法的解決方法。通過Matlab的仿真實驗，量化數(shù)據(jù)的前后對比，表明本文對于云資源調(diào)度過程的改進是可行的，能夠在更短的時間內(nèi)對云資源提供者CSP和云資源使用者CSU進行匹配，并且避免了局部最優(yōu)，使得出的最優(yōu)解更具有說服力，對以后的云資源動態(tài)調(diào)度過程有一定指導意義。

參考文獻：

[1] 陶飛，張霖，郭華，等. 云制造特征及云服務組合關鍵問題研究[J]. 計算機集成制造系統(tǒng)，2011，17（3）：477-486.

[2] 張勇凱，李芳，等. 改進蝙蝠算法在云制造供應鏈中的應用[J]. 數(shù)學理論與應用，2015，35（2）：83-94.

[3] 倪志偉，王會穎，等. 基于MapReduce和多目標蟻群算法的制造云服務動態(tài)選擇算法[J]. 中國機械工程，2014，10（20）：2751

-2760.

[4] 武超然，江海濤，等. 云制造平臺下基于蝙蝠算法的供需調(diào)度時間優(yōu)化[J]. 現(xiàn)代情報，2014，10（10）：35-40.

[5] 唐海波，黃瓊瓊，等. 云制造環(huán)境下資源動態(tài)調(diào)度系統(tǒng)研究[J]. 機械工程與自動化，2014，12（6）：4-6.

[6] 付超，肖明. 云制造環(huán)境下的云服務組合優(yōu)選方法[J]. 計算機應用研究，2014，6（6）：1744-1751.

[7] 李芳，單大亞，馬婷. 基于多智能體的虛擬企業(yè)群協(xié)同生產(chǎn)調(diào)度模式研究[J]. 計算機應用研究，2013，30（6）：1624-1629.

[8] 吳昊，倪志偉，王會穎. 基于MapReduce的蟻群算法[J]. 計算機集成制造系統(tǒng)，2012，16（7）：1503-1509.

[9] 李伯虎，張霖，王時龍，等. 云制造——面向服務的網(wǎng)絡化制造新模式[J]. 計算機集成制造系統(tǒng)，2010，16（1）：1-7，16.

[10] 李伯虎，張霖，任磊，等. 云制造典型特征、關鍵技術與應用[J]. 計算機集成制造系統(tǒng)，2012，18（7）：1345-1356.

[11] 蔡坦，劉衛(wèi)寧，等. 一種新的基于直覺模糊集的制造云服務優(yōu)選方法[J]. 中國機械工程，2014，2（3）：352-356.

[12] 劉衛(wèi)寧，李一鳴，劉波. 基于自適應粒子群算法的制造云服務組合研究[J]. 計算機集成制造系統(tǒng)，2012，18（10）：2869-2874.

[13] 李京生，王愛民. 基于動態(tài)資源能力服務的分布式協(xié)同調(diào)度技術[J]. 計算機集成制造系統(tǒng)，2012（7）：1563-1574.

[14] 葛江華，孫月洲. 云制造車間資源調(diào)度與配置模型及優(yōu)化研究[D]. 哈爾濱：哈爾濱理工大學（碩士學位論文），2012：59.

[15] Udhayakumar P， Kummana N N S. Sequencing and scheduling of job and tool in a flexible manufacturing system using ant colony optimization algorithm[J]. International Journal of Advanced Mancturing Technology， 2010，50（9-12）：1075-1084.

[16] TAO Fei， ZHAO Dongmi ng， ZHANG Lin. Resource service optimal-selection based on intuitionistic fuzzy set and non-functionality QoS in manufacturing grid system[J]. Knowledge and Informai on Systems， 2010，25（1）：185-208.endprint