Scheduling with Communication Delays via LP Hierarchies and Clustering
Scheduling with Communication Delays via LP Hierarchies and Clustering
复制标题
DOI：
10.1109/focs46700.2020.00081
复制
发表时间：
2020-04
期刊：
影响因子：
--
通讯作者：
Sami Davies;Janardhan Kulkarni;T. Rothvoss;Jakub Tarnawski;Yihao Zhang
中科院分区：
文献类型：
--
作者：
Sami Davies;Janardhan Kulkarni;T. Rothvoss;Jakub Tarnawski;Yihao Zhang
我们考虑在沟通延迟的情况下，在相同的机器上安排工作的经典问题，并在相同的机器上具有优先限制，以最大程度地减少Makepan。在此设置中，由$ \ mathrm {p} \ \ vert \ \ text {prec}，c \ \ vert \ c _ {\ max} $表示，如果在不同的机器上安排了两个因工作，则至少$ c $时间单位必须在执行之间通过。尽管它与许多应用相关，但该模型仍然是调度理论中最糟糕的理解之一。即使对于有无限数量的机器可用的特殊情况，最著名的近似值也为$ 2/3 \ cdot（C+1）$，而Graham的贪婪列表安排算法已经给出（$ C+1 $）-AppRoximation -approximation在那个环境中。 Schuurman和Woeginger的前十名列表中的一个杰出的开放问题及其最近的Bansal更新询问是否存在恒定因子近似算法。在这项工作中，我们给出了一个多项式时间$ o（\ log c \ cdot \ log m）$ - 此问题的近似算法，其中$ m $是机器的数量，$ c $是通信延迟。我们的方法是基于Sherali-Adams的线性编程松弛的提升和该升力引起的半学空间的随机聚类。本文的完整版本可在Arxiv上找到。
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 $\mathrm{P}\ \vert\ \text{prec}, c\ \vert\ C_{\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. The full version of this paper is available on arXiv.