论文标题
基于层次结构的算法，以最大程度地减少在优先级和沟通约束下的pan
Hierarchy-Based Algorithms for Minimizing Makespan under Precedence and Communication Constraints
论文作者
论文摘要
我们考虑了在一组相同的机器上进行优先限制的调度作业的经典问题，以最大程度地减少MakePan目标功能。当机器数量是常数是调度理论中的一个众所周知的问题时，了解问题的确切近似性。确实，加里（Garey）和约翰逊（Johnson）经典书中的一个杰出的开放问题问，即使在3台机器和单位长度工作的情况下，这个问题是否也是NP-HARD。在最近的一项突破中，Levey和Rothvoss给出了$（1+ε）$ - 近似算法，该算法几乎在准多项式时间内运行，而工作的情况则具有单位长度。但是，一个更困难的案例是，工作的任意处理长度仍然开放。 我们在这个更普遍的问题上取得了进展。我们表明，存在$（1+ε）$ - 近似算法（具有与Levey和Rothvoss相似的运行时间），用于非迁移设置：当必须将每个作业完全安排在单个机器上，但是在机器中，在一台计算机中，在连续时间步骤中不需要安排工作。此外，我们还表明，我们的算法框架将概括为另一种经典方案，在这种情况下，以及优先限制，这些作业还具有通信延迟约束。这两个基本问题都与数据中心计划的实践高度相关。
We consider the classic problem of scheduling jobs with precedence constraints on a set of identical machines to minimize the makespan objective function. Understanding the exact approximability of the problem when the number of machines is a constant is a well-known question in scheduling theory. Indeed, an outstanding open problem from the classic book of Garey and Johnson asks whether this problem is NP-hard even in the case of 3 machines and unit-length jobs. In a recent breakthrough, Levey and Rothvoss gave a $(1+ε)$-approximation algorithm, which runs in nearly quasi-polynomial time, for the case when job have unit lengths. However, a substantially more difficult case where jobs have arbitrary processing lengths has remained open. We make progress on this more general problem. We show that there exists a $(1+ε)$-approximation algorithm (with similar running time as that of Levey and Rothvoss) for the non-migratory setting: when every job has to be scheduled entirely on a single machine, but within a machine the job need not be scheduled during consecutive time steps. Further, we also show that our algorithmic framework generalizes to another classic scenario where, along with the precedence constraints, the jobs also have communication delay constraints. Both of these fundamental problems are highly relevant to the practice of datacenter scheduling.
