面向大規模并發制造服務請求的資源優化配置

張宏國　石巖磊　馬超　張淑麗　劉勝輝

摘 要：針對如何高效處理云制造服務平臺中大規模時序并發的制造服務請求這一問題，提出了一種面向服務響應時間的制造服務請求分段算法，通過制造任務相似性距離算法來保障分段算法的準確性。在分段算法保證制造服務請求完整性的前提下，構建了制造服務資源的關聯區域。在此基礎上，進一步提出了一種基于關聯區域的制造服務資源分配算法，在時間維度上，保障了制造服務資源提供的公平性，從而提高了資源受限情況下的制造服務資源全局優化配置效率。最后通過實驗測試和分析證明了算法的正確性和有效性。

關鍵詞：云制造;大規模請求;制造資源配置

DOI：10.15938/j.jhust.2019.03.002

中圖分類號： TP391

文獻標志碼： A

文章編號： 1007-2683（2019）03-0009-07

Abstract：Aiming at how to efficiently handle the massive temporal sequential manufacturing service request in cloud manufacturing service platform， this paper proposes a service response timeoriented service request segmentation algorithm. The manufacturing task similarity distance algorithm is used to guarantee the segmentation algorithm accuracy. Then the correlated region is constructed under the premise of ensuring the integrity of manufacturing service request. On the basis of this， a manufacturing service resources allocation algorithm based on correlated region is proposed so as to ensure the equal distribution of manufacturing service resources in temporal dimensions， and then to improve the efficiency of the global optimization of the manufacturing service resources in the case of limited resources. Finally， the correctness and validity of the algorithm are proved by experiment and analysis.

Keywords：cloud manufacturing; massive service requests; manufacturing resource allocation

0 引 言

隨著“互聯網+”模式被廣泛的認同，作為近年來熱門研究方向的敏捷化制造獲得了更快速的發展。越來越多的世界一流企業、公共機構都在往敏捷化更高的云服務平臺上遷移。通過云服務平臺可以實現效率的最大化和成本的降低。云制造作為一種先進的敏捷制造模式由李伯虎院士提出，它是對已有網絡制造的延續和云升級。云制造是一種面向服務的網絡化制造新模式，云制造基于云計算、物聯網和大數據等先進的信息化技術，它將傳統制造企業分散的制造資源，通過虛擬化的方式接入到云制造服務平臺進行統一管理，為制造企業提供全生命周期的制造服務[1]。既實現了同網絡化制造一樣的“分散資源集中利用”，又實現了“集中資源分散使用”的設計思想。一方面使得接入企業的制造資源可以同時向多個企業提供服務，大大的提高了制造資源的利用率[2-3];另一方面能力有限的企業可以通過使用云制造服務來提高自身的加工能力，提升企業的競爭力和市場占有率，從而提高企業的經濟收益。

目前，云制造的研究主要集中在云制造平臺的整體架構、制造資源的虛擬化[4]、落地應用[5]等方面。在制造任務的處理和資源的分配方面Lartigau J等[6]提出了一種將制造任務訂單分解成多個子任務的云制造任務處理模型，通過多任務去匹配云平臺中的制造資源共同執行一個訂單任務，實現了一種基于云平臺級的云制造資源的配置方法。王時龍等[7]建立了以物料流和信息流的成本和時間為主要影響因素的云制造資源配置模型，以成本最少、時間最短和質量最優為優化目標，采用最大繼承法對模型進行求解。蘇凱凱等[8]等建立了一種考慮云制造平臺服務運營者和服務請求者雙方的制造資源配置雙層優化模型，以服務質量和柔性指標為優化目標，使用改進的多目標算法對問題進行求解。尹超等[9]針對云制造服務配置過程中多個目標建立了一種面向新產品開發的優選模型，采用灰色關聯度方法對模型的求解進行了分析和驗證。然而多數學者在制造資源優化配置方面通常都是對單一任務的處理[10]，然而在云制造平臺實際運行過程中，將面臨著大規模、時序并發性的云制造服務請求處理，這方面的研究卻很少受到學者的關注。云制造平臺作為開放的平臺，如何高效的處理大規模并發的任務請求;同時現代客戶對制造服務的需求也從基本功能關注逐漸的轉變成了以服務收益和滿意度為標準的個性化服務請求[11]，如何提高用戶的整體滿意度。這些新的問題對云制造平臺的落地實施提出新的挑戰。

