趙道致， 王忠?guī)?/p>

(天津大學 理與經(jīng)濟學部,天津 300072)

0 引言

近年來信息物理系統(tǒng)(Cyber Physical Systems, CPS)和工業(yè)物聯(lián)網(wǎng)(Industrial Internet of Things, IIoT)技術的快速發(fā)展，催生了許多基于分享經(jīng)濟的資源配置模式和“制造即服務(Manufacture as a service, MaaS)”的新概念的云制造平臺(Cloud Manufacturing Platform, CMP)及相應的創(chuàng)新業(yè)務，如“航天云網(wǎng)”提供的“云制造平臺”和“資源共享”等服務、“淘工廠”提供的服裝商家定制與工廠制造對接等服務。區(qū)別于傳統(tǒng)車間調(diào)度情境與方法，云制造環(huán)境下企業(yè)級資源調(diào)度與配置過程中加工過程的不確定性信息準確反饋，使得云環(huán)境下加工能力分享調(diào)度方法具有動態(tài)性、實時性、柔性、反饋性等重要特征，將原來相對獨立的企業(yè)車間級調(diào)度優(yōu)化轉(zhuǎn)化為信息兼容化，數(shù)據(jù)實時化，調(diào)度柔性化的云制造平臺調(diào)度優(yōu)化，將進一步影響確定條件下生產(chǎn)作業(yè)計劃制定的準確性和制造資源利用的合理性，非云環(huán)境下的傳統(tǒng)車間生產(chǎn)資源調(diào)度方法模型的解將很難達到云平臺上動態(tài)實時的要求。

李伯虎院士曾于2009年率先提出了“云制造”的概念和架構體系[1,2]。之后，李伯虎等也給出了云制造的典型特征、云平臺的體系架構、關鍵技術等方面的研究成果[3～5]。根據(jù)近年來云制造的創(chuàng)新實踐和分享經(jīng)濟的理論，可給出云制造的定義：云制造就是利用IIoT技術(如GE的Predix)將企業(yè)的制造資源(asset)鏈接在工業(yè)互聯(lián)網(wǎng)中，通過資源管理形成可分享利用的云制造資源，由云制造平臺整合最終客戶的定制化的加工與服務需求，優(yōu)化配置網(wǎng)格化的云制造資源，完成基于知識的智能化制造過程。在云制造的體系架構和關鍵技術的基礎上，趙道致等人基于Alvin E. Roth的匹配市場理論[6]，圍繞云制造資源的匹配和調(diào)度，研究了云制造平臺資源雙邊匹配機制及穩(wěn)定性問題[7]。之后，趙道致等人又研究了面向云制造參與人有限理性決策的雙邊匹配機制設計[8]。

在加工能力分享的調(diào)度優(yōu)化方面，隨著網(wǎng)絡化制造的發(fā)展，傳統(tǒng)單工廠生產(chǎn)模式正在向網(wǎng)格化分布異地的多工廠轉(zhuǎn)變。Ozturk等研究了定量描述不同類型多工廠生產(chǎn)調(diào)度計劃問題及求解機制[9]。Behnamian等總結了多工廠生產(chǎn)調(diào)度問題的現(xiàn)狀，得出生產(chǎn)制造任務調(diào)度和加工設備計劃配置模型[10]。Godinho等梳理了FMS調(diào)度中應用遺傳算法和粒子群優(yōu)化算法的現(xiàn)狀[11]。Tambuskar等研究了為完成靜態(tài)制造任務需求，在備選設備中優(yōu)選虛擬動態(tài)實體調(diào)度模型的求解技術[12]。Aalaei等研究了供應鏈環(huán)境下VMC的資源配置和集成調(diào)度問題[13]。Kai等研究了新工件插入的柔性車間調(diào)度問題，比較了不同的調(diào)度方法，給出了各自的應用場合[14]。Ke等研究了服裝業(yè)不同情境下可持續(xù)生產(chǎn)能力共享機制[15]。李京生等基于面向服務的云制造思想，研究了云制造中動態(tài)資源能力服務的分布式協(xié)同調(diào)度技術[16]。王軍強等基于聚類的思想給出了非瓶頸能力界定的方法，構建了云制造車間機器能力界定模型[17]。Tao等研究了智能云制造系統(tǒng)中基于尋優(yōu)算法的仿真方法，對多個樣本進行迭代計算，最后給出一種基于神經(jīng)網(wǎng)絡的尋優(yōu)算法，為云制造系統(tǒng)確定最優(yōu)序列提供了基礎[18]。

