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

柯　鵬（武漢科技大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院，武漢430065）

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

柯鵬
（武漢科技大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院，武漢430065）

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

云計算；負(fù)載分配；調(diào)度；粒子群算法

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

0　引言

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

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

1　關(guān)鍵調(diào)度方法的實現(xiàn)

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

1.1調(diào)度方法的實現(xiàn)基礎(chǔ)

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

1.2生產(chǎn)調(diào)度相關(guān)實體描述

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

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

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

表1　子任務(wù)類型與加工設(shè)備間的功能映射

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

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

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

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

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

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

圖3　子任務(wù)調(diào)度分配和處理過程示例

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

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

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

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

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

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

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

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

圖7　單位時間設(shè)備利用率仿真結(jié)果

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

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

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

2　CloudSim平臺仿真

在CloudSim平臺，Datacenter類管理大量的主機(jī)體，這些主機(jī)體按一定的分配策略能夠被分配到一個或多個虛擬機(jī)上，它們能模擬與云相關(guān)的基礎(chǔ)設(shè)施服務(wù)。因此，在CloudSim平臺上不必考慮基礎(chǔ)設(shè)施，可以更多考慮集群資源調(diào)度策略。

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

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

3　結(jié)語

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

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

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

[2]陳全,鄧倩妮.云計算及其關(guān)鍵技術(shù)[J].計算機(jī)應(yīng)用,2009,29（9）:2562～2567

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

[4]楊正洪.智慧城市——大數(shù)據(jù)、物聯(lián)網(wǎng)和云計算之應(yīng)用[M].清華大學(xué)出版社,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