本文從云制造平臺的實際運行角度出發，對大規模時序并發制造服務請求的問題分析，設計了一種保證任務完整性的制造服務請求分段方法，并且提出在此基礎之上的制造服務資源分配方法，可以在云制造平臺的宏觀層面上保證用戶獲得服務的公平性和全局最優，進而提升平臺中用戶的整體滿意度。

1 云制造環境下制造任務與制造資源的虛擬化描述

云制造平臺讓所有用戶與企業的互動集中在同一個平臺，使得客戶提高了從設計到產品的轉換率，企業提高了制造資源利用率，是一個雙贏的服務平臺。云制造平臺結構示意圖，如圖1所示。通過云制造平臺的紐帶作用，制造資源服務提供方將資源通過虛擬化接入到平臺中供平臺調度使用，服務請求方將制造服務請求下達至云制造平臺，平臺將根據每個制造服務請求生成相應的制造任務訂單，粒度大的產品級任務將進行分解成零部件級和工件級然后分配相應的制造資源進行加工，粒度小的任務可以直接參與制造資源的分配和調度。通過實際問題的分析發現，云制造設備資源不像云計算資源可以不受限于服務資源的地理位置，在云制造服務的過程中需要將服務請求者的工件通過物流運輸至不同的企業中進行多次車間現場加工，所以配置資源的過程中運輸因素也是要充分考慮的一個特點。

云制造服務請求問題可描述為：有n個制造任務{Task1，Task2，…，Taskn}，有m處制造服務資源{Service1，Service2，…，Servicem}可以提供服務，每個制造任務可以通過一個或多個資源進行加工。

首先，對云制造環境下的制造服務請求和制造資源云服務進行虛擬化描述，本文主要研究的制造資源為制造設備資源。

1.1 制造服務請求

每個制造服務請求以制造任務的形式進行表示。制造任務Task描述為一個六元組，Task=，其中

1）TaskID是任務的唯一編號。

2）BAttrInfo是對任務的基本靜態屬性信息描述，BAttrInfo=（Name， PList， Material， Num， Unit， Grade），分別表示加工任務的名稱、工序列表、材料、加工數量、計量單位、任務等級（產品級、零部件級、工序級）。PList 表示工序列表，其中的每一個列表項表示一項待處理的任務，Process=（ProcessID， Name， Precision）分別表示工序唯一編號，名稱、加工精度。

3）Constraints表示對任務的加工約束信息描述，Constraints=（maxTime， maxCost， minQuality， minSatisfaction），分別表示任務要求的最大服務完工時間，最多資金花費，最低的質量標準，最低的滿意度標準。

4）TraInfoList是對任務的運輸相關信息描述，其中每一個列表項表示一個物流信息，TraInfo=（ProcessID， StartLocation， EndLocation， Conveyance， TranTime， TranCost， Remark），分別表示加工任務的工序唯一編號、運輸起點企業、到達的終點企業、運輸方式、運輸花費時間、運輸花費資金、特殊的運輸說明。

5）DAttrInfo是對任務的動態信息進行描述，DAttInfo=（curProcessID， State， curStartTime， curEndTime），分別表示當前任務的執行狀態，有在制、在途、等待、完成四種狀態、當前對應工序編號、當前狀態開始加工時間、結束時間。

6）AttaInfo是任務的附件信息描述，AttaInfo=（note， URL），分別表示附件信息說明、附件信息網絡地址。附件中可以是工件的設計圖紙、特殊工藝說明等等。

1.2 制造設備資源云服務

制造設備資源云服務。制造設備資源云服務Service可以定義為一個五元組，Service=，其中

1）ServiceID是設備云服務的唯一編號。

2）BAttrInfo是設備云服務的基本靜態屬性信息描述，BAttrInfo=（Name， Model， Enterprise， Location， Cost， Unit），分別表示設備云服務的名稱、型號、提供企業、物理位置，以“元/單位”表示，單位Unit包括不同的計量方式小時、件等。

