论文标题
关于与固定数量的平行相同机器的调度问题的复杂性
On the Complexity of Scheduling Problems With a Fixed Number of Parallel Identical Machines
论文作者
论文摘要
在并行机器调度中，我们将获得一组作业，以及许多机器，我们的目标是为每个作业，何时和在哪台机器上进行确定，以便将其安排到最小化某些目标功能。不同的机器模型，工作特性和目标功能会导致许多调度问题，其中许多是NP-HARD，即使对于固定数量的相同机器也是如此。在这项工作中，我们为大量的调度问题提供有条件的运行时间下限，这表明某些经典算法的最佳性。最值得注意的是，我们证明了Lawler和Moore的算法，价格为$ 1 || \ sum w_ju_j $和$ pm || c_ {max} $，以及Lee和Uzsoy的算法，价格为$ p2 || \ sum w_jc_j $可能是最佳的。对于$ 1 | rej \ leq q | \ sum w_ju_j $算法，Zhang等人的算法仍然有很小的改进空间。我们还为$ p2 | any | c_ {max} $提供了一个下限，并将du和leung的动态程序从$ \ Mathcal {o}（np^2）$到$ \ Mathcal {o}（o}（np）$匹配，与此新的下部下限匹配。在这里，$ p $是所有处理时间的总和。同样的想法还改善了$ p3 | any | c_ {max} $的算法，并从$ \ mathcal {o}（np^5）（np^5）$转换为$ \ mathcal {o}（np^2）$。尽管我们的结果表明了某些经典算法的最佳性，但它们在最著名的算法不太匹配的情况下也激发了未来的研究。
In parallel machine scheduling, we are given a set of jobs, together with a number of machines and our goal is to decide for each job, when and on which machine(s) it should be scheduled in order to minimize some objective function. Different machine models, job characteristics and objective functions result in a multitude of scheduling problems and many of them are NP-hard, even for a fixed number of identical machines. In this work, we give conditional running time lower bounds for a large number of scheduling problems, indicating the optimality of some classical algorithms. Most notably, we show that the algorithm by Lawler and Moore for $1||\sum w_jU_j$ and $Pm||C_{max}$, as well as the algorithm by Lee and Uzsoy for $P2||\sum w_jC_j$ are probably optimal. There is still small room for improvement for the $1|Rej\leq Q|\sum w_jU_j$ algorithm by Zhang et al., the algorithm for $1||\sum T_j$ by Lawler and the FPTAS for $1||\sum w_jU_j$ by Gens and Levner. We also give a lower bound for $P2|any|C_{max}$ and improve the dynamic program by Du and Leung from $\mathcal{O}(nP^2)$ to $\mathcal{O}(nP)$, matching this new lower bound. Here, $P$ is the sum of all processing times. The same idea also improves the algorithm for $P3|any|C_{max}$ by Du and Leung from $\mathcal{O}(nP^5)$ to $\mathcal{O}(nP^2)$. While our results suggest the optimality of some classical algorithms, they also motivate future research in cases where the best known algorithms do not quite match the lower bounds.
