云制造平臺加工能力分享調(diào)度優(yōu)化研究

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

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

0 引言

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

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

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

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

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

1 問題描述與模型建立

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

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

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

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

1.2.1 符號約定

表1 符號約定

1.2.2 模型構(gòu)建

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

目標(biāo)函數(shù):

(1)

(2)

(3)

約束條件：

Ci≤DCi

(4)

ts(i,Ni+1)≤DTi

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

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

1.2.3 模型求解

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

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

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

①種群編碼

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

②種群初始化

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

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

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

③粒子更新方法

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

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)

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

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

圖2 算法流程圖

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

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

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

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

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

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

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

2 算例分析

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

表2 云制造任務(wù)的加工序列和時(shí)間表

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

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

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

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

圖5 算法適應(yīng)度變化曲線

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

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

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

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

3 結(jié)論

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