3）FunAttrInfo是設備云服務的加工能力描述，FunAttrInfo=（Type， Material， Shape， Size， Precision），分別表示設備云服務的生產類型，對象材料特征，對象形狀特征，對象尺寸特征，對象加工精度。

4）EvaList表示用戶評價歷史集合，每一個列表項表示一次用戶評價，Evaluation=（UserID， TaskID， Scores， EvaTime） 分別表示評價的用戶編號、任務的唯一編號、評分、評價時間。

5）TList表示動態的任務處理列表，TList=（State， PTask） 其中State表示服務的狀態，有空閑、工作、報修、維修四種狀態，每一個列表項PTask表示一項處理任務，PTask=（TaskID， Num， State， RemainNum， ProcessID， EsStartTime， MaxResTime），分別表示任務的編號、需要加工數量、任務的執行狀態、未處理的數量、工序編號、預計開始加工時間、服務的最大響應時間。

2 大規模時序并發制造服務請求的高效處理

在云制造服務請求過程中不同的制造服務請求者可能在短時間內發出多個服務請求，這些目標不同的請求構成了大規模并發性制造服務請求，由于本文主要考慮的制造資源為制造設備，制造設備資源是有限的所以無法在短時間內滿足每個客戶的請求。如果使用傳統的算法，那么在時間維度上先到達的客戶會優先使用全部可用的服務資源，后續的用戶優化效果往往都要受限于先前的資源使用情況，可能優化的效果僅僅是局部最優，由此產生的服務優化效果對整體用戶的滿意度將產生負面的影響。這種資源分配算法無法保證平臺可以公平的為每個用戶提供不受時間序列限制的服務資源，隨著用戶的滿意度下降最終也將導致平臺的收益下降。針對大規模制造服務請求優化問題，在考慮任務的完整性和服務公平性的角度，對大規模請求進行分段處理和分段間制造服務力進行均衡配置，進而達到時間維度的全局最優，提高用戶整體滿意度。

2.1 制造任務分解方法

在云制造產品生產過程中，加工產品往往是由一組工件組裝而成，每個工件的制造過程中還要考慮彼此的約束關系。往往云制造產品的生產規模大、復雜度高、任務粒度粗等特點，本文首先將粒度大的任務訂單進行多任務的分解，便于協同加工提高制造效率。根據產品的所處階段，可以將制造任務分為產品級、零部件級和工件級三層。根據每個子任務的生產工藝分解成一道或多道工序，形成一個整體的工藝加工樹狀圖，從樹的葉節點開始執行任務，最終到達根節點完成整個產品。

對已有的分解方法進行研究后[12-13]，本文依據大規模并發任務的特點采用自上而下的分解方法，即根據產品逐層向下細分。在分解過程中會根據平臺分解任務的歷史記錄尋找相似的任務分解方案，形成一定的分解模板。根據新產品的約束條件和目標，在模板上通過局部調整從而生成新產品任務分解結構，通過對任務分解結構模板的利用，可以減少在任務分解中的工作量，提高工作效率。除使用模板外還將結合客戶定制計劃。當客戶對產品的整個生產有詳細的分解計劃進行服務請求時，平臺首先需要分析計劃是否可以滿足，在滿足需求的情況下平臺將分配資源去執行加工任務，如果平臺無法滿足需求則使用平臺提供的分解方案進行調整。

2.2 面向服務響應時間的制造服務請求分段算法

傳統算法是將整個制造服務請求流進行時間維度的均勻分段處理，然而實際的制造服務請求流中分布可能是不均勻的。圖2展示了傳統方法處理過程，其中每個文檔圖標代表一個制造服務請求產生的制造任務，每個分段間由虛線進行分割，左側部分表示正在接受服務的請求。傳統算法針對整個時間維度的請求都進行了均勻分割。圖3展示了制造服務請求分段算法處理過程，該方法依據每個請求的服務響應時間上限來進行分段間距控制，保證了每個請求不會因為分段算法而產生服務質量的明顯影響。