上述文獻從不同層面和角度對網(wǎng)格化調(diào)度問題進行了研究，但都沒有考慮到云制造系統(tǒng)的客戶需求的多樣性、制造加工資源的分享碎片化、資源需求的時間窗約束以及供分享資源的能力約束和成本差異?，F(xiàn)有的學者研究主要關注在理論和結構體系方面，少有利用完整的云制造技術手段，完成傳統(tǒng)生產(chǎn)車間調(diào)度向云制造轉(zhuǎn)型發(fā)展，建立實際云制造需求環(huán)境下企業(yè)級制造資源調(diào)度優(yōu)化模型，因此，隨著制造智能化和工業(yè)互聯(lián)網(wǎng)平臺的快速發(fā)展，云制造企業(yè)級資源調(diào)度將是未來新型云制造模式轉(zhuǎn)型的技術前提，其理論研究意義和實際應用價值也日益明顯。

本文立足于云制造平臺，構建了云制造生產(chǎn)加工調(diào)度優(yōu)化方法模型，同時，為提高企業(yè)資源利用率，考慮企業(yè)加工能力分享的時間窗，兼顧工期和成本的雙重優(yōu)化，設計改進的二階粒子群算法，確定云任務的最優(yōu)調(diào)度序列，并提出可分享加工能力時間窗的更新策略，最后通過算例進行仿真驗證，并討論平臺如何進一步提高云資源的利用率。

1 問題描述與模型建立

1.1 加工能力分享調(diào)度問題描述

云平臺在保證云資源可用能力(云資源具有的能力減現(xiàn)有負荷與已分配負荷)約束前提下，再根據(jù)交付時間和成本優(yōu)化匹配調(diào)度云資源，以完成云任務訂單的加工。云任務訂單在平臺上進行資源調(diào)度與配置過程中，平臺根據(jù)資源提供方給出的可分享的加工能力，為云任務訂單確定最優(yōu)的物理資源，在實際調(diào)度中，企業(yè)有自有任務的作業(yè)計劃，可看作初始調(diào)度，根據(jù)設備能力約束，將可分享的加工能力上傳云平臺，云平臺根據(jù)云任務訂單情況，將云任務作為新任務插入，新插入任務的調(diào)度則是采用盡可能在不改變初始調(diào)度方案基礎上進行調(diào)度。加工能力分享的調(diào)度是以企業(yè)自有任務完成為基礎，以提高企業(yè)制造資源利用率為目標，具體調(diào)度框架如圖1所示。

圖1 加工能力分享調(diào)度流程圖

1.2 加工能力分享調(diào)度模型的構建

1.2.1 符號約定

表1 符號約定

1.2.2 模型構建

構建加工能力分享調(diào)度模型，既要滿足實時制造任務前后工序的連續(xù)性和制造時間的最短，又要保證加工成本最低，因此分別以云任務的工期最短和加工任務成本最低為目標函數(shù)。由于加工能力分享調(diào)度存多個優(yōu)化目標并且關聯(lián)性很強，要求調(diào)度目標函數(shù)能正確反映目標函數(shù)間的關系，為此，本文采用加權平均模型對各目標函數(shù)進行歸一化處理，作為調(diào)度目標，如式(1)～(3)所示。同時，根據(jù)云制造加工能力分享的實際情景對目標函數(shù)進行了約束。

目標函數(shù):

(1)

(2)

(3)

約束條件：

Ci≤DCi

(4)

ts(i,Ni+1)≤DTi

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

式(4)為成本約束，表示完成制造任務的總成本不高于需求方對該制造任務的成本要求；式(5)為交期約束，表示制造任務最后一道工序的完工時刻不晚于需求方對該制造任務的時間要求；式(6)為資源約束，表示每個云企業(yè)同時只能加工一道工序；式(7)為工序約束，表示同一制造任務的不同工序不能同時加工；式(8)為云企業(yè)可分享加工能力約束，表示制造任務須在云企業(yè)的空閑時間窗內(nèi)進行加工；式(9～12)為空閑時間窗可用約束，式(9)表示工序加工時間小于空閑時間窗，式(10)表示工序k需在空閑時間窗內(nèi)能完成，式(11)表示第一道工序開工時間為可用空閑時間窗的上界，式(12)表示對其它工序開工時間約束。

1.2.3 模型求解

