基于雙層規(guī)劃的云制造資源服務(wù)組合

王 平,肖 涵，2+，潘燕華

(1.江蘇科技大學(xué) 經(jīng)濟管理學(xué)院，江蘇 鎮(zhèn)江 212003；2.鎮(zhèn)江市高等專科學(xué)校 現(xiàn)代裝備制造學(xué)院，江蘇 鎮(zhèn)江 212028)

0 引言

云制造[1]融合廣泛地域中海量資源為各類制造需求提供豐富的定制化服務(wù)，實現(xiàn)制造無縫銜接、資源互通共享的優(yōu)化協(xié)同[2]。云制造模式的應(yīng)用能夠為制造企業(yè)拓展制造能力，拓寬制造范圍，降低運營成本，提高社會資源的綜合利用率，并最終實現(xiàn)多方共贏[3]。然而，隨著云制造技術(shù)的快速發(fā)展，以及制造任務(wù)的日益復(fù)雜，單一的云服務(wù)已經(jīng)難以滿足需求者的任務(wù)需求，因此云制造平臺需要通過云制造服務(wù)組合來滿足復(fù)雜的制造需求[4]。如何在大量功能相同但質(zhì)量參差不齊的制造資源中為服務(wù)需求方構(gòu)建出既能滿足需要，且綜合質(zhì)量最優(yōu)的服務(wù)是云制造領(lǐng)域面臨的難題[5]。

目前，對云制造服務(wù)組合的研究主要集中在評價指標(biāo)體系、評價方法以及智能化算法等方面。

(1)評價指標(biāo)體系方面 賀可太等[6]從需求方利益和風(fēng)險兩方面建立了服務(wù)質(zhì)量評價指標(biāo)體系；吳艷霞等[7]在服務(wù)質(zhì)量的基礎(chǔ)上增加了知識貢獻度、服務(wù)評價和使用優(yōu)先級；蔡安江等[8]構(gòu)建了以時間、成本、可用性、準(zhǔn)確性、創(chuàng)新性、可信性為優(yōu)化目標(biāo)的服務(wù)組合優(yōu)化模型；徐宣國等[9]建立了云服務(wù)組合柔性的四維屬性測度評價指標(biāo)體系。

(2)評價方法方面 趙道致等[10]建立了基于需求方服務(wù)質(zhì)量和平臺柔性的多屬性資源分配的雙層結(jié)構(gòu)優(yōu)化決策模型；丁濤等[11]從資源服務(wù)、功能服務(wù)和流程服務(wù)3個層次構(gòu)建了服務(wù)組合優(yōu)選的質(zhì)量評估模型；陳友玲等[12]以需求方和供應(yīng)方為基礎(chǔ)，建立了服務(wù)組合綜合評估雙層約束模型；吳艷霞等[7]構(gòu)建了云制造平臺可持續(xù)性最強、供應(yīng)方服務(wù)質(zhì)量最優(yōu)的雙層規(guī)劃模型。

(3)智能化算法方面 陳友玲等[13]提出一種基于反向和局部學(xué)習(xí)的蟻群算法，求解并行制造云服務(wù)的組合優(yōu)化問題；鄭煒等[14]采用雙層蟻群算法解決云服務(wù)組合后靈活度降低、解空間被限制等問題；金鴻等[15]利用教—學(xué)算法求解云服務(wù)組合整體服務(wù)質(zhì)量最優(yōu)組合；朱李楠等[16]結(jié)合云制資源組合的跨地域高度分散性的特征，設(shè)計了改進的差分進化算法對資源組合進行求解。

