云制造環境下基于蟻群算法資源動態調度優化

江笑妍　李芳

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

關鍵詞：云制造；蟻群算法；資源動態調度函數；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 引 言

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

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

1 云制造資源調度過程的描述

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

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

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

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

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

現在就將封裝中的CSP進行改進優化，如果某個CSP在完成整個封裝中的任務且通過質量監測后可變成游離狀態，即可開始搜索CSU進行下一批次的封裝任務。假設：

CSP

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

2 云資源動態調度函數

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

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

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

3 通過蟻群算法進行優化

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

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

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

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

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

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

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

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

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

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

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

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

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

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

①最短距離的對比

②局部最優的改進

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

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

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

4 結 論

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

參考文獻：

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

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

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

-2760.

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

[5] 唐海波，黃瓊瓊，等. 云制造環境下資源動態調度系統研究[J]. 機械工程與自動化，2014，12（6）：4-6.

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

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

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

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

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

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

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

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

[14] 葛江華，孫月洲. 云制造車間資源調度與配置模型及優化研究[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