云計算環(huán)境下工業(yè)生產(chǎn)負載分配及調度方法設計

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

云計算環(huán)境下工業(yè)生產(chǎn)負載分配及調度方法設計

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

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

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

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

0　引言

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

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

1　關鍵調度方法的實現(xiàn)

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

1.1調度方法的實現(xiàn)基礎

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

1.2生產(chǎn)調度相關實體描述

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

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

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

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

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

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

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

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

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

具體的示例如下：若Tk的工序中包含STn，且依據(jù)F將Tk的STn調度到Ei上，則設置分配標記Uk，n,i=1，否則為0。依據(jù)圖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。各任務及其中的子任務用不同樣式的邊框表示?？紤]到有多個設備能夠完成同一子任務，調度分配方案可能有很多種，并導致不同的生產(chǎn)效能[9]。

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

1.3生產(chǎn)調度的粒子群算法實現(xiàn)模型

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

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

依據(jù)不同的優(yōu)化目標[9]，得到不同的適應度函數(shù)。其中面向總開銷最小化，給出設備Ei上的生產(chǎn)開銷描述為：

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

系統(tǒng)總開銷優(yōu)化調度（COS）的目標表述為：

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

圖6　總生產(chǎn)開銷仿真結果

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

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

對應的適應度函數(shù)為：

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

2　CloudSim平臺仿真

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

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

從以上分析和實驗可以看出，時延優(yōu)化調度能提供最短的系統(tǒng)加工時延，達到最高的加工效率，開銷優(yōu)化調度則提供最小的系統(tǒng)加工開銷，實現(xiàn)最經(jīng)濟的運作，而隨機調度方法的效果最差。

3　結語

本文實現(xiàn)了云計算環(huán)境下工業(yè)生產(chǎn)負載的智能分配及調度，其中能夠充分感知相關生產(chǎn)元素的狀態(tài)和特征，并實現(xiàn)了基于粒子群算法的智能調度方法，用于不同生產(chǎn)目標的優(yōu)化。

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

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

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

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

[4]楊正洪.智慧城市——大數(shù)據(jù)、物聯(lián)網(wǎng)和云計算之應用[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