模型求解的整體思路，首先，根據(jù)云企業(yè)可分享加工能力的時間窗，對模型中各制造任務i的各工序開工時間的約束進行求解；其次，根據(jù)優(yōu)化目標函數(shù)，求解各個制造任務i的最優(yōu)調(diào)度序列X={x1,x2,…,xn}；最后，根據(jù)調(diào)度序列，將制造任務的每道工序在云企業(yè)可分享加工能力時間窗內(nèi)進行插入并進行更新，得到云任務最優(yōu)的制造時間序列ts={ts(i,1),ts(i,2),…,ts(i,Ni)}。

(1)制造任務調(diào)度序列的求解

為求解各制造任務的調(diào)度序列，本文在原有二階粒子群算法的基礎上，在算法中引入制造任務的簡易編碼和隨機權重，設計了一種改進的二階粒子群算法(IPSO)，以提高搜索速度和獲取最優(yōu)解的質(zhì)量。

①種群編碼

利用制造任務的順序進行整數(shù)編碼，代表調(diào)度序列，長度為制造任務的個數(shù)。如粒子[3 1 5 4 2]，表示5個制造任務的調(diào)度序列為3→1→5→4→2。

②種群初始化

本算法的搜索空間假設為n維，對粒子的位置和速度的定義分別為:Xi=(xi1,xi2,…,xin),Vi=(vi1,vi2,…,vin)。初始化種群Xi、Vi的元素。

云制造加工能力分享調(diào)度優(yōu)化屬于組合優(yōu)化問題，種群粒子的位置元素與制造任務序列一一對應。因此，對初始化種群進行變換可以利用粒子位置元素值排序法。利用粒子位置元素值建立對應的向量，按照升序?qū)υ叵蛄颗判?，此向量則代表制造任務的調(diào)度序列順序，越小越優(yōu)先調(diào)度。例如，隨機生成的五維粒子位置元素向量[0.98 3.88 0.15 2.67 1.36]，由此可見在元素向量中，制造任務3的位置元素值最小，則優(yōu)先調(diào)度，以此類推，得到制造任務調(diào)度序列[3 1 5 4 2]。

令優(yōu)化目標函數(shù)F作為適應度函數(shù)，即：fitness(X)=F。其中：X代表制造任務調(diào)度序列順序，fitness(X)為X的適應度值，F(xiàn)為按式(3)計算的優(yōu)化目標函數(shù)值。

③粒子更新方法

在傳統(tǒng)粒子群算法中，習慣將粒子飛行速度作為粒子位置的函數(shù)，這樣求解結果容易造成局部最優(yōu)而飛全局最優(yōu)，二階粒子群算法彌補了缺憾，而本文優(yōu)化對粒子群的更新，尋求全局最優(yōu)解，則在二階算法中進一步引入隨機權重ω，粒子速度更新表達式如下：

vij(t+1)=ωvij(t)+c1r1?pij-2xij(t)+xij(t-1)」+

c2r2?gbest-2xij(t)+xij(t-1)」

xij(t+1)=xij(t)+vij(t+1),?j∈{1,2,…,n}

ω=μ+σ×N(0,1),μ=μmin+(μmax-μmin)×rand(0,1)

其中：ω為隨機權重，表達了對粒子當前速度的傳承，ω～N(0,1)；C1和C2代表正的學習因子，分別表示為粒子進行自我學習總結和向優(yōu)秀個體學習的能力；r1,r2～rand(0,1)；pij為粒子i的過去最優(yōu)值；gbest為種群的全局最優(yōu)值。

采用改進的二階粒子群算法求解加工任務加工序列的算法流程如圖2所示。

圖2 算法流程圖

(2)可分享加工能力時間窗的更新策略

在云制造環(huán)境下，企業(yè)可分享加工能力時間窗是隨著生產(chǎn)計劃的推進而不斷變化，當云任務介入時，該云任務的每道工序要插入到各個云企業(yè)可分享加工能力時間窗內(nèi)，并實時更新可分享加工能力時間窗。更新策略主要分為以下四種情況：

1)當ts(i,k)=α(j,rj),te(i,k)<β(j,rj),則更新后的可分享加工能力時間窗縮短，α(j,rj)=te(i,k-1),β(j,rj)=β(j,rj)，空閑時間窗總個數(shù)不變，如圖3(a)所示。

2)若ts(i,k)>α(j,rj),te(i,k)=β(j,rj)，則更新后的可分享加工能力時間窗縮短，α(j,rj)=α(j,rj),β(j,rj)=ts(i,k)，總空閑時間窗個數(shù)不變，如圖3(b)所示。

3)若ts(i,k)>α(j,rj),te(i,k)<β(j,rj)，則更新后的可分享加工能力時間窗被分為兩部分，α(j,rj)=α(j,rj),β(j,rj)=ts(i,k),α(j,rj+1)=te(i,k),β(j,rj+1)=β(j,rj)，總可分享加工能力時間窗增加一個，如圖3(c)所示。

