Scheduling and Traffic Allocation for Tasks with Bounded Splittability
Scheduling and Traffic Allocation for Tasks with Bounded Splittability
复制标题
具有有限可分割性的任务的调度和流量分配
DOI：
--
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
Berthold Vöcking
中科院分区：
文献类型：
--
作者：
Piotr Krysta;P. Sanders;Berthold Vöcking
我们调查的问题的变种调度任务的一致相关的机器，以尽量减少最大完工时间。在k-可拆分排序问题中，每个任务最多可以分解为k ≥ 2个任务分配给不同的机器。在更一般的SAC问题中，每个任务j都有自己的可拆分性参数k j ≥ 2。这些问题是NP难的，以前的研究主要集中在近似算法。
We investigate variants of the problem of scheduling tasks on uniformly related machines to minimize the makespan. In the k-splittable scheduling problem each task can be broken into at most k ≥ 2 pieces to be assigned to different machines. In a more general SAC problem each task j has its own splittability parameter k j ≥ 2. These problems are NP-hard and previous research focuses mainly on approximation algorithms.