基于需求預測的云制造服務租賃配置優(yōu)化

陳晟愷，方水良，唐任仲

(浙江大學 機械工程學院，浙江 杭州 310027)

0 引言

作為面向制造服務的一種先進制造模式，云制造基于信息技術、物聯(lián)網(wǎng)、虛擬化、云計算等技術能夠實現(xiàn)制造資源的虛擬化和服務化[1-4]。服務需求方可以隨時按需申請使用云端化的制造服務[5-6]，并將其需求描述成制造任務發(fā)布于平臺；服務提供商通過平臺提供的虛擬化封裝技術，以服務的形式共享其制造資源和制造能力[7]。隨著云制造需求復雜性的增加，簡單的制造服務配置租賃已無法滿足客戶在工期、質量、成本等方面的要求，云平臺需要通過先進的服務租賃配置方法來更好地滿足大量用戶的需求。目前制造服務租賃模式尚無標準的建模方式，相關研究主要圍繞云服務使用模式、多任務調度及制造服務配置優(yōu)化等方面展開。

在服務模式上，國內外相關研究主要集中于訪問控制模型和定價機制。劉強等[8]從使用角度對制造服務進行分類，分析其在平臺中的使用和訪問需求控制，并設計了相應的訪問控制模型，以確保服務安全使用；魏樂等[9]設計了基于競標機制的服務定價方式，促使服務交易雙方共同獲利。實際應用中，Amazon的EC2通過現(xiàn)貨實例(Spot Instance, SI)的動態(tài)定價機制來引導云服務需求配置[10]，通過用戶對價格、運行效果和可靠性進行權衡來達到合理利用非專用服務的目的；Javadi等[11]研究了SI的特征化，通過全面分析分時分日的服務請求和定價數(shù)據(jù)設計了相應的服務動態(tài)調度算法。在這樣的服務租賃框架下，云平臺需要為客戶確定所需服務的租賃起止時間。

單個客戶的間歇性下單是云平臺制造任務到達的一種模式，如周期性的訂貨計劃等。在制造服務可用容量的約束下，進行任務的排產是一個拓展的資源約束調度問題[12-14]。然而，云制造環(huán)境下眾多客戶不同任務需求的不確定性及其任務結構多樣性增加了該NP-hard問題的決策難度，傳統(tǒng)的全局優(yōu)化模型及相應算法已經不再適用，對服務調度及配置優(yōu)化的研究逐漸轉向實時智能算法。

張宏國等[15]通過計算任務的距離相似程度，構建分段請求的資源配置方法，在時間維度上提高了資源利用率；郝予實等[16]通過功能信息重構將服務場景進行聚類，在識別用戶需求的基礎上綜合考慮資源的使用狀態(tài)，對其推薦合適的制造資源；Li等[17]對高度個性化需求的復雜任務進行建模，設計了以處理時長、準備時間、物流時間、響應成本為多目標的元啟發(fā)式算法，來應對各異的任務之間存在的復雜層級關系；蘇凱凱等[18]將服務優(yōu)化配置問題轉化為非合作博弈問題，建立了云制造環(huán)境下制造資源優(yōu)化配置的非合作博弈決策模型；Abdullahi等[19]提出離散共生組織搜索算法以解決任務調度問題，該方法基于模仿生態(tài)系統(tǒng)中的共生關系，其解收斂很快；Zhang等[20]基于實時數(shù)據(jù)驅動，采用博弈論改進任務調度策略來處理實時、準確、增值的制造信息。

可見，隨著問題的復雜化，制造服務調度的求解算法和規(guī)則設計越來越偏向于基于學習的智能算法，一方面由于傳統(tǒng)的優(yōu)化方法已不適用于復雜巨量的制造環(huán)境，另一方面是需求的變化和多樣化使決策環(huán)境變得復雜，對調度模型響應能力提出了較高的要求。

本文分析了云制造環(huán)境中的制造服務過程，提出一種可行的制造服務租用模式，建立了相應的優(yōu)化配置模型，以最小化租賃成本、最大化服務效用、最小化任務延期為目標，設計定時間間隔和定決策隊列長度的雙觸發(fā)式在線調度模式，并通過需求預測提升實時動態(tài)調度的效果，最后通過相應的對比實驗驗證所提方法的有效性。

1 問題背景描述