4)若ts(i,k)=α(j,rj),te(i,k)=β(j,rj)，則更新后的可分享加工能力時間窗被置空，總可分享加工能力時間窗減少一個，如圖3(d)所示。

圖3 可分享加工能力時間窗的更新策略圖

2 算例分析

云平臺在t時刻經(jīng)過云任務訂單整合為2 PC B2，1 SET B4，8 SET C1，3 PC C2，4SET C3，2 M C4的六個訂單任務。下面根據(jù)云任務訂單的加工能力要求，利用云制造加工能力分享調(diào)度模型進行調(diào)度，并對算法進行驗證。根據(jù)六個制造任務相應的加工序列和所需的加工時間如表2所示，以24h為一個制造周期，給出云企業(yè)E1，E2，E3，E4，E5在初始調(diào)度后可分享加工能力的時間如表3所示。

表2 云制造任務的加工序列和時間表

表3 云企業(yè)可分享加工能力時間表

根據(jù)模型求解可得最優(yōu)調(diào)度序列為[2,3,6,5,1,4]，并按照可分享加工能力時間窗的更新策略進行插入，得到圖4所示云平臺加工能力分享調(diào)度甘特圖，其中空白代表云企業(yè)的初始調(diào)度方案，其余為可分享加工能力時間窗，完工時間為15h，成本為320萬元。根據(jù)調(diào)度結果可以進一步分析云平臺對于加工能力分享利用率的影響如表4所示。

圖4 云平臺加工能力分享調(diào)度甘特圖

表4 云企業(yè)可分享加工能力及利用率分析表

圖5 算法適應度變化曲線

由表可知在云平臺參與后，云制造企業(yè)的能力得到充分分享，使得企業(yè)資源利用率顯著提升，但對于可分享加工能力的利用率不到40%，說明云制造企業(yè)對于可分享加工能力的利用還不充分，因此可以結合云制造的特點進一步分析如何提高可分享加工能力的利用率。首先，云平臺任務是按批次交付，可以在一個生產(chǎn)周期內(nèi)對剩余資源安排多批次的云任務，直至不可再利用，進一步增加云企業(yè)經(jīng)濟效益；另一方面，若一個生產(chǎn)周期無法完成本批次所有的制造任務，可以在本周期剩余資源最小條件下，完成下個生產(chǎn)周期安排的部分制造任務，節(jié)省下一個周期的制造時間，進而安排更多的云任務。

為驗證本文算法(IPSO)的優(yōu)越性，將其分別與標準粒子群算法(PSO)、蟻群算法(ACO)、遺傳算法(GA)進行比較。以相同迭代次數(shù)下，算法的收斂速度和最優(yōu)解作為評價指標，設定四種算法迭代次數(shù)為150次，得到各算法適應度變化曲線，如圖5所示。

以算法魯棒性作為評價指標，四種算法分別在迭代次數(shù)為50，100，150次條件下，獨立運行次數(shù)為10次，比較四種算法在三種迭代次數(shù)下運行10次得到適應度的最大值，最小值和平均值，如表5所示。

由圖5可知，本文提出的算法，在提高搜索迭代速度要明顯高于其他算法，獲取的最優(yōu)解也明顯優(yōu)于其它三種算法，通過表5的魯棒性分析，表明改進的具有隨機權重的二階粒子群算法的搜索性能和平穩(wěn)性相比其他算法具有優(yōu)越性。

3 結論

云制造環(huán)境下的供應鏈主體計劃調(diào)度問題具有跨地域、跨企業(yè)、多時間粒度等顯著特點。本文以平臺為決策主體，解決了云制造環(huán)境下生產(chǎn)加工能力分享調(diào)度的企業(yè)級資源調(diào)度優(yōu)化問題。構建了云制造平臺加工能力分享調(diào)度模型，同時設計了隨機權重的二階粒子群算法，來提高搜索最優(yōu)制造序列的速度和性能，并基于云企業(yè)可分享加工能力時間窗提出更新策略，最后通過算例驗證了調(diào)度機制的可行性。本文為云平臺合理將網(wǎng)格化制造資源分享提供決策方法，協(xié)調(diào)了各主體在合作決策中的利益，實現(xiàn)了資源能力的高度共享。本文將進一步研究在混合周期中，云任務多批次隨機到達的平臺調(diào)度問題，并進一步考慮初始調(diào)度允許更改的混合調(diào)度問題。