本文選題：資源調度 + 最小費用最大流　； 參考：《軟件學報》2017年03期

【摘要】：并行作業(yè)是大規(guī)模資源調度的研究熱點.已有的研究工作通常采用隊列進行資源調度建模,僅能滿足局部最優(yōu)解且只能適應調度目標固定不變的場景,靈活性不夠.提出了一種基于最小費用最大流的大規(guī)模資源調度建模方法,將任務的資源需求和物理資源供給問題轉換成最小費用最大流圖的構造和求解問題.首先,選擇公平性、優(yōu)先級和放置約束這3種典型度量作為切入點,從資源視角映射為圖的構造問題,通過改變圖的結構,使其具備適應性調整能力;其次,針對圖的求解時間復雜度高的問題,實現(xiàn)了一種增量式優(yōu)化算法;最后,實驗對比公平性、優(yōu)先級和放置約束這3種資源調度典型系統(tǒng),驗證了該方法可通過按需配置,支持多種調度目標,具備靈活性.并通過實驗仿真,驗證了萬級規(guī)模下,基于圖的資源調度延遲比基于未優(yōu)化圖算法的資源調度延遲最多降低90%.
[Abstract]:Parallel jobs are the research focus of large-scale resource scheduling. The existing researches usually use queue to model the resource scheduling, which can only satisfy the local optimal solution and only adapt to the situation where the scheduling goal is fixed, so it is not flexible enough. In this paper, a modeling method of large-scale resource scheduling based on minimum cost and maximum flow is proposed. The problem of resource demand and physical resource supply of task is transformed into the construction and solution of minimum cost maximum flow graph. Firstly, three typical metrics, fairness, priority and placement constraints, are selected as the starting point to map to graph construction from the perspective of resources, and make the graph have adaptive adjustment ability by changing the structure of the graph. In order to solve the problem of high complexity of graph solving time, an incremental optimization algorithm is implemented. Finally, compared with three typical resource scheduling systems, fairness, priority and placement constraints, it is verified that the method can be configured on demand. Support for multiple scheduling objectives with flexibility. The simulation results show that the resource scheduling delay based on graph can be reduced by 90% compared with that based on unoptimized graph algorithm.
【作者單位】： 中國科學院軟件研究所軟件工程技術研究開發(fā)中心;計算機科學國家重點實驗室(中國科學院軟件研究所);中國科學院大學;
【基金】：國家重點研發(fā)計劃(2016YFB1000103) 國家自然科學基金(61572480) 國家科技支撐計劃(2015BAH55F02)~~
【分類號】：O224

【相似文獻】

相關期刊論文 前10條

1 婁惠元,付連魁,楊冬梅;最小費用最大流的擴流問題[J];沈陽黃金學院學報;1997年03期

2 張遠福;譚毓澄;余劍敏;;制造網(wǎng)絡的一個最小費用最大流算法[J];江西師范大學學報(自然科學版);2007年06期

3 劉耕;;一類最小費用最大流的擴張問題研究[J];物流技術;2009年12期

4 劉旭浩;;最小費用最大流新解嘗試[J];福建電腦;2010年10期

5 趙禮峰;白睿;宋常城;;求解最小費用最大流的新方法[J];計算機技術與發(fā)展;2012年05期

6 謝政，湯澤瀅;帶有模糊容量限制的網(wǎng)絡中的最佳最小費用最大流[J];模糊系統(tǒng)與數(shù)學;1996年01期

7 彭位炳;求解最小費用最大流問題的外枝界定法[J];湖北汽車工業(yè)學院學報;1998年02期

8 李瓊婕;薛耀文;;最小費用最大流維度拓展及其在反洗錢中的應用研究[J];山西師范大學學報(自然科學版);2014年01期

9 金志敏;關于最小費用最大流算法的一點改進[J];浙江經(jīng)專學報;1990年02期

10 謝凡榮;運輸網(wǎng)絡中求最小費用最大流的一個算法[J];運籌與管理;2000年04期

相關會議論文 前1條

1 周忱;彭錦;;網(wǎng)絡最小費用最大流的不確定容量擴張期望值模型[A];第九屆中國不確定系統(tǒng)年會、第五屆中國智能計算大會、第十三屆中國青年信息與管理學者大會論文集[C];2011年

相關碩士學位論文 前2條

1 周忱;不確定網(wǎng)絡最小費用最大流問題[D];上海師范大學;2012年

2 宋常城;基于最小費用最大流算法的若干研究與分析[D];南京郵電大學;2012年

，

本文編號：1853073