基於序貫時空博弈的動態鄰接資源調度研究

《基於序貫時空博弈的動態鄰接資源調度研究》是依託武漢理工大學，由張曉盼擔任項目負責人的青年科學基金項目。

基本介紹

• 中文名：基於序貫時空博弈的動態鄰接資源調度研究
• 項目類別：青年科學基金項目
• 項目負責人：張曉盼
• 依託單位：武漢理工大學

項目摘要

鄰接資源調度是一類特殊的資源約束調度，特點是系統資源必須以鄰接模式分配，即離散資源必須相鄰排列，連續資源必須構成不可重疊的單連通區域，常見於以多處理器陣列或封閉空間為服務資源的調度領域。在這一模式下，資源分配過程類似於剛性物體布局，構成了一種複雜的非線性組合資源約束，並與任務時序安排緊密關聯，形成時空耦合效應。由於目前缺乏完善的時空耦合效應系統演化理論，以及有效的時序安排和資源分配同步實時最佳化算法，動態鄰接資源調度成為理論研究與實際套用中的難點問題。本項目依據約束最佳化的拉格朗日鬆弛方法與零和博弈的相關性理論，提出動態鄰接資源調度的博弈論分析框架- - 序貫時空博弈模型，力求通過以時序最佳化、布局最佳化和鄰接約束懲罰為主體的3方雙層博弈結構，深入闡釋時空耦合效應下的動態鄰接資源調度最佳化決策機制和系統演化規律，並結合具有時空隨機特性的排隊系統模型，設計基於協同博弈策略學習的最佳化決策算法和系統仿真平台。

結題摘要

以一維空間資源的動態鄰接資源調度為主要背景，構建了動態鄰接資源調度系統的基本仿真模型，細分了動態調度策略的組成方式，將其分解為“資源分配策略”、“佇列排序策略”、“任務指派策略”、“伺服器運行策略”4種子策略的組合。以計算機仿真為主要手段，通過鄰接資源分配約束下排隊系統臨界穩定狀態下的服務強度測算研究了系統穩態下的平均服務資源分配效率，並通過模擬極端飽和任務流情況下足夠長時間內伺服器資源占用效率研究了資源利用效率的平均指標，發現在給定任務尺寸分布區間後，基於先到先服務（FCFS）策略的開放式鄰接資源調度過程的臨界服務強度特徵近似於一個縮減了服務資源尺寸後的常規多服務台排隊系統，並且其縮減比例等於飽和任務流情況下的伺服器資源穩態利用效率。基於上述定性結論，進一步在仿真實驗的基礎上，通過數據統計分析探討了鄰接資源調度中的時空耦合規律，主要研究了鄰接資源分配約束下，伺服器可用容量分布狀態對動態調度目標最佳化的價值，利用matlab符號運算工具箱得到了任意尺寸分布區間下和服務資源容量與服務效率相關性函式生成算法，揭示出服務效率隨服務資源容量增加而振盪性增加的非線性特徵。根據這一性質提出了基於任務等待時間與伺服器填充效率之間競爭性博弈的動態調度策略最佳化框架，並採用區間圖（Interval Graph）模型提出了任務個體在時空資源上的競爭性博弈統一框架。理論套用方面，在前期研究基礎上設計了“基於多Agent的三峽工程通航調度仿真平台”，並針對三峽船閘通航調度的具體問題研究了滾動時域框架下的三峽—葛洲壩聯合通航調度模型和算法。結合課題在資源最佳化分配方面的研究成果，以輸電網路中的動態監測和空間資源最佳化布局問題為背景，在動態資源最佳化、信息融合、智慧型算法等方面進行了一系列拓展研究，構建了基於進化算法和模糊Petri網路的絕緣子運行狀態診斷模型，以及基於圖論模型研究了PMU（向量監測單元）在電網路上的最優分配問題，提出利用電網拓撲結構和最小生成樹算法改進遺傳算法的最佳化方法。