论文标题
通过LP层次结构和集群进行通信延迟安排
Scheduling with Communication Delays via LP Hierarchies and Clustering
论文作者
论文摘要
我们考虑在沟通延迟的情况下，在相同的机器上安排工作的经典问题，并在相同的机器上具有优先限制，以最大程度地减少Makepan。在此设置中，由$ \ Mathsf {p} \ Mid \ Mathsf {PROC}，C \ MID C _ {\ Mathsf {Max}} $表示，如果将两个依赖的作业安排在不同的机器上，则至少在$ c $的时间之间进行$ C $单位必须通过执行权之间。尽管它与许多应用相关，但该模型仍然是调度理论中最糟糕的理解之一。即使在有无限数量的机器可用的特殊情况下，最著名的近似比率为$ 2/3 \ cdot（C+1）$，而Graham的贪婪列表安排算法已经给出了$（C+1）$ - 在这种情况下 - 近似值。 Schuurman和Woeginger的前十名列表中的一个杰出的开放问题及其最近的Bansal更新询问是否存在恒定因子近似算法。 在这项工作中，我们给出了一个多项式时间$ o（\ log c \ cdot \ log m）$ - 此问题的近似算法，其中$ m $是机器的数量，$ c $是通信延迟。我们的方法是基于Sherali-Adams的线性编程松弛的提升和该升力引起的半学空间的随机聚类。
We consider the classic problem of scheduling jobs with precedence constraints on identical machines to minimize makespan, in the presence of communication delays. In this setting, denoted by $\mathsf{P} \mid \mathsf{prec}, c \mid C_{\mathsf{max}}$, if two dependent jobs are scheduled on different machines, then at least $c$ units of time must pass between their executions. Despite its relevance to many applications, this model remains one of the most poorly understood in scheduling theory. Even for a special case where an unlimited number of machines is available, the best known approximation ratio is $2/3 \cdot (c+1)$, whereas Graham's greedy list scheduling algorithm already gives a $(c+1)$-approximation in that setting. An outstanding open problem in the top-10 list by Schuurman and Woeginger and its recent update by Bansal asks whether there exists a constant-factor approximation algorithm. In this work we give a polynomial-time $O(\log c \cdot \log m)$-approximation algorithm for this problem, where $m$ is the number of machines and $c$ is the communication delay. Our approach is based on a Sherali-Adams lift of a linear programming relaxation and a randomized clustering of the semimetric space induced by this lift.
