Coflow scheduling is a challenging optimization problem that underlies many data transmission and parallel computing applications. In this paper, we study the indivisible coflow scheduling problem on parallel identical machines with the objective to minimize the makespan, i.e., the completion time of the last flow. In our problem setting, the number of the input/output ports in each machine is a fixed constant, each port has a unit capacity, and all the flows inside a coflow should be scheduled on the same machine. We present a \((2 + \epsilon )\) -approximation algorithm for the problem, in which the number of machines can be either a fixed constant or part of the input, for any \(\epsilon > 0\) .

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Improved Approximation Algorithms for Multiprocessor Indivisible Coflow Scheduling

  • Mingyang Gong,
  • Guohui Lin,
  • Bing Su

摘要

Coflow scheduling is a challenging optimization problem that underlies many data transmission and parallel computing applications. In this paper, we study the indivisible coflow scheduling problem on parallel identical machines with the objective to minimize the makespan, i.e., the completion time of the last flow. In our problem setting, the number of the input/output ports in each machine is a fixed constant, each port has a unit capacity, and all the flows inside a coflow should be scheduled on the same machine. We present a \((2 + \epsilon )\) -approximation algorithm for the problem, in which the number of machines can be either a fixed constant or part of the input, for any \(\epsilon > 0\) .