服務(wù)組合優(yōu)化是云制造中構(gòu)造松耦合敏捷制造方案、實現(xiàn)資源優(yōu)化配置的關(guān)鍵技術(shù)[17]，現(xiàn)有研究已取得了豐碩成果，但仍然存在一些不足：現(xiàn)有研究大多依據(jù)時間、成本等QoS指標(biāo)，忽略了資源供應(yīng)方的生產(chǎn)能力對云制造平臺資源組合的影響；多數(shù)學(xué)者從云制造的某一方或供需雙方的視角構(gòu)建模型，忽略了云制造平臺在資源優(yōu)化配置過程中的作用；問題求解過程中忽略了大量的模糊性和不確定性評價信息。本文在現(xiàn)有研究的基礎(chǔ)上，提出了基于雙層規(guī)劃的云制造資源服務(wù)組合優(yōu)選模型。該模型將供需雙方同時作為上層決策者，利用前景理論計算服務(wù)需求方對資源供應(yīng)方的滿意度，并以時間、質(zhì)量、成本、信譽度為約束條件，實現(xiàn)服務(wù)質(zhì)量最優(yōu)；以云制造平臺作為下層決策者，供應(yīng)方的剩余負(fù)載及需求方的滿意度作為約束條件實現(xiàn)資源利用率的最大化，并采用結(jié)合云模型中云滴的確定性和穩(wěn)定性[18]而設(shè)計出的云遺傳算法對該雙層規(guī)劃模型進行求解。

1 云制造資源服務(wù)組合評價指標(biāo)體系

1.1 評價指標(biāo)體系構(gòu)建

基于現(xiàn)有云環(huán)境下制造資源服務(wù)組合評價指標(biāo)體系，本文構(gòu)建了涉及服務(wù)需求方、資源供應(yīng)方和云制造平臺三方的雙層規(guī)劃模型(如圖1)。雙層規(guī)劃模型[19]是一種上下層擁有各自目標(biāo)和約束條件的主從決策優(yōu)化模型[20]，可以很好地解決云環(huán)境下制造資源服務(wù)組合優(yōu)選問題。

通過構(gòu)建雙層規(guī)劃模型圖，可以清晰地了解所構(gòu)建的雙層規(guī)劃模型中各層的決策主體以及目標(biāo)函數(shù)、約束條件和上下層之間的關(guān)系。圖1中上層決策主體為需求方和供應(yīng)方，下層決策主體為云制造平臺。下層模型的優(yōu)化目標(biāo)為資源利用率MRU，約束條件為供應(yīng)方的剩余負(fù)載LP與需求方對供應(yīng)方的滿意度S，計算出最優(yōu)MRU的排名，下層模型最為優(yōu)先決策層，將結(jié)果反饋至上層決策主體，上層模型的優(yōu)化目標(biāo)為服務(wù)質(zhì)量QoS，約束條件為時間T、成本C、交付物質(zhì)量Q，信譽度H。上、下層之間相互制約又相互依賴。評價指標(biāo)的具體描述如表1所示。

表1 云制造服務(wù)組合評價指標(biāo)

1.2 制造資源服務(wù)滿意度求解

前景理論以決策者有限理性為前提，能夠較好地刻畫決策者的心理行為特征[23]。該理論利用實際值rij與參照點eij之間的距離作為衡量滿意度大小的依據(jù)，根據(jù)評價指標(biāo)不同的屬性(即成本型或效益型)計算各指標(biāo)的損益值[24]。利用前景理論計算服務(wù)需求方對資源供應(yīng)方的滿意度，不但可以增加供需雙方匹配的約束條件，而且有利于資源匹配完成后，供需雙方對制造任務(wù)的配合，提高云制造平臺的工作效率，具體計算如下：

(1)計算各待選資源時間(t)、成本(c)、交付物質(zhì)量(q)、信譽度(h)的實際值rij與其各自參照點eij(需求方的最低要求)之間的距離dij，

dij=|rij-eij|。

(1)

(2)計算各待選資源針對不同指標(biāo)的損益值。

(2)

(3)

(3)計算各待選資源的前景值并進行歸一化處理。

(4)

(5)

(6)

其中：α，β(0<α,β<1)表示不同的風(fēng)險敏感系數(shù)，取值越大，決策者對風(fēng)險越敏感；λ(λ>1)表示決策者損失規(guī)避系數(shù)，取值越大，決策者對損失的規(guī)避意愿越強烈。

