[發明專利]一種基于復雜網絡的制造網格復雜任務資源節點選擇方法

在審

• 申請號: 201410180427.4
• 申請日: 2014-04-30
• 公開（公告）號: CN103944998A
• 公開（公告）日: 2014-07-23
• 發明（設計）人: 尹勇;撒繼銘;周祖德
• 申請（專利權）人: 武漢理工大學
• 主分類號: H04L29/08
• 分類號: H04L29/08
• 代理公司: 湖北武漢永嘉專利代理有限公司 42102
• 代理人: 鐘鋒

技術領域

本發明涉及制造網格技術領域，尤其涉及一種基于復雜網絡的制造網格復雜任務資源節點選擇方法。

背景技術

???在以制造資源和服務共享為基礎的制造網格環境下，資源的選擇及其優化調度方法是資源共享和協同的關鍵。為了使制造用戶“在合適的時間以合適的方式使用合適的資源”，國內外許多學者針對Globus資源管理體系中的不足，提出了各自的資源選擇方法?？梢詺w納為以下幾點：

（1）基于智能算法模型的資源選擇

基于智能算法的資源選擇方法比較適合資源對象不明確的情況，它根據輸入輸出數據用神經網絡等智能方法來確定黑箱模型。一些學者將智能化方法，如神經網絡、蟻群算法、禁忌搜索算法、遺傳算法、多智能體等用于制造資源的選擇中，取得一些研究成果。這類方法的優點很明確，具有以下共同的要素：自適應的結構、隨機產生的或指定的初始狀態、適應度的評測函數、修改結構的操作、系統狀態存儲器、終止計算的條件、指示結果的方法、控制過程的參數。這些智能優化算法具有自學習、自組織、自適應的簡單特征和簡單、通用、魯棒性強、適于并行處理的優點，在并行搜索、聯想記憶、模式識別、知識自動獲取等方面得到廣泛的應用。但這些方法的缺點同樣明顯，對于制造網格多資源動態的復雜資源選擇而言，由于不了解復雜資源對象的內部結構，因此不能有效地指導后續的選擇算法設計。同時，當資源選擇規模進一步擴大特別是在動態調度環境中，這類方法滿足不了實時性的要求，故這類方法適合求解適當規模的靜態資源選擇問題。

（2）基于圖論模型的資源選擇

最早將圖論模型用于資源選擇問題的是Balas于1969年提出的析取圖，析取圖是最簡單的一種圖論模型，通過此種描述，每種資源選擇實現都可以看作是該圖中的一條路徑，因此極小化最后一個任務完成時間的選擇目標可以看成是提取其中的某個完備子圖使得其中的最大路徑極小化；排隊論網絡模型在資源選擇中的應用也得到研究，在排隊理論中，每個制造資源作為節點，每個節點上子任務的堆積視為該節點上的隊列，如果兩個節點之間的隊列有直接關聯，即如果一個任務在某個節點上加工完緊接著還要到另一個節點上加工，則該兩個節點對應的節點有邊相連，從而使得選擇問題一定程度上可以采用排隊論理論來求解。一些學者將Petri網模型用于制造網格的資源選擇問題中，取得一定效果。由于該類模型非常注重細節，因此具有極強的描述能力，但也正因為如此，Petri網的狀態空間會存在指數爆炸問題，這限制了該模型更為廣泛的應用；莫瑜等將節點著色模型應用到制造網格的資源管理中，其出發點是為了完成一定量的任務所需要的某種資源的最少量。通常完成一定量的任務可以用一個網絡圖來表示，而計算某種資源的最少量則可以相應地轉化為該網絡圖上的節點著色問題。節點著色模型由于它的圖論本質，具有形象化的優點，同時它的描述方法比Petri網簡單很多。

所有這些模型都有一個共同的假設，即在分析具體問題時，圖的結構都必須是固定的，即必須是一個靜態的圖。比如對于析取圖而言，如果網絡結構一直在變化，要從中提取出一條最長路徑幾乎是不可能的；對于Petri網而言，所分析的也是一個靜態的圖，即所有待處理的事件都需要提前給定；節點著色模型只能針對一類比較狹窄的選擇問題，即選擇目標必須是某類資源的某種個數最少，這一事實限制了這類模型的應用范圍，無法解決制造網格環境下多資源、動態異構的復雜資源選擇問題。

發明內容

本發明要解決的技術問題在于針對現有技術中資源選擇方法在制造網格分布、動態環境下復雜制造任務資源節點選擇上的不足，提供一種基于復雜網絡的制造網格復雜任務資源節點選擇方法，以解決制造網格環境下多資源、動態異構的資源節點的全局優化選擇問題。

本發明解決其技術問題所采用的技術方案是：一種基于復雜網絡的制造網格復雜任務資源節點選擇方法,包括以下步驟：

(1）對復雜制造任務進行分解：根據制造任務要求，復雜制造任務分解成適合于網格資源節點加工的可并行或串行執行的相關的n個子任務t_i（i?=1，2，…n）；

具體如下：

1.1）將復雜制造任務T按加工需求分解成n個子任務t_i；

1.2）如果t_i是最小子任務，則進入步驟2）；否則進入步驟(1.3）；

1.3）對非最小子任務進行滿意度測評，若達到任務分解平均滿意度后則不必再分解，進入步驟2）；否則回到步驟1.1）繼續對該任務進行分解；