论文标题
在相关机器和无关机器上安排几类作业的复杂性
Complexity of Scheduling Few Types of Jobs on Related and Unrelated Machines
论文作者
论文摘要
将作业安排到机器的任务，同时最大程度地减少了整个Makepan，加权完成时间的总和或负载向量的规范，是组合优化中最古老，最基本的任务之一。由于所有这些问题总体上都是NP-HARD，因此对只有少数$ k $的工作类型的政权引起了很多关注，但可能是$ n $的工作数量很大。这是少数工作类型，即高级授权制度。尽管结果有很多积极的结果，但直到现在才能理解该制度的硬度边界。 我们表明，在均匀相关的机器上将PAN最小化（$ q | hm | c _ {\ max} $）已经具有$ 6 $的工作类型，并且相关的切割库存问题已经是NP-HARD，已经具有$ 8 $的项目类型。对于更一般的无关机器模型（$ r | hm | c _ {\ max} $），我们表明，如果最大的作业大小$ p _ {\ max} $或作业$ n $的数量在实例上是多实际界限的，则在实例$ | i | $中，具有复杂性$ | i | i | i | i | toy |我们的主要结果是，这不太可能得到改进，因为$ q || c _ {\ max} $是w [1] - hard hard是由$ k $在$ n $，$ n $，$ p _ {\ max max} $中的参数化，并且描述速度的数字是$ | i | i | $ | $ | $;当作业尺寸矩阵的排名$ 2 $时，$ r | hm | c _ {\ max} $（无速度）的同样存在。我们的正面和负面结果也扩展到目标$ \ ell_2 $ -Norm最小化负载向量的最小化，以及部分加权完成时间的总和$ \ sum sum w_j c_j $。 在此过程中，我们肯定地回答了在相同机器上最小化的问题（$ p || c _ {\ max} $）是固定参数可通过$ k $进行参数的固定参数，从而扩展了我们对这个基本问题的理解。加上我们的硬度结果，$ q || c _ {\ max} $这意味着$ p | hm | c _ {\ max} $的复杂性是唯一剩下的开放式案例。
The task of scheduling jobs to machines while minimizing the total makespan, the sum of weighted completion times, or a norm of the load vector, are among the oldest and most fundamental tasks in combinatorial optimization. Since all of these problems are in general NP-hard, much attention has been given to the regime where there is only a small number $k$ of job types, but possibly the number of jobs $n$ is large; this is the few job types, high-multiplicity regime. Despite many positive results, the hardness boundary of this regime was not understood until now. We show that makespan minimization on uniformly related machines ($Q|HM|C_{\max}$) is NP-hard already with $6$ job types, and that the related Cutting Stock problem is NP-hard already with $8$ item types. For the more general unrelated machines model ($R|HM|C_{\max}$), we show that if either the largest job size $p_{\max}$, or the number of jobs $n$ are polynomially bounded in the instance size $|I|$, there are algorithms with complexity $|I|^{\textrm{poly}(k)}$. Our main result is that this is unlikely to be improved, because $Q||C_{\max}$ is W[1]-hard parameterized by $k$ already when $n$, $p_{\max}$, and the numbers describing the speeds are polynomial in $|I|$; the same holds for $R|HM|C_{\max}$ (without speeds) when the job sizes matrix has rank $2$. Our positive and negative results also extend to the objectives $\ell_2$-norm minimization of the load vector and, partially, sum of weighted completion times $\sum w_j C_j$. Along the way, we answer affirmatively the question whether makespan minimization on identical machines ($P||C_{\max}$) is fixed-parameter tractable parameterized by $k$, extending our understanding of this fundamental problem. Together with our hardness results for $Q||C_{\max}$ this implies that the complexity of $P|HM|C_{\max}$ is the only remaining open case.