(4)求解各待選資源的滿意度S，

(7)

式中ωj表示各指標(biāo)前景值所對應(yīng)的指標(biāo)權(quán)重。

1.3 制造資源服務(wù)組合QoS求解

云制造環(huán)境下的服務(wù)組合主要包括串聯(lián)、循環(huán)、選擇、并行4種結(jié)構(gòu)。串聯(lián)結(jié)構(gòu)是最基礎(chǔ)、最重要的服務(wù)組合形式，其余3種結(jié)構(gòu)均可以簡化，等效為一個獨立的制造服務(wù)環(huán)境，與其他部分組成串聯(lián)結(jié)構(gòu)的服務(wù)組合[25]。因此，本文以串聯(lián)結(jié)構(gòu)作為云服務(wù)組合研究對象。

(1)總時間最少

(8)

式中：ti為子任務(wù)i的候選制造資源加工時間;n為子任務(wù)數(shù)。

(2)總成本最小

(9)

式中：ci為子任務(wù)i的候選制造資源加工成本;n為子任務(wù)數(shù)。

(3)交付物質(zhì)量最優(yōu)

(10)

(4)信譽最優(yōu)

(11)

式中：5表示信譽度的最高評價值，其取值范圍在1～5之間;n為子任務(wù)數(shù)。

(5)QoS計算

采用線性加權(quán)方法將QoS的多目標(biāo)函數(shù)轉(zhuǎn)化為單目標(biāo)優(yōu)化函數(shù)：

(12)

式中：ωT、ωC、ωQ、ωH分別為時間、成本、交付物質(zhì)量、信譽度的權(quán)重;T′max、C′max分別為需求方能夠接受的最長時間、最高價格;Q′max=1-Q′min、H′max=5-H′min，Q′min、H′min分別為需求方最低交付物質(zhì)量要求、最低信譽度。

1.4 制造資源利用率求解

云制造平臺在進行服務(wù)資源匹配時，需要考慮資源供應(yīng)方的剩余工作能力，即剩余負(fù)載，優(yōu)先選擇剩余負(fù)載與需求負(fù)載相接近的資源作為候選資源，從而提高平臺資源的利用率，同時保證云制造平臺工作效率和服務(wù)質(zhì)量。制造資源的利用率為：

首先，要求現(xiàn)有在職學(xué)生管理人員充分認(rèn)識到信息技術(shù)已成為了信息時代對高校學(xué)生管理工作最基本的能力要求，只有具有相應(yīng)的信息技術(shù)，才能做好大學(xué)生管理工作。其次，通過開展輔導(dǎo)員沙龍等形式，為教師間搭建良好的交流平臺，促進學(xué)生管理隊伍大數(shù)據(jù)分析能力的有效提升。最后，通過開展講座、報告及交流等活動，促進高校學(xué)生管理團隊多媒體操作技能與學(xué)生管理信息化系統(tǒng)管理能力的全面提升。

(13)

2 云服務(wù)組合雙層規(guī)劃模型構(gòu)建

2.1 數(shù)學(xué)模型

在確定供需雙方滿意度后，建立以服務(wù)質(zhì)量為目標(biāo)函數(shù)的上層優(yōu)化模型，以及考慮最大資源利用率的下層優(yōu)化模型，具體云服務(wù)組合優(yōu)化數(shù)學(xué)模型為：

(U)

min (QoS)。

s.t.

T′max≥T;

C′max≥C;

(L)

max (MRU)。

s.t.

Smin≤Si,i=1,2,…,n。

(14)

2.2 云服務(wù)組合雙層規(guī)劃模型求解

2.2.1 云遺傳算法