云制造平臺上匯集了分散的制造服務，需求用戶需要通過相關模塊以租賃的方式使用相應的服務。在云制造環(huán)境中，制造服務的租賃配置指將制造任務需求映射到相應的制造服務上進行處理的過程。處理制造任務需要在具體的服務資源上占用一定容量和時間[21]，而不同制造服務提供商的服務資源容量及其租用狀態(tài)各異，導致其所能承擔的制造任務容量不同，云平臺需要動態(tài)優(yōu)化安排租賃服務以滿足眾多制造任務的需求。合理的服務租賃配置既要滿足需求方最小租賃成本、最大服務使用效用、最小任務延期值的要求，又要兼顧服務可用容量的不確定性。

云平臺上合理的租賃服務問題的本質是多組并行資源綜合優(yōu)化調度問題，一般可以采用基于工作量的分析方法，以服務效用、服務質量、服務成本等為目標，建立相應的優(yōu)化模型進行求解[22]，然后根據(jù)結果將各任務優(yōu)化安排到相應的資源點。該方法有較高的實時性需求，其求解依賴能夠快速響應的算法，如基于改進學習速率的調度結果預測算法[23]。

為了更好地安排任務，本文采用前瞻式在線調度來確定各任務被服務的起止時刻。當?shù)却幚淼娜蝿諗?shù)量或者離前一次調度的時間間隔達到閾值時，便會觸發(fā)平臺執(zhí)行一次任務重調度計算。然而，任務所需服務容量的不確定性增加了在線調度的難度，本文通過需求預測應對這一不確定性，即對未到達平臺的任務進行所需服務容量評估，并將其并入調度的決策集合。若預測將有工期緊急任務到達，則系統(tǒng)會預先留出空位，提前給將要到達的任務安排好可能的加工時間窗口。

本文提出的云制造服務租賃框架如圖1所示，主要包括任務發(fā)布系統(tǒng)(c)、需求預測系統(tǒng)(f)和服務租賃配置系統(tǒng)(b)3大模塊，所涉及的符號如表1所示。

表1 符號說明表

續(xù)表1

任務發(fā)布系統(tǒng)匯集需求客戶定期發(fā)布的制造任務(a)于平臺的任務池內，并根據(jù)時間順序進入相應服務類型的等待隊列(d)；需求預測系統(tǒng)對不同系列的任務需求進行預測，并將預測結果與等待隊列中的任務合并為調度決策隊列(h)；服務租賃配置系統(tǒng)通過調度觸發(fā)器觸發(fā)調度模塊(e)，計算出等待隊列中各任務的服務起止時間(b)。

圖1中任務等待隊列(d)和服務租賃配置系統(tǒng)(h)均需考慮如圖2所示的服務類型匹配，每個系列的制造任務對應一種所需的服務類型，而每種服務類型可以對應多個服務實例；服務租賃配置系統(tǒng)(b)中的黑色部分表示在調度時刻已被實際任務占用的區(qū)間，虛線框表示預留給虛擬任務的空間，實線框表示實際到達任務的服務配置區(qū)間；調度觸發(fā)(e)以服務類型τ=2為例，其他類型類似，故不在該圖中重復表達。

調度的觸發(fā)由隊列長度和時刻計數(shù)兩方面決定，當時間間隔到達閾值而隊列長度未到達決策所需的長度時，需要調用預測模塊進行任務預測。服務租賃配置系統(tǒng)在安排任務時，會盡可能滿足實際任務的加工配置，同時結合需求預測系統(tǒng)提供的虛擬任務隊列為其預留服務時間和服務容量，以提升制造服務配置的前瞻性。

1.1 云制造任務和云制造服務

本文所表達的制造任務是客戶需求的一種表現(xiàn)形式，需要類型匹配的制造服務消耗一定的容量和時間才能處理完成?？蛻鬸第s次發(fā)布到平臺的制造任務記為MT(j,s)，其完整的屬性用元組表示為：

s>0。

(1)

本文所表達的制造服務是云制造平臺的任務處理單元，由來自不同企業(yè)的制造資源能力虛擬化和封裝而成。制造服務供應商i注冊于平臺的制造服務記為MS(i)，由最大可被租用容量Ki、服務類型Φi、單位租賃費用Ci、服務效用系數(shù)Pi、t時刻等待處理的任務隊列Qi(t)和正在處理的任務集合Ai(t)等屬性組成，用元組表示為：

