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

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

Large-Scale Resource Scheduling Based on Minimum Cost Maximum Flow

Concurrent job is a hot topic in large-scale resource scheduling research.Existing efforts employ queueing model with local optimal solution to schedule co-located tasks,it can only fit a specific requirement.Hence,how a single scheduler to meet diverse requirments is challenging.In this paper,we introduce Sirius,a new foundation basd on minimum cost maximum flow network for resource scheduling.It is easy to express scheduling requirments,including FAIRNESS,PRIORITY and PLACEMENT CONSTRAINT,on a unified way,which is a typical graph construction and solution problem.Meanwhile,we speed up flow network solver by representing an incremental algorithm,which can significantly reduce runtime of flow network solver upto 10 times.