雙層規(guī)劃問題非凸性、非連續(xù)性的特征，導(dǎo)致該模型具有高度的不確定性，對其進行求解是一種強NP難問題。雖然遺傳算法是一種全局優(yōu)化搜索算法，但它不在單點上尋優(yōu)，而是在整個解空間尋找全局最優(yōu)，局部搜索能力差，搜索速度慢且容易發(fā)生提前收斂現(xiàn)象[27]，交叉與變異的概率不能對實際云環(huán)境下的服務(wù)組合的不確定性進行準(zhǔn)確描述。云遺傳算法[28](Cloud Genetic Algorithm，CGA)的基本思想是利用云模型云滴的隨機性和穩(wěn)定傾向性特點，保持個體多樣性從而避免搜索陷入局部極值，并且可以很好地保護較優(yōu)個體對全局最值進行自適應(yīng)定位[29]，結(jié)合遺傳算法交叉變異思想，由云模型的Y條件云生成算法實現(xiàn)交叉操作，基于云發(fā)生器實現(xiàn)變異操作[30]，完成進化過程。

算法1CGA交叉概率Pc生成算法[28]。

E′n=norm(En,He) ，

(15)

算法2CGA變異概率Pm生成算法[28]。

E′n=norm(En,He) ，

(16)

2.2.2 算法流程

(1)首先，利用前景理論(式(1)～式(7))計算出各候選服務(wù)資源的滿意度，然后對候選資源服務(wù)組合進行編碼，例如MR1,2-MR2,3-MR3，3-MR4，1-MR5，2,其對應(yīng)的十進制編碼為{2-3-3-1-2}。

(2)種群初始化。設(shè)定種群初始規(guī)模為N，最大迭代次數(shù)為I，生成初始種群P(0)。

(3)適應(yīng)度計算。將下層目標(biāo)函數(shù)max(MRU)轉(zhuǎn)化為適應(yīng)度函數(shù)，計算每個制造資源個體的適應(yīng)度。

(4)確定選擇算子。采用輪盤賭法，按照制造資源適應(yīng)度大小進行排序，從種群P(t)中選出滿足下層約束最優(yōu)的候選制造資源，復(fù)制到下一代種群P(t+1)中。

(5)交叉算子操作。利用算法1，其中C1=C2=0.6，k1=k2=0.9，生成交叉概率Pc(t) ，采用一點交叉對群體P(t)的個體進行交叉操作。

(6)變異算子操作。利用算法2，其中C3=C4=0.1，k3=k4=0.5，生成變異概率Pm(t)，對群體P(t)中的個體進行變異操作。

(7)判斷終止條件。P(t)經(jīng)過遺傳算子操作(選擇、交叉、變異)產(chǎn)生新群體P(t+1)，若t≥T，則進化過程中所得到的具有最大適應(yīng)度的個體作為最優(yōu)解，代入下層規(guī)劃目標(biāo)函數(shù)，更新目標(biāo)函數(shù)值，輸出結(jié)果；若t

(8)將步驟(7)輸出的解集作為上層目標(biāo)函數(shù)的可行解，分別計算各個可行解，選取QoS最優(yōu)即min(QoS)的制造資源組合方案。

3 應(yīng)用分析

3.1 案例設(shè)計

某企業(yè)在云制造平臺發(fā)布了一項制造任務(wù)Ta，并提交需求(如表2)。云制造平臺將制造任務(wù)Ta分解為5個子任務(wù)，Ta={MS1,MS2,MS3,MS4,MS5}，如表3所示。云制造平臺經(jīng)過初步篩選，選出符合制造子任務(wù)的候選制造資源MRi,j，候選資源指標(biāo)相關(guān)參數(shù)如表4所示。云制造平臺通過對子任務(wù)候選資源的優(yōu)選，實現(xiàn)制造任務(wù)服務(wù)組合最優(yōu)。

表2 需求方相關(guān)需求

表3 候選服務(wù)資源

表4 候選資源評價指標(biāo)相關(guān)參數(shù)

