基于制造網格的虛擬企業資源調度問題研究
2008-12-31 00:00:00高陽張坤
計算機應用研究 2008年7期
摘 要：為支持虛擬企業間資源的高效調度，在制造網格的基礎上，提出了虛擬企業的資源調度平臺。研究了基于GlobusToolkit 4和agent技術的平臺實現方法和工作流程。在此基礎上，提出了以T、C、Q、S為目標的多目標資源優化調度模型，結合制造網格與計算網格的差異，將網格底層的跨地域實體物流交互對資源調度的影響納入優化調度模型，使虛擬企業資源調度方案更加合理。最后，以一個具體的實例，驗證了多目標優化調度模型的有效性。
關鍵詞：制造網格； 資源調度平臺； 多目標優化
中圖分類號：TP311 文獻標志碼：A
文章編號：1001-3695(2008)07-2087-04
Research on manufacturing resources scheduling of virtual
enterprise based on manufacturing grid
GAO Yang， ZHANG Kun
(Dept. of Management Science Information， School of Business， Central South University， Changsha 410008， China)
Abstract:To support efficient scheduling of manufacturing resources among virtual enterprises，resources scheduling framework of virtual enterprise based on manufacturing grid was proposed. Implementation methods of framework were developed with reference to Globus Toolkits and multi-agent. Then，a multi-objective optimization model was put forward，which was based on T，C，Q and S. At last，the results of a scheduling case prove the validity of model.
Key words：manufacturing grid; resources scheduling framework; a multi-objective optimization
虛擬企業的制造資源調度過程是虛擬企業運營中的重要環節，調度效率的提高將在很大程度上改善整個虛擬企業的運營效率。在目前的網絡條件下，虛擬企業缺少一種可靠而有效的制造資源管理機制，難以監控各成員企業制造資源的信息和狀態，無法實現虛擬企業制造資源的高效調度[1]。而制造網格基于網格和相關先進的計算機與信息技術，通過網絡將分散在不同企業中的制造資源通過封裝和集成，屏蔽資源的異構性和地理分布性，使企業或經營個體能夠以請求服務的方式方便地獲得所有與制造相關的服務，能夠像使用本地資源一樣方便地使用封裝在制造網格中的所有資源[2]。與目前的網絡相比，網格具有可擴展性、互操作性、自適應性和動態性等特點。利用網格提供的資源搜索功能和信息服務，能夠針對用戶要求，快速選擇最優的資源服務，提高虛擬企業的調度效率。
本文在制造網格的基礎上，創建了虛擬企業資源調度平臺模型，并研究了資源調度平臺的工作流程，進而提出資源優化調度模型，并最終得出最優的資源調度方案。
1 基于制造網格的虛擬企業資源調度平臺
虛擬企業的資源調度平臺是建立在制造網格的基礎之上，利用網格提供的資源搜索功能和信息服務，能大大提高虛擬企業的資源調度效率，并能獲得較優的資源調度結果。
1．1 資源調度平臺的體系結構
圖1是資源調度平臺的體系結構，分為資源層、網絡層、協議層、網格中間件層和應用層五個層次。
1）資源層 處于平臺的最底層，由制造網格中的各個資源組成，包括硬件資源、軟件資源以及數據庫資源等。
2）網絡層 平臺運行所需的Internet/Intranet基礎環境。
3）協議層 包括網絡、網格協議及相關技術標準與規范。
4）網格中間件層 它是平臺的核心層，主要實現網格平臺的資源共享和調度。主要由以下兩部分組成：
（1）資源封裝系統。實現把制造資源封裝成網格服務的形式，并部署在網格服務容器中。
（2）資源調度系統。根據應用層用戶提交的任務進行分解，生成子任務，然后，在信息服務的支持下搜索平臺中可用的資源集合，進行任務調度和資源分配，并采用容錯機制對異常情況進行處理，最后將制造任務調度給所選的資源企業。
5）應用層 利用JSP開發資源調度平臺門戶portal，以更好地為平臺的管理者和用戶提供管理（如安全服務、QoS監控）、應用（如注冊服務、提交服務）支持界面[3]。
1．2 資源調度平臺的實現技術
基于制造網格的資源調度平臺需要滿足以下基本功能需求：a)制造資源的封裝和發布；b)制造任務的分解、分配和調度；c)基于制造任務需求的資源發現；d)容錯處理。根據以上要求，本文設計了如圖2所示的制造網格資源調度平臺模型。該平臺的實現主要依靠agent技術和Globus 軟件包。基于agent技術構建的網格中間件實現了制造網格制造任務的分解、分配和調度。Globus 軟件包作為整體框架實現的平臺，提供網格安全基礎設施（ grid security infrastructure，GSI）、資源分配管理者（globus resource allocation manager，GRAM）和監控與發現系統（monitoring and discovery system，MDS)組件等，以保證整體框架安全、有效地實現[3]。
1．2．1 資源封裝系統
該系統主要是基于Web服務資源框架WSRF來實現的。本文將制造網格中的制造資源分為九大類進行封裝，如表1所示[4]。
表1 制造網格資源關鍵類抽象
類的名稱類的概念描述類的對象實例
設備資源類制造活動中所需要的具有某種功能的物理設備機床、夾具、量具等
人力資源類制造活動中所需要的具有某種操作、管理和技術能力的人技術人員、管理人員、營銷人員等
技術資源類制造活動中所需要的技術性資源或條件，是在企業制造過程中固化的設計圖紙、設計流程、工藝流程、管理流程和營銷流程等的集合設計圖紙、設計流程、工藝流程等
物料資源類制造活動中所需要的物理材料、半成品和成品等毛坯、零部件、原材料等
應用系統資源類制造系統的整個生命周期中用到的所有軟件資源的集合，可以從功能的角度細化為設計系統、分析系統、仿真系統、虛擬現實、三維展示系統和管理系統等Pro/E、CAD、UG、PDM、ERP、CRM等
服務資源類為資源使用者提供各種信息的資源、培訓和維護等國家標準、行業標準、企業標準等
用戶信息資源類記錄資源提供者和資源使用者的一些基本信息，如資源提供方的誠信度、規模、產品特點等，為以后的資源評估、發現和調度提供依據企業、會員等
計算資源類在制造網格環境下計算機的CPU、存儲器等資源也成為制造資源的一部分，這種資源已經超出了傳統制造資源的范疇CPU、存儲器等
其他相關資源類如記賬、日志和公共信息等不在上述資源里的所有資源的集合記賬、日志等
針對每一類制造資源，將它們的公共屬性描述和操作抽取出來，定義在公共的資源接口文件中，即定義資源封裝模板來支持對資源的封裝。
1．2．2 資源調度系統
該系統主要是基于Globus Toolkit 4的監控與MDS組件和網格資源分配管理者以及agent技術的基礎上建立的。
1）MDS作為Globus Toolkit的信息服務組件，提供資源的注冊、發現和描述，并對服務狀態進行監控，起到對網格服務資源的組織功能。GT4版本的MDS稱為MDS4或WS MDS， MDS4包括以下三個組件：
(1)WS MDS index service。該服務搜集網格資源的狀態信息，并將其存入一個存儲單元。
（2）WS MDS trigger service。該服務用于監視資源并跟蹤所選擇的資源屬性，在資源狀態到達某個閾值時執行某些預定的操作。
(3)WS MDS aggregator。這是（1）（2）兩個服務構建于其上的軟件框架。Aggregator框架負責對aggregator源中的數據進行搜集、管理和編索引，并將這些數據發送給一個aggregator接收器進行處理[5]。
2）GRAM位于Globus Toolkit網格資源管理結構的底層，是應用與資源的橋梁，主要處理資源請求、遠程應用的執行、分配資源和管理活動任務，周期性地更新所轄資源在網格信息服務系統中的可用性和性能的信息，并把資源的動態情況反映給MDS[6]。
3）任務分解agent負責將用戶提交的任務分解成若干子任務，形成任務列表；然后根據子任務進行任務分配、調度，并根據所需要的制造資源在制造網格中重新選擇執行資源[7]。
4）任務分配agent負責監督與管理任務執行的全過程，在信息服務的支持下，針對任務列表中每一個子任務確定各個任務的資源集合，實現任務的分配，并形成任務隊列。當有緊急任務插入或資源提供方出現問題時，任務分配agent找出所受影響的任務，進行再調度與分配[7]。
5）任務調度agent 通過任務隊列的輸入數據結合調度模型和算法庫進行調度問題優化。當面對復雜任務調度問題時，將任務隊列中的開始、截止時間和約束關系作為條件，結合算法庫，選擇合適的優化算法，進行調度優化，并將結果輸出[7]。
1．3 資源調度平臺的工作流程
在制造網格中，企業分為兩類：a)通過平臺發布本企業多余或空閑的制造資源，為平臺提供資源和服務，稱之為資源企業[4]；b)利用平臺查找所需的制造資源或制造服務，選擇合作伙伴，建立虛擬企業，稱之為客戶企業。制造網格資源調度平臺的工作流程如下：
a）資源企業通過網格門戶，按照封裝模板將資源封裝為WSRF資源，并注冊到WS MDS index service中，供用戶查詢。
b）客戶企業通過網格門戶提交制造任務。
c）任務分解agent將任務分解成若干子任務，形成任務列表。
d）針對任務列表中每一個子任務，任務分配agent根據資源屬性匹配在WS MDS index service組件中查詢所需的資源，確定各個任務的資源集合，并形成任務隊列。
e）任務調度agent通過任務隊列的輸入數據結合調度模型和算法庫進行調度問題優化，形成資源調度方案，并將資源請求提交給協同分配器。
f）協同分配器將涉及多個資源的請求分成多個部分，并將它們發送到合適的本地資源管理器GRAM，資源管理器通過到各種本地資源管理系統的接口，將收到的RSL轉換為本地的具體資源管理系統的操作。
g）WS MDS trigger service組件對資源進行監視，當出現資源故障等異常情況時通知任務分配agent，任務分配agent找出所受影響的任務重新查詢可用資源，進行再調度與分配。
2 基于制造網格的虛擬企業資源調度方法
在制造網格環境下，資源企業通過制造網格平臺將制造資源封裝成網格服務（grid service，GS），并注冊為網格服務節點（grid service node，GSN）。因此基于制造網格的資源調度問題就轉換成為對GSN的調度問題。本文對文獻[10]中提出的多目標優化模型進行了改進。最后，以一個具體的實例，驗證了多目標優化模型的有效性。
2．1 基于制造網格的資源調度問題求解過程
資源調度問題求解過程描述如下：
a）根據制造任務類型，將制造任務分解成多個子任務的集合，直至每個子任務都可以由相應的GS來完成，也就是將制造任務映射為網格服務的有序集合。制造任務模型可以表示為
MT→{GS1，GS2，…，GSi，…，GSn}(1)
例如，某零件的生產任務可以映射為{CAD設計服務，CAE分析服務，數控車床加工服務，數控銑床加工服務，數控磨床加工服務，其他機器加工服務…}。
b）根據制造資源屬性匹配即網格服務的類型和參數在制造網格平臺中對提供GSi的GSN進行搜索，得到GSN的集合Gi={GSNi1，GSNi2，…，GSNimi}，mi為Gi中GSN的個數，制造資源特征包括功能特征（如銑端面、磨平面等）、技術特征（如加工精度、測量精度等）、狀態特征（如設備所處的狀態等）。
c）結合式(1)，所有可能的調度組合為∏ni=1mi種可能。對所有可能的調度組合進行評價，獲得最優的調度組合。
2．2 多目標資源優化調度模型
由于制造業的特殊性，資源具有的加工能力是衡量資源是否能夠滿足加工任務要求的最重要指標。此外，交貨及時性T(time，時間) 、加工質量高低Q(quality) 、加工成本高低C(cost) 、服務的優劣S(service) 也是影響產品市場競爭力的關鍵性能指標[10]。因此，基于制造網格的制造資源調度目標是使整個制造任務的制造過程最優，即流程時間（T）最短、加工質量（Q）最好、流程成本（C）最低和服務質量（S）最好。可見，制造資源的優化調度是個多目標優化問題。
2．2．1 構建優化調度目標函數的幾點假設
與計算網格不同，制造網格的應用除了信息的在線交流以外，還存在現實中的實體交流，因此不能如同計算網格所體現的虛擬跨地域，必須考慮實體物流交互對流程時間和流程成本的影響。如設計階段的業務協同完全可以建立在電子化的基礎之上，可完全在網格環境下展開。但對于制造、采購、運輸和服務等，除了網格信息交流，還需要考慮底層實體在供應鏈和物流環境中的交互[7]。因此，針對優化目標函數的構建作如下假設：
a）網格服務的在線調用不必考慮地域的限制，具有完全透明的處理過程，因此資源網格節點間的在線連接成本和連接時間忽略不計。
b）當資源服務節點對應的企業之間有實體物流的交互時，要考慮實體物流的交互帶來的連接成本和連接時間。連接成本與連接距離之間的關系為常數Xc，連接時間與連接距離之間的關系為常數Xt。
c）若有實體物流交互的資源節點對應的企業是同一企業，即企業內部的實體物流交互的連接成本和時間不予考慮。
d）為簡化問題，假設制造過程中不存在并行生產。
2．2．2 優化調度目標函數
1）總的流程時間最短
式中:Tin為資源服務節點的內在加工時間；Tlink為資源服務節點之間的連接時間；
Tij為Gi中第j個資源服務節點的內在任務加工時間，通過神經網絡，以數據庫中第j個資源服務節點的任務加工歷史信息作為輸出，輸出與具體制造任務有關的加工時間Tij;Li，i+1(j，l)為Gi中第j個資源服務節點與相鄰Gi+1中第l個資源服務節點的連接距離；Xt為連接時間與連接距離之間的關系。
2）總的流程成本最低
0 GSNij與GSNi+1(l)之間無實體物流的交互
j∈[1，mi]，l∈[1，mi+1]
式中:Cin為資源服務節點的內在加工時間；Clink為資源服務節點之間的連接時間；Cij為Gi中第j個資源服務節點的內在任務加工成本，采用神經網絡，以數據庫中第j個資源服務節點的任務加工歷史信息作為輸出，輸出與具體制造任務有關的加工成本Cij;Li，i+1(j，l)為Gi中第j個資源服務節點與相鄰Gi+1中第l個資源服務節點的連接距離；Xc為連接時間與連接距離之間的關系。
3）總的加工質量最優[12]
Qij為Gi中GSNij通過神經網絡計算出的加工質量指標值。
4）總的資源服務最好[12]
Sij為Gi中GSNij通過神經網絡計算出的服務質量指標值。
2．3 算例論證
某復雜零件的制造任務模型可以描述為MT→{GS1，GS2，GS3，GS4，GS5，GS6}。其中各個GS如表2所示。
表2 GS類型信息
編號GS1GS2GS3GS4GS5GS6
名稱CAD設計毛坯加工數控車床加工數控銑床加工立式銑床加工數控磨床加工
針對提交的模型信息， 從制造網格平臺中搜索所有匹配的GSN，通過神經網絡計算出任務在每個GSN上的內在加工時間(T)、加工質量(Q)、內在加工成本(C)和服務質量指標(S)，如表3所示。其中，Addr為GSN所屬企業的地理位置信息。
根據給出的任務模型，結合用戶對TQCS 目標權重的要求，通過采用文獻[10]中提出的遺傳算法對所有的調度方案進行優選。其中，各個企業之間的連接距離（km）信息如表4所示。
算法計算過程中，種群數量取30，交叉概率取0.9，變異概率取0.1，最優個體滯留10 代算法終止，Xt=0.01，Xc=1，用戶的目標權重為WT=0.20，WQ=0.15，WC=0.55，WS=0.10，通過計算得到最優解個體編碼為213122，則最優的資源調度方案為{GSN2，GSN3，GSN9，GSN10，GSN13，GSN17}。
3 結束語
本文在制造網格的基礎上，研究了虛擬企業資源調度平臺，并提出了以T、C、Q、S為目標的多目標資源優化調度模型。但所提出的模型并未將網絡層的應用考慮在內，如網絡傳輸帶寬、吞吐率都會對T、C、Q、S指標產生影響，并且沒有考慮并行任務的情況，有待于進一步研究。
參考文獻：
［1］鄧宏，陳笠，鄧倩妮，等.基于制造網格的虛擬企業組織變更與制造資源調度問題研究[J]. 計算機集成制造系統， 2006，12(8):1211-1219.
[2]顏波，黃必清，鄭力，等. 網格研究現狀及其在制造業中的應用[J]. 計算機集成制造系統，2004，10(9):1021-1030.
[3]樸杰，朱云龍. 網格技術在虛擬企業中的應用研究[J]. 計算機集成制造系統， 2005，11(2):176-181.
[4]胡業發，陶飛. 支持協同制造的制造網格平臺研究[J]. 中國機械工程， 2006，18:1903-1908.
[5]谷清范. 網格環境下的服務調度機制研究[D].南京: 東南大學，2006.
[6]劉麗蘭. 制造網格及其基于QoS 的資源管理方法的研究[D] . 上海:上海大學，2004.
[7]王愛民，范莉婭，肖田元，等.面向制造網格的應用平臺及虛擬企業建模研究[J].機械工程學報，2005，41(2):176-181.
[8]高陽，周偉. 基于多agent的虛擬企業調度研究與實現[J]. 中國機械工程，2005，16(24):2192-2197.
[9]谷清范， 吳介一， 張颯兵. 網格調度機制研究綜述[J]. 計算機應用研究， 2006，23(5): 1-4.
[10]張傳順，莫容，石勝友，等.基于遺傳算法的制造網格資源調度方法研究[J].中國機械工程，2006，17(18):1916-1920.
[11]LIU Li-lan， YU Tao， SHI Zhan-bei， et a1. Resource management and scheduling in manufacturing grid[C]//GCC 2003， LNCS 3033.Berlin:Springer-Verlag， 2004:137-140.
[12]QIU R G.Manufacturing grid:a next generation manufacturing model[C]//Proc of IEEE International Conference on Systems， Man and Cybernetics.The Hague:[s.n.]，2004.
[13]LI Zhi， JIN Xian-long，CAO Yuan，et al. Conception and implementation of a collaborative manufacturing grid[J].Int J Advanced Manuf Technol，2007，34(11-12):1224-1235.
注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。”