MS(i):=(Ki,Φi,Ci,Pi,Qi(t),Ai(t)),?i∈I。

(2)

除了Qi(t)和Ai(t)是時變量之外，其余屬性皆為靜態(tài)值。

1.2 制造服務租賃配置

以編號為j的客戶第s次發(fā)布到平臺的制造任務為例，制造服務租賃配置指云平臺確定MT(j,s)加工處理所用的MS(i)及其起止時刻和服務占用量。如圖3所示，平臺根據(jù)MT(j,s)配置滿足類型匹配條件Φi=φj的MS(i)，即在[bj,i,ej,i)區(qū)間內占用MS(i)部分服務容量。圖中深色部分表示在決策時刻MS(i)已被占用的情況，淺色部分表示MT(j,s)的服務配置情況。

顯然，服務租賃需要滿足以下兩個基本約束：

i∈I,j∈J,s>0;

(3)

(4)

其中式(3)表示各制造任務的租用容量不能超過服務能提供的最大容量，式(4)表示租用時長需要滿足制造任務加工處理所需要的時間。

1.3 基于預測的制造任務在線調度

本文采用如圖4所示的基于需求預測的前瞻式在線調度應對制造任務所需服務容量的不確定性，其輸出是相應的租賃配置結果。監(jiān)聽到達任務子程由制造任務到達事件觸發(fā)，到達的制造任務會根據(jù)其所需制造服務類型進入相應的等待隊列。采用最長時間間隔和調度容量兩個觸發(fā)條件共同確定是否需要開始一次調度計算，當某服務類型在滿足時間間隔觸發(fā)調度條件時，若其等待隊列長度小于調度容量(即||Qτ||

2 云制造服務租賃配置優(yōu)化模型

2.1 模型假設

制造服務的租賃配置優(yōu)化是一個復雜的問題，需要考慮的因素很多，為了限定本文的研究范圍，進行以下模型假設：

(1)MT(j,s)的加工時段是長度固定為pj的連續(xù)區(qū)間。

(3)只要制造服務的服務容量足夠，就可以支持同一時刻的多個制造任務同時租用。

(4)制造服務的服務容量可恢復，即制造任務處理結束后，會釋放占用的服務容量。

(5)處理完成后，制造任務獲得的服務效用由所租制造服務的效用系數(shù)Pi決定。

(6)暫不考慮制造任務和制造服務的地理分布因素。

2.2 相關約束

本文研究的制造服務租賃配置支持多制造任務并發(fā)處理，不失一般性，以單個制造任務MT(j,s)為視角構建相關約束，并使用定義為式(5)所示的租用指示變量來簡化后續(xù)的約束描述。

(5)

首先，MT(j,s)只能選擇1個制造服務配置租賃，被選到的MS(i)需要與MT(j,s)類型匹配。式(6)表示匹配方案只中能有1個制造服務被選擇，式(7)表示不匹配的制造服務不會被選擇。

(6)

(7)

其次，若最終MS(i)被租用，則需要滿足式(8)所示的服務容量限制，即在任意時刻t，正在處理的制造任務所需服務容量之和小于MS(i)的最大容量。

(8)

式中Ai(t)為t時刻租用MS(i)的任務集合。

?j∈J;s>0},?i∈I;t>0，

(9)

其為一個以時間為變量的動態(tài)集合，會使問題求解變得困難[24]。

由于每個具體的制造任務只有1個所需的服務類型，可以按照式(10)先將所有制造服務按類型劃分，再將同一類別的制造服務看作并行機環(huán)境。

Sτ:={i|Φi=τ,?i∈I},?τ∈T。

(10)

不失一般性，仍以MT(j,s)為例，定義式(11)所示的集合為在線調度的輸入。

Wτ:=Qτ∪Fτ,τ=φj。

(11)

式中Qτ和Fτ分別為實際制造任務等待隊列和虛擬制造任務預測集合。當?shù)却犃虚L度足夠觸發(fā)調度時(||Qτ||≥Nτ)，系統(tǒng)將會跳過預測模塊(Fτ=?)，直接進入調度步驟，如圖4所示。進一步，制造任務等待隊列可以表示為式(12)，由φj類各候選制造服務當前時刻的制造任務等待隊列(式(13))拼接而成。

(12)

?j∈J;s>0},?i∈I;t>0。

(13)

2.3 制造服務租賃配置的優(yōu)化目標