根據(jù)以上模型所需要的參數(shù)，Tmax=300，Cmax=2500，Qmin=0.95，Hmin=3，Ld=40,Smin=0.46以及ωt=0.3，ωc=0.25，ωq=0.25，ωh=0.2，結(jié)合式(12)～式(14)可得算例雙層規(guī)劃模型：

(U)

min(QoS)=min

s.t.

T≤300;

C≤2 500;

qi≥0.95,i=1,2,…,5;

hi≥3,i=1,2,…,5。

(L)

s.t.

S≥0.46。

(17)

3.2 算例求解

(1)滿意度計算

利用前景理論，以各正、負(fù)指標(biāo)理想數(shù)值作為參照點，利用式(1)～式(7)計算服務(wù)需求方對各個候選制造資源的滿意度，計算結(jié)果如表5所示，其中α=β=0.88，λ=2.25。

(2)算法驗證

利用2.2.2節(jié)算法流程對式(17)進行求解，取初始種群N=50，最大迭代次數(shù)I=100。如圖2所示，綠色和紅色分別表示云遺傳的最小適應(yīng)度值和平均適應(yīng)度值，紫色和黃色分別表示遺傳算法的最小適應(yīng)度值和平均適應(yīng)度值。由于關(guān)于QoS的模型求解以求解最小值為最優(yōu)值，從圖中可以看出,運用云遺傳算法計算的的QoS平均適應(yīng)度與最小適應(yīng)度值在100次的迭代過程中，均小于云遺傳算法的QoS值，因此，運用云遺傳算法求解的種群平均適應(yīng)度值和最優(yōu)適應(yīng)度值均比傳統(tǒng)遺傳算法的適應(yīng)度值更優(yōu)化，并且在100代的計算中可以看出，云遺傳算法的最優(yōu)適應(yīng)度具有更好的多樣性和隨機性，能夠很好地避免算法陷入局部最優(yōu)解，不易收斂；而傳統(tǒng)遺傳算法在第50代左右出現(xiàn)收斂。

表5 需求方對各制造資源滿意度

3.3 結(jié)果對比分析

為了證明模型算例的有效性，采用窮舉法計算云制造資源服務(wù)組合的最優(yōu)解為min(QoS)=0.330 9，服務(wù)資源組合為MR1,3-MR2,2-MR3,1-MR4,4-MR5，2。同時分別對傳統(tǒng)遺傳算法與云遺傳算法的10次迭代運算結(jié)果進行對比，如表6所示。

由表6的對比結(jié)果可知，云遺傳算法10次迭代運算輸出結(jié)果均為最優(yōu)解，具有穩(wěn)定性，而傳統(tǒng)的遺傳算法10次迭代輸出結(jié)果僅出現(xiàn)4次最優(yōu)解，相對于云遺傳算法，缺少了一定的穩(wěn)定性。因此，本文的模型算法優(yōu)化了傳統(tǒng)算法搜索全局最優(yōu)解的能力。

表6 遺傳算法與云遺傳算法結(jié)果對比

4 結(jié)束語

本文以前景理論求解出的需求方對供應(yīng)方滿意度為前提，綜合考慮需求方、供應(yīng)方以及云制造平臺三方利益，構(gòu)建了上層以服務(wù)質(zhì)量為目標(biāo)函數(shù)，下層考慮資源利用率最大化的制造資源服務(wù)組合雙層規(guī)劃模型；基于云制造環(huán)境下該模型的不確定性及隨機性等問題，采用具有穩(wěn)定傾向性的云遺傳算法進行數(shù)據(jù)求解，并將計算結(jié)果與窮舉法、遺傳算法進行對比。結(jié)果表明，所提模型及求解算法可以高效、準(zhǔn)確地解決云制造資源服務(wù)組合問題，研究結(jié)果能夠為云制造服務(wù)平臺的建設(shè)供應(yīng)方法參考和實踐支持。下一步，將考慮針對云制造資源個性化服務(wù)需求與配置的模型優(yōu)化問題進行深入研究。