2.3 制造任務相似性距離

在分段處理過程中，需要對任務的執行時間進行預估，在預估時將使用功能性相似的請求作為參考[14-15]。在制造加工的同一領域中制造服務請求的加工任務規模、涉及的加工工序及流程都是具有較高的相似性，不同的服務請求可能包含的具體工序數目和前后關系不一致，但其執行服務過程中存在大量的重疊部分，這意味著功能性相似的請求間存在大量的相同加工工序和制造設備資源使用，而不同的用戶會在服務綜合質量上有著各種個性化的要求。因此對同一制造領域中服務請求的相似程度通過請求間的相似距離進行描述，請求間的相似距離通過式（1）進行計算：

其中：Task1、Task2表示需要計算的兩個任務，Q+表示對評價有正相關的m個評價指標;Q-表示對評價有負相關的n個評價指標。

Q+包含服務質量和用戶滿意度。其中服務質量平臺根據服務可靠性、設備故障率和可維護性三項指標對資源進行評分。服務質量通過歸一化后使用數值[1，10]進行評分，數值越大代表質量越好;用戶滿意度可以通過資源歷史使用者的評價進行計算得出，使用數值[1，5]進行評分，數值越大代表滿意度越高。

Q-包含服務完成時間和服務成本。服務執行過程中工件需要在不同地理區域進行運輸。其中服務完成時間包括服務執行時間和運輸時間。服務成本包括服務執行費用和運輸費用。

2.4 基于關聯區域的制造服務資源分配算法

在經過請求分段后，第i分段的制造服務請求占用的制造資源所影響區域Srelai，稱為第i段的關聯區域。如圖4所示，圖中第i段的關聯區域為分段的結束時刻到所有制造服務使用完畢的最晚時刻。所以設分段Si包含n個請求，則Si的關聯區域Srelationi=[tei，tei+max{Tk|k=1，2，…，n}]。

3.2 測試與分析

為了驗證模型和算法的有效性，通過某電機制造任務數據結合云制造平臺的實際特點進行實驗設計和測試。使用電機制造過程中常用的車床、鉆床、鏜床、刨床、銑床等制造設備資源作為制造服務供平臺使用，云制造平臺中的候選制造服務滿足T∈[2，10]C∈[10，20]Q∈[9.5，9.8]S∈[4.5，4.8]。通過隨機產生制造任務請求，用戶請求要滿足T∈（15，20）C∈（1850，2000）S∈（4.40，4.70）Q∈（9.5，9.70），每個單位時間產生[0，4]個新請求。

平臺首先在接到任務請求訂單后先通過2.1節分解方法進行任務的分解，然后使用請求分段算法對大規模的制造任務請求進行分段，進而進行制造服務資源分配，使用粒子群算法來對方案進行搜索和資源配置[16-9]，設置種群大小為50，進化代數為300。產生120個單位時間的模擬數據，使用前80個單位時間作為歷史數據的收集，后40個單位時間作為算法測試。

為了驗證算法在不同服務資源條件下的性能，通過設同類型機器分別提供5、10、15 3種并發。圖5到圖7分別是算法在3種條件下的運算結果。x軸表示時間，y表示該時間點上的評價綜合服務質量通過圖中結果可以看出傳統的方法在制造任務執行的開始階段由于資源充足，使得加工的服務質量較優，然而隨著時間的推移服務資源的短缺，導致服務質量出現明顯的波動，造成制造后續到達的用戶無法得到高質量的服務。而基于關聯區域的制造資源分配算法可以在服務資源充足和不足的情況中均表現出較好的服務質量穩定性，可以為用戶提供與到達時間無關的公平資源使用條件。

表3表示兩種配置算法在不同條件下的測試結果，數值越大代表綜合質量越優。通過服務平均綜合質量可以看出分段算法保證了任務的完整性，在配置資源時保證時間維度的加工連續性提高了服務平均綜合質量。從服務綜合質量標準差可以看出，分段算法和關聯區域制造資源分配算法通過對后序制造請求的考慮，保證了加工質量的穩定性，提高了用戶的整體滿意度。

4 結 論

