基于最小费用最大流的大规模资源调度方法

来源：软件学报杂志2017年第3期北京时间：

作者：陈晓旭,吴恒,吴悦文,陆志刚,张文博

单位：陈晓旭，中国科学院 软件研究所 软件工程技术研究开发中心, 北京 100190;计算机科学国家重点实验室(中国科学院 软件研究所), 北京 100190;中国科学院大学, 北京 10004911,吴恒，中国科学院 软件研究所 软件工程技术研究开发中心, 北京 10019002,吴悦文，中国科学院 软件研究所 软件工程技术研究开发中心, 北京 100190;计算机科学国家重点实验室(中国科学院 软件研究所), 北京 100190;中国科学院大学, 北京 10004903,陆志刚，计算机科学国家重点实验室(中国科学院 软件研究所), 北京 100190;中国科学院大学, 北京 10004904,张文博，中国科学院 软件研究所 软件工程技术研究开发中心, 北京 10019005

摘要：并行作业是大规模资源调度的研究热点.已有的研究工作通常采用队列进行资源调度建模，仅能满足局部最优解且只能适应调度目标固定不变的场景，灵活性不够.提出了一种基于最小费用最大流的大规模资源调度建模方法，将任务的资源需求和物理资源供给问题转换成最小费用最大流图的构造和求解问题.首先，选择公平性、优先级和放置约束这3种典型度量作为切入点，从资源视角映射为图的构造问题，通过改变图的结构，使其具备适应性调整能力；其次，针对图的求解时间复杂度高的问题，实现了一种增量式优化算法；最后，实验对比公平性、优先级和放置约束这3种资源调度典型系统，验证了该方法可通过按需配置，支持多种调度目标，具备灵活性.并通过实验仿真，验证了万级规模下，基于图的资源调度延迟比基于未优化图算法的资源调度延迟最多降低90%.

关键词：资源调度;最小费用最大流;增量式算法

基金资助：国家重点研发计划（2016YFB1000103）；国家自然科学基金（61572480）；国家科技支撑计划（2015BAH55F02）