Design of approximation algorithms for scheduling on unrelated machines

在这个项目中，我们研究了几个未解决的问题，这些问题是关于具有最小完工时间的无关机器上的调度问题。这是一个经典的组合问题，其中一组作业必须分配给一组机器。每个作业j具有取决于其被分配到的机器i的处理时间p_ij。我们的研究主要集中在(但不限于)限制指派问题的研究上，其中p_ij是p_j(与机器无关)或无限大。对于这种特殊情况，发现了一种局部搜索算法，它产生的解至多为33/17opt_lp，其中opt_lp是配置LP的最佳值，这是一种强LP松弛。到目前为止，该算法只被用来讨论配置LP的完整性间隙，因为它的运行时间没有好的界。一个多项式变量将有很大的影响，因为这将改进超过25年前建立的2-近似。此外，我们想要在无关机器上的问题调度的背景下研究LP/SDP层次结构，例如Lasserre层次结构。这里有趣的问题是，这些层次结构是否可以用来找到比配置LP更强的松弛。

In this project we work on several open questions regarding the problem Scheduling on Unrelated Machines with makespan minimization. This is a classical combinatorial problem, in which a set of jobs has to be distributed among a set of machines. Each job j has a processing time p_ij depending on the machine i it is assigned to. The objective is to minimize the maximum load among all machines, the makespan.Our research has a particular focus on (but is not limited to) the study of the Restricted Assignment problem, in which p_ij is either p_j (independent of the machine) or infinite. For this special case a local search algorithm was discovered, which produces a solution of value at most 33/17 OPT_LP, where OPT_LP is the optimum value of the configuration LP, a strong LP relaxation. So far, this algorithm has only been used to argue about the integrality gap of the configuration LP, since no good bounds on its running time are known. A polynomial variant would have a great impact, because this would improve on the 2-approximation established more than 25 years ago.Additionally we want to study LP/SDP hierarchies, such as the Lasserre hierarchy, in the context of problem Scheduling on Unrelated Machines. The interesting question here iswhether these hierarchies can be used to find an even stronger relaxation than the configuration LP.