论文标题
（内）间隔，资源限制和低级计划的近似性结果
(In-)Approximability Results for Interval, Resource Restricted, and Low Rank Scheduling
论文作者
论文摘要
我们考虑必须将一组作业分配给一组机器的限制性分配问题的变体，对于每个作业，都会给出一个大小和一组合格的机器，并且只能将作业分配给合格的机器，以实现MakePan Minimization的目标。对于具有间隔限制的变体，可以将机器安排在路径上，以使每个作业都有资格在子路径上，我们提出的第一个比$ 2 $ appproximation更好，并提高了不适当的不适合性结果。特别是，我们给出了$（2- \ frac {1} {24}）$ - 近似值，并表明除非p = np，否则不可能更好。此外，我们考虑使用$ R $ Resource限制的限制任务，排名$ D $无关的计划。在前一种问题中，如果机器可以满足$ R $（可再生）资源的资源要求，则可以处理一项工作。在后者中，作业的大小取决于分配给的机器，相应的处理时间矩阵最多排名$ d $。间隔限制的问题包括1个资源变体，由2个资源变体所包含，并且关于近似值，$ r $ Resource variant本质上是等级$ r+1 $问题的特殊情况。我们表明，对于3个资源，2个资源和等级3变体是可能的（除非p = np），否则不得超过$ 3/2 $，$ 8/7 $和$ 3/2 $ -AppRoximation（除非P = NP）。间隔情况的近似结果和等级3变体的不Xibibibibibility结果都是在以前的工作中所述的打开挑战的解决方案。最后，我们还考虑了反向目标，即最大化任何机器收到的最小负载，并获得相似的结果。
We consider variants of the restricted assignment problem where a set of jobs has to be assigned to a set of machines, for each job a size and a set of eligible machines is given, and the jobs may only be assigned to eligible machines with the goal of makespan minimization. For the variant with interval restrictions, where the machines can be arranged on a path such that each job is eligible on a subpath, we present the first better than $2$-approximation and an improved inapproximability result. In particular, we give a $(2-\frac{1}{24})$-approximation and show that no better than $9/8$-approximation is possible, unless P=NP. Furthermore, we consider restricted assignment with $R$ resource restrictions and rank $D$ unrelated scheduling. In the former problem, a machine may process a job if it can meet its resource requirements regarding $R$ (renewable) resources. In the latter, the size of a job is dependent on the machine it is assigned to and the corresponding processing time matrix has rank at most $D$. The problem with interval restrictions includes the 1 resource variant, is encompassed by the 2 resource variant, and regarding approximation the $R$ resource variant is essentially a special case of the rank $R+1$ problem. We show that no better than $3/2$, $8/7$, and $3/2$-approximation is possible (unless P=NP) for the 3 resource, 2 resource, and rank 3 variant, respectively. Both the approximation result for the interval case and the inapproximability result for the rank 3 variant are solutions to open challenges stated in previous works. Lastly, we also consider the reverse objective, that is, maximizing the minimal load any machine receives, and achieve similar results.
