云計算環境下工業生產負載分配及調度方法設計

柯　鵬（武漢科技大學計算機科學與技術學院，武漢430065）

云計算環境下工業生產負載分配及調度方法設計

柯鵬
（武漢科技大學計算機科學與技術學院，武漢430065）

針對未來工業生產的發展趨勢，設計基于云計算環境下的的負載分配及調度方法，通過對設備、工藝及生產過程的智能感知和處理，實現總加工時延優化和總開銷的任務調度方法這兩種維度的優化調度方法。在CloudSim平臺進行仿真測試，結果表明，該調度策略有效且執行效率較高。

云計算；負載分配；調度；粒子群算法

湖北省教育廳科技研究計劃（No.B2015356）

0　引言

未來的工業化生產將朝著兩個方向發展：一是生產設備的功能多元化、彈性且具有多種生產環境適應性的機械方能適應多樣性的市場需求；二是生產控制智能化，工業4.0的大潮將帶來更廣泛的自動化和信息技術，實現實時、精準、高效的過程控制[1]。目前我國的工業生產存在很多共性問題，包括：①原材料損耗大，物流配送調度粗放且效率低下；②機械裝配及制造的信息化水平較低，很多裝配工作仍然是手工進行；③對原材料、設備和產品的狀況沒有良好的跟蹤、控制和共享手段[2]。云計算環境下針對工業生產過程中的數據感知、數據處理和過程優化，目前尚無有效的負載分配及調度策略的研究。

本文探討了云計算環境下的工業生產負載和分配策略，將粒子群算法（PSO）應用于云計算環境下的資源調度，服務集群能夠推薦出一個較優的有效資源，并且能盡量避免資源調度負載失衡，重點對基于此算法的智能生產調度方法的原理、優化目標和實現進行了闡述，并對調度系統的仿真結果進行分析和比較。

1　關鍵調度方法的實現

基于以上系統實現高效生產的關鍵環節在于如何依照獲取的各感知對象的狀態，將各種并行的包裝印刷生產任務分配給各個不同功能的設備，這就需要高效的生產調度方法。

1.1調度方法的實現基礎

工業生產任務通常需要通過不同工藝和組裝等步驟[4]及設備中的若干個來依次實現，這樣就需要將一個生產任務分解為若干個子任務，每個子任務在一個設備中加工。考慮到生產設備的多類性和數目、子任務間的關聯性及產量規模，因為各個子任務分配加工設備是一個復雜的離散最優化問題，本文采用粒子群算法[1～2]解決此問題。粒子群算法通過模仿自然界的進化過程來解決優化問題，算法始于一個隨機選擇的染色體編碼初始解集合，按照一定的操作規則不斷的迭代，包括適應度函數評價、染色體選擇、交叉替換、變異等步驟，在每次迭代中隨機生成更優的新解，同時舍棄一些次優解。它是一種自適應的多方向搜索尋優過程，能直接對結果對象進行操作，具有良好的魯棒性。

1.2生產調度相關實體描述

考慮到加工設備及其功能的多樣性，將設備實現對應功能所需的費用和時間統一用標準參考產品SRP來折算，例如用某加工設備完成某個功能，所需的費用相當于生產x個SRP，而所需的時間相對于y個SRP。生產調度相關實體及其屬性描述如下：

第i臺加工設備Ei（0≤i＜ENum），其中ENum為加工設備總數。其屬性包括：①單元生產時延（記為PDi）表示用Ei生產一個標準參考部件的時延；②單元生產費用（含原料開銷，記為PCi）表示用Ei生產一個標準參考部件的費用；③通過感知手段獲取的設備當前狀態（停止、工作、空閑和維修）及負載Li（等效為SRP的數目）。

將一個生產任務分解為多個子任務后，第n類子任務STn（0≤n＜STNum，其中STNum為子任務類型的總數）是分解到各加工設備上的最小單元，STn和設備Ei之間存在如圖1所示的功能映射矩陣F[STNum][ENum]，如果某設備能對某類子任務進行處理，則相應矩陣元素為1，否則為0。

表1　子任務類型與加工設備間的功能映射

第m類工序Pm（0≤m＜PNum，其中PNum為工序類型總數）將不同子任務按特定生產流程組合得到樹型結構[8]，最后完成的子任務為工序樹的根節點。圖2為兩種不同工序的構成方式示例。

圖2　子任務按樹型組成不同工序示例

每個樹節點為一個子任務，其相關屬性包括：

子任務等效生產量PVm，n，指在Pm中STn的產出等效為多少個SRP。

待處理的第k個任務Tk（0≤k＜TNum，TNum為此次調度將處理的任務個數）具有的屬性包括：此任務對應的工序類型Prck；STn在Tk對應的工序樹中的父節點的子任務類型Prnk，n；總生產件數TMk；以Ek，n表示Tk所含的子任務STn被分配到的設備。

具體的示例如下：若Tk的工序中包含STn，且依據F將Tk的STn調度到Ei上，則設置分配標記Uk，n,i=1，否則為0。依據圖2和圖3，有PNum=2、STNum=5、ENum=4，給定3個待處理任務，其中task0的工序類型為process0，task1和task2的工序類型為process1，則得到如圖3所示的分配示例，task0中的ST2分配到E0上，對應為U0，0，0=1，而task1中的ST2分配到E2上，對應為U1，2，2=1。各任務及其中的子任務用不同樣式的邊框表示?？紤]到有多個設備能夠完成同一子任務，調度分配方案可能有很多種，并導致不同的生產效能[9]。

