Inapproximability Results for Scheduling with Interval and Resource Restrictions
Inapproximability Results for Scheduling with Interval and Resource Restrictions
复制标题
DOI：
10.4230/lipics.stacs.2020.5
复制
发表时间：
2019-07
期刊：
影响因子：
--
通讯作者：
M. Maack;K. Jansen
中科院分区：
文献类型：
--
作者：
M. Maack;K. Jansen
在受限指派问题中，输入由一组机器和一组工件组成，每个工件都有一个加工时间和一个合格机器子集。目标是找到一个分配的工作，机器最大完工时间最小化，也就是说，最大的总和处理时间的任何机器接收。在这里，作业应该只分配给那些机器上，他们是合格的。众所周知，除非P=NP，否则没有多项式时间近似算法的近似保证小于1.5。在这项工作中，我们显示出硬度的结果与特定类型的限制的限制分配问题的变种。在间隔限制的情况下，机器可以完全排序，使得作业在连续的机器上都是合格的。我们解决了这个问题是否承认一个多项式时间近似方案（PTAS）的负面（除非P=NP）的公开问题。有几个特殊的情况下，这个问题已知承认一个PTAS。此外，我们考虑一个变种的资源限制，每台机器的能力和每个作业的需求为一个固定数量的资源。如果作业的需求最多是机器对每个资源的容量，则该作业在机器上是合格的。对于一个资源，这个问题是已知的，承认PTAS，对于两个，包含的情况下，间隔限制，并在一般情况下，该问题是密切相关的不相关的调度与低秩的处理时间矩阵。我们表明，有没有多项式时间近似算法的速率小于48/47或1.5调度与资源限制与2或4个资源，分别，除非P=NP。我们所有的结果都可以扩展到所谓的圣诞老人变量的问题，其目标是最大化任何机器接收的最小处理时间。
In the restricted assignment problem, the input consists of a set of machines and a set of jobs each with a processing time and a subset of eligible machines. The goal is to find an assignment of the jobs to the machines minimizing the makespan, that is, the maximum summed up processing time any machine receives. Herein, jobs should only be assigned to those machines on which they are eligible. It is well-known that there is no polynomial time approximation algorithm with an approximation guarantee of less than 1.5 for the restricted assignment problem unless P=NP. In this work, we show hardness results for variants of the restricted assignment problem with particular types of restrictions. In the case of interval restrictions the machines can be totally ordered such that jobs are eligible on consecutive machines. We resolve the open question of whether the problem admits a polynomial time approximation scheme (PTAS) in the negative (unless P=NP). There are several special cases of this problem known to admit a PTAS. Furthermore, we consider a variant with resource restriction where each machine has capacities and each job demands for a fixed number of resources. A job is eligible on a machine if its demand is at most the capacity of the machine for each resource. For one resource, this problem is known to admit a PTAS, for two, the case of interval restrictions is contained, and in general, the problem is closely related to unrelated scheduling with a low rank processing time matrix. We show that there is no polynomial time approximation algorithm with a rate smaller than 48/47 or 1.5 for scheduling with resource restrictions with 2 or 4 resources, respectively, unless P=NP. All our results can be extended to the so called Santa Claus variants of the problems where the goal is to maximize the minimal processing time any machine receives.