云制造環(huán)境下的制造服務租賃配置優(yōu)化主要從成本、服務效用、延期3個方面考慮，相應的調度目標如下：

(14)

(15)

(16)

決策向量y(τ)(式(18))由決策集合Wτ中制造任務相關的決策變量(式(17))組成，表示MT(j,s)的開始處理時刻。

(17)

(18)

因此對于決策輸入Wτ，制造服務租賃配置的優(yōu)化目標可以表示為

V-miny(τ)∈N{fM(y(τ)),-fU(y(τ)),fD(y(τ))}T,

?τ∈T;N=||Wτ||。

(19)

在這些目標中，降低租賃成本是吸引需求客戶的重要手段，也是平臺優(yōu)化的重要目標。對于每一個MT(j,s)，服務租賃成本可以表示為

(20)

即被選制造服務的租用時長、容量與其單價的乘積。

與服務租用成本類似，獲得優(yōu)質服務同樣是吸引客戶的重要的優(yōu)化目標。對于每一個制造任務，其完成后制造服務的使用效用為

(21)

即所選制造服務的使用效用。

較低的任務延期是滿足客戶需求的重要指標，其值與服務租賃配置的結果有關。每一個制造任務的逾期量是超出約定工期的時間間隔，即

(22)

3 基于長短期記憶的制造服務容量需求預測

3.1 長短期記憶模型簡介

由于自身結構的原因，普通RNN單元存在長期依賴等問題，往往得不到預期的效果，實踐中會用長短期記憶(Long Short Term Memory, LSTM)等單元替換基本RNN單元。LSTM由Hochreiter等[25]于1997年首次提出，該單元在原有短期記憶單元的基礎上，增加了一個記憶單元來保持長期記憶，同時輔以遺忘程度來控制長期記憶的程度。從網(wǎng)絡結構設計的角度來說，LSTM單元通過門控制器增加了對不同時刻記憶程度的權重控制。

3.2 預測模型

3.2.1 預測目標

云制造中任務調度的本質是根據(jù)平臺中制造服務的狀態(tài)信息和制造任務的實時信息產生最優(yōu)的任務執(zhí)行方案[23]。如圖1所示，預測系統(tǒng)的目標是根據(jù)周期性到達平臺的制造任務歷史數(shù)據(jù)，預測接下來同系列制造任務的服務需求容量，據(jù)此產生虛擬制造任務補充到調度模塊的決策隊列中。對預測系統(tǒng)中的模型進行訓練，就是求解式(23)所表達的近似函數(shù)。

f(I0,I1,I2,…,It)≈Ot,t≥0。

(23)

式中：I0,I1,I2,…,It為采樣數(shù)據(jù)t時刻的輸入序列樣本；Ot為采樣數(shù)據(jù)t時刻的輸出標簽。

對于需求類型為τ的各系列制造任務，當某個調度決策時刻的等待制造任務隊列滿足||Qτ||

(24)

3.2.2 數(shù)據(jù)準備

如前所述，訓練近似函數(shù)式(23)需要進行數(shù)據(jù)采樣。以客戶j為例，平臺采集其周期性發(fā)布的制造任務相關數(shù)據(jù)，以到達次數(shù)s為步進量，將對應的制造服務需求容量看作如式(25)所列的序列數(shù)據(jù)。

(25)

需要注意的是，不同客戶會產生不同的序列，例如需求客戶j1發(fā)布的系列任務為MT(j1,0)，MT(j1,1)，MT(j1,2)，…；客戶j2發(fā)布的系列任務為MT(j2,0)，MT(j2,1)，MT(j2,2)，…。由于不同客戶的需求特性各不相同，即其服務使用量需求、到達時刻、所需服務類型、處理時長等重要屬性皆存在不同的特性，需要對每一個客戶產生的序列數(shù)據(jù)分別進行預測訓練。

為了將所采樣的序列數(shù)據(jù)導入訓練模型，需要通過如圖5所示的移動窗口法進行數(shù)據(jù)轉化。序列數(shù)據(jù)以固定大小的窗口為單位，每次向右移動w個時間單位，將輸入的原始數(shù)據(jù)整合為

t≥0，

(26)

并作為模型的輸入輸出數(shù)據(jù)單元。

舉例來說，當w=3，且以2個時間窗為預測步長時，相應的輸入輸出樣本表示為：

(27)

3.2.3 損失函數(shù)