圖3　子任務調度分配和處理過程示例

1.3生產調度的粒子群算法實現模型

粒子群算法實現的每個染色體給出了對各任務中的子任務進行調度的一個方案，Tk中的每個STn對應一個基因，基因的索引編號為k×STNum+n，如果此Tk中的STn被分配到Ei上，則染色體的值為i。如果STn不在Tk中，則此基因被賦值為-1。基于圖3的工序，對3個任務的染色體編碼的例子如圖4所示。

隨機生成N個染色體形成初始種群，N的范圍為[40，120]。

依據不同的優化目標[9]，得到不同的適應度函數。其中面向總開銷最小化，給出設備Ei上的生產開銷描述為：

設計要素Ei所具有的間接入度影響為：

系統總開銷優化調度（COS）的目標表述為：

此批任務的總加工時延取決于完成最后一個加工子任務的時間。由于各子任務間的復雜依賴關系，往往需要等待位于另一個設備中的前步子任務完成后，才能進行當前子任務，故難以準確描述實際的加工處理時間。在理想的調度分配方案下，最晚完成加工任務的設備應該能夠不間斷地執行其中各項子任務而沒有空閑等待，其中各子任務在各自工序中相關的前步子任務均已在其他設備上加工就緒。這種情況下最后停工的設備的實際工作時間即為理想系統加工時延，表示為此設備上各子任務獨立處理時間的總和，再加上設備上當前負載所需的加工時間。

圖6　總生產開銷仿真結果

圖7　單位時間設備利用率仿真結果

總加工時延最優化調度（DOS）的目標表述為：

對應的適應度函數為：

后繼步驟包括染色體的選擇、交叉和變異，生產新種群后繼續下一代遺傳操作，直到足夠多的代數或適應度函數值收斂。

2　CloudSim平臺仿真

在CloudSim平臺，Datacenter類管理大量的主機體，這些主機體按一定的分配策略能夠被分配到一個或多個虛擬機上，它們能模擬與云相關的基礎設施服務。因此，在CloudSim平臺上不必考慮基礎設施，可以更多考慮集群資源調度策略。

設定9個任務場景，其中各包含若干任務，隨機設定各任務的工序類型，但任務總量分別對應為1000～9000個SRP。針對隨機調度（RAN）、DOS、COS，獲取總生產時延、總生產開銷、單位時間設備利用率這三個指標，結果如圖5～圖7所示。

從以上分析和實驗可以看出，時延優化調度能提供最短的系統加工時延，達到最高的加工效率，開銷優化調度則提供最小的系統加工開銷，實現最經濟的運作，而隨機調度方法的效果最差。

3　結語

本文實現了云計算環境下工業生產負載的智能分配及調度，其中能夠充分感知相關生產元素的狀態和特征，并實現了基于粒子群算法的智能調度方法，用于不同生產目標的優化。

未來的工作包括對所感知信息的充分利用，及針對原料運輸和產品入庫的智能調度方法。

[1]張曉東,張培林,傅建平,等.基于MATLAB/Fluent的協同仿真技術[J].計算機工程,2010,36（20）:220～221

[2]陳全,鄧倩妮.云計算及其關鍵技術[J].計算機應用,2009,29（9）:2562～2567

[3]陳康,鄭緯民.云計算:系統實例與研究現狀[J].軟件學報,2009,20（5）:1337～1348

[4]楊正洪.智慧城市——大數據、物聯網和云計算之應用[M].清華大學出版社,2014

[5]Chang Guiran,Wang Chuan,Xiong Yu,et al.Efficient Nash Equilibrium Based Cloud Resource Allocation by Using a Continuous Double Auction[C].Proc.of International Conference on Computer Design and Applications.Shenyang,China:IEEE Press,2010

[6]Foster I,Zhao Yong,Raicu I,et al.Cloud Computing and Grid Computing 360-degree Compared[C].Proc.of Grid Computing Environments Workshop.Austin,USA:IEEE Press,2008:1～10

[8]Lartigau Jorick,Nie Lanshun,Xu Xiaofei,et al.Scheduling Methodology for Production Services in Cloud Manufacturing[C].Proc.of Int'l Joint Conference on Service Sciences，2012：34～39

[9]Geyik Faruk.Process Plan and Part Routing Optimization in a Dynamic Flexible Job Shop Scheduling Environment:An Optimization Via Simulation Approach[J].Neural Computing and Applications，2013,23（6）:1631～1641

[10]Michael L.Pinedo.Scheduling:Theory,Algorithms and Systems[M].New York,USA:Springer Science and Business Media,LLC，2008

柯鵬（1977-），湖北武漢人，博士，研究方向為智能計算

Cloud Computing;Load Distribution;Scheduling;Particle Swarm Optimization

Design of Industrial Production Load Distribution and Scheduling Method in the Cloud Computing Environment

KE Peng
（College of Computer Science and Technology,Wuhan University of Science and Technology,Wuhan 430081）

For the future development trend of industrial production,designs load distribution and scheduling method based on cloud computing environment,through the equipment,technology and production process of intelligent sensing and processing,optimizes the total processing delay and scheduling methods related to the above two dimensions'optimizations.In CloudSim platform simulation test results show that the scheduling policy effective and higher efficiency.

1007-1423（2015）14-0003-04

10.3969/j.issn.1007-1423.2015.14.001

2015-04-10

2015-05-10