本文依據云制造平臺中任務的特點進行制造任務分解，以此提高加工效率和任務整體穩定性。然后考慮到云制造平臺制造任務大規模并發性的特點，對大規模并發任務進行了制造任務分段和服務資源預留的處理，既保證了用戶對資源調用的公平性，又保證了有限的服務資源可以在大規模請求序列中達到全局最優，從而提高了用戶的整體滿意度，可以為平臺贏得更多的用戶。通過上述算法在實驗中的使用，可以證明該方法高效的解決了云制造環境下大規模并發性制造任務請求的制造資源服務全局優化配置問題。

參 考 文 獻：

[1] FEI T， HU Y， ZHOU Z.Correlationaware Resource Service Composition and Optimalselection in Manufacturing Grid[J]. European Journal of Operational Research， 2010， 201（1）：129.

[2] SCHULTE S， HOENISCH P， HOCHREINER C， et al. Towards Process Support for Cloud Manufacturing[C]// IEEE International Conference on Enterprise Distributed Object Computing. 2014：142.

[3] 李伯虎，張 霖， 王時龍，等. 云制造—面向服務的網絡化制造新模式[J].計算機集成制造系統， 2010， 16（1）： 1.

[4] 任磊， 張霖， 張雅彬，等. 云制造資源虛擬化研究[J]. 計算機集成制造系統， 2011， 17（3）：511.

[5] 萬曹雷， 邵俊鵬. 云制造環境下車間制造資源網格管理設計[J]. 哈爾濱理工大學學報， 2013， 18（5）：37.

[6] LARTIGAU J， NIE L， XU X， et al. Scheduling Methodology for Production Services in Cloud Manufacturing[C]// International Joint Conference on Service Sciences. IEEE Computer Society， 2012：34.

[7] 王時龍， 宋文艷， 康玲，等. 云制造環境下的制造資源優化配置研究[J]. 計算機集成制造系統， 2012， 18（7）：1396.

[8] 蘇凱凱， 徐文勝， 李建勇. 云制造環境下基于雙層規劃的資源優化配置方法[J]. 計算機集成制造系統， 2015， 21（7）：1941.

[9] 尹超， 張云， 鐘婷. 面向新產品開發的云制造服務資源組合優選模型[J]. 計算機集成制造系統， 2012， 18（7）：1368.

[10]張淑麗， 劉勝輝， 沙晨明. 求解柔性作業車間調度的島嶼模型遺傳算法[J]. 哈爾濱理工大學學報， 2016， 21（5）：101.

[11]胡艷娟， 武理哲， 張霖，等. 云制造服務評價理論與方法研究綜述[J]. 計算機集成制造系統， 2017， 23（3）.

[12]易樹平， 譚明智， 郭宗林，等. 云制造服務平臺中的制造任務分解模式優化[J]. 計算機集成制造系統， 2015， 21（8）：2201.

[13]劉明周， 王強， 凌琳. 基于分層任務網絡的云制造任務分解方法[J]. 中國機械工程， 2017， 28（8）：924.

[14]王國新， 杜景軍， 閻艷，等. 面向加工功能均衡分布的制造系統構形優化[J]. 計算機集成制造系統， 2015， 21（6）：1497.

[15]賀可太，朱道云. 云制造服務質量評價研究[J]. 計算機集成制造系統， 2017.

[16]ZHANG Hongguo， HE Linyan， MA Chao， et al.Improved MultiRulesBased ACO algorithm for FJSS Problem in Cloud Manufacturing Environment [J].International Journal of Hybrid Information Technology 2016：29.

[17]張宏國， 宮雪. Jobshop調度求解的廣義蟻群算法[J]. 哈爾濱理工大學學報， 2017， 22（1）：91.

[18]劉勝輝， 李小陽， 張淑麗. 求解車間調度問題的雙禁忌表禁忌搜索算法[J]. 哈爾濱理工大學學報， 2016， 21（6）：50.

[19]喬佩利，馬麗麗，鄭林. 基于改進粒子群算法的車間作業調度問題研究[J]. 哈爾濱理工大學學報，2011，16（2）：35.

（編輯：關 毅）