Structural Parameters for Scheduling with Assignment Restrictions
Structural Parameters for Scheduling with Assignment Restrictions
复制标题
DOI：
10.1007/978-3-319-57586-5_30
复制
发表时间：
2017-01
期刊：
影响因子：
--
通讯作者：
K. Jansen;M. Maack;Roberto Solis-Oba
中科院分区：
文献类型：
--
作者：
K. Jansen;M. Maack;Roberto Solis-Oba
我们考虑在相同和不相关的并行机上的调度与作业分配的限制。这些问题是NP难的，除非P = NP，否则不允许使用近似比小于1.5的多项式时间近似算法。然而，如果我们对可以处理作业的机器集合施加限制，问题有时会变得更容易，因为存在近似比优于1.5的算法。我们介绍了三个图，基于分配限制和研究的计算复杂性的调度问题，这些图的结构特性，特别是它们的树和rankwidth。我们确定的情况下，承认多项式时间近似方案或FPT算法，推广和扩展以前的结果在这方面。
We consider scheduling on identical and unrelated parallel machines with job assignment restrictions. These problems are NP-hard and they do not admit polynomial time approximation algorithms with approximation ratios smaller than 1.5 unless P = NP. However, if we impose limitations on the set of machines that can process a job, the problem sometimes becomes easier in the sense that algorithms with approximation ratios better than 1.5 exist. We introduce three graphs, based on the assignment restrictions and study the computational complexity of the scheduling problem with respect to structural properties of these graphs, in particular their tree- and rankwidth. We identify cases that admit polynomial time approximation schemes or FPT algorithms, generalizing and extending previous results in this area.