[發明專利]一種可消除優先權沖突的任務與資源優化配置方法

無效

• 申請號: 201310245696.X
• 申請日: 2013-06-19
• 公開（公告）號: CN103279812A
• 公開（公告）日: 2013-09-04
• 發明（設計）人: 張麗麗;邱昭瑩;李玉貞;王慧斌;李臣明
• 申請（專利權）人: 河海大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04
• 代理公司: 南京蘇高專利商標事務所(普通合伙) 32204
• 代理人: 柏尚春

技術領域

本發明涉及復雜系統優化與建模技術領域，特別是涉及一種可消除優先權沖突的任務與資源優化配置方法。

背景技術

人們總是按最大化效益、最小化成本這一資源優化配置原則進行生產活動。在生產活動過程中，由于資源的稀缺性，利用有限的資源去完成多項任務時，優先完成的任務必然要保障資源的優先投入，但這樣會導致投入到完成其他任務資源的減少，因此，尋找優化算法來對任務和資源進行優化配置顯得尤為重要。優化算法對于解決不同任務和資源優化配置問題重點不同，很多學者對此已展開實證研究，我國學者李洪瑞將模擬退火算法(SA)用于解決火力優化配置問題；國防科技大學陳洪輝等利用多維動態列表規劃(MDLS)算法和多優先級動態列表規劃(MPLDS)算法解決了作戰任務和資源間的優化配置問題；河海大學李臣明等人將Agent群決策技術應用在跨流域水資源的優化調度中去。利用優化算法去解決資優化源配置問題應用非常廣泛，如物資調度、運輸管理、經濟研究和作戰訓練等，具有非常重要的科研價值和實際意義。

在處理復雜的任務與資源配置上，可利用多維動態列表規劃算法(MDIS)來進行優化配置，但多維動態列表規劃算法在資源配置中存在缺陷，如容易陷入局部最優搜索和優先權函數合理性問題。

發明內容

發明目的：基于復雜資源調度問題上存在局部搜索和優先權函數的合理性問題，本發明提供了一種可消除優先權沖突的任務與資源優化配置方法。

技術方案：一種可消除優先權沖突的任務與資源優化配置方法，包括：

（1）初始化算法數據，完成時間更新和分配可行性檢查，采用了加權長度算法來計算任務的優先權系數pr，當用加權長度算法計算任務的優先權系數pr時，pr值越小的任務對應的任務優先級越大。

（2）根據優先權選擇要處理的任務，定義平臺選擇任務優先權pt，按平臺選擇任務的時間優先系數pt₁和任務資源需求矢量距離優先系數pt₂對還沒有處理的任務進行優先級的排序，以最小化整個任務過程的完成時間為目標。

（3）消解優先選擇沖突，選擇處理任務的最佳平臺組，最佳平臺組的選擇包括：任務對平臺的選擇、平臺對未處理任務的選擇以及兩種選擇沖突的消解。采用加權方法解決任務與平臺優先選擇的沖突，引入選擇優先權參數，消解優先權沖突。

本發明采用上述技術方案，具有以下有益效果：本發明以任務完成時間最短或以提高資源利用率為目標，方法設計中引入加權方法來解決任務優先權或任務與任務平臺相互優先權問題，解決了復雜資源調度問題上存在局部搜索和優先權函數的合理性問題，引入優先權參數，可以有效消解任務與資源選擇優先權沖突問題，提高了算法的效率。

附圖說明

圖1為本發明實施例的方法流程圖；

圖2為本發明實施例的初始數據狀態圖；

圖3為本發明實施例的任務選擇流程圖；

圖4為本發明實施例的資源在任務上的配置示意圖；

圖5為本發明實施例的任務流程圖；

圖6為本發明實施例的一種任務與資源優化結果圖；

圖7為本發明實施例另一種任務與資源優化結果圖。

具體實施方式

下面結合具體實施例，進一步闡明本發明，應理解這些實施例僅用于說明本發明而不用于限制本發明的范圍，在閱讀了本發明之后，本領域技術人員對本發明的各種等價形式的修改均落于本申請所附權利要求所限定的范圍。

（1）初始化數據，確定任務選擇優先權

初始化數據：設置MT₀=ST′∪{0}，建立初始的任務集合MT₀與可獲取的資源集合SP₀，初始數據狀態如圖2。

如沒有初始化數據，則第一步要先檢查和選擇基本狀態空間g，在g狀態空間中選擇最佳狀態，計算任務到訓練資源不同配置情況下的f_g′，選擇g狀態空間的選擇流程如圖3所示。

有多種方法對等待被處理的任務t_i進行選擇，由于任務間存在邏輯和時間順序關系，對等待被處理的任務t_i采用不同選擇方法會影響最終運算結果，因此在從初始任務集中選擇可被處理的任務t_i時，本發明采用了加權長度算法計算任務的優先權系數pr，當用加權長度算法計算任務的優先權系數pr時，pr值越小的任務對應的任務優先級越大：