由于本文預測問題不屬于分類問題，各輸出有相同的重要程度，這里使用均方誤差(式(28))作為預測模型訓練的損失函數(shù)，并用RMSProp優(yōu)化算法[26]對梯度下降過程進行優(yōu)化。

式中tmax為采樣的最大時刻。

4 算例研究與分析

本文通過仿真算例對所提制造服務租賃配置方法進行有效性分析。采用隨機分布的發(fā)生器產生研究所需的仿真算例，搭建基于Tensorflow1.2.1的LSTM預測模型，并通過DOcplex 2.7.113建立調度模塊，調用IBM?ILOG?CP Optimizer 12.7.0.0求解引擎求解服務租賃配置。因為目前并無相關的應用系統(tǒng)或相關算例，所以采用仿真算例進行數(shù)據(jù)采樣、模型訓練和系統(tǒng)驗證。

4.1 算例設計及參數(shù)設定

表2 算例生成器基本參數(shù)設定表

預測模型中input_size和num_steps為關鍵參數(shù)，經過圖6所示的交叉實驗后，選擇擬合效果最好的參數(shù)組合(如圖6c)作為這兩個參數(shù)的值，其余參數(shù)設置如表3所示。

表3 預測模型參數(shù)設置表

4.2 實驗結果分析

表4 對比實驗結果

4.2.1 服務租賃成本

對于各制造任務，所提方法在服務租賃成本上的變化程度為使用需求預測和不使用需求預測的在線調度成本之比，即

(29)

圖7所示為服務租賃成本比值在不同類型制造服務上的情況，可見大部分比值小于1，即使用需求預測可以縮減制造任務租賃的服務成本。

采用式(30)計算成本優(yōu)化目標值提升率，基于需求預測的在線調度方法可以在總體上縮減4.50%的服務租賃成本。

(30)

其中Mτ為需要租用τ類制造服務的制造任務集合，

Mτ:={(j,s)|φj=τ;?j∈J;s>0},τ∈T。

(31)

4.2.2 服務使用效用對比

對于各制造任務，所提方法在該目標上的變化程度是使用需求預測和不使用需求預測的服務使用效用比值，即

(32)

圖8所示為服務使用效用比值在不同類型制造服務上的情況，可見大部分比值大于1，即應用制造服務容量需求預測的結果可以提升服務使用效用。

采用式(33)計算服務效用優(yōu)化目標值提升率，基于需求預測的在線調度方法可以在總體上提升0.86%的服務使用效用。

(33)

4.2.3 任務延期對比

各制造任務的延期可定義為式(22)，因為存在非延期的可能(即延期值為0)，所以使用需求預測和不使用需求預測的任務延期差值式(34)作為評價指標，即

(34)

圖9所示為任務延期差值在不同類型制造服務上的改進情況，可見任務的延期得到了較大改進。

相對于任務延期值，需求客戶更關心任務的延期率。采用式(35)計算任務延期優(yōu)化目標值提升率，基于需求預測的在線調度方法在總體上可以縮減5.15%的任務延期率。

(35)

綜上所述，采用基于需求預測的在線調度方法可以使制造任務的服務租賃配置在成本、使用效用和任務延期方面都得到改善，主要原因是需求預測給基于事件驅動的在線調度方法帶來了一定的前瞻性，從而使各制造任務的匹配和加工起止時刻安排得更加合理。

5 結束語

本文提出一種面向多種具有不同周期性的制造任務序列，考慮其后續(xù)任務量預測的云制造服務租賃配置實時優(yōu)化方法，以服務成本、服務效用及其任務延期量為優(yōu)化目標進行對比實驗，實驗結果驗證了基于需求預測的在線調度方法的有效性。所提方法的實際調度計算便捷，效果良好，對云制造環(huán)境下的制造服務租賃優(yōu)化具有參考價值。

然而，本文方法的改進均體現(xiàn)在整體統(tǒng)計意義上，對于任務規(guī)模較小的算例，會出現(xiàn)少量制造任務及其制造服務的配置目標值略微變差的情況，平臺統(tǒng)籌安排租賃配置方式存在通過犧牲小部分客戶的利益來提升整體服務效用的現(xiàn)象；另外，本文沒有對制造任務的預測數(shù)量進行實驗優(yōu)化，對每個制造任務的交貨期設置得也比較簡單，這些不足都將在下一步研究中改進。