/MMFScheduling

Project for Algorithm Design and Analysis

Primary LanguagePython

Algorithm Design

  1. Floyd算法全源最短路预处理,计算任意两个数据中心之间的“最短路”,这边两个数据中心之间的距离取带宽的倒数
  2. 根据max-min fairness,依次分配计算资源slots,所谓max-min fairness,我们的理解是尽量的平均分配计算资源,所以我们在各个job轮流分配slots
  3. 每个job采用贪心策略,计算sub-task放在哪个data center执行时长是最优的,即计算时间+传输时间最短,如果最优的数据中心的slots占满了就选次优解,以此类推。
  4. 一直执行2、3步骤直到所有job完成,算法结束。

该算法没有考虑多个任务同时抢占带宽的情况,即认为每个任务拥有的